Path planning for automated guided vehicle systems with time constraints using timed Petri nets

Abstract

Automated guided vehicles (AGVs) are extensively used in many applications such as intelligent transportation, logistics, and industrial factories. In this paper, we address the path planning problem for an AGV system (i.e. a team of identical AGVs) with logic and time constraints using Petri nets. We propose a method to model an AGV system and its static environment by timed Petri nets. Combining the structural characteristics of Petri nets and integer linear programming technique, a path planning method is developed to ensure that all task regions are visited by AGVs in time and forbidden regions are always avoided. Finally, simulation studies are presented to show the effectiveness of the proposed path planning methodology.

Introduction

With the rapid development of Industrial 4.0, automated guided vehicles (AGVs) have been extensively employed to handle complicated tasks efficiently. The path planning problem of AGV systems has been an active research topic in recent decades. Related works involve single AGV target reachability and multiple AGV obstacle avoidance.^1,2 The problem aims to optimize several criteria such as travel distance and energy consumption under certain requirements: deadlock prevention, obstacle avoidance, and multi-task agents.^3–8

An AGV system can be regarded as a discrete event system (DES) where the environment of the system is divided into several regions (or zones), and the vehicle movement from one region to another can be regarded as a discrete event.^9–12 Petri nets (PNs) are a graph-based mathematical tool and are widely applied for modeling,^13–18 control,^19–29 and scheduling^30–33 of DES, including AGV systems, manufacturing systems, and transportation systems. By assuming that some regions have a limited capacity, a deadlock prevention strategy is developed for robot planning in order to avoid collisions. ² Hsieh and Kang ³⁴ present a method to convert an AGV system into a control-based PN model and develop a control design method for avoiding collisions. Costelha and Lima propose a generalized stochastic PN model to address the robot task planning. ⁴ Petri net modeling for robotic assembly and trajectory planning is studied in McCarragher. ⁷ In the work of Kloetzer and Mahulea, ³⁵ the running environment of an AGV system is partitioned into several regions where each region and the connection between two regions are represented by a place and a transition of PNs, respectively. Then, an online supervising procedure updates the paths whenever an AGV deviates from the planned trajectory. Mahulea and Kloetzer ³⁶ propose an approach to find the shortest path of an AGV system with Boolean constraints. By modeling the environment as a state machine and transforming the Boolean constraints into a set of linear constraints, an integer linear programming problem (ILPP) is developed to find an optimal trajectoriy for an AGV system such that the total travel distance is minimized. In order to cooperatively finish some complex tasks, the types of AGVs are assumed to be different in a system. ³⁷ Then, the task allocation problem for AGV systems is studied by using colored PNs. Recently, Luo et al. ⁹ develop an optimal PN controller for AGV systems in order to avoid collisions under the condition that some events are indistinguishable and uncontrollable due to the limited sensors and actuators.

In real-world systems, tasks usually have time constraints. Therefore, it is important to take the time information into consideration when dealing with the path planning problem for AGV systems. However, there are few works dealing with path planning for AGV systems with time constraints in the framework of DESs. Tanaka and Araki tackle the single machine scheduling problem and present an exact algorithm to find an optimal path. ³⁸ Fanti ³⁹ describe an AGV system using a colored timed PN and develop a control method to avoid collisions and deadlocks. Time windows are assigned to vehicles for the control at urban intersections in order to improve the throughput. ⁴⁰ The robot rescue problem with time constraints is studied in Geng et al. ¹ and a particle swarm optimization method is developed to obtain the best transition sequence. A real-time robot path planning algorithm is developed to minimize the total distance in a dynamic environment. ⁴¹

