IEEE Robotics & Automation Magazine - June 2015 - 93

among the various threads of a multithreaded software. Recently, the work in [22] and [21] sought to extend the basic
PN-based representation of the considered RAS to address
time-related constraints.
But the primary open challenge for the effective complementation of the RAS control framework that has been delineated in
this article is the effective and efficient resolution of the RAS
performance control problem. Any pertinent solution to this
new RAS control problem must integrate all of the existing results of the corresponding logical control theory and
remain computationally tractable. It must also account for all of
the stochasticities that are encountered in the underlying application domains and remain robust to these stochasticities.
Chapter 6 of [47] shows how (some variations of) the resulting
scheduling problem can be formulated, in principle, using the
fundamental modeling frameworks of Markov decision processes (MDP) and stochastic dynamic programming (DP) [3].
This analysis has also shown how the operating logic of the applied DAP can be effectively integrated in the problem formulation, and the synergies that are developed by this integration,
since the resulting MDP problem belongs to an MDP subclass
with a rich theory and powerful solution algorithms. But it is
also true that the enumerative nature of the optimal MDP/
scheduling policy with respect to the underlying state space renders challenging (usually intractable) even the description of
such a policy, let alone its computation. A solution to these computational challenges can be pursued in the context of the rather
fledgling area of approximate DP (ADP) [4], [41]. ADP has
shown significant potential for providing powerful and structured approximations to the optimal policy in many DP applications, but, at the same time, the effective customization of the
more generic ideas offered by this theory to a particular application context require substantial methodological as well as contextual insights and extensive tuning through empirical
experimentation. Some very recent developments that seek to
customize a version of the current ADP theory to the aforementioned RAS scheduling problem, and seem to hold particular
promise regarding their ability to provide an effective balance
between the computational tractability and the operational efficiency of the derived solutions, are presented in [31]. But definitely much more work is needed in this particular direction.
Finally, as the presented RAS theory grows and strengthens
its methodology along the lines indicated in the previous paragraphs, additional efforts must be made toward the development of the human capital and of the technological and
computational base that will enable the constructive migration
of this theory to the future engineering practice. This endeavor
certainly involves the eventual undertaking of some pilot largescale applications that will highlight the technical strength of
the theory and the competitive advantage that can be supported by it. But even more importantly, it must also seek the effective integration of the existing and the emerging results into
the relevant engineering curricula, and the organization of
these results in a series of computational platforms that will
enable their robust and expedient utilization by the field engineers. In fact, this last activity can be part of a broader initiative

concerning the further promotion of DES theory and of the
emerging formal methods in the engineering curriculum and
practice. It is expected that, collectively, all of these endeavors
will define a spectrum of fundamental developments and
trends with profound and transformative repercussions for the
related fields of control and automation engineering.
Acknowledgment
This article is based on a tutorial on RAS theory that I offered
while visiting the Automation group at the Chalmers University of Technology. I would like to thank the group for the
hospitality and constructive discussions that I enjoyed during
my visit.
References
[1] T. Araki, Y. Sugiyama, and T. Kasami, "Complexity of the deadlock avoidance problem," in Proc. 2nd IBM Symp. Mathematical Foundations Computer
Science, 1977, pp. 229-257.
[2] Z. A. Banaszak and B. H. Krogh, "Deadlock avoidance in flexible manufacturing systems with concurrently competing process flows," IEEE Trans.
Robot. Automat., vol. 6, no. 6, pp. 724-734, 1990.
[3] D. P. Bertsekas, Dynamic Programming and Optimal Control, vol. 2. Belmont, MA: Athena Scientific, 1995.
[4] D. P. Bertsekas and J. N. Tsitsiklis, Neuro-Dynamic Programming. Belmont,
MA: Athena Scientific, 1996.
[5] P. Brass, Advanced Data Structures. Cambridge, U.K.: Cambridge Univ.Press, 2008.
[6] R. E. Bryant, "Symbolic boolean manipulation with ordered binary-decision diagrams," ACM Comput. Surv., vol. 24, no. 3, pp. 293-318, 1992.
[7] C. G. Cassandras and S. Lafortune, Introduction to Discrete Event Systems,
2nd ed. New York: Springer, 2008.
[8] F. Chu and X.-L. Xie, "Deadlock analysis of Petri nets using siphons and mathematical programming," IEEE Trans. Robot. Automat., vol. 13, no. 6, pp. 793-804, 1997.
[9] E. M. Clarke Jr., O. Grumberg, and D. A. Peled, Model Checking. Cambridge, MA: The MIT Press, 1999.
[10] H. M. Deitel, Operating Systems. Reading, MA: Addison Wesley, 1990.
[11] L. E. Dickson, "Finiteness of the odd perfect and primitive abundant numbers
with n distinct prime factors," Amer. J. Math., vol. 35, no. 4, pp. 413-422, 1913.
[12] E. W. Dijkstra, "Cooperating sequential processes," Technological Univ.,
Eindhoven, The Netherlands, 1965.
[13] J. Ezpeleta, J. M. Colom, and J. Martinez, "A Petri net based deadlock prevention policy for flexible manufacturing systems," IEEE Trans. Robot. Automat., vol. 11, no. 2, pp. 173-184, 1995.
[14] J. Ezpeleta, F. Tricas, F. Garcia-Valles, and J. M. Colom, "A Banker's solution for deadlock avoidance in FMS with flexible routing and multiresource
states," IEEE Trans. Robot. Automat., vol. 18, no. 4, pp. 621-625, 2002.
[15] M. P. Fanti, B. Maione, S. Mascolo, and B. Turchiano, "Event-based feedback control for deadlock avoidance in flexible production systems," IEEE
Trans. Robot. Automat., vol. 13, no. 3, pp. 347-363, 1997.
[16] M. P. Fanti, B. Maione, and B. Turchiano, "Event control for deadlock avoidance in production systems with multiple capacity resources," Stud. Inform. Control, vol. 7, pp. 343-364, 1998.
[17] Z. Fei, "Symbolic supervisory control of resource allocation systems," Ph.D. thesis, Signals and Systems Dept., Chalmers Univ. Technol., Gothenburg, Sweden, 2014.
[18] A. Giua, F. DiCesare, and M. Silva, "Generalized mutual exclusion constraints on nets with uncontrollable transitions," in Proc. Int. Conf. Systems,
Man Cybernetics, 1992, pp. 974-979.

June 2015

IEEE ROBOTICS & AUTOMATION MAGAZINE

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