=Paper=
{{Paper
|id=None
|storemode=property
|title=Deadlock Control Software for Tow Automated Guided Vehicles using Petri Nets
|pdfUrl=https://ceur-ws.org/Vol-827/21_CarlosRovetto_article.pdf
|volume=Vol-827
|dblpUrl=https://dblp.org/rec/conf/acsd/RovettoCC10
}}
==Deadlock Control Software for Tow Automated Guided Vehicles using Petri Nets==
https://ceur-ws.org/Vol-827/21_CarlosRovetto_article.pdf
Deadlock Control Software for Tow Automated
Guided Vehicles using Petri Nets
Carlos Rovetto1 , Elia Cano1 and José-Manuel Colom2
1
Dpt. of Computer Science and Systems Engineering (DIIS)
2
Aragón Institute of Engineering Research (I3A)
University of Zaragoza, Spain
{carlos.rovetto,elia.cano}@utp.ac.pa, jm@unizar.es
Abstract. Factoring and warehouse distribution centers face numerous
and interrelated challenges in their eorts to move products and materi-
als through their facilities. New technologies in navigation and guidance
allow true autonomy with more exibility and resource e ciency. In this
paper we investigate a complete design approach to obtain deadlock-free
minimal adaptive routing algorithms for these systems. The approach is
based in an abstract view of the system as a Resource Allocation System.
The interconnection network and the routing algorithm elaborated by the
designer, are the initial information used to obtain in an automatic way
a Petri Net model. For this kind of routing algorithms, we prove that the
obtained Petri Net belongs to the well-known class of S 4 P R net systems,
and therefore the rich set of analysis and synthesis results can be applied
to enforce the liveness property of the routing algorithm.
Key words: AGVs, Control Software, Resource Allocation Systems (RAS),
Modular Models, Structural Analysis.
1 Introduction
Nowadays, many factories and warehouse and distribution centers use Auto-
matic Guided Vehicles (AGV s) for item transportation among workstations.
The wheeled trailers are the most productive form of AGV for tugging and tow-
ing because they haul more conveyor-loads per trip than other AGV types. In
this paper we consider a warehouse distribution center as a programmable sys-
tem for conveyor-loads movement among workstations using tugger AGV . The
problem to be investigated concerns the design of Deadlock-Free minimal adap-
tive routing algorithms for the guidance system of tuggers AGV s, travelling into
an warehouse distribution center. We say that the routing algorithm is minimal
because only routes of minimal length between two workstations are taken into
account. Moreover, the routing algorithms we are considering are adaptive in
the sense that the route of a conveyor-load is constructed segment by segment.
The assignment of a segment to the route of a conveyor-load is done in a work-
station when the rst trailer try to leave the workstation towards its destination
workstation.
From the methodological point of view, the design of deadlock-free minimal
adaptive routing algorithms is a complex task, where the designer experience
is required because deadlock states can appear. There exist several approaches
Recent Advances in Petri Nets and Concurrency, S. Donatelli, J. Kleijn, R.J. Machado, J.M. Fernandes
(eds.), CEUR Workshop Proceedings, ISSN 1613-0073, Jan/2012, pp. 251–265.
252 Petri Nets & Concurrency Rovetto, Cano, and Colom
to cope with this problem [15]. They consider more general routing algorithms
than those considered in this paper (including, for example, non-minimal routes).
Because this generality, very few powerful analysis and synthesis results are
available.
Our approach gives a full design cycle for minimal adaptive routing algorithms
using Petri Nets as formal model that allows structural analysis of the liveness
property of the model. Afterwards, if it is necessary, the initial routing algorithm
is changed. From the point of view of software engineering, in the context of the
control software for AGV s systems, this paper intends to make contributions in
the following directions: (a) The formalization of an abstraction process of the
system to retain only the relevant characteristics in the study of deadlock prob-
lems in the routing software of AGV s. This abstraction is constructed around a
minimal set of concepts processes and resources. (b) The demonstration that
for AGVs with minimal adaptive routing algorithms, the proposed abstraction
process gives rise to models belonging to a well known class of Petri Nets named
S 4 P R, and so, we have many available results to cope with these systems. (c)
A modular methodology to construct the models based on the speci cation of
processes with resources that form the modules. The modules are composed by
the fusion of common shared resources (segments) by dierent modules. This
paper is organized as follows. In Section 2 an illustrative example is presented.
In section 3 the proposed methodology is presented in detail. Section 4 presents
the rst step of the methodology consisting of the abstraction of the warehouse
distribution center and the routing algorithm to retain only those aspects related
to the appearing of deadlocks. Section 5 is devoted to the Petri Net model rep-
resenting the Resource Allocation view of the system. This section also proves
that the Petri Nets obtained for these routing algorithms belong to the class
of the S 4 P R nets. Section 6 presents the analysis and synthesis phases of the
methodology that pro t the theoretical results known for the class of S 4 P R.
Finally, section 7 presents some conclusions.
2 An Example
In this section, a simple example of a warehouse distribution center, will be pre-
sented. The speci cation of this example illustrates the typical situation in the
transportation system of items. We start with a layout of the shipping areas
de ned by a set of workstations W S and a set of segments SG interconnecting
the workstations. The connection pattern among workstations will be called the
f ramework of the warehouse distribution center. The example that we are con-
sidering is an unidirectional ring in clockwise fashion as underlying framework.
There are four workstations W S ={w0 , w1 , w2 , w3 } and they are interconnected
by a set of segments SG={sa0 , sa1 , sa2 , sl1 , sl2 , sl3 }. This warehouse distribution
center is depicted in schematic way in Fig. 1.a. Observe that if a workstation
has two output segments, a train can follow any of them. This decision is taken
by the local minimal adaptive routing algorithm of the workstation. The other
de ning element of the warehouse distribution center is the behavior of the
conveyors because a train can tow single or multiple trailers hence the length
of the conveyors is variable. As the conveyors ow in pipeline fashion through
Deadlock control software for vehicles Petri Nets & Concurrency – 253
Fig. 1. a) Framework skeleton and its, b) Warehouse Graph.
the framework, these can have simultaneously allocated several segments of the
framework. The rst trailer of the AV G train is the head of the conveyors and
reserve the segments to transit; the last trailer is the tail and release them. Tra-
ditionally, each segment supports only one conveyor at time to avoid collisions.
In our example, each workstation executes, an instance of the following minimal
adaptive routing algorithm parameterized by the identity of the workstation.
ALGORITHM 1 Minimal Adaptive Routing Algorithm for workstation i.
Input: The head trailer cl from the conveyor-load queue.
Local: Si ⊆ SG, output segments for workstation i
F ⊆ Si , set of non-assigned output segments
Output: The next segment to be used for cl
begin
if (destination(cl) = i) then store the conveyor-load cl in workstation i
else
if ( sai ∈ F ) then use sai ; F :=F \{sai }
else
if ((destination(cl) < i) ∧ (sli ∈ F )) then
use sli ; F :=F \{sli }
else enqueue cl
end if
end if
end if
end
That means the workstation knows its non-assigned output segments and the
algorithm assigns, if it is possible, the output segment that the rst trailer must
follows in order to reach its destination. In other words, to reach a destination
workstation, wd , dierent to the current workstation wi , the algorithm tries to
assign the output segment sai if it is an output free segment of wi . Otherwise,
sli is assigned if this segment is an output free segment of wi and the index d
of the workstation wd is less than the index i of wi . This reservation is done by
the head trailers. The intermediate trailers follow through the reserved segments
and the tail trailer release the segments that they will be added to the set of free
segments F . The design of minimal adaptive routing algorithms can lead to so-
lutions where deadlock states can be reached. A deadlock state, in a warehouse
distribution center, arise when a set of conveyor-loads are in transit to their
respective destination workstations but all of them are stopped forever in inter-
mediate workstations. They are waiting for the availability of output segments of
254 Petri Nets & Concurrency Rovetto, Cano, and Colom
these intermediate workstations that have been previously assigned to conveyor-
loads belonging to this set. Therefore, none of the implied conveyor-loads will
reach their destination workstations. The minimal adaptive routing algorithm
of our example presents this anomaly that we illustrate by means of the fol-
lowing deadlock state. We have four conveyor-loads, {cl1 , cl2 , cl3 , cl4 }, each one
composed by more than one trailer. It is easy to verify that the state described
in table 1, for the four conveyor-loads in transit, is reachable, where H and T
represent the current workstations of the head and tail trailers, respectively. The
rest of the columns in the table 1 represent: Allocated segments − segments as-
signed to the conveyor-load; Destination workstation − represents the destination
workstation of the conveyor-load; Next segment − segment to be assigned to the
head trailer according to the minimal adaptive routing algorithm. Observe that
Conveyor Trailers Allocated Destination Next
-loads H T Segments Workstation segment
cl1 w0 w3 sl3 w1 sa0
cl2 w1 w0 sa0 w2 sa1
cl3 w2 w1 sa1 w3 sa2
cl4 w3 w2 sa2 w1 sl3
Table 1. Deadlock state reached in the example concerning four conveyor-loads.
all conveyor-loads are in intermediate workstations and in order to advance in
the warehouse distribution center, all conveyor-loads need segments (those given
by the minimal adaptive routing algorithm) that they are allocated by other
conveyor-loads in the same set (compare the two columns "Allocated Segments"
and "Next segment" in the table 1). On the other hand, none of the tail trailers
can release segments because if some tail trailer moves ahead, it will be in the
same workstation that the head trailer and this is not possible. Therefore, we
have reached a deadlock state where the four classical necessary conditions for
the existence of a deadlock are ful lled. Finally, you can observe that although
we are in a deadlock state, there exist two segments, sl1 and sl2 , that they are
free, and the minimal adaptive routing algorithm cannot assign these segments
to the four conveyor-loads of our scenario.
3 The proposed methodology
In this paper we advocate for a methodology where, after an analysis phase
of the model obtained from the framework (the interconnection network) and
the minimal adaptive routing algorithm, a synthesis procedure transform the
original routing algorithm to make it deadlock-free. In order to implement this
methodology we will make use of Petri Net models. Therefore, the rst task will
be the construction of the Petri Net model that retains only those aspects related
to the appearing of the deadlock states. Deadlocks appear as a consequence of
the allocation of the segments by the conveyor-loads in transit in the warehouse
distribution center. Therefore, we will adopt a Resource Allocation perspective
to abstract the system (RAS view of the warehouse distribution center) where
segments will be considered as resources, that they are used in a conservative
way (they are not created nor destroyed) by the user processes that they are
Deadlock control software for vehicles Petri Nets & Concurrency – 255
the conveyor-load moving from a source workstation to a destination worksta-
tion. In next section, from the framework and the routing algorithm we will
obtain a Routing Graph for each destination workstation. One of these Routing
Graphs represents a transition graph where we present the reachable states of a
conveyor-load, composed by more than one trailer, from a source workstation of
the warehouse distribution center to the destination workstation corresponding
to the Routing Graph. From these Routing Graph and the segments consid-
ered as resources, in section 5 we obtain a Petri Net that, in the case of minimal
adaptive routing algorithms, belongs to the well known class of S 4 P R nets. Now,
using the known analysis results for this class of nets we can characterize the
existence of deadlocks using a structural reasoning. The synthesis procedure is
based on the methods for liveness enforcing developed by dierent authors [6]
[7] [8]. The Fig. 2 presents in graphical form the methodology we propose for the
design of deadlock-free minimal adaptive routing algorithms. In this methodol-
ogy, the Petri Nets play a central role, because they are used to model the RAS
view of the warehouse distribution center, and this is the reason of this paper:
to present how to obtain these Petri Nets and to prove that they belong to a
previously known class of Petri Nets (S 4 P R), and so well studied.
Start
Specification
Framework Minimal Adaptive Designer
Routing Algorithm Specification
Warehouse Graph State space
of a given
Segments
conveyor-load
Abstraction
Minimal Path Graph with destination
workstation wsi
Conveyor Behaviour Graph
Routing Graph
Resources Processes
Formal
Model
RAS view
Petri Net of the class S4PR Formal Model
Liveness Analysis in S4PR
Analysis Synthesis Phase
The designer
No Yes specification
Live is accepted
Backward propagation
Synthesis procedure of the constrains on The modified
for liveness the model to the specification
enforcing in the minimal adaptive
warehouse net model is accepted
routing algorithm
Fig. 2. Design Flow Methodology.
256 Petri Nets & Concurrency Rovetto, Cano, and Colom
4 Construction of the Routing Graph
The goal of this section is to represent, step by step, the construction of the so
called Routing Graph from the information about the framework of the ware-
house distribution center and the minimal adaptive routing algorithm. This
Routing Graph will represent the sequence of states that a conveyor-load must
follow to reach a given destination workstation, wi . The de nition of the state
concerns the set of segments that the conveyor-load is using each time. Therefore,
RG give us the so called Resource Allocation (RAS) view of the warehouse distri-
bution center. First, the framework is formalized through the Warehouse Graph
(WG). The W G is a labeled graph W G=(W, S), where W is a set of vertices
and S is a set of edges. The set W is equal to W S and S⊆W ×2SG ×W , where
W S is the set of vertices and SG the set of segments. An edge (w1 , s, w2 )∈S
means that there exists a set of segments s⊆SG from the workstation w1 to the
workstation w2 , as it is shown in the Fig. 1.b. We are considering the class of
minimal adaptive routing algorithms. Therefore we will represent for each desti-
nation workstation wi all the paths of minimal length from a workstation wj to
the destination workstation wi . This information is captured into the Minimal
Path Graph (M P Gi ) with destination workstation wi . Each one of these graphs
is a subgraph of the W G = (W, S) and it will be an acyclic directed labeled
graph, M P Gi =(V, E), where V =W , and E⊆S , verifying that:
1. All output arcs of wi in W G do not belong to E .
2. The function Li :V →IN is well de ned: Li (wi )=0 and ∀wj ̸=wi , Li (wj )=k ,
where k is the length of the minimal path from wj to wi in the W G.
3. All arcs (w1 , s, w2 ) ∈ S in W G, such that Li (wi )+1 ̸=Li (w2 ), do not belong
to E .
The graphs M GPi for the example of Fig. 1 are depicted in the Fig. 3. Observe
that we will have four of these graphs, one for each possible destination worksta-
tion. Each M P Gi can be seen as the set of paths that can follow a conveyor-load
Fig. 3. Minimal Path Graph for all destination of our example.
originated in the workstation wj with destination workstation wi , an this path
satisfy the minimality condition of the considered routing algorithm. Neverthe-
less, we are considering conveyor-loads with more than one trailer of length,
because a conveyor-load with only one trailer cannot participate into a dead-
lock, since a deadlock must ful ll the Hold and Wait condition. Therefore in our
model we must distinguish states according to the workstations where the head
and tail trailers can be found. On the other hand, it is important to say that the
Deadlock control software for vehicles Petri Nets & Concurrency – 257
advancement of the head trailer from a workstation to another can be done if and
only if there exists at least a segment that can be allocated for this movement.
Segments, therefore are resources in our RAS view of the warehouse distribution
center. If the head trailer allocates the needed resources for the movement of the
full conveyor-load, the tail trailer take charge of the release operation after the
use of a segment. In order to represent the states of a conveyor-load with desti-
nation workstation wi we will construct, from the M P Gi , the so called Conveyor
Behaviour Graph (CBG) for the destination workstation wi , CBGi =(Q, F ), ver-
ifying that.
1. Q⊆V ×V , where ∀wh , wt ∈Q, wh =wt or L(wh ) 0.
∪
2. T = i∈IN Ti , Ti ̸= ∅, Ti ∩ Tj = ∅, for all i ̸= j
3. For all i ∈ IN , the subnet Ni generated by PSi ∪ {p0i } ∪ Ti is a strongly
connected state machine, such that every cycle contains p0i .
4. For each r ∈ PR there exists a minimal PSemi ow, yr ∈ IN|P | , such that
{r} =∪||yr || ∩ PR , yr [r] = 1, P0 ∩ ||yr || = ∅, and PS ∩ ||yr || ̸= ∅.
5. PS = r∈PR (||yr || \ {r}).
Each place p0i is called idle place. Places of PR are called resource places being
unique for the whole model. The Places of PS are called process places. This def-
inition must be completed with the de nition of the acceptable initial markings.
Initial markings represent no activity in the system, allowing the routing of each
conveyor-load in isolation.
De nition 2 Let N = ⟨P0 ∪ PS ∪ PR , T, C⟩ be a S 4 P R net. An initial marking
m0 is acceptable for N if and only if: (1) ∀i ∈ IN , m0 [p0i ] > 0. (2) ∀p ∈ PS ,
m0 [p] = 0. (3) ∀r ∈ PR , m0 [r] ≥ maxp∈||yr ||\{r} yr [p].
From the previous de nitions and the procedures described in the sections 4 and
5 to obtain the Petri Net model of an warehouse distribution center the following
result can be easily veri ed.
Proposition 1 Given an warehouse distribution center speci ed by means of
a framework and a minimal adaptive routing algorithm, the Petri Net model
obtained through the procedure described in sections 4 and 5, belongs to the class
of S 4 P R net systems.
Proof (Sketch of the proof ). In the section 5, after the rules to obtain the Petri
Nets Ni from the corresponding Routing Graph RGi , we have proven that each
Ni is a strongly connected state machine, and for all Ni ,Nj , i ̸= j , they are
disjoint net systems. We have also proven that every cycle of each strongly
connected state machine Ni contains P0i . Therefore, to complete the proof we
only need to prove the existence of a unique p-semi ow yr ∈ IN|P | for each
resource r. But this is very easy to proof because from each transition where the
resource place r inputs (the resource is allocated), there exists a unique path, in
the strongly connected state machine, to reach each transition where r outputs
(the resource is released). Moreover, all transitions where r is an output place
in the state machine Ni are connected by means of a minimal path from some
transition where r is an input place. Therefore, the resource r plus all the process
places de ning the minimal paths connecting the output transitions of r and the
input transitions of r form the p-semi ow that it is unique because we are dealing
with the nets Ni that they are state machines.
Deadlock control software for vehicles Petri Nets & Concurrency – 263
Observe that the previous result is also true for non-regular frameworks because
we are considering in an explicit way the paths to a destination workstation.
Therefore, non regularity does not aect the nal Petri Net. Nevertheless, non-
minimality of the path selection algorithms can lead to more general class of
nets than the S 4 P R in the case of existence of cycles in the followed route by
some conveyor-load. Once we have characterized the type of nets we can obtain,
we can use the developed theory for S 4 P R, trying to interpret these results from
the point of view of the warehouse distribution centers, in the next section. In
some cases we will see that we arrive to some negative results.
6 The Analysis and synthesis phase
The Petri Net model obtained in the previous section belong to the S 4 P R class.
Therefore, we can take advantage of this property and use the theoretical results
about the liveness characterization in S 4 P R. One of this results is presented in
the following theorem.
Theorem 2 ([6]) An S 4 PR , ⟨N , m0 ⟩, is nonlive if and only if there exists a
marking m ∈ RS(N , m0 ) such that the set of mprocessenabled transitions is
nonempty and each one of these transitions is mresourcedisabled.
This characterization is a state based characterization. The interpretation in
terms of the warehouse distribution center is very easy. A token in a process place
of the state machine Ni represent a conveyor-load in an intermediate workstation
with destination workstation wi . That is, is a conveyor-load in transit. The
theorem 2 says that if all conveyor-loads in transit cannot advance because there
is no an available segment to advance (each one of these transitions is not enabled
because an input resource place is empty), this situation characterizes a deadlock
state: none of these conveyor-loads will arrive to its destination workstation
because they are stopped forever in the current process places. In [6], veri cation
procedures of the characterization stated in this theorem are presented. They
are based in Integer Linear Programming Techniques.
An equivalent characterization to the previous one is based in the Petri Net
concept of siphon. A siphon is a set of places that if they become a set of empty
places, they remain empty forever (these is a structural de nition of siphon but
we prefer to present the deep reason for the appearing of deadlocks in this class of
nets). Therefore, all output transitions of the places of the empty siphon will be
dead forever because at least an input place (that belong to the siphon) is empty
forever. The presence of one of this siphons in the net is potentially bad because
this siphon can become an empty siphon. The veri cation procedures search
for a siphon and a reachable marking under which the siphon is empty. Empty
siphons represent a generalization of the circular waits, because in a siphon we
can nd an intricate structure of superposed cycles of empty resources. For the
Petri Net in Fig. 6, you can nd the two following bad siphons Di ={p1 , p2 , p3 ,
p4 , p13 , p15 , p17−to−20 , p22 , p24 , p25 , p28 , p30 , p31 , p33 , p34 , p36 , p37 , p39 , p40 ,
p42 , p43 , p45 , p46 } and Dj ={p1 , p2 , p3 , p4 , p6 , p13 , p15 , p17−to−20 , p22 , p24 , p25 ,
p27 , p28 , p30 , p31 , p33 , p34 , p36 , p37 , p39 , p40 , p42 , p43 , p45 , p46 }. The deadlock
state described in section 2 corresponds to the reachable marking written as a
symbolic sum mr = p5 + p6 + 5 · p7 + 2 · p8 + ·p9 + 2 · p10 + p29 + p32 + p38 + p44 . The
264 Petri Nets & Concurrency Rovetto, Cano, and Colom
reader can easily verify that the siphon Di is insu ciently marked or he/she can
verify the mr satisfy the conditions of the theorem 2. Therefore, we conclude that
the proposed path selection algorithm is not deadlock-free. After the previous
analysis phase, the theory of S 4 P R nets gives results and methods to enforce
the liveness in the case of nets presenting deadlock states. These techniques
transform the initial Petri Net model in such a way that deadlock states become
not reachable. In some sense, they correspond to deadlock prevention techniques.
We can incorporate this phase because we are using Petri Nets as formal model
and they belong to the subclass of S 4 P R. The known synthesis approaches
enforcing liveness work on the bad siphons that can be found in the Petri Net
model. These techniques can be classi ed into two groups.
1. Centralized Approach: [6][9] These techniques compute a place for each
bad siphon preventing that the siphon becomes empty. This new place is of
the same category that the resource places, and so it is said that the synthesis
problem is solved by using virtual resources that they are implemented as
a centralized monitors in the central software. In the case of the Petri Net
of the Fig. 6 we need three places to make live the net. In fact, in some
cases, to take the decision to allocate the virtual resource/segment in a local
workstation we can need coordinate the local path selection algorithm with
other local routing algorithms.
2. Distributed Approach:[10]. Previous limitations are solved developing a
distributed control policy using the so called swap virtual segments.
All these methods are iterative, but the performed transformations maintain the
transformed Petri Net inside the class of S 4 P R nets.
7 Conclusions
The design of deadlock-free minimal adaptive routing algorithms for warehouse
distribution centers is a complex and tedious task, for which the current method-
ologies, in many cases, only supply trial and error procedures. The assistance to
the designer is very small in order to x the problem in the proposed algorithm.
In this paper we propose a methodology oriented to the design of deadlock-free
minimal adaptive routing algorithms trying to cope with all phases of the design.
The rst step in this methodology consists of the abstraction of the system in or-
der to retain only the elements of the system allowing the study of the appearing
of deadlocks. These elements are the segments of the warehouse distribution cen-
ter, that they are seen as the resources for which the routing processes compete
to send conveyor-loads to destination workstations. The other elements are the
routing processes itself that represent the routing sequence through the frame-
work according to the routing algorithm. The result of this abstraction process is
formalized by means of a Routing Graph for each possible destination worksta-
tion. From the Routing Graphs and the segments we have obtained Petri Nets
that, for the class of routing algorithms that we are considering, belong to the
class of S 4 P R. Therefore, we pro t that the class of S 4 P R is a well studied sub-
class of Petri Nets and using the known results we can proceed with the analysis
and synthesis phases of our methodology. So, the deadlock-free property in the
warehouse distribution center correspond to the liveness-property in our Petri
Deadlock control software for vehicles Petri Nets & Concurrency – 265
Net model. The analysis of this liveness property can be done by two alternative
characterizations that have a good interpretation at the level of warehouse dis-
tribution center. Algorithms and methods to verify the property can be found in
[6]. In the case of non-liveness, there exist methods to enforce the liveness prop-
erty based in the addition of places that can be interpreted in terms of Petri Net
model as centralized software monitors.
References
1. Fanti, M.: A deadlock avoidance strategy for AGV systems modelled by coloured
Petri nets. In: Discrete Event Systems, 2002. Proc. Sixth Int. Workshop on. (2002)
61 66
2. Wu, N., Zhou, M.: Resource-oriented Petri nets in deadlock avoidance of AGV
systems. In: Robotics and Autom., 2001. Proc. 2001 ICRA. IEEE Int. Conf. on.
Volume 1. (2001) 64 69 vol.1
3. Wu, N., Zhou, M.: Modeling and deadlock control of automated guided vehicle
systems. Mechatronics, IEEE/ASME Transactions on 9(1) (2004) 50 57
4. Wu, N., Zhou, M.: Modeling and deadlock avoidance of automated manufacturing
systems with multiple automated guided vehicles. Systems, Man, and Cybernetics,
Part B: Cybernetics, IEEE Transactions on 35(6) (2005) 1193 1202
5. Wu, N., Zhou, M.: Shortest routing of bidirectional automated guided vehicles
avoiding deadlock and blocking. Mechatronics, IEEE/ASME Transactions on 12(1)
(2007) 63 72
6. Tricas, F.: Analysis, Prevention and Avoidance of Deadlocks in Sequential Resource
Allocation Systems. PhD thesis, Zaragoza. España, Departamento de Ingeniería
Eléctrica e Informática, Universidad de Zaragoza (2003)
7. Tricas, F., Colóm, J., Ezpeleta, J.: A Solution to the Problem of Deadlocks in
Concurrent Systems Using Petri Nets and Integer Linear Programming. In Horton,
G., Moller, D., Rude, U., eds.: Proc. of the 11th European Simulation Symp.,
Erlangen, Germany, The society for Computer Simulation Int. (1999) 542546
8. Park, J., Reveliotis, S.A.: Enhancing the Flexibility of Algebraic Deadlock Avoid-
ance Policies Through Petri Net Structural Analysis. In: Proc. of the 2000 IEEE
Int. Conf. on Robotics and Autom., San, Francisco, USA (2000) 33713376
9. Tricas, F., García-Vallés, F., Colóm, J.M., Ezpeleta, J.: A Petri Net Structure-
Based Deadlock Prevention Solution for Sequential Resource Allocation Systems.
In: Proc. of the 2005 IEEE Int. Conf. on Robotics and Autom., Barcelona, Spain
(2005) 272278
10. Rovetto, C., Cano, E., Colóm, J.: Liveness Enforcing Methods for Resource Allo-
cation Distributed Systems using Petri Nets, Research Report RR-056-09. Depto
de Informática e Ingeniería de Sistemas., University of Zaragoza (2009)
Acknowledgement
This work has been partially supported by the European Community's Seventh
Framework Programme under project DISC (Grant Agreement n. INFSO-ICT-
224498). This work has been also partially supported by the project CICYT-
FEDER DPI2006-15390.