In this paper, we address the path planning for AGV systems with logic and time constraints using PNs. The tasks to be accomplished contain logic constraints on some regions along the trajectories and on the final states. In addition, we assume that some of the task regions should be visited in a predefined time window. We show that an AGV system and its static environment can be modeled by timed Petri nets (TPNs). Furthermore, an optimal path planning approach for AGV systems with time constraints is developed by solving an ILPP. Simulation studies show that the developed method is more accurate than the previous one. For the collision avoidance problem of AGV systems, it has been extensively studied in the literature (some recently published studies can be found in Refs.^9,42 and is not the main focus of this paper.

This paper is structured in six sections. The basic concepts of PNs and the modeling framework are introduced in Section “Preliminary”. In Section “Problem statement”, the problem under consideration is formulated. In Section “Path planning for AGV systems using PNs”, we develop an ILPP for path planning for AGV systems with time constraints. Simulation studies are exposed in Section “Simulation results”. Conclusions and future works are finally drawn in Section “Conclusion”.

Preliminary

Petri net

A Petri net is a four-tuple $N=(P,T,\mathit{Pre},\mathit{Post})$ , where $P$ is a set of $n$ places; $T$ is a set of $m$ transitions; $\mathit{Pre}:P\times T\to \mathbb{N}$ and $\mathit{Post}:P\times T\to \mathbb{N}$ are the pre- and post-incidence functions that specify the arcs from places to transitions and transitions to places, respectively, where $\mathbb{N}=\{0,1,2,\dots \}$ denotes the set of nonnegative integers. $\mathit{Pre}$ ( $\mathit{Post}$ ) can be tabulated in a rectangular array and represented by an $n\times m$ matrix indexed by $P$ and $T$ . The incidence matrix of $N$ is defined as $\mathit{C}=\mathit{Post}-\mathit{Pre}\in {\mathbb{Z}}^{n\times m}$ , where $\mathbb{Z}$ denotes the set of integers.

A marking is a mapping $\mathit{M}:P\to \mathbb{N}$ that assigns to each place of a PN a nonnegative integer of tokens. The marking of place $p$ is denoted by $M(p)$ . A Petri net system $〈N,{\mathit{M}}_0〉$ is a net $N$ with an initial marking ${\mathit{M}}_0$ . A transition $t$ is enabled at $\mathit{M}$ if $\mathit{M}\ge \mathit{Pre}(·,t)$ , denoted by $\mathit{M}[t〉$ . An enable transition $t$ may fire yielding a new marking $\mathit{M}\prime$ with

$$\mathit{M}\prime =\mathit{M}+\mathit{C}(·,t),$$

(1)

where $\mathit{Pre}(·,t)$ (resp. $\mathit{C}(·,t)$ ) denotes the column of the matrix $\mathit{Pre}$ (resp. $C$ ) associated with transition $t$ .

Marking $\mathit{M}$ is said to be reachable from ${\mathit{M}}_0$ if there exist a sequence of transitions $\sigma =t_0{t}_1\dots t_n$ and markings ${\mathit{M}}_1,{\mathit{M}}_2,\dots$ , and ${\mathit{M}}_n$ such that ${\mathit{M}}_0[t_0〉{\mathit{M}}_1[t_1〉{\mathit{M}}_2\dots {\mathit{M}}_n[t_n〉\mathit{M}″$ holds, that is,

$$\mathit{M}″={\mathit{M}}_0+\mathit{C}·\sigma ,$$

(2)

where $\sigma =[\sigma (t_1),\dots ,\sigma (t_m){]}^T\in {\mathbb{N}}^m$ is the firing count vector whose $i$ -th component represents the number of times that transition $t_i$ appears in sequence $\sigma$ . The set of markings reachable from ${\mathit{M}}_0$ in $〈N,{\mathit{M}}_0〉$ is called the reachability set of the PN system $〈N,{\mathit{M}}_0〉$ , denoted by $R(N,{\mathit{M}}_0)$ . Note that equation (2) is a necessary condition for the reachability of a marking. The markings satisfying equation (2) that are not reachable are said to be spurious. Due to the existence of spurious markings, it is not easy to check if a marking $\mathit{M}$ is reachable.

A state machine is a PN such that each transition has at most one input and at most one output place. A PN system $〈N,{\mathit{M}}_0〉$ is said to be live if from every marking $\mathit{M}\in R(N,{\mathit{M}}_0)$ there exists a firing sequence containing all transitions. It is well known that for a live state machine, condition (2) becomes necessary and sufficient, that is, the markings satisfying equation (2) are unique and reachable.^43–45

Timed Petri net model for AGV systems

Inspired by the work in Mahulea and Kloetzer ³⁶ that models an AGV system by a Petri net, we develop a method to model an AGV system with a timed Petri net by taking the timing information into consideration.

Definition 1 A timed Petri net (TPN) is a pair $N_d=(N,\theta )$ , where:

• $N=(P,T,\mathit{Pre},\mathit{Post})$ is a PN,

• $\theta :T\to {\mathbb{R}}_{\ge 0}$ is a firing delay function that assigns to each transition a non-negative real number, where ${\mathbb{R}}_{\ge 0}$ denotes the set of nonnegative real numbers.

A TPN ( $N,\theta$ ) is said to be a timed state machine (TSM) if net $N$ is a state machine. A TSM system is a triple $G=〈N,\theta ,{\mathit{M}}_0〉$ , where $〈N,\theta 〉$ is a TSM and ${\mathit{M}}_0$ is an initial marking.

The environment of an AGV system that is known and static is partitioned into $n$ regions labeled with ${\pi }_1,{\pi }_2,\dots ,$ and ${\pi }_n$ . We denote the set of regions by $\mathrm{\Pi }=\{{\pi }_1,\dots ,{\pi }_n\}$ . Each region ${\pi }_i$ is modeled by a place $p_i$ and an event in which a vehicle moves from region ${\pi }_i$ to its adjacent region ${\pi }_j$ is modeled by a transition $t_{i,j}$ . The number of AGVs currently located in region ${\pi }_i$ can be modeled by the number of tokens in place $p_i$ . We associate each transition $t_{i,j}$ with a deterministic duration $\theta (t_{i,j})$ to represent the AGV movement time from ${\pi }_i$ to ${\pi }_j$ . Algorithm 1 returns a TSM system $G=〈N,\mathbf{\theta },{\mathit{M}}_0〉$ for an AGV system and a vector $\mathit{w}\in {\mathbb{R}}_{\ge 0}^m$ that contains the average distance for traveling between two adjacent regions.

Alogrithm 1. Construct a TSM system for an AGV system.

Input: Environment with a set of $n$ regions $\mathrm{\Pi }=\{{\pi }_1,\dots ,{\pi }_n\}$ and the initial position of AGVs Output: A TSM system $G=〈N,\mathbf{\theta },{\mathit{M}}_0〉$ and a vector $\mathit{w}\in {\mathbb{R}}_{\ge 0}^m$ 1:  Let $P=\{p_1,p_2,\dots ,p_n\}$ , $T=\varphi$ , $\mathit{Pre}=0$ , $\mathit{Post}=0$ , $\theta =0$ , ${\mathit{M}}_0=0$ , and $\mathit{w}=0$ . 2:  Associate each region ${\pi }_i$ with a place $p_i$ from set $P$ . 3:  for $p_i\in P$ do 4:   for $p_j\in P$ , $j\ne i$ do 5:    if $p_i$ and $p_j$ are adjacent (i.e. regions ${\pi }_i$ and ${\pi }_j$ are adjacent) then 6:     $T=T\cup \{t_{i,j}\}$ ; 7:     $\mathrm{Pre}(p_i,t_{i,j})=1$ , $\mathrm{Post}(p_j,t_{i,j})=1$ ; 8:     $\theta (t_{i,j})=$ average time traveled by an AGV from ${\pi }_i$ to ${\pi }_j$ ; 9:      $w(t_{i,j})=$ average distance traveled by an AGV from ${\pi }_i$ to ${\pi }_j$ . 10:    end if 11:   end for 12:  end for 13: for $p_i\in P$ do 14:    $M_0(p_i)$ = number of AGVs initially located in region ${\pi }_i$ ; 15: end for

Path requirement: Logic and time constraints

Among all the regions of an AGV system, we are interested in a set of regions that should be visited or avoided, denoted by ${\mathrm{\Pi }}^I$ (where ${\mathrm{\Pi }}^I\subseteq \mathrm{\Pi }$ ). In particular, we consider two types of interest regions: task regions that should be visited and forbidden regions that should be always avoided. The path requirement for an AGV system under consideration consists of logic and time constraints for the AGVs’ trajectories and the final states. Therefore, we divide the set of interest regions ${\mathrm{\Pi }}^I$ into three disjoint subsets ${\mathrm{\Pi }}^t$ , ${\mathrm{\Pi }}^f$ , and ${\mathrm{\Pi }}^a$ such that ${\mathrm{\Pi }}^I={\mathrm{\Pi }}^t\cup {\mathrm{\Pi }}^f\cup {\mathrm{\Pi }}^a$ , where ${\mathrm{\Pi }}^t$ , ${\mathrm{\Pi }}^f$ , and ${\mathrm{\Pi }}^a$ denote the sets of task regions that should be visited along the trajectory, task regions that should be visited at the final state, and forbidden regions that should be always avoided, respectively.

For each interest region $\pi \in {\mathrm{\Pi }}^I$ , we define a state function $\mathrm{\Delta }(\pi )$ as follows:

$$\mathrm{\Delta }:{\mathrm{\Pi }}^I\to \{A,F,J\},$$

(3)

where

• $\mathrm{\Delta }(\pi )=J$ if region $\pi$ should be visited along the trajectory;

• $\mathrm{\Delta }(\pi )=F$ if region $\pi$ should be visited at the final state;

• $\mathrm{\Delta }(\pi )=A$ if region $\pi$ should be always avoided.

In addition, we assume that the time constraint associated with a task region ${\pi }_i$ is a predefined time window $[e_i,l_i]$ , where $e_i$ and $l_i$ represent the earliest (global) time instant and the latest (global) time instant that region ${\pi }_i$ should be visited, respectively. If a region has no time constraint, its time window is assumed to be $[0,+\infty ]$ .

Given an AGV system and an environment with $n$ regions labeled with ${\pi }_1,{\pi }_2,\dots ,{\pi }_n$ , a path requirement that contains logic and time constraints is a sequence $\phi =({\pi }_{j_1},\mathrm{\Delta }({\pi }_{j_1}),[e_{j_1},l_{j_1}]),({\pi }_{j_2},\mathrm{\Delta }({\pi }_{j_2}),[e_{j_2},l_{j_2}]),\dots ,$ $({\pi }_{j_k},\mathrm{\Delta }({\pi }_{j_k}),[e_{j_k},l_{j_k}])$ (To simplify the notation, in the rest of the paper we omit the time window $[0,+\infty ]$ in $\phi$ for all interest regions that have no time constraints), where ${\pi }_{j_i}\in {\mathrm{\Pi }}^I$ is an interest region, $\mathrm{\Delta }({\pi }_{j_i})$ is a state function as defined in equation (3), and $[e_{j_i},l_{j_i}]$ is a predefined time constraint for region ${\pi }_{j_i}$ .

For example, considering the following path requirement for an AGV system

$$\phi =({\pi }_1,J),({\pi }_2,F),({\pi }_3,J,[2,5]),({\pi }_4,A),$$

it requires that region ${\pi }_1$ (resp., ${\pi }_2$ ) should be visited along the trajectory (resp., at the final state) without time constraint, region ${\pi }_3$ should be visited along the trajectory in the time window $[2,5]$ , and region ${\pi }_4$ should be always avoided.

Problem statement

In this paper, we deal with the path planning problem for AGV systems with logic and time constraints. In particular, we consider a team of $k$ identical AGVs moving in a known and static environment with $n$ regions. Given a path requirement $\phi$ that contains logic and time constraints discussed in Section “Path planning for AGV systems using PNs”, we aim to find an optimal trajectory of the AGV system such that all task regions are visited by AGVs in time and forbidden regions are always avoided, while the total travel distance is minimized. In this paper, we assume that any region could be visited multiple times by AGVs, except for the forbidden regions.^1,9,36 On the other hand, in order to finish some complex tasks, multiple types of AGVs may be needed. ³⁷ This problem is also a challenge issue of path planning and will be investigated in our future work.

It is worth mentioning that an optimal solution for the path planning for AGV systems with logic constraints using PNs was developed in Mahulea and Kloetzer. ³⁶ Nevertheless, the time constraints for AGV system are not discussed in Mahulea and Kloetzer. ³⁶

Path planning for AGV systems using PNs

In this section, we first introduce the method developed in Mahulea and Kloetzer ³⁶ to transform the logic constraint into a set of linear constraints. Since the path requirement for AGV systems considered in this paper is different from the one in Mahulea and Kloetzer, ³⁶ we propose some methods to transform the logic and time constraints into a set of linear constraints. Finally, we develop an ILPP to obtain an optimal trajectory for an AGV system such that the total travel distance is minimized.

Transformation of logic constraint

Logic constraint on the trajectory: ³⁶ In the following, we denote the maximum number of steps for AGVs to complete the tasks by $h$ . The trajectory of an AGV system can be represented by a finite sequence of markings ${\mathit{M}}_0,{\mathit{M}}_1,\dots ,{\mathit{M}}_h$ of the TSM system $G$ such that:

$$\{\begin{array}{c}{\mathit{M}}_i={\mathit{M}}_{i-1}+\mathit{C}·{\sigma }_i,\hfill \\ \multicolumn{1}{c}{{\mathit{M}}_{i-1}-\mathit{Pre}·{\mathbf{\sigma }}_i\ge 0,}\\ \multicolumn{1}{c}{1^T·{\mathbf{\sigma }}_i\le 1,}\\ \multicolumn{1}{c}{i=1,\dots ,h,}\end{array}$$

(4)

where ${\mathbf{\sigma }}_i=[{\sigma }_i(t_1),\dots ,{\sigma }_i(t_m){]}^T\in {\mathbb{N}}^m$ is the firing count vector at the $i$ -th step. The final constraint of equation (4) enforces that between markings ${\mathit{M}}_{i-1}$ and ${\mathit{M}}_i$ each token moves at most through one transition, that is, the team of AGVs advances maximum one region at each step.

For each interest region ${\pi }_j\in {\mathrm{\Pi }}^I$ , we define an $n$ -component vector ${\mathit{v}}_{{\pi }_j}=[v_{{\pi }_j}(p_1),$ $\dots ,v_{{\pi }_j}(p_n)]$ with all its elements be zero except the $j$ -th element which is equal to one, that is,

$$v_{{\pi }_j}(p_i)=\{\begin{array}{c}\multicolumn{1}{c}{1,\mathrm{if}i=j,}\\ \multicolumn{1}{c}{0,\mathrm{else}.}\end{array}$$

Therefore, a task region ${\pi }_j$ is visited at marking M iff ${\mathit{v}}_{{\pi }_j}·\mathit{M}\ge 1$ holds.

Since the trajectory of an AGV system is represented by the sequence of $h$ markings ${\mathit{M}}_1,{\mathit{M}}_2,\dots ,{\mathit{M}}_h$ obtained by firing a series of transitions from the initial marking ${\mathit{M}}_0$ , the logic constraint on the trajectory should be considered for all the markings, that is, ${\mathit{M}}_1,\dots ,{\mathit{M}}_h$ . The following constraint guarantees that an AGV will visit region ${\pi }_j\in {\mathrm{\Pi }}^t$ as required in $\phi$ along the trajectory:

$$\{\begin{array}{c}k·h\ge {\mathit{v}}_{{\pi }_j}·(\sum _{i=1}^h{\mathit{M}}_i),\forall {\pi }_j\in {\mathrm{\Pi }}^t,\hfill \\ \multicolumn{1}{c}{1\le {\mathit{v}}_{{\pi }_j}·(\sum _{i=1}^h{\mathit{M}}_i),\forall {\pi }_j\in {\mathrm{\Pi }}^t,}\end{array}$$

(5)

where $k$ is the total number of AGVs.

Logic constraint on the final state: ³⁶ The final state of an AGV system can be represented by the final marking ${\mathit{M}}_h$ , where $h$ is the maximal number of steps for AGVs to complete the tasks. Therefore, The following constraint guarantees that an AGV will visit region ${\pi }_j\in {\mathrm{\Pi }}^f$ as required in $\phi$ at the final state:

$$\{\begin{array}{c}k\ge {\mathit{v}}_{{\pi }_j}·{\mathit{M}}_h,\forall {\pi }_j\in {\mathrm{\Pi }}^f,\hfill \\ \multicolumn{1}{c}{1\le {\mathit{v}}_{{\pi }_j}·{\mathit{M}}_h,\forall {\pi }_j\in {\mathrm{\Pi }}^f,}\end{array}$$

(6)

Transformation of logic constraint under considered path requirement

Considering the path planning problem for the AGV system discussed in Section “Problem statement”, we assume that a task region ${\pi }_j$ should be visited by at least one AGV along the trajectory (if ${\pi }_j\in {\mathrm{\Pi }}^t$ ) or at the final state (if ${\pi }_j\in {\mathrm{\Pi }}^f$ ). For each AGV $q$ ( $q=1,\dots ,k$ ), we denote by ${\mathit{M}}_{q,i}=[M_{q,i}(p_1)\dots ,M_{q,i}(p_n){]}^T$ the marking of AGV $q$ at the $i$ -th step ( $i=1,\dots ,h$ ), where $M_{q,i}(p_j)=1$ if robot $q$ is located in region ${\pi }_j$ at the $i$ -th step and $M_{q,i}(p_j)=0$ otherwise.

Logic constraint on the trajectory under considered path requirement

For any task region ${\pi }_j\in {\mathrm{\Pi }}^t$ that should be visited by an AGV along the trajectory, the following logic constraint should be satisfied:

$$\exists q\in \{1,\dots ,k\},\exists i\in \{1,\dots ,h\},M_{k,i}(p_j)=1,\forall {\pi }_j\in {\mathrm{\Pi }}^t.$$

(7)

As one can observe, constraint (7) is a logic “or” constraint. In the following proposition, we show how to transform constraint (7) into a set of linear constraints.

Proposition 1. The logic constraint on the trajectory (7) can be transformed into a set of linear constraints as follows:

$$\{\begin{array}{c}\begin{array}{c}{\mathit{v}}_{{\pi }_j}·\left(\sum _{i=1}^h{\mathit{M}}_{q,i}\right)-h\le z_j(q)·H,\forall {\pi }_j\in {\mathrm{\Pi }}^t\hfill \\ \multicolumn{1}{c}{1-{\mathit{v}}_{{\pi }_j}·\left(\sum _{i=1}^h{\mathit{M}}_{q,i}\right)\le z_j(q)·H,\forall {\pi }_j\in {\mathrm{\Pi }}^t}\end{array}\}(a)\hfill \\ \multicolumn{1}{c}{z_j(1)+z_j(2)+\dots +z_j(k)\le k-1,(b)}\\ \multicolumn{1}{c}{z_j(1),\dots ,z_j(k)\in \{0,1\},(c)}\\ \multicolumn{1}{c}{q=1,\dots ,k,i=1,\dots ,h.(d)}\end{array}$$

(8)

where $H\in {\mathbb{R}}_{\ge 0}$ is a constant satisfying

$$H>max\{|{\mathit{v}}_{{\pi }_j}·\left(\sum _{i=1}^h{\mathit{M}}_{q,i}\right)-h|,|1-{\mathit{v}}_{{\pi }_j}·\left(\sum _{i=1}^h{\mathit{M}}_{q,i}\right)|\}.$$

(9)

Proof: Constraints $(8b)$ and $(8c)$ impose that at least one variable $z$ should be zero. By assuming that $z_j(r)=0$ ( $r\in \{1,\dots ,k\}$ ), constraint $(8a)$ can be simplified as follows:

$$\{\begin{array}{c}{\mathit{v}}_{{\pi }_j}·\left(\sum _{i=1}^h{\mathit{M}}_{r,i}\right)\le h,\forall {\pi }_j\in {\mathrm{\Pi }}^t,\hfill \\ \multicolumn{1}{c}{1\le {\mathit{v}}_{{\pi }_j}·\left(\sum _{i=1}^h{\mathit{M}}_{r,i}\right),\forall {\pi }_j\in {\mathrm{\Pi }}^t.}\end{array}$$

(10)

According to equation (5), it guarantees that AGV $r$ will visit the task region ${\pi }_j$ along the trajectory. For any other variable $z_j(q)=1$ ( $q\ne r$ ), we have the following condition:

$$\{\begin{array}{c}{\mathit{v}}_{{\pi }_j}·\left(\sum _{i=1}^h{\mathit{M}}_{q,i}\right)-h\le H,\forall {\pi }_j\in {\mathrm{\Pi }}^t,\hfill \\ \multicolumn{1}{c}{1-{\mathit{v}}_{{\pi }_j}·\left(\sum _{i=1}^h{\mathit{M}}_{q,i}\right)\le H,\forall {\pi }_j\in {\mathrm{\Pi }}^t.}\end{array}$$

(11)

Since $H$ is a large enough number as defined in equation (9), condition (11) becomes redundant and imposes no constraint on the trajectory of AGV $q$ ( $q\ne r$ ). Therefore, the logic constraint on the trajectory (7) is implemented by Proposition 1.

Logic constraint on the final state under the considered path requirement

For any task region ${\pi }_j\in {\mathrm{\Pi }}^f$ that should be visited by an AGV at the final step $h$ (i.e., the final marking ${\mathit{M}}_h$ ), the following logic constraint should be satisfied:

$$\exists q\in \{1,\dots ,k\},M_{q,h}(p_j)=1,\forall {\pi }_j\in {\mathrm{\Pi }}^f.$$

(12)

Similarly, we can transform the logic constraint (12) on the final state into a set of linear constraints by the following proposition.

Proposition 2. The logic constraint (12) on the final state can be transformed into a set of linear constraints as follows:

$$\{\begin{array}{c}\begin{array}{c}{\mathit{v}}_{{\pi }_j}·{\mathit{M}}_{q,h}-1\le z_j(q)·H,\forall {\pi }_j\in {\mathrm{\Pi }}^f\hfill \\ \multicolumn{1}{c}{1-{\mathit{v}}_{{\pi }_j}·{\mathit{M}}_{q,h}\le z_j(q)·H,\forall {\pi }_j\in {\mathrm{\Pi }}^f}\end{array}\}(a)\hfill \\ \multicolumn{1}{c}{z_j(1)+z_j(2)+\dots +z_j(k)\le k-1,(b)}\\ \multicolumn{1}{c}{z_j(1),\dots ,z_j(k)\in \{0,1\},(c)}\\ \multicolumn{1}{c}{q=1,\dots ,k.(d)}\end{array}$$

(13)

where $H\in {\mathbb{R}}_{\ge 0}$ is a constant satisfying

$$H>|{\mathit{v}}_{{\pi }_j}·{\mathit{M}}_{q,h}-1|.$$

(14)

Proof: This proof is analogous to the proof of Proposition 1. Constraints $(13b)$ and $(13c)$ impose that at least one variable $z_j$ should be zero. If $z_j(r)=0$ ( $r\in \{1,\dots ,k\}$ ) holds, condition $(13a)$ can be simplified as ${\mathit{v}}_{{\pi }_j}·{\mathit{M}}_{r,h}=1$ , which implies that AGV $r$ will finally be located in region ${\pi }_j$ . Otherwise, condition $(13b)$ becomes redundant since $H$ is a large enough number as defined in equation (14). Therefore, the logic constraint on the final state (12) is implemented by Proposition 2.

Logic constraint on avoidance

It is easy to verify that the logic constraint on a forbidden region ${\pi }_j\in {\mathrm{\Pi }}^a$ that should be avoided by AGVs can be implemented by the following constraint:

$${\mathit{v}}_{{\pi }_j}·\left(\sum _{q=1}^k\sum _{i=1}^h{\mathit{M}}_{q,i}\right)=0,\forall {\pi }_j\in {\mathrm{\Pi }}^a.$$

(15)

Transformation of time constraint

In this subsection, we propose a method to transform the time constraint of an AGV system into a set of linear constraints. For any task region ${\pi }_j\in {\mathrm{\Pi }}^t\cup {\mathrm{\Pi }}^f$ with a predefined time window $[e_{{\pi }_j},l_{{\pi }_j}]$ , at least one AGV should visit ${\pi }_j$ along the trajectory (if ${\pi }_j\in {\mathrm{\Pi }}^t$ ) or at the final state (if ${\pi }_j\in {\mathrm{\Pi }}^f$ ) in the time window $[e_{{\pi }_j},l_{{\pi }_j}]$ . In other words, place $p_j$ of the TSM system obtained by Algorithm 1 should be marked in the predefined time window at least once. In the following, we denote by ${\tau }_{q,i}$ the time instant when an AGV $q$ visits a region at the $i$ -th step, where $q\in \{1,\dots ,k\}$ and $i\in \{1,\dots ,h\}$ .

Time constraint on the trajectory: For any task region ${\pi }_j\in {\mathrm{\Pi }}^t$ that should be visited along the trajectory with time constraint $[e_{{\pi }_j},l_{{\pi }_j}]$ , the following condition should be satisfied:

$$\begin{array}{c}\exists q\in \{1,\dots ,k\},\exists i\in \{1,\dots ,h\},M_{q,i}(p_j)=1,\hfill \\ \multicolumn{1}{c}{{\tau }_{q,i}\in [e_{{\pi }_j},l_{{\pi }_j}],\forall {\pi }_j\in {\mathrm{\Pi }}^t.}\end{array}$$

(16)

We can transform the time constraint on the trajectory (16) into a set of linear constraints by the following proposition.

Proposition 3. The time constraint on the trajectory (16) can be transformed into a set of linear constraints as follows:

$$\{\begin{array}{c}\begin{array}{c}{\mathit{v}}_{{\pi }_j}·(\sum _{i=1}^h{\mathit{M}}_{q,i})-h\le z_j(q)·H,\forall {\pi }_j\in {\mathrm{\Pi }}^t\hfill \\ \multicolumn{1}{c}{1-{\mathit{v}}_{{\pi }_j}·(\sum _{i=1}^h{\mathit{M}}_{q,i})\le z_j(q)·H,\forall {\pi }_j\in {\mathrm{\Pi }}^t}\\ \multicolumn{1}{c}{z_j(1)+z_j(2)+\dots +z_j(k)\le k-1,}\\ \multicolumn{1}{c}{z_j(1),\dots ,z_j(k)\in \{0,1\},}\\ \multicolumn{1}{c}{q=1,\dots ,k,i=1,\dots ,h,}\end{array}\}(a)\hfill \\ \multicolumn{1}{c}{\begin{array}{c}{\tau }_{q,i}={\tau }_{q,i-1}+\theta ·{\sigma }_{q,i},\hfill \\ \multicolumn{1}{c}{{\tau }_{q,0}=0,}\end{array}\}(b)}\\ \multicolumn{1}{c}{\begin{array}{c}{e}_{{\pi }_j}-{\tau }_{q,i}\le [1-M_{q,i}(p_j)+o_j(q)]·H,\forall {\pi }_j\in {\mathrm{\Pi }}^t\hfill \\ \multicolumn{1}{c}{{\tau }_{q,i}-l_{{\pi }_j}\le [1-M_{q,i}(p_j)+o_j(q)]·H,\forall {\pi }_j\in {\mathrm{\Pi }}^t}\\ \multicolumn{1}{c}{z_j(q)\le o_j(q),}\\ \multicolumn{1}{c}{o_j(1),\dots ,o_j(k)\in \{0,1\},}\\ \multicolumn{1}{c}{o_j(1)+o_j(2)+\dots +o_j(k)\le k-1,}\end{array}\}(c)}\end{array}$$

(17)

where $\theta =[\theta (t_1),\dots ,\theta (t_m)]$ is the firing delay vector that represents the movement time between adjacent regions, ${\sigma }_{q,i}=[{\sigma }_{q,i}(t_1),\dots ,{\sigma }_{q,i}(t_m){]}^T\in {\mathbb{N}}^m$ is the firing count vector of AGV $q$ at the $i$ -th step, and $[e_{{\pi }_j},l_{{\pi }_j}]$ is a prescribed time window for task region ${\pi }_j$ . Parameter $H\in {\mathbb{R}}_{\ge 0}$ is a constant satisfying

$$\begin{array}{c}H>max\{|{\mathbf{v}}_{{\pi }_j}·\left(\sum _{i=1}^h{M}_{q,i}\right)-h|,|{\tau }_{q,i}-e_{{\pi }_j}|,\hfill \\ |1-{\mathbf{v}}_{{\pi }_j}·\left(\sum _{i=1}^h{M}_{q,i}\right)|,|{\tau }_{q,i}-l_{{\pi }_j}|\}.\hfill \end{array}$$

(18)

Proof: According to Proposition 1, constraint (17 $a$ ) imposes that region ${\pi }_j$ will be visited by at least one AGV along the trajectory. Constraint (17 $b$ ) represents the time instant when an AGV $q$ visits a region at each step.

For any AGV $r$ that does not appear in the region ${\pi }_j$ , that is, $z_j(r)=1$ and $M_{r,i}(p_j)=0$ ( $i=1,\dots ,h$ ), constraint (17 $c$ ) can be simplified as follows:

$$\{\begin{array}{c}{e}_{{\pi }_j}-{\tau }_{r,i}\le H,\forall {\pi }_j\in {\mathrm{\Pi }}^t\hfill \\ \multicolumn{1}{c}{{\tau }_{r,i}-l_{{\pi }_j}\le H,\forall {\pi }_j\in {\mathrm{\Pi }}^t}\end{array}$$

(19)

Since $H$ is a large enough number as defined in equation (18), condition (19) becomes redundant and imposes no time constraint for the AGV $r$ .

If region ${\pi }_j$ is visited by an AGV $q$ at the $i$ -th step, that is, $z_j(q)=0$ and $M_{q,i}(p_j)=1$ , then constraint (17 $c$ ) is simplified as follows:

$$\{\begin{array}{c}\begin{array}{c}{e}_{{\pi }_j}-{\tau }_{q,i}\le o_j(q)·H,\forall {\pi }_j\in {\mathrm{\Pi }}^t\hfill \\ \multicolumn{1}{c}{{\tau }_{q,i}-l_{{\pi }_j}\le o_j(q)·H,\forall {\pi }_j\in {\mathrm{\Pi }}^t}\\ \multicolumn{1}{c}{0\le o_j(q),}\\ \multicolumn{1}{c}{o_j(1)+o_j(2)+\dots +o_j(k)\le k-1,}\\ \multicolumn{1}{c}{o_j(1),\dots ,o_j(k)\in \{0,1\},}\end{array}\hfill \end{array}$$

(20)

Since $o_j(q)$ is a binary variable, there exist two possible situations: Situation 1) if $o_j(q)=0$ holds, condition (20) can be simplified as follows:

$$\{\begin{array}{c}{e}_{{\pi }_j}-{\tau }_{q,i}\le 0,\forall {\pi }_j\in {\mathrm{\Pi }}^t\hfill \\ \multicolumn{1}{c}{{\tau }_{q,i}-l_{{\pi }_j}\le 0,\forall {\pi }_j\in {\mathrm{\Pi }}^t}\end{array}\Rightarrow e_{{\pi }_j}\le {\tau }_{q,i}\le l_{{\pi }_j},$$

(21)

which guarantees that the time instant when the region ${\pi }_j$ is visited by an AGV $q$ at the $i$ -th step will satisfy the prescribed time constraint; Situation 2) if $o_j(q)=0$ holds, condition (20) is equivalent to (19) that is redundant. It means that AGV $q$ will visit the region ${\pi }_j$ without a specified time constraint. The final constraint of (17 $c$ ) ensures that at least one AGV will visit region ${\pi }_j$ in the time window $[e_{{\pi }_j},l_{{\pi }_j}]$ . Therefore, the time constraint on the trajectory (16) is implemented by Proposition 3.

Time constraint on the final state: For any task region ${\pi }_j\in {\mathrm{\Pi }}^f$ that should be visited at the final state with time constraint $[e_{{\pi }_j},l_{{\pi }_j}]$ , the following condition should be satisfied:

$$\begin{array}{c}\exists q\in \{1,\dots ,k\},M_{q,h}(p_j)=1,{\tau }_{q,h}\in [e_{{\pi }_j},l_{{\pi }_j}],\forall {\pi }_j\in {\mathrm{\Pi }}^f.\hfill \end{array}$$

(22)

Similarly, we can transform the time constraint (22) on the final state into a set of linear constraints by the following proposition.

Proposition 4. The time constraint on the final state (22) can be transformed into a set of linear constraints as follows:

$$\{\begin{array}{c}\begin{array}{c}{\mathit{v}}_{{\pi }_j}·{\mathit{M}}_{q,h}-1\le z_j(q)·H,\forall {\pi }_j\in {\mathrm{\Pi }}^f\hfill \\ \multicolumn{1}{c}{1-{\mathit{v}}_{{\pi }_j}·{\mathit{M}}_{q,h}\le z_j(q)·H,\forall {\pi }_j\in {\mathrm{\Pi }}^f}\\ \multicolumn{1}{c}{z_j(1)+z_j(2)+\dots +z_j(k)\le k-1,}\\ \multicolumn{1}{c}{z_j(1),\dots ,z_j(k)\in \{0,1\},}\\ \multicolumn{1}{c}{q=1,\dots ,k,{\tau }_{q,i}={\tau }_{q,i-1}+\mathbf{\theta }·{\sigma }_{q,i},}\end{array}\}(a)\hfill \\ \multicolumn{1}{c}{\begin{array}{c}{\tau }_{q,0}=0,\hfill \\ \multicolumn{1}{c}{i=1,\dots ,h,}\end{array}\}(b)}\\ \multicolumn{1}{c}{\begin{array}{c}{e}_{{\pi }_j}-{\tau }_{q,h}\le [1-M_{q,h}(p_j)+o_j(q)]·H,\forall {\pi }_j\in {\mathrm{\Pi }}^f\hfill \\ \multicolumn{1}{c}{{\tau }_{q,h}-l_{{\pi }_j}\le [1-M_{q,h}(p_j)+o_j(q)]·H,\forall {\pi }_j\in {\mathrm{\Pi }}^f}\\ \multicolumn{1}{c}{z_j(q)\le o_j(q),}\\ \multicolumn{1}{c}{o_j(1),\dots ,o_j(k)\in \{0,1\},}\\ \multicolumn{1}{c}{o_j(1)+o_j(2)+\dots +o_j(k)\le k-1,}\end{array}\}(c)}\end{array}$$

(23)

where $H\in {\mathbb{R}}_{\ge 0}$ is a constant satisfying

$$\begin{array}{c}H>max\{|{\mathit{v}}_{{\pi }_j}·{\mathit{M}}_{q,h}-1|,|{\tau }_{q,h}-e_{{\pi }_j}|,|{\tau }_{q,h}-l_{{\pi }_j}|\}.\hfill \end{array}$$

(24)

Proof: According to Proposition 2, constraint (23 $a$ ) imposes that region ${\pi }_j\in {\mathrm{\Pi }}^f$ will be visited by at least one AGV at the final state. Constraint (23 $b$ ) represents the time instant when an AGV $q$ visits a region at each

step. By Proposition 3, constraint (23 $c$ ) enforces that at least one AGV will visit the region ${\pi }_j$ at the final step $h$ in the time window $[e_{{\pi }_j},l_{{\pi }_j}]$ . Therefore, the time constraint on the final state (22) is implemented by Proposition 4.

Path Planning for AGV systems with an ILPP

Combining above results, we present an ILPP to solve the path planning problem for an AGV system with time constraints as follows:

$$\begin{array}{c}min\mathit{w}·\sum _{q=1}^k\sum _{i=1}^h{\mathbf{\sigma }}_{q,i}\hfill \\ \begin{array}{c}{\mathit{M}}_{q,i}={\mathit{M}}_{q,i-1}+\mathit{C}·{\mathbf{\sigma }}_{q,i},\hfill \\ \multicolumn{1}{c}{{\mathit{M}}_{q,i-1}-\mathit{Pre}·{\mathbf{\sigma }}_{q,i}\ge \mathit{0},}\\ \multicolumn{1}{c}{1^T·{\mathbf{\sigma }}_{q,i}\le 1,}\end{array}\}(a)\hfill \\ \begin{array}{c}{\mathit{v}}_{{\pi }_j}·\left(\sum _{i=1}^h{\mathit{M}}_{q,i}\right)-h\le z_j(q)·H,\forall {\pi }_j\in {\mathrm{\Pi }}^t,\hfill \\ \multicolumn{1}{c}{1-{\mathit{v}}_{{\pi }_j}·\left(\sum _{i=1}^h{\mathit{M}}_{q,i}\right)\le z_j(q)·H,\forall {\pi }_j\in {\mathrm{\Pi }}^t,}\\ \multicolumn{1}{c}{e_{{\pi }_j}-{\tau }_{q,i}\le [1-M_{q,i}(p_j)+o_j(q)]·H,\forall {\pi }_j\in {\mathrm{\Pi }}^t,}\\ \multicolumn{1}{c}{{\tau }_{q,i}-l_{{\pi }_j}\le [1-M_{q,i}(p_j)+o_j(q)]·H,\forall {\pi }_j\in {\mathrm{\Pi }}^t,}\end{array}\}(b)\hfill \\ \begin{array}{c}{\mathit{v}}_{{\pi }_j}·{\mathit{M}}_{q,h}-1\le z_j(q)·H,\forall \pi \in {\mathrm{\Pi }}^f,\hfill \\ \multicolumn{1}{c}{1-{\mathit{v}}_{{\pi }_j}·{\mathit{M}}_{q,h}\le z_j(q)·H,\forall {\pi }_j\in {\mathrm{\Pi }}^f,}\\ \multicolumn{1}{c}{e_{{\pi }_j}-{\tau }_{q,h}\le [1-M_{q,h}(p_j)+o_j(q)]·H,\forall {\pi }_j\in {\mathrm{\Pi }}^f,}\\ \multicolumn{1}{c}{{\tau }_{q,h}-l_{{\pi }_j}\le [1-M_{q,h}(p_j)+o_j(q)]·H,\forall {\pi }_j\in {\mathrm{\Pi }}^f,}\end{array}\}(c)\hfill \\ \begin{array}{c}{\tau }_{q,i}={\tau }_{q,i-1}+\mathbf{\theta }·{\mathbf{\sigma }}_{q,i},\hfill \\ \multicolumn{1}{c}{{\tau }_{q,0}=0,}\end{array}\}(d)\hfill \\ {\mathit{v}}_{{\pi }_j}·\left(\sum _{q=1}^k\sum _{i=1}^h{\mathit{M}}_{q,i}\right)=0,\forall {\pi }_j\in {\mathrm{\Pi }}^a,(e)\hfill \\ \begin{array}{c}{z}_j(1)+z_j(2)+\dots +z_j(k)\le k-1,\forall {\pi }_j\in {\mathrm{\Pi }}^t\cup {\mathrm{\Pi }}^f,\hfill \\ \multicolumn{1}{c}{z_j(1),\dots ,z_j(k)\in \{0,1\},\forall {\pi }_j\in {\mathrm{\Pi }}^t\cup {\mathrm{\Pi }}^f,}\\ \multicolumn{1}{c}{o_j(1)+o_j(2)+\dots +o_j(k)\le k-1,\forall {\pi }_j\in {\mathrm{\Pi }}^t\cup {\mathrm{\Pi }}^f,}\\ \multicolumn{1}{c}{z_j(q)\le o_j(q),\forall {\pi }_j\in {\mathrm{\Pi }}^t\cup {\mathrm{\Pi }}^f,}\\ \multicolumn{1}{c}{o_j(1),\dots ,o_j(k)\in \{0,1\},\forall {\pi }_j\in {\mathrm{\Pi }}^t\cup {\mathrm{\Pi }}^f,}\end{array}\}(f)\hfill \\ q=1,\dots ,k,i=1,\dots ,h,(g)\hfill \end{array}$$

(25)

where $H\in {\mathbb{R}}_{\ge 0}$ is a constant satisfying

$$\begin{array}{c}H>max\{|{\mathit{v}}_{{\pi }_j}·\left(\sum _{q=1}^h{\mathit{M}}_{q,i}\right)-h|,|{\mathit{v}}_{{\pi }_j}·{\mathit{M}}_{q,h}-1|,\hfill \\ |1-{\mathit{v}}_{{\pi }_j}·\left(\sum _{q=0}^h{\mathit{M}}_{q,i}\right)|,|{\tau }_{q,i}-e_{{\pi }_j}|,|{\tau }_{q,i}-l_{{\pi }_j}|\},\hfill \end{array}$$

(26)

Note that parameter $h$ in (25) is a predesigned number that represents the maximum number of steps for AGVs to complete the tasks, which is lower than or equal to the total number of transitions, that is, $h\le m$ . The objective function in (25) accounts for the total travel distance of all AGVs in the system. Constraint (25 $a$ ) from (4) enforces the correctness of the firing count vector. Note that constraint (25 $a$ -3) imposes that an AGV can advance maximum one region at each step. Constraints (25 $b$ ) (resp., (25 $c$ )), (25 $d$ ), (25 $f$ ), and (25 $g$ ) jointly impose the logic and time constraints on the trajectory (resp., on the final state) for the task regions. Constraint (25 $e$ ) imposes the avoidance requirement for the forbidden regions. The optimal solution ${\sigma }_{q,i}$ ( $q=1,\dots ,k$ , $i=1,\dots ,h$ ) of ILPP (25) represents the sequence of the firing count vector of the TSM system $G$ that corresponds to the trajectory of each AGV.

Computational complexity

The optimization problem (25) is a standard ILPP whose computational complexity is well known as NP-hard. However, it can be efficiently solved by some off-the-shelf tools such as LINGO, MATLAB, and CPLEX. The computational burden of an ILPP is usually characterized by the number of variables and constraints. Problem (25) has $3\mathrm{kh}+2k(|{\mathrm{\Pi }}^t|+|{\mathrm{\Pi }}^f|)$ variables and $2\mathrm{kh}+(3\mathrm{kh}+3k+2)·(|{\mathrm{\Pi }}^t|+|{\mathrm{\Pi }}^f|)+|{\mathrm{\Pi }}^a|+2k$ constraints in total, where $|{\mathrm{\Pi }}^t|$ , $|{\mathrm{\Pi }}^f|$ , and $|{\mathrm{\Pi }}^a|$ denote the numbers of regions that should be visited along the trajectory, regions that should be visited at the final state, and regions that should be always avoided, respectively.

Simulation results

In this section, the illustration of the developed approach for the path planning problem of AGV systems with time constraints is made on an example that is taken from Mahulea and Kloetzer. ³⁶ The environment of the system is partitioned by using a constrained triangular decomposition ⁴⁶ and has 30 regions as shown in Figure 1, that is, $\mathrm{\Pi }=\{{\pi }_1,{\pi }_2,\dots ,{\pi }_{30}\}$ . There are three AGVs (i.e. $k=3$ ) moving in the environment whose initial positions are marked by circles in Figure 1, that is, regions ${\pi }_5$ (green circle), ${\pi }_{16}$ (blue circle), and ${\pi }_{17}$ (yellow circle) each contain one AGV.

Figure 1.

Simulation results obtained by the proposed approach.

By Algorithm 1, we obtain a TSM system $G$ that consists of 86 transitions and 30 places, as depicted in Figure 2. For exemplification purposes, we consider unitary distance vector $\mathbf{w}=1$ and unitary firing delay vector $\theta =1$ . The firing delays of transitions are omitted in Figure 2 for the sake of brevity and readability.

Figure 2.

The TSM system $G=〈N,\theta ,{\mathit{M}}_0〉$ of the AGV system in Figure 1.

Consider a set of interest regions as follows:

• ${\mathrm{\Pi }}^t$ ={ ${\pi }_8$ , ${\pi }_{10}$ , ${\pi }_{21}$ , ${\pi }_{22}$ , ${\pi }_{23}$ },

• ${\mathrm{\Pi }}^f$ ={ ${\pi }_7$ , ${\pi }_{12}$ , ${\pi }_{29}$ }, and

• ${\mathrm{\Pi }}^a=\{{\pi }_1\}$ ,

it implies that regions ${\pi }_{10}$ , ${\pi }_8$ , ${\pi }_{21}$ , ${\pi }_{22}$ , and ${\pi }_{23}$ should be visited along the trajectory, region ${\pi }_1$ should be avoided (red region in Figure 1), and regions ${\pi }_7$ , ${\pi }_{12}$ , and ${\pi }_{29}$ should be occupied at the final state, that is, AGVs will stop in these regions. We assume that regions ${\pi }_{10}$ , ${\pi }_{12}$ , and ${\pi }_{21}$ must be visited in the time windows $[1,2]$ , $[1,3]$ , and $[2,4]$ , respectively. Therefore, the path requirement of the AGV system can be represented as follows:

$$\begin{array}{c}\phi =({\pi }_1,A),({\pi }_7,F),({\pi }_8,J),({\pi }_{10},J,[1,2]),({\pi }_{12},F,\hfill \\ [1,3]),({\pi }_{21},J,[2,4]),({\pi }_{22},J),({\pi }_{23},J),({\pi }_{29},F).\hfill \end{array}$$

The developed approach is implemented by MATLAB with the ILPP toolbox YALMIP ⁴⁷ and Optimal Solver Gurobi on a Windows operating system with i5-7500 CPU 3.40 GHz and 4 GB memory. By solving ILPP (25) with a maximum number of steps $h=16$ (in approximately 0.82 s), we obtain a series of firing sequences that can be translated into the trajectories of the AGVs, as depicted in Figure 1. Regions ${\pi }_7$ , ${\pi }_8$ , and ${\pi }_{10}$ are visited by the green AGV, region ${\pi }_{12}$ is visited by the blue AGV, and regions ${\pi }_{21}$ , ${\pi }_{22}$ , ${\pi }_{23}$ , and ${\pi }_{29}$ are visited by the yellow AGV.

• yellow AGV: ${\pi }_{17},{\pi }_{18},{\pi }_{21},{\pi }_{20},{\pi }_{22},{\pi }_{30},{\pi }_{26},{\pi }_{25},{\pi }_{24},$ ${\pi }_{23},{\pi }_{24},{\pi }_{25},{\pi }_{29}$

• blue AGV: ${\pi }_{16},{\pi }_{27},{\pi }_{15},{\pi }_{12}$

• green AGV: ${\pi }_5,{\pi }_{11},{\pi }_{10},{\pi }_{14},{\pi }_8,{\pi }_7$

In addition, the approach developed in Mahulea and Kloetzer ³⁶ is implemented by ignoring the time constraints for task regions ${\pi }_{10}$ , ${\pi }_{12}$ , and ${\pi }_{21}$ , that is, task regions ${\pi }_{10}$ , ${\pi }_{12}$ , ${\pi }_{21}$ can be visited at any time. The obtained trajectories of the AGVs are shown in Figure 3. Regions ${\pi }_7$ and ${\pi }_8$ are visited by the yellow AGV, regions ${\pi }_{10}$ and ${\pi }_{12}$ are visited by the green AGV, and regions ${\pi }_{21}$ , ${\pi }_{22}$ , ${\pi }_{23}$ , and ${\pi }_{29}$ are visited by the blue AGV.

• yellow AGV: ${\pi }_{17},{\pi }_8,{\pi }_7$

• blue AGV: ${\pi }_{16},{\pi }_{28},{\pi }_{20},{\pi }_{22},{\pi }_{20},{\pi }_{21},{\pi }_{24},{\pi }_{23},{\pi }_{24},$ ${\pi }_{25},{\pi }_{29}$

• green AGV: ${\pi }_5,{\pi }_{11},{\pi }_{10},{\pi }_{11},{\pi }_{12}$

Figure 3.

Simulation results obtained by the approach developed in Mahulea and Kloetzer. ³⁶

In Table 1, we compare the visiting time of the task regions obtained by the proposed approach and that developed in Mahulea and Kloetzer. ³⁶ The method developed in Mahulea and Kloetzer ³⁶ aims to find the optimal trajectories of AGVs such that all the task regions are visited (without specifying the visiting time), while the total travel distance is minimized. Therefore, the time constraints considered in this paper cannot be implemented by the method developed in Mahulea and Kloetzer, ³⁶ which means that the visiting time of the task regions may fall into the time window (e.g. region ${\pi }_{10}$ in Table 1), less than the lower bound, or beyond the upper bound (e.g. region ${\pi }_{12}$ and ${\pi }_{21}$ in Table 1).

Table 1.

Visiting time of the task regions obtained by the proposed approach and that developed in Mahulea and Kloetzer. ³⁶

Task regions	${\pi }_7$	${\pi }_8$	${\pi }_{10}$	${\pi }_{12}$	${\pi }_{21}$	${\pi }_{22}$	${\pi }_{23}$	${\pi }_{29}$	Total travel distance
Proposed approach	5	4	2	3	2	4	9	12	20
Approach developed in Mahulea and Kloetzer 36	2	1	2	4	5	3	7	10	16

Conclusion

This paper deals with the path planning problem for AGV systems with logic and time constraints using PNs. We propose an analytical approach to ensure that task regions are visited by AGVs in time and forbidden regions are avoided. We propose a method to model an AGV system and its static environment by timed Petri nets. Combining the structural characteristics of Petri nets and integer linear programming technique, a path planning method is developed to obtain the optimal trajectories of AGVs such that the total travel distance is minimzed. Simulation studies are presented to show that our developed method is more accurate than the previous method.

It should be noticed that all the AGVs are assumed to be identical, that is, a single type of AGVs is considered. From a practical point of view, multiple types of AGVs may be needed to cooperatively finish some complex tasks. Our future work focuses on the path planning problem with time constraints for AGV systems that contain multiple types of AGVs.