Kybernetika 48 no. 6, 1114-1135, 2012

Supervisory controller design for timed-place Petri nets

Aydın Aybar and Altuğ İftar

Abstract:

Supervisory controller design to avoid deadlock in discrete-event systems modeled by timed-place Petri nets (TPPNs) is considered. The recently introduced approach of place-stretching is utilized for this purpose. In this approach, given an original TPPN (OPN), a new TPPN, called the place-stretched Petri net (PSPN), is obtained. The PSPN has the property that its marking vector is sufficient to represent its state. By using this property, a supervisory controller design approach for TPPNs to avoid deadlock is proposed in the present work. An algorithm to determine the set of all the states of the PSPN which lead to deadlock is presented. Using this set, a controller for the PSPN is defined. Using this controller, a controller for the OPN is then obtained. Assuming that the given Petri net is bounded, the proposed approach always finds a controller in finite time whenever there exists one. Furthermore, this controller, when exists, is maximally permissive.

Keywords:

Petri nets, discrete-event systems, time-delay, supervisory control, deadlock

Classification:

93C65, 93A30, 93B03

References:

  1. H. {Apayd\i n}, A. Manay, A. Aybar and A. {\.Iftar}: A program for analysis and control of Petri nets. In: Proc. IEEE International Conference on Computational Cybernetics, Vienna 2004, pp. 309-314.   CrossRef
  2. A. Aybar and A. {\.Iftar}: Overlapping decompositions and expansions of Petri nets. IEEE Trans. Automat. Control 47 (2002), 511-515.   CrossRef
  3. A. Aybar and A. {\.I}ftar: Decentralized supervisory controller design to avoid deadlock in Petri nets. Internat. J. Control 76 (2003), 1285-1295. Also see: A. Aybar and A. \.Iftar: Corrections to decentralized supervisory controller design to avoid deadlock in Petri nets. Internat. J. Control 76 (2003), 1584.   CrossRef
  4. A. Aybar and A. {\.Iftar}: Supervisory controller design for timed Petri nets. In: Proc. IEEE International Conference on System of Systems Engineering, Los Angeles 2006, pp. 59-64.   CrossRef
  5. A. Aybar and A. {\.Iftar}: Deadlock avoidance controller design for timed Petri nets using stretching. IEEE Systems J. 2 (2008), 178-188.   CrossRef
  6. A. Aybar and A. {\.Iftar}: Decentralized structural controller design for large-scale discrete-event systems modelled by Petri nets. Kybernetika 45 (2009), 3-14.   CrossRef
  7. A. Aybar and A. {\.Iftar}: Representation of the state of timed-place Petri nets using stretching. In: Proc. 4th IFAC Workshop on Discrete-Event System Design, Playa de Gandia 2009, pp. 79-84.   CrossRef
  8. A. Aybar and A. {\.I}ftar: Supervisory controller design to enforce some basic properties in timed-transition Petri nets using stretching. Nonlinear Analysis: Hybrid Systems 6 (2012), 712-729.   CrossRef
  9. A. Aybar, A. {\.I}ftar and H. Apayd\i n-Özkan: Centralized and decentralized supervisory controller design to enforce boundedness, liveness, and reversibility in Petri nets. Internat. J. Control 78 (2005), 537-553.   CrossRef
  10. F. D. J. Bowden: A brief survey and synthesis of the roles of time in Petri nets. Math. Comput. Modelling 31 (2000), 55-68.   CrossRef
  11. C. G. Cassandras and S. Lafortune: Introduction to Discrete Event Systems. Kluwer Academic, Norwell 1999.   CrossRef
  12. M. P. Fanti, B. Maione and B. Turchiano: Comparing digraph and Petri net approaches to deadlock avoidance in FMS. IEEE Trans. Systems, Man Cybernet. - Part B, 30 (2000), 783-798.   CrossRef
  13. M. P. Fanti and M. Zhou: Deadlock control methods in automated manufacturing systems. IEEE Trans. Systems, Man, Cybernet. - Part A 34 (2004), 5-22.   CrossRef
  14. P. Freedman: Time, Petri nets, and robotics. IEEE Trans. Robotics Automat. 7 (1991), 417-433.   CrossRef
  15. A. Ghaffari, N. Rezg and X. Xie: Maximally permissive and non blocking control of Petri nets using theory of regions. In: Proc. IEEE International Conference on Robotics and Automation, Washington, D. C. 2002, pp. 1895-1900.   CrossRef
  16. A. Giua, C. Seatzu and F. Basile: Observer-based state-feedback control of timed Petri nets with deadlock recovery. IEEE Trans. Automat. Control 49 (2004), 17-29.   CrossRef
  17. C. N. Hadjicostis and G. C. Verghese: Structured redundancy for fault tolerance in state-space models and Petri nets. Kybernetika 35 (1999), 39-55.   CrossRef
  18. Z. W. Li, M. C. Zhou and N. Q. Wu: A survey and comparison of Petri net-based deadlock prevention policies for flexible manufacturing systems. IEEE Trans. Systems, Man, Cybernet. - Part C 38 (2008), 173-188.   CrossRef
  19. T. Murata: Petri nets: Properties, analysis and applications. Proc. IEEE 77 (1989), 541-580.   CrossRef
  20. S. Pinchinat and S. Riedweg: You can always compute maximally permissive controllers under partial observation when they exist. In: Proc. American Control Conference, Portland 2005, pp. 2287-2292.   CrossRef
  21. I. Rivera-Rangel, A. Ramirez-Trevino, L. I. Aguirre-Salas and J. Ruiz Leon: Geometrical characterization of observability in interpreted Petri nets. Kybernetika 41 (2005), 553-574.   CrossRef
  22. M. Uzam and M. Zhou: An iterative synthesis approach to Petri net-based deadlock prevention policy for flexible manufacturing systems. IEEE Trans. Systems, Man, Cybernet. - Part A 37 (2007), 362-371.   CrossRef
  23. N. Viswanadham, Y. Narahari and T. L. Johnson: Deadlock prevention and deadlock avoidance in flexible manufacturing systems using Petri net models. IEEE Trans. Robotics Automat. 6 (1990), 713-723.   CrossRef
  24. J. Wang: Timed Petri Nets: Theory and Application. Kluwer Academic, Boston 1998.   CrossRef
  25. M. Zhou and F. DiCesare: Petri Net Synthesis for Discrete Event Control of Manufacturing Systems. Kluwer Academic Publishers, Norwell 1993.   CrossRef
  26. W. M. Zuberek: Timed Petri nets in modeling and analysis of cluster tools. IEEE Trans. Robotics Automat. 17 (2001), 562-575.   CrossRef