IEEE Robotics & Automation Magazine - June 2015 - 83
automaton (FSA) [7], to be denoted by G (U) [47], [56]. The
state space S of this automaton consists of all of the p -dimensional nonnegative integer vectors s representing the
RAS states that are feasible with respect to the available resource capacities; that is, each component s [l] of s corresponds to a processing stage N jk / N l of U and reports the
number of process instances executing this processing stage,
while s satisfies the following constraints:
p
6i = 1, f, m, / s [l] $ A (N l) [i] # C i .
l =1
(1)
The notation A ^N l h should be interpreted as the resource-al-
location vector associated with the processing stage that corresponds to the l th component of the state vector s. We also
notice, for completeness, that the finiteness of the state set s
can be deduced from (1) and the nonzero nature of each resource-allocation vector A ^N l h .
The event set E of the FSA G (U) consists of the events
corresponding to: 1) the initiation (or loading) of a new process
instance, 2) the advancement of these process instances among
their different stages in a manner that is consistent with the
sequential logic that defines these processes, and 3) the eventual
termination (or unloading) of a process instance by its
retirement from the system and the release of all the currently
held resources. The transition function f of the FSA G (U)
formalizes the RAS dynamics that are generated by the
aforementioned events. Furthermore, f is a partial function
since the occurrence of a certain event e ! E at a given state
s ! S will be feasible only if 1) the considered state s avails of
active process instances that can execute the contemplated event
e and 2) the state sl that will result from the execution of e in s
satisfies the constraints of (1); the satisfaction of the first of these
two conditions is characterized as process enablement of event e
in state s, while the satisfaction of the second condition is
characterized as resource enablement of e in s. The initial state
s 0 of the FSA G (U) is the state s = 0, i.e., the state where U is
empty of any process instances; the same state also defines the
unique marked state of G (U), a fact that expresses the
requirement for complete process runs. Finally, in the sequel, we
shall also use the notation tf to denote the natural extension of
the state transition function f to S # E ), where E ) denotes the
set of all the finite strings of E, including the empty string f.
More specifically, for any state s ! S and the empty event
string f, tf (s, f) = s, while for any s ! S, v ! E ) and
e ! E, tf (s, ve) = f (tf (s, v), e) . (In the last formula, it is
implicitly assumed that tf (s, ve) is undefined if any of the onestep transitions that are involved in the right-hand-side
recursion are undefined.)
In the context of the modeling framework that is defined
by the FSA G (U), the feasible behavior of the RAS U is modeled by the language L (G) generated by G (U), i.e., by all
strings v ! E ) such that tf (s 0, v) is defined. On the other
hand, the desired-or, more formally, the admissible-behavior of U is modeled by the marked language L m (G) of the
FSA G (U); since the set of marked states of G (U) is the singleton containing the initial state s 0, the marked language
L m (G) consists of exactly those strings v ! L (G) that lead
back to the empty state s 0 . To facilitate the subsequent discussion, we also define the reachable subspace S r of G (U) by
S r / " s ! S: 7v ! L (G) s.t. tf (s 0, v) = s ,
(2)
and its coreachable subspace S s by
S s / " s ! S: 7v ! E ) s.t. tf (s, v) = s 0 , .
(3)
Furthermore, we shall denote the respective complements of S r
and S s with respect to S by S rr and S sr, and we shall also use the
notation S xy, x ! " r, r ,, y ! " s, sr ,, to denote the intersection of
the corresponding sets S x and S y . In the context of the RAS-related literature, state coreachability has been historically characterized as the property of state safety; hence, in the sequel, we
shall tend to refer to the state set S S as the set of safe RAS states
and, correspondingly, to the state set S Sr as the set of unsafe states.
Figure 4 provides the state transition diagram (STD) of the
reachable subspace of the FSA G (U) corresponding to the
RAS U that abstracts the qualitative dynamics of the buffer
allocation taking place in Figure 1. Furthermore, the figure
also depicts the separation of the reachable space S r into its
safe and unsafe subspaces, S rs and S rsr .
The Optimal Nonblocking Supervisor
and Its Complexity
It is easy to see from all of the definitions provided in the
previous paragraphs and the example of Figure 4 that the admissible behavior for the RAS U, characterized by the
marked language L m (G), confines the FSA G (U) exactly in
its subspace defined by S rs. In the relevant terminology of
DES theory, the subautomaton of G (U) that is induced by
the state subset S rs is known as the trim of G (U), and it can
be computed by the standard algorithms provided by qualitative DES theory. Hence, a natural way to ensure the deadlock-free operation of a given RAS U is by first computing
the trimmed subautomaton Gu (U) of the corresponding FSA
G (U) and subsequently implementing a logical controller
that allows for the occurrence of any process and resourceenabled transition in G (U) only if this transition also appears in Gu (U). In fact, such an implementation of the
necessary supervision for ensuring the deadlock-free operation of the RAS U is in line with the classical theory for the
qualitative control of DES known as Ramadge and Wonham
(R&W) SCT [42]. This implementation is also associated
with a notion of optimality since it establishes deadlock freedom while enforcing the minimal possible restriction to the
feasible behavior of the underlying RAS. From the more holistic viewpoint of the control framework of Figure 3, the
minimal restrictiveness-or, equivalently, maximal permissiveness-of the applied logical control policy should be interpreted as increased behavioral latitude for the controlled
system that can potentially lead to an enhanced performance. Furthermore, the corresponding DES theory provides additional results that characterize the minimally
June 2015
*
IEEE ROBOTICS & AUTOMATION MAGAZINE
*
83
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