IEEE Robotics & Automation Magazine - June 2015 - 84

single resource R i, i = 1, f, m, the state space cardinality of
the corresponding FSA G (U) is

restrictive deadlock avoidance policy (DAP) and support its
effective computation in the form of a subautomaton of the
FSA G (U), even in the case where the underlying RAS U
exhibits uncontrollable behavior [7], [42]. Finally, all of the
necessary algorithms for the computation of the policy-encoding subautomaton Gu (U) from the original FSA G (U) are
of polynomial complexity with respect to the size of G (U),
where the latter is determined by the number of the states
and the transitions of this automaton.
However, the effective deployment of the control scheme
outlined in the previous paragraph is severely challenged by
the fact that, for most practical RAS instantiations, the size of
the FSA G (U) grows superpolynomially (actually, very) fast
with respect to the size of U. [Characteristically, we mention
that, for a single-unit RAS U, where C / max i {C i} and D
denotes the maximum number of stages supported by any

O `` C + D j j .
C
m

The quantity

`

C +D
j
C

in this expression characterizes all of the possible ways to
partition the C units of capacity of any single resource type
to the D + 1 options that are defined by its D supporting
stages and the pool of its idle units. On the other hand, the
complete expression
C +D m
` C j

q0

q1

q2

J11

J21
q15

q3
J11

J12
q5
J11 J12

J11

J13

J11 J12 J21

J12 J13
q13

J22
q7

J13

J23

J12 J21
q18

q11

J21

q6

q16

q9

q4

q8
J22 J21
q17

q10

J11 J22

J23

J21

q19
J11 J22 J21

q12
J23 J22
q14

J11 J12 J13

J23 J22 J21

Figure 4. The STD for the reachable state space of the FSA G (U) that models the buffer allocation taking place in the manufacturing cell
of Figure 1. The various RAS states are depicted graphically, with the three internal rectangles at each node representing the three work
tables corresponding to resources R 1, R 2, and R 3 and with the annotation J jk of these rectangles indicating the processing stage executed
by the process instance that is currently loaded in the corresponding worktable. On the other hand, the considered RAS model ignores the
buffering capacity of the AGV depicted in Figure 1 since this vehicle has only a facilitating role in the part transfers taking place among the
system workstations. The blue arrow pointing at the empty RAS state q 0 defines this state as the initial state for the RAS operation, while
the thick borderline of the same state indicates its marked role in the RAS dynamics modeled by G (U). The states depicted in red indicate
the unsafe region S rrs of the considered FSA. The maximally permissive nonblocking supervisor for this FSA must confine the operation
of the underlying RAS within the remaining set of (white and green) states by recognizing and preventing the transitions that cross the
boundary between the safe and unsafe subspaces; these transitions are marked by red crossings in the figure.

84

*

IEEE ROBOTICS & AUTOMATION MAGAZINE

*

June 2015
Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - June 2015
