IEEE Robotics & Automation Magazine - June 2015 - 89
has been especially active and influential in the relevant literature over the last three decades. More generally, together with
FSAs, PNs are the second major modeling framework used by
the qualitative DES theory, and they are particularly recognized for the richness and clarity of their semantics. These semantics enable a concise and lucid representation of the
behavioral dynamics of the modeled DES while avoiding an
explicit enumeration of the corresponding state space. In the
sequel, we shall assume that the reader is familiar with the
basic PN modeling framework; some excellent introductions
to this subject are provided in [7] and [36].
In the PN modeling framework, an RAS U is represented
by a process-resource net N, consisting of a set of process
subnets modeling the various process types of the RAS and a
set of resource places that model the availability of the system
resources. The aforementioned process subnets are interconnected through the resource places, and the corresponding
connectivity models the allocation of the system resources to
the running process instances. One of the first key results in
the theory of process-resource nets was the connection of the
concept of the RAS deadlock in disjunctive/single-unit RAS
to the concept of the empty siphon. This concept and its connection to the RAS deadlock are exemplified in Figure 5,
which depicts the empty siphon characterizing the RAS deadlock of Figure 1. The seminal result in [13] established that a
disjunctive/single-unit RAS with no cycling in its process
types will possess no RAS deadlocks in its behavior (or that
the corresponding process-resource net will be live and reversible) if and only if there are no reachable empty siphons
for the corresponding process-resource net. But the presence
of an empty siphon in any given marking M of some PN N
can be easily tested by algorithms of polynomial complexity
with respect to the size of N, where the latter is defined by
the size of the bipartite digraph that defines N [8]. Furthermore, the work in [8] showed that, in the case of bounded
PNs, these algorithms can be converted to a mixed-integer
programming (MIP) formulation employing a number of
variables and constraints that are polynomially related to the
size of PN N; in the resulting test, the main outcome is communicated by the optimal value of the MIP formulation,
while, in the case that the tested marking M contains empty
siphons, the returned optimal solution also enables the identification of the maximal empty siphon in M. The MIP formulation mentioned earlier becomes even more useful when the
tested marking M is converted into a variable that lives in the
reachability space of the corresponding net N; in this way,
the resulting MIP formulation becomes an instrument for
testing the presence of an empty siphon over the entire reachability space of N. (Since, however, the analytical characterization of the reachability space of a given PN N by a set of
linear inequalities is a challenging task, in general, one has to
resort to overapproximations of this set that are obtained by
means of the state equation of the net and/or its place invariants. The employment of such an overapproximation raises
the possibility of detecting empty siphons that do not belong
to a reachable marking and turns the overall test into a
T20
T10
P11
R1
T11
P10
P12
T21
R2
2
T12
P13
3
P
P21
P22
P20
T22
2
R3
T13
3
P23
T23
2
Figure 5. The process-resource net modeling the buffer allocation
that takes place in the example manufacturing cell of Figure 1.
The two process types corresponding to J 1 and J 2 are modeled
by the two circuits annotated by black lining in the depicted net.
In particular, the process places p ij, i = 1, 2, j = 1, 2, 3 model the
corresponding processing stages of the underlying RAS, while
the idle places p i0, i = 1, 2 model the external environment for
the two process types. The resource availability is traced by the
marking of the resource places R 1, R 2, and R 3 . The particular
marking depicted in this figure corresponds to the RAS deadlock
state depicted in Figure 1. In the transitional dynamics of the
depicted net, the occurring deadlock is manifested by the
presence of the set of empty places S = " p 12, p 23, R 1, R 2 ,, which is
annotated in yellow. Letting : S (respectively, S : ) denote the set
of transitions that have an output (respectively, input) place in S,
it can be verified that, in the considered case, : S 3 S : . This last
property renders S a siphon. Furthermore, since all places of S
are empty, S is an empty siphon. But then, all the transitions in
S : are disabled in the considered marking, since they require at
least one token from some place in S. Moreover, any transition
in : S that could bring new tokens in S is part of S : , and
therefore, disabled. Hence, it can be concluded that the depicted
empty siphon S will remain empty throughout the entire
evolution of the dynamics of the considered process-resource
net, and the transitions in S : will be dead during this evolution.
sufficiency test for the absence of empty siphons.) When
combined with the results in [13], the aforementioned MIP
formulation eventually becomes a verification tool for the absence of deadlock in any instance from the corresponding
subclass of disjunctive/single-unit RAS.
The extension of these results to broader RAS classes is
quite a nontrivial task since it must account for the nonuniformity of the posed resource requests with respect to any single resource type. This nonuniformity can give rise to
deadlocking situations where the resources that are entangled
in the deadlock have a nonzero slack capacity, but yet this capacity is not adequate for satisfying the requests of the deadlocked processes. Furthermore, in this more general case, the
blocking resources might not be part of a deadlock but of a
livelock, where the slack capacity of these resources can be
used repetitively to satisfy the requests of other running processes that are not entangled in the deadlock. These complications can be effectively circumvented by: 1) extending the
notion of empty siphon to that of deadly marked siphon and
2) searching for deadly marked siphons that interpret any
June 2015
*
IEEE ROBOTICS & AUTOMATION MAGAZINE
*
89
Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - June 2015
IEEE Robotics & Automation Magazine - June 2015 - Cover1
IEEE Robotics & Automation Magazine - June 2015 - Cover2
IEEE Robotics & Automation Magazine - June 2015 - 1
IEEE Robotics & Automation Magazine - June 2015 - 2
IEEE Robotics & Automation Magazine - June 2015 - 3
IEEE Robotics & Automation Magazine - June 2015 - 4
IEEE Robotics & Automation Magazine - June 2015 - 5
IEEE Robotics & Automation Magazine - June 2015 - 6
IEEE Robotics & Automation Magazine - June 2015 - 7
IEEE Robotics & Automation Magazine - June 2015 - 8
IEEE Robotics & Automation Magazine - June 2015 - 9
IEEE Robotics & Automation Magazine - June 2015 - 10
IEEE Robotics & Automation Magazine - June 2015 - 11
IEEE Robotics & Automation Magazine - June 2015 - 12
IEEE Robotics & Automation Magazine - June 2015 - 13
IEEE Robotics & Automation Magazine - June 2015 - 14
IEEE Robotics & Automation Magazine - June 2015 - 15
IEEE Robotics & Automation Magazine - June 2015 - 16
IEEE Robotics & Automation Magazine - June 2015 - 17
IEEE Robotics & Automation Magazine - June 2015 - 18
IEEE Robotics & Automation Magazine - June 2015 - 19
IEEE Robotics & Automation Magazine - June 2015 - 20
IEEE Robotics & Automation Magazine - June 2015 - 21
IEEE Robotics & Automation Magazine - June 2015 - 22
IEEE Robotics & Automation Magazine - June 2015 - 23
IEEE Robotics & Automation Magazine - June 2015 - 24
IEEE Robotics & Automation Magazine - June 2015 - 25
IEEE Robotics & Automation Magazine - June 2015 - 26
IEEE Robotics & Automation Magazine - June 2015 - 27
IEEE Robotics & Automation Magazine - June 2015 - 28
IEEE Robotics & Automation Magazine - June 2015 - 29
IEEE Robotics & Automation Magazine - June 2015 - 30
IEEE Robotics & Automation Magazine - June 2015 - 31
IEEE Robotics & Automation Magazine - June 2015 - 32
IEEE Robotics & Automation Magazine - June 2015 - 33
IEEE Robotics & Automation Magazine - June 2015 - 34
IEEE Robotics & Automation Magazine - June 2015 - 35
IEEE Robotics & Automation Magazine - June 2015 - 36
IEEE Robotics & Automation Magazine - June 2015 - 37
IEEE Robotics & Automation Magazine - June 2015 - 38
IEEE Robotics & Automation Magazine - June 2015 - 39
IEEE Robotics & Automation Magazine - June 2015 - 40
IEEE Robotics & Automation Magazine - June 2015 - 41
IEEE Robotics & Automation Magazine - June 2015 - 42
IEEE Robotics & Automation Magazine - June 2015 - 43
IEEE Robotics & Automation Magazine - June 2015 - 44
IEEE Robotics & Automation Magazine - June 2015 - 45
IEEE Robotics & Automation Magazine - June 2015 - 46
IEEE Robotics & Automation Magazine - June 2015 - 47
IEEE Robotics & Automation Magazine - June 2015 - 48
IEEE Robotics & Automation Magazine - June 2015 - 49
IEEE Robotics & Automation Magazine - June 2015 - 50
IEEE Robotics & Automation Magazine - June 2015 - 51
IEEE Robotics & Automation Magazine - June 2015 - 52
IEEE Robotics & Automation Magazine - June 2015 - 53
IEEE Robotics & Automation Magazine - June 2015 - 54
IEEE Robotics & Automation Magazine - June 2015 - 55
IEEE Robotics & Automation Magazine - June 2015 - 56
IEEE Robotics & Automation Magazine - June 2015 - 57
IEEE Robotics & Automation Magazine - June 2015 - 58
IEEE Robotics & Automation Magazine - June 2015 - 59
IEEE Robotics & Automation Magazine - June 2015 - 60
IEEE Robotics & Automation Magazine - June 2015 - 61
IEEE Robotics & Automation Magazine - June 2015 - 62
IEEE Robotics & Automation Magazine - June 2015 - 63
IEEE Robotics & Automation Magazine - June 2015 - 64
IEEE Robotics & Automation Magazine - June 2015 - 65
IEEE Robotics & Automation Magazine - June 2015 - 66
IEEE Robotics & Automation Magazine - June 2015 - 67
IEEE Robotics & Automation Magazine - June 2015 - 68
IEEE Robotics & Automation Magazine - June 2015 - 69
IEEE Robotics & Automation Magazine - June 2015 - 70
IEEE Robotics & Automation Magazine - June 2015 - 71
IEEE Robotics & Automation Magazine - June 2015 - 72
IEEE Robotics & Automation Magazine - June 2015 - 73
IEEE Robotics & Automation Magazine - June 2015 - 74
IEEE Robotics & Automation Magazine - June 2015 - 75
IEEE Robotics & Automation Magazine - June 2015 - 76
IEEE Robotics & Automation Magazine - June 2015 - 77
IEEE Robotics & Automation Magazine - June 2015 - 78
IEEE Robotics & Automation Magazine - June 2015 - 79
IEEE Robotics & Automation Magazine - June 2015 - 80
IEEE Robotics & Automation Magazine - June 2015 - 81
IEEE Robotics & Automation Magazine - June 2015 - 82
IEEE Robotics & Automation Magazine - June 2015 - 83
IEEE Robotics & Automation Magazine - June 2015 - 84
IEEE Robotics & Automation Magazine - June 2015 - 85
IEEE Robotics & Automation Magazine - June 2015 - 86
IEEE Robotics & Automation Magazine - June 2015 - 87
IEEE Robotics & Automation Magazine - June 2015 - 88
IEEE Robotics & Automation Magazine - June 2015 - 89
IEEE Robotics & Automation Magazine - June 2015 - 90
IEEE Robotics & Automation Magazine - June 2015 - 91
IEEE Robotics & Automation Magazine - June 2015 - 92
IEEE Robotics & Automation Magazine - June 2015 - 93
IEEE Robotics & Automation Magazine - June 2015 - 94
IEEE Robotics & Automation Magazine - June 2015 - 95
IEEE Robotics & Automation Magazine - June 2015 - 96
IEEE Robotics & Automation Magazine - June 2015 - 97
IEEE Robotics & Automation Magazine - June 2015 - 98
IEEE Robotics & Automation Magazine - June 2015 - 99
IEEE Robotics & Automation Magazine - June 2015 - 100
IEEE Robotics & Automation Magazine - June 2015 - 101
IEEE Robotics & Automation Magazine - June 2015 - 102
IEEE Robotics & Automation Magazine - June 2015 - 103
IEEE Robotics & Automation Magazine - June 2015 - 104
IEEE Robotics & Automation Magazine - June 2015 - 105
IEEE Robotics & Automation Magazine - June 2015 - 106
IEEE Robotics & Automation Magazine - June 2015 - 107
IEEE Robotics & Automation Magazine - June 2015 - 108
IEEE Robotics & Automation Magazine - June 2015 - 109
IEEE Robotics & Automation Magazine - June 2015 - 110
IEEE Robotics & Automation Magazine - June 2015 - 111
IEEE Robotics & Automation Magazine - June 2015 - 112
IEEE Robotics & Automation Magazine - June 2015 - 113
IEEE Robotics & Automation Magazine - June 2015 - 114
IEEE Robotics & Automation Magazine - June 2015 - 115
IEEE Robotics & Automation Magazine - June 2015 - 116
IEEE Robotics & Automation Magazine - June 2015 - 117
IEEE Robotics & Automation Magazine - June 2015 - 118
IEEE Robotics & Automation Magazine - June 2015 - 119
IEEE Robotics & Automation Magazine - June 2015 - 120
IEEE Robotics & Automation Magazine - June 2015 - Cover3
IEEE Robotics & Automation Magazine - June 2015 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2023
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2023
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2023
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2023
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2022
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2022
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2022
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2022
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2021
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2021
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2021
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2021
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2020
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2020
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2020
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2020
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2019
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2019
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2019
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2019
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2018
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2018
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2018
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2018
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2017
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2017
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2017
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2017
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2016
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2016
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2016
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2016
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2015
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2015
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2015
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2015
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2014
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2014
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2014
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2014
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2013
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2013
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2013
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2013
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2012
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2012
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2012
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2012
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2011
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2011
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2011
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2011
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2010
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2010
https://www.nxtbookmedia.com