1932

Abstract

This article begins with an introduction to the modeling of discrete event systems, a class of dynamical systems with discrete states and event-driven dynamics. It then focuses on logical discrete event models, primarily automata, and reviews observation and control problems and their solution methodologies. Specifically, it discusses diagnosability and opacity in the context of partially observed discrete event systems. It then discusses supervisory control for both fully and partially observed systems. The emphasis is on presenting fundamental results first, followed by a discussion of current research directions.

Loading

Article metrics loading...

/content/journals/10.1146/annurev-control-053018-023659
2019-05-03
2024-06-25
Loading full text...

Full text loading...

/deliver/fulltext/control/2/1/annurev-control-053018-023659.html?itemId=/content/journals/10.1146/annurev-control-053018-023659&mimeType=html&fmt=ahah

Literature Cited

  1. 1.  Cassandras CG, Lafortune S 2008. Introduction to Discrete Event Systems New York: Springer. 2nd ed.
    [Google Scholar]
  2. 2.  Seatzu C, Silva M, van Schuppen J, eds 2013. Control of Discrete Event Systems: Automata and Petri Net Perspectives London: Springer
    [Google Scholar]
  3. 3.  Baier C, Katoen JP 2008. Principles of Model Checking Cambridge, MA: MIT Press
    [Google Scholar]
  4. 4.  Belta C, Yordanov B, Gol EA 2017. Formal Methods for Discrete-Time Dynamical Systems Cham, Switz.: Springer
    [Google Scholar]
  5. 5.  Tabuada P 2009. Verification and Control of Hybrid Systems: A Symbolic Approach Dordrecht, Neth.: Springer
    [Google Scholar]
  6. 6.  Murata T 1989. Petri nets: properties, analysis and applications. Proc. IEEE 77:541–80
    [Google Scholar]
  7. 7.  Giua A, Silva M 2018. Petri nets and automatic control: a historical perspective. Annu. Rev. Control 45:223–39
    [Google Scholar]
  8. 8.  Alur R, Dill DL 1994. A theory of timed automata. Theor. Comput. Sci. 126:183–235
    [Google Scholar]
  9. 9.  Sampath M, Sengupta R, Lafortune S, Sinnamohideen K, Teneketzis D 1995. Diagnosability of discrete event systems. IEEE Trans. Autom. Control 40:1555–75
    [Google Scholar]
  10. 10.  Zaytoon J, Lafortune S 2013. Overview of fault diagnosis methods for discrete event systems. Annu. Rev. Control 37:308–20
    [Google Scholar]
  11. 11.  Lafortune S, Lin F, Hadjicostis C 2018. On the history of diagnosability and opacity in discrete event systems. Annu. Rev. Control 45:257–66
    [Google Scholar]
  12. 12.  Sears D, Rudie K 2016. Minimal sensor activation and minimal communication in discrete-event systems. Discrete Event Dyn. Syst. Theory Appl. 26:295–349
    [Google Scholar]
  13. 13.  Cabasino MP, Giua A, Seatzu C 2010. Fault detection for discrete event systems using Petri nets with unobservable transitions. Automatica 46:1531–39
    [Google Scholar]
  14. 14.  Cabasino MP, Giua A, Lafortune S, Seatzu C 2012. A new approach for diagnosability analysis of Petri nets using verifier nets. IEEE Trans. Autom. Control 57:3104–17
    [Google Scholar]
  15. 15.  Cabasino MP, Giua A, Hadjicostis CN, Seatzu C 2015. Fault model identification and synthesis in Petri nets. Discrete Event Dyn. Syst. Theory Appl. 25:419–40
    [Google Scholar]
  16. 16.  Thorsley D, Teneketzis D 2005. Diagnosability of stochastic discrete-event systems. IEEE Trans. Autom. Control 50:476–92
    [Google Scholar]
  17. 17.  Bertrand N, Fabre E, Haar S, Haddad S, Hélouët L 2014. Active diagnosis for probabilistic systems. Foundations of Software Science and Computation StructuresA Muscholl 2942 Berlin: Springer
    [Google Scholar]
  18. 18.  Chen J, Keroglou C, Hadjicostis CN, Kumar R 2018. Revised test for stochastic diagnosability of discrete-event systems. IEEE Trans. Autom. Sci. Eng. 15:404–8
    [Google Scholar]
  19. 19.  Saboori A, Hadjicostis CN 2007. Notions of security and opacity in discrete event systems. 46th IEEE Conference on Decision and Control505661 New York: IEEE
    [Google Scholar]
  20. 20.  Lin F 2011. Opacity of discrete event systems and its applications. Automatica 47:496–503
    [Google Scholar]
  21. 21.  Jacob R, Lesage JJ, Faure JM 2016. Overview of discrete event systems opacity: models, validation, and quantification. Annu. Rev. Control 41:135–46
    [Google Scholar]
  22. 22.  Ramadge PJ, Wonham WM 1987. Supervisory control of a class of discrete event processes. SIAM J. Control Optim. 25:206–30
    [Google Scholar]
  23. 23.  Wonham WM, Ramadge PJ 1987. On the supremal controllable sublanguage of a given language. SIAM J. Control Optim. 25:637–59
    [Google Scholar]
  24. 24.  Ramadge PJ, Wonham WM 1989. The control of discrete event systems. Proc. IEEE 77:81–98
    [Google Scholar]
  25. 25.  Wonham WM, Cai K, Rudie K 2018. Supervisory control of discrete-event systems: a brief history. Annu. Rev. Control 45:250–56
    [Google Scholar]
  26. 26.  Moor T, Schmidt K, Perk S 2010. Applied supervisory control for a flexible manufacturing system. 10th IFAC Workshop on Discrete Event Systems25358 IFAC Proc 4312 Amsterdam: Elsevier
    [Google Scholar]
  27. 27.  Forschelen STJ, van de Mortel-Fronczak JM, Su R, Rooda JE 2012. Application of supervisory control theory to theme park vehicles. Discrete Event Dyn. Syst. Theory Appl. 22:511–40
    [Google Scholar]
  28. 28.  Liao H, Wang Y, Stanley J, Lafortune S, Reveliotis S et al. 2013. Eliminating concurrency bugs in multithreaded software: a new approach based on discrete-event control. IEEE Trans. Control Syst. Technol. 21:2067–82
    [Google Scholar]
  29. 29.  Theunissen RJM, Petreczky M, Schiffelers RRH, van Beek DA, Rooda JE 2014. Application of supervisory control synthesis to a patient support table of a magnetic resonance imaging scanner. IEEE Trans. Autom. Sci. Eng. 11:20–32
    [Google Scholar]
  30. 30.  Rawlings BC, Christenson B, Wassick JM, Ydstie BE 2014. Supervisor synthesis to satisfy safety and reachability requirements in chemical process control. 12th IFAC International Workshop on Discrete Event Systems195200 IFAC Proc 472 Amsterdam: Elsevier
    [Google Scholar]
  31. 31.  Atampore F, Dingel J, Rudie K 2016. Automated service composition via supervisory control theory. 2016 13th International Workshop on Discrete Event Systems (WODES)2835 New York: IEEE
    [Google Scholar]
  32. 32.  Reijnen FFH, Goorden MA, van de Mortel-Fronczak JM, Rooda JE 2017. Supervisory control synthesis for a waterway lock. 2017 IEEE Conference on Control Technology and Applications (CCTA)156263 New York: IEEE
    [Google Scholar]
  33. 33.  Moody J, Antsaklis P 1998. Supervisory Control of Discrete Event Systems Using Petri Nets Boston: Kluwer Acad.
    [Google Scholar]
  34. 34.  Iordache MV, Antsaklis PJ 2006. Supervisory Control of Concurrent Systems: A Petri Net Structural Approach Boston: Birkhäuser
    [Google Scholar]
  35. 35.  Ehlers R 2013.Symmetric and efficient synthesis PhD Thesis Saarland Univ., Saarbrücken, Ger.
  36. 36.  Liu J, Ozay N, Topcu U, Murray R 2013. Synthesis of reactive switching protocols from temporal logic specifications. IEEE Trans. Autom. Control 58:1771–85
    [Google Scholar]
  37. 37.  Kress-Gazit H, Lahijanian M, Raman V 2018. Synthesis for robots: guarantees and feedback for robot behavior. Annu. Rev. Control Robot. Auton. Syst. 1:211–36
    [Google Scholar]
  38. 38.  Alur R, Henzinger TA, Lafferriere G, Pappas GJ 2000. Discrete abstractions of hybrid systems. Proc. IEEE 88:971–84
    [Google Scholar]
  39. 39.  Ehlers R, Lafortune S, Tripakis S, Vardi MY 2017. Supervisory control and reactive synthesis: a comparative introduction. Discrete Event Dyn. Syst. Theory Appl. 27:209–60
    [Google Scholar]
  40. 40.  Schmuck AK, Moor T, Majumdar R 2018. On the relation between reactive synthesis and supervisory control of input/output behaviours. 14th IFAC Workshop on Discrete Event Systems G De Tommasi 3138 IFAC-PapersOnLine 517 Amsterdam: Elsevier
    [Google Scholar]
  41. 41.  Leduc RJ, Brandin BA, Lawford M, Wonham WM 2005. Hierarchical interface-based supervisory control—part I: serial case. IEEE Trans. Autom. Control 50:1322–35
    [Google Scholar]
  42. 42.  Flordal H, Malik R, Fabian M, Åkesson K 2007. Compositional synthesis of maximally permissive supervisors using supervision equivalence. Discrete Event Dyn. Syst. Theory Appl. 17:475–504
    [Google Scholar]
  43. 43.  Feng L, Wonham WM 2008. Supervisory control architecture for discrete-event systems. IEEE Trans. Autom. Control 53:1449–61
    [Google Scholar]
  44. 44.  Schmidt K, Moor T, Perk S 2008. Nonblocking hierarchical control of decentralized discrete event systems. IEEE Trans. Autom. Control 53:2252–65
    [Google Scholar]
  45. 45.  Hill RC, Tilbury DM, Lafortune S 2010. Modular supervisory control with equivalence-based abstraction and covering-based conflict resolution. Discrete Event Dyn. Syst. Theory Appl. 20:139–85
    [Google Scholar]
  46. 46.  Su R, van Schuppen JH, Rooda JE 2010. Aggregative synthesis of distributed supervisors based on automaton abstraction. IEEE Trans. Autom. Control 55:1627–40
    [Google Scholar]
  47. 47.  Gummadi R, Singh N, Sreenivas RS 2011. On tractable instances of modular supervisory control. IEEE Trans. Autom. Control 56:1621–35
    [Google Scholar]
  48. 48.  Komenda J, Masopust T, van Schuppen JH 2012. Supervisory control synthesis of discrete-event systems using a coordination scheme. Automatica 48:247–54
    [Google Scholar]
  49. 49.  Mohajerani S, Malik R, Fabian M 2014. A framework for compositional synthesis of modular nonblocking supervisors. IEEE Trans. Autom. Control 59:150–62
    [Google Scholar]
  50. 50.  Nazeem A, Reveliotis S, Wang Y, Lafortune S 2011. Designing compact and maximally permissive deadlock avoidance policies for complex resource allocation systems through classification theory: the linear case. IEEE Trans. Autom. Control 56:1818–33
    [Google Scholar]
  51. 51.  Nazeem A, Reveliotis S 2012. Designing compact and maximally permissive deadlock avoidance policies for complex resource allocation systems through classification theory: the nonlinear case. IEEE Trans. Autom. Control 57:1670–84
    [Google Scholar]
  52. 52.  Bryant RE 1992. Symbolic Boolean manipulation with ordered binary-decision diagrams. ACM Comput. Surv. 24:293–318
    [Google Scholar]
  53. 53.  Fei Z, Miremadi S, Åkesson K, Lennartson B 2014. Efficient symbolic supervisor synthesis for extended finite automata. IEEE Trans. Control Syst. Technol. 22:2368–75
    [Google Scholar]
  54. 54.  Rawlings BC, Wassick JM, Ydstie BE 2017. Application of formal verification and falsification to large-scale chemical plant automation systems. Comput. Chem. Eng. 114:211–20
    [Google Scholar]
  55. 55.  Claessen K, Een N, Sheeran M, Sörensson N, Voronov A, Åkesson K 2009. SAT-solving in practice, with a tutorial example from supervisory control. Discrete Event Dyn. Syst. Theory Appl. 19:495
    [Google Scholar]
  56. 56.  Shoaei MR, Kovács L, Lennartson B 2014. Supervisory control of discrete-event systems via IC3. Hardware and Software: Verification and Testing E Yahav 25266 Berlin: Springer
    [Google Scholar]
  57. 57.  Lin F, Wonham W 1988. On observability of discrete-event systems. Inf. Sci. 44:173–98
    [Google Scholar]
  58. 58.  Cieslak R, Desclaux C, Fawaz AS, Varaiya P 1988. Supervisory control of discrete-event processes with partial observations. IEEE Trans. Autom. Control 33:249–60
    [Google Scholar]
  59. 59.  Cho H, Marcus SI 1989. On supremal languages of classes of sublanguages that arise in supervisor synthesis problems with partial observation. Math. Control Signals Syst. 2:47–69
    [Google Scholar]
  60. 60.  Hadj-Alouane NB, Lafortune S, Lin F 1996. Centralized and distributed algorithms for on-line synthesis of maximal control policies under partial observation. Discrete Event Dyn. Syst. Theory Appl. 6:379–427
    [Google Scholar]
  61. 61.  Yin X, Lafortune S 2016. Synthesis of maximally permissive supervisors for partially observed discrete event systems. IEEE Trans. Autom. Control 61:1239–54
    [Google Scholar]
  62. 62.  Cai K, Zhang R, Wonham WM 2015. Relative observability of discrete event systems and its supremal sublanguages. IEEE Trans. Autom. Control 60:659–70
    [Google Scholar]
  63. 63.  Chatterjee K, Doyen L, Henzinger TA, Raskin JF 2006. Algorithms for omega-regular games with imperfect information. Computer Science Logic Z Ésik 287302 Berlin: Springer
    [Google Scholar]
  64. 64.  Yin X, Lafortune S 2018. Synthesis of maximally permissive nonblocking supervisors for the lower bound containment problem.. IEEE Trans. Autom. Control 634435–41
    [Google Scholar]
  65. 65.  Yin X, Lafortune S 2016. A uniform approach for synthesizing property-enforcing supervisors for partially-observed discrete-event systems. IEEE Trans. Autom. Control 61:2140–54
    [Google Scholar]
  66. 66.  Sandberg H, Amin S, Johansson KH 2015. Cyberphysical security in networked control systems: an introduction to the issue. IEEE Control Syst. 35:20–23
    [Google Scholar]
  67. 67.  Farwell JP, Rohozinski R 2011. Stuxnet and the future of cyber war. Survival 53:23–40
    [Google Scholar]
  68. 68.  Chen QA, Yin Y, Feng Y, Mao ZM, Liu HX 2018. Exposing congestion attack on emerging connected vehicle based traffic signal control Paper presented at the 25th Network and Distributed System Security Symposium, San Diego, CA, Feb. 18–21 https://www.ndss-symposium.org/wp-content/uploads/2018/02/ndss2018_01B-2_Chen_paper.pdf
    [Google Scholar]
  69. 69.  Teixeira A, Pérez D, Sandberg H, Johansson KH 2012. Attack models and scenarios for networked control systems. Proceedings of the 1st International Conference on High Confidence Networked Systems5564 New York: ACM
    [Google Scholar]
  70. 70.  Han S, Pappas GJ 2018. Privacy in control and dynamical systems. Annu. Rev. Control Robot. Auton. Syst. 1:309–32
    [Google Scholar]
  71. 71.  Thorsley D, Teneketzis D 2006. Intrusion detection in controlled discrete event systems. Proceedings of the 45th IEEE Conference on Decision and Control604754 New York: IEEE:
    [Google Scholar]
  72. 72.  Wakaiki M, Tabuada P, Hespanha JP 2017. Supervisory control of discrete-event systems under attacks. arXiv:1701.00881 [cs.SY]
  73. 73.  Su R 2017. A cyber attack model with bounded sensor reading alterations. 2017 American Control Conference (ACC)32005 New York: IEEE
    [Google Scholar]
  74. 74.  Meira Góes R, Kang E, Kwong R, Lafortune S 2017. Stealthy deception attacks for cyber-physical systems. 2017 IEEE 56th Annual Conference on Decision and Control (CDC)422430 New York: IEEE
    [Google Scholar]
  75. 75.  Lima PM, Carvalho LK, Moreira MV 2018. Detectable and undetectable network attack security of cyber-physical systems. 14th IFAC Workshop on Discrete Event Systems G De Tommasi 17983 IFAC-PapersOnLine 517 Amsterdam: Elsevier
    [Google Scholar]
  76. 76.  Meira Góes R, Rawlings BC, Recker N, Willett G, Lafortune S 2018. Demonstration of indoor location privacy enforcement using obfuscation. 14th IFAC Workshop on Discrete Event Systems G De Tommasi 14551 IFAC-PapersOnLine 517 Amsterdam: Elsevier
    [Google Scholar]
/content/journals/10.1146/annurev-control-053018-023659
Loading
  • Article Type: Review Article
This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error