IEEE Robotics & Automation Magazine - June 2015 - 80
the resolution of any emergent deadlock through some realtime improvisation. Hence, in nonautomated settings, there is
no (strongly) felt need to address the deadlocking problem at a
formal level. On the other hand, the ubiquitous and highly disruptive nature of this problem was strongly manifested in the
1990s, where some attempts of that era to materialize the notions of the flexibly automated manufacturing cell and of the
lights-out factory, based on ad-hoc integrating schemes, resulted in major fiascos for the companies involved. Furthermore,
because of those past negative experiences, almost all current
attempts to employ large-scale automation in the production
and service sectors have sought to address the behavioral
problem of deadlock formation at the design level by adopting
very simple structural designs and by complementing these
structural designs with some very conservative operational
policies that seek to negate the third of the aforementioned
conditions for deadlock formation. Figure 2 exemplifies these
designs and policies by presenting a typical topology-or layout-for the MHS guide path network employed by the current semiconductor manufacturing industry. Similar
simplifying approaches to the deadlock problem have been
pursued even in presumably more sophisticated fields such as
the field of multithreaded software and parallel programming.
However, as shown in Figure 2, while being robust with respect to the resolution of the deadlock problem itself, the currently pursued approaches also substantially limit the
concurrency and flexibility of the underlying system, and, in
the end, they compromise the operational efficiencies and the
Tool Under Intrabay
Interbay
OHT/OHS
Stocker
Intrabay
Figure 2. The material-handling layout [53]-usually known as the
spine layout [58]-that is used in contemporary semiconductor
fabs. This MHS is an overhead monorail system with its guide path
network decomposed into a set of unidirectional loops: one loop
interconnecting the processing tools of each bay of the fab (i.e., the
blue intrabay loops depicted in the figure) and a central loop that
acts as the spine of the facility and supports wafer transfers among
the fab bays (i.e., the brown interbay loop in the figure). Intrabay
loops are interfaced to the interbay loop through buffering facilities
known as stockers. By maintaining a unidirectional vehicle motion
on each loop, the considered layout eliminates the potential for
deadlock formation among the traveling vehicles. But, at the same
time, vehicles tend to travel much longer distances for any single
requested transfer, they tend to file up behind the slowest vehicle,
and the interbay traffic might involve considerable double-handling
of the transported wafer cassettes at the intermediate stockers.
OHT: overhead transporter; OHS: overhead shuttle.
80
*
IEEE ROBOTICS & AUTOMATION MAGAZINE
*
June 2015
enhanced performance potential that are typically sought from
flexible automation.
It is evident from the previous discussion that the deployment of automated solutions for the aforementioned applications in a way that provides a robust and efficient operation
of the underlying system can be effectively supported only
through the development of a rigorous control paradigm that
will enable the formal modeling of the underlying system behavior and the imposed specifications and will facilitate the
thorough analysis and design of the necessary control policies. At the same time, to be practically effective, such a control paradigm must explicitly address the representational
and computational complexities of the problems investigated
and eventually effect a systematic tradeoff between the computational tractability of the developed methodology and the
operational efficiency of the obtained solutions.
The rest of this article outlines such a control paradigm that
is built on the formal abstraction of a (sequential) resource-allocation system (RAS) [47]. We provide a formal characterization
and a taxonomy of the RAS concept, outline a control paradigm that can be defined by it while leveraging and extending
existing results from various areas of modern control theory,
and, subsequently, focus on the particular problem of deadlock
avoidance-or nonblocking supervision-for the considered
RAS. For this last problem, we provide a formal characterization by means of the supervisory control theory (SCT) of discrete-event systems (DESs) [7] and establish a notion of
optimality for the derived solutions in the form of maximal
permissiveness. On the other hand, a formal complexity analysis reveals that the computation of the maximally permissive
nonblocking supervisor is an NP-hard task for most RAS instantiations. Hence, a considerable part of the article is dedicated to the endeavors of our group and the broader research
community to cope with this negative result. The article concludes with some discussion of the remaining open challenges
with respect to the RAS supervisory control problem and of all
the additional issues that must be effectively addressed for the
complete development of the presented RAS theory, its migration to the engineering practice, and its effective integration
into the relevant engineering curricula. Collectively, the presented developments epitomize the corresponding endeavors
by the author, his collaborators, and a broader group within
the relevant research community over a time span of more
than 20 years. They also reveal how some important challenges faced in the area of automation can benefit from, but also
extend and promote, foundational disciplines such as those of
control engineering, operations research, and theoretical computer science.
The RAS Modeling Abstraction, the Corresponding
Control Paradigm, and an RAS Taxonomy
The RAS Modeling Abstraction
As stated previously, the primary modeling abstraction that
enables a unifying treatment of the real-time operations taking
place in all of the applications described in the "Automation as
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