IEEE Robotics & Automation Magazine - June 2015 - 86
The PK-DAPs that are currently available can address arbitrary resource allocation (i.e., conjunctive RAS in the taxonomy
of Table 1), but, in terms of the process-defining logic, they primarily support process types that evolve as atomic entities
throughout their execution. Besides Banker's algorithm, some
of the best-known policies of this type can be found in [2], [13],
[25], [26], [28], and [40]. In general, it can be argued that the
identification of a pertinent property P that can lead to a correct PK-DAP is more of an art. On the other hand, in the case
of RASs with no cyclic behavior in their process types, formal
correctness proofs for PK-DAPs, defined by a certain property
P, can be structured as an inductive argument that establishes:
1) the satisfaction of property P by the initial state s 0 and 2) the
existence of policy-admissible transitions for every RAS state s
that satisfies property P. Furthermore, in the "Coping with the
RAS Deadlock in the Petri Net Modeling Framework" section,
we discuss a methodology that automates the correctness evaluation of tentative PK-DAPs for RASs with no cyclic behavior
in their process types by means of certain tests that take the
form of a mathematical programming formulation.
Closing this discussion on PK-DAPs for the considered
RAS, we also notice that the disjunction of a set of properties
P1, ..., Pl defining correct PK-DAPs for a given RAS U, is
another correct PK-DAP for U as long as the number of the
employed properties, l, is polynomially related to the RAS
size |U|. The subspace of S rs that is admitted by this new disjunctive policy is the union of the subspaces of S rs that are
admitted by the constituent policies. Hence, by utilizing a set
of PK-DAPs for a given RAS, one can obtain a tighter
(under) approximation of the maximally permissive DAP.
The significance of this remark is further increased by the
fact that some available PK-DAPs are defined through the
imposition of some arbitrary ordering on the underlying resource set, with different resource orders leading to the admissibility of different parts of the underlying state space. For
a comprehensive discussion on the existing set of PK-DAPs
and the systematic exploitation of all of the aforementioned
possibilities, the reader is directed to [47, Chs. 4 and 5].
RAS Admitting Optimal Nonblocking
Supervision of Polynomial Complexity
A second typical reaction to an NP-completeness or NP-hardness result is the quest for a special structure of practical interest
that can lead to polynomial-complexity solutions for the problem at hand. In fact, the seminal works in [1] and [19], which
established the first NP-completeness results for the problem of
the RAS state safety, also discussed certain conditions on the sequences of the resource-allocation requests posed by the RAS
process types that would lead to a safety assessment of polynomial complexity with respect to the size of the underlying RAS.
Generally speaking, these conditions imply the existence of easily identifiable transition sequences leading to a monotonic increase of the pool of free resources in the RAS behavioral space
G (U), which, as in the case of the ordered RAS states, further
enables a greedy search for a transition sequence that will terminate all of the active process instances.
86
*
IEEE ROBOTICS & AUTOMATION MAGAZINE
*
June 2015
A more recent line of results leading to polynomialcomplexity implementations of the maximally permissive
DAP for certain RAS classes of the taxonomy of Table 1 is
based on the essential differentiation between the notions of
an unsafe state and a deadlock. We remind the reader that, in
the considered RAS context, a deadlock has been defined as
an RAS state containing a subset of active process instances
that block each other in a circular manner since each of them
holds resources requested by some other processes in the set
to advance to their next processing stages. On the other hand,
the set of unsafe states of a given RAS contains all of its deadlock states but might also contain a subset of states that do not
contain any deadlocked processes; such an unsafe state is exemplified by state q 15 in the STD of Figure 4. Unsafe states
containing no deadlocked processes are characterized as
deadlock-free unsafe states. The realization of the existence of
deadlock-free unsafe states becomes essential for the complexity analysis of the considered RAS when noticing that, for
most of the RAS classes of the taxonomy of Table 1, the detection of a deadlock state is a task of polynomial complexity
with respect to the underlying RAS size; this result is especially true for the class of disjunctive/conjunctive RAS, and a relevant deadlock detection algorithm is presented in [47].
Hence, it can be inferred that, for the aforementioned RAS
class, the NP-completeness of state safety is due to the presence of deadlock-free unsafe states. On the other hand, if it
could be established that, for certain subclasses of this RAS
class, there are no deadlock-free unsafe states, then the test for
state safety could be effectively substituted by the corresponding test for deadlock, and assessing the state safety would become a task of polynomial complexity with respect to the
corresponding RAS size. Indeed, such results are available for
certain subclasses of the disjunctive/single-unit RAS that are
defined by easily testable conditions on the RAS structure. A
more concrete example, and one of the first results of this type
appearing in the literature, is stated in [49] and establishes the
absence of deadlock-free unsafe states for any disjunctive/single-unit RAS where every resource has at least two units of capacity and the RAS process types exhibit no internal cycling.
From a more practical standpoint, this result implies that the
problem of establishing deadlock-free buffer allocation in
flexibly automated production cells, exemplified in Figure 1,
is an easy problem as long as every workstation has a buffer
with at least two slots. Also, the more recent work in [50] has
exploited the aforementioned result to develop an asynchronous, distributed coordination protocol able to ensure collision-free and nonblocking traffic for the systems of the
free-ranging mobile agents that were described in the "Automation as a Resource Allocation Function: A Set of Motivating Applications" section. Furthermore, the works in [15] and
[16] have further established that the aforementioned requirement for nonunit resource capacities must be satisfied only by
a critical subset of the resource types of the considered disjunctive/single-unit RASs, while additional extensions of all of
these results are developed in [29]. A comprehensive treatment of the topic of RASs admitting maximally permissive
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