Skip to main content
Log in

A Survey of Petri Net Methods for Controlled Discrete Event Systems

  • Published:
Discrete Event Dynamic Systems Aims and scope Submit manuscript

Abstract

This paper surveys recent research on the application of Petri net models to the analysis and synthesis of controllers for discrete event systems. Petri nets have been used extensively in applications such as automated manufacturing, and there exists a large body of tools for qualitative and quantitative analysis of Petri nets. The goal of Petri net research in discrete event systems is to exploit the structural properties of Petri net models in computationally efficient algorithms for computing controls. We present an overview of the various models and problems formulated in the literature focusing on two particular models, the controlled Petri nets and the labeled nets. We describe two basic approaches for controller synthesis, based on state feedback and event feedback. We also discuss two efficient techniques for the on-line computation of the control law, namely the linear integer programming approach which takes advantage of the linear structure of the Petri net state transition equation, and path-based algorithms which take advantage of the graphical structure of Petri net models. Extensions to timed models are briefly described. The paper concludes with a discussion of directions for future research.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  • Ashley, Jr., J., and Holloway, L. E. 1994. Characterizing uncontrollable reachability for colored controlled petri nets. Proceedings of 1994 IEEE International Conference on Systems, Man, and Cybernetics, San Antonio, Texas.

  • Baccelli, F., Cohen, G., Olsder, G., and Quadrat, J. P. 1992. Synchronization and Linearity: An Algebra for Discrete Event Systems. Wiley.

  • Banaszak, Z. A., and Krogh, B. H. 1990. Deadlock avoidance in flexible manufacturing systems with concurrently competing process flows. IEEE Trans. on Robotics and Automation 6(6): 724–734.

    Google Scholar 

  • Barroso, G. C., Lima, A. M. N., and Perkusich, A. 1996. Supervision of discrete event systems using Petri nets and Supervisory Control theory. Proc. of 1st Int. Workshop on Manufacturing and Petri Nets, 17th Int. Conf. on Application and Theory of Petri Nets, Osaka, Japan, pp. 77–96.

  • Berthelot, G. 1987. Transformations and decompositions of nets. Petri Nets: Central Models and Their Properties, Advances in Petri Nets 1986, (Brauer, W., Reisig, W., and Rosenberg, G. eds.) Lecture Notes in Computer Science, vol. 254-I, New York: Springer Verlag, pp. 359–376.

    Google Scholar 

  • Best, E. 1987. Structural theory of Petri nets: the free choice haitus. Lecture Notes in Computer Science, vol. 254, New York: Springer Verlag, pp. 168–206.

    Google Scholar 

  • Boel, R. K., Ben-Naoum, L., and Van Breusegem, V. 1993. On forbidden state problems for controlled closed controlled state machines. Preprints of the 12th IFAC World Congress, Vol. 4, Sidney, Australia, pp. 161–164.

    Google Scholar 

  • Boel, R. K., Ben-Naoum, L., and Van Breusegem, V. 1995. On forbidden state problems for a class of colored Petri nets. IEEE Trans. on Automatic Control 40(1): 1717–1731.

    Google Scholar 

  • Boissel, O. R., and Kantor, J. C. 1995. Optimal feedback control design for discrete-event systems using simulated annealing. Computers in Chemical Engineering 19(3): 253–266.

    Google Scholar 

  • Brandin, B. A., and Wonham, W. M. 1992. Supervisory control of timed discrete-event systems. Proc. 31st IEEE Conf. on Decision and Control, Tuscon, Arizona, pp. 3357–3362.

  • Brave, Y., and Heymann, M. 1988. Formulation and control of real-time discrete event processes. Proc. 27th IEEE Conf. on Decision and Control, Austin, Texas, pp. 1131–1132.

  • Brave, Y., and Krogh, B. H. 1993. Maximally permissive policies for controlled time marked graphs. Proc. 12th IFAC World Congress, Sydney, Australia, pp. I:263–266.

    Google Scholar 

  • Bruno, G., and Marchetto, G. 1986. Process-translatable Petri nets for the rapid prototyping of process control systems. IEEE Trans. on Software Engineering 12(2): 346–357.

    Google Scholar 

  • Cofer, D. 1995. Control and Analysis of Real-Time Discrete Event Systems. PhD thesis, Dept. of ECE, University of Texas at Austin.

  • Cofer, D., and Garg, V. K. 1995. Control of event separation times in discrete event systems. Proceedings of the 34th Conference on Decision and Control, New Orleans, LA, pp. 2005–2010.

  • Cofer, D., and Garg, V. K. 1996. Supervisory control of real-time discrete event systems using lattice theory. IEEE Transactions on Automatic Control 41(2): 199–109.

    Google Scholar 

  • Cohen, G., Moller, P., Quadrat, J.-P., and Voit, M. 1989. Algebraic tools for the performance evaluation of discrete event systems. Proceedings of the IEEE 77(1): 39–58.

    Google Scholar 

  • Colom, J. M., and Silva, M. 1991. Improving the linearly based characterization of P/T nets. Advances in Petri Nets 1990, (Rozenberg, G. ed.), Lecture Notes in Computer Science, vol. 483, New York: Springer Verlag, pp. 113–145.

    Google Scholar 

  • David, R. 1993. Petri nets & Grafcet for specification of logic controllers. Proc. 12th IFAC World Congress, Sydney, Australia, pp. III:335–340.

    Google Scholar 

  • David, R., and Alla, H. 1992. Petri Nets and Grafcet. New York: Prentice Hall.

    Google Scholar 

  • Desel, J. 1992. A proof of the rank theorem for extended free choice nets. Application and Theory of Petri Net 1992, (Jensen, K., ed.), Lecture Notes in Computer Science, vol. 616, New York: Springer Verlag, pp. 134–154.

    Google Scholar 

  • Coffman, E. G., et al. 1971. System deadlocks. Computing Surveys 3(2): 67–78.

    Google Scholar 

  • Ezpeleta, J., Colom, J. M., and Martinez, J. 1995. A Petri net based deadlock prevention policy for flexible manufacturing systems. IEEE Transactions on Robotics and Automation 11(2): 173–184.

    Google Scholar 

  • Giua, A., and DiCesare, F. 1991. Supervisory design using Petri nets. Proc. 30th IEEE Conf. on Decision and Control, Brighton, UK, pp. 92–97.

  • Giua, A., and DiCesare, F. 1994a. Blocking and controllability of Petri nets in supervisory control. IEEE Trans. on Automatic Control 39(4): 818–823.

    Google Scholar 

  • Giua, A., and DiCesare, F. 1994b. Petri net structural analysis for supervisory control. IEEE Trans. on Robotics and Automation 10(2): 185–195.

    Google Scholar 

  • Giua, A., and DiCesare, F. 1995. Decidability and closure properties of weak Petri net languages in supervisory control. IEEE Trans. on Automatic Control 40(5): 906–910.

    Google Scholar 

  • Giua, A., DiCesare, F., and Silva, M. 1992. Generalized mutual exclusion constraints on nets with uncontrollable transitions. Proc. 1992 IEEE Int. Conf. on Systems, Man, and Cybernetics, Chicago, Illinois, pp. 974–979.

  • Giua, A., DiCesare, F., and Silva, M. 1993. Petri net supervisors for generalized mutual exclusion constraints. Proc. 12th IFAC World Congress, Sidney, Australia, pp. I:267–270.

    Google Scholar 

  • Golaszewski, C. H., and Ramadge, P. J. 1988a. Discrete event processes with arbitrary controls. Advanced Computing Concepts and Techniques in Control Engineering, (Denham, M. J., and Laub, A. J., eds.), New York: Springer Verlag, pp. 459–469.

    Google Scholar 

  • Golassewaski, C. H., and Ramadge, P. J. 1988b. Mutual exclusion problems for discrete event systems with shared events. Proc. 27th IEEE Conf. on Decision and Control, Austin, Texas, pp. 234–239.

  • Hanisch, H.-M., Luder, A., and Rausch, M. 1996. Controller synthesis for net condition/event systems with incomplete state observation. Proceedings of Computer Integrated Manufacturing and Automation Technology (CIMAT'96) Conference, Grenoble, France.

  • Haoxun, C. 1994. Synthesis of feedback control logic for controlled Petri nets with forward and backward conflict-free uncontrolled subnet. In Proc. 33rd IEEE Trans. on Decision and Control, Lake Buena Vista, FL, pp. 3098–3103.

  • Haoxun, C., and Baosheng, H. 1991. Distributed control of discrete event systems described by a class of controlled Petri nets. Preprints of IFAC Int. Symp. on Distributed Intelligence Systems, Arlington, Virginia.

  • Haoxun, C., and Baosheng, H. 1993. Control of discrete event systems with their dynamics and legal behavior specified by Petri nets. Proc. 32nd IEEE Trans. on Decision and Control, San Antonio, TX, pp. 239–240.

  • Holloway, L. E. 1988. Feedback control synthesis for a class of discrete event systems using distributed state models. Laboratory for Automated Systems and Information Processing, Dept. of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA. Technical Report LASIP-88-17.

    Google Scholar 

  • Holloway, L. E. 1996. Time measures and state maintainability for a class of composed systems. Proceedings of the 1996 International Workshop on Discrete Event Systems (WODES96), Edinburgh, UK.

  • Holloway, L. E., and Krogh, B. H. 1990. Synthesis of feedback control logic for a class of controlled Petri nets. IEEE Trans. on Automatic Control 35(5): 514–523. Also appears in Discrete Event Dynamic Systems: Analyzing Complexity and Performance in the Modern World, (Ho., Y. C., ed.), New York: IEEE Press, 1992.

    Google Scholar 

  • Holloway, L. E., and Krogh, B. H. 1992. On closed-loop liveness of discrete event systems under maximally permissive control. IEEE Trans. on Automatic Control 37(5): 692–697.

    Google Scholar 

  • Holloway, L. E., Guan, X., and Zhang, L. 1996. A generalization of state avoidance policies for controlled Petri nets. IEEE Trans. on Automatic Control 41(6): 804–816.

    Google Scholar 

  • Holloway, L. E., and Hossain, F. 1992. Feedback control for sequencing specifications in controlled Petri nets. Proc. Third Int. Conf. on Computer Integrated Manufacturing, Troy, New York, pp. 242–250.

    Google Scholar 

  • Hsieh, F.-S., and Chang, S.-C. 1994. Dispatching-driven deadlock avoidance controller synthesis for flexible manufacturing systems. IEEE Transactions on Robotics and Automation 10(2): 196–209.

    Google Scholar 

  • Ichikawa, A., and Hiraishi, K. 1988. Analysis and control of discrete event systems represented by Petri nets. Discrete Event Systems: Models and Applications, (Varaiya, P., and Kurzhanski, A. B., eds.), Lecture Notes in Control and Information Sciences, vol. 103, New York: Springer Verlag, pp. 115–134.

    Google Scholar 

  • Jantzen, M. 1987a. Complexity of place/transition nets. Petri Nets: Control Models and Their Properties, Advances in Petri Nets 1986, (Reisig, W., Brauer, W., and Rozenberg, G., eds.), Lecture Notes in Computer Sciences, vol. 254-I, New York: Springer Verlag, pp. 413–434.

    Google Scholar 

  • Jantzen, M. 1987b. Language theory of Petri nets. Petri Nets: Control Models and Their Properties, Advances in Petri Nets 1986, (Reisig, W., Brauer, W., and Rosenberg, G., eds.), Lecture Notes in Computer Sciences, Vol. 254-I, Springer Verlag, New York, pp. 397–412.

    Google Scholar 

  • Jeng. M. D., and DiCesare, F. 1993. A review of synthesis techniques for petri nets with applications to automated manufacturing systems. IEEE Trans. on Systems, Man, and Cybernetics 23(1): 301–312.

    Google Scholar 

  • Jensen, K. 1995. Coloured Petri Nets. Vol. 1 & 2, Springer.

  • Johnson, J. L., and Murara, T. 1985. Structure mmatrices for Petri nets. Journal of the Franklin Institute 319(3): 299–309.

    Google Scholar 

  • Jones, N. D., Landweber, L. H., and Lien, Y. E. 1977. Complexity of some problems in Petri nets. Theoretical Computer Science 4: 277–299.

    Google Scholar 

  • Kosaraju, S. R. 1982. Decidability of reachability in vector addition systems. Proc. 14th Ann. ACM Symp. on Theory of Computing, San Francisco, California, pp. 267–281.

  • Krogh, B. H. 1987. Controlled Petri nets and maximally permissive feedback logic. Proc. 25th Annual Allerton Conference, University of Illinois, Urbana, pp. 317–326.

    Google Scholar 

  • Krogh, B. H., and Holloway, L. E. 1991. Synthesis of feedback control logic for discrete manufacturing systems. Automatica 27(4): 641–651.

    Google Scholar 

  • Krogh, B. H., Magott, J., and Holloway, L. E. 1991. On the complexity of forbidden state problems for controlled marked graphs. Proc. 30th IEEE Conf. on Decision and Control, Brighton, UK, pp. 85–91.

  • Kumar, R., and Holloway, L. D. 1996. Supervisory control of deterministic Petri nets with regular specification languages. IEEE Trans. on Automatic Control 41(2): 245–249.

    Google Scholar 

  • Lafortune, S., and Yoo, H. 1991. Some results on Petri net languages. IEEE Trans. on Automatic Control 35(4): 482–485.

    Google Scholar 

  • Lewis, F. L., Pastravanu, O. C., and Huang, H.-H. 1993. Controller design and conflict resolution in discrete event manufacturing systems. Proc. 32nd IEEE Conf. on Decision and Control, IEEE Control Systems Society, pp. 3288–3293.

  • Li, Y., 1991. Control of Vector Discrete-Event Systems. PhD thesis, Systems and Control Group, Department of Electrical Engineering, University of Toronto, Toronto, Ontario.

    Google Scholar 

  • Li, Y., and Wonham, W. M. 1993. Control of vector discrete-event systesm I—the base model. IEEE Trans. on Automatic Control 38(8): 1214–1227.

    Google Scholar 

  • Li, Y., and Wonham, W. M. 1994. Control of vector discrete-event systesm II—controller synthesis. IEEE Trans. on Automatic Control 39(3): 512–531.

    Google Scholar 

  • Li, Y., and Wonham, W. M. 1995. Concurrent vector discrete-event systems. IEEE Trans. on Automatic Control 40(4): 628–638.

    Google Scholar 

  • Makungu, M., Barbeau, M., and St-Denis, R. 1994. Synthesis of controllers with colored Petri nets. Proc. 32nd Annual Allerton Conference, University of Illinois, Urbana, pp. 709–718.

    Google Scholar 

  • Mayr, E. W. 1984. An algorithm for the general Petri net reachability problem. SIAM J. of Computing 13(3): 441–460.

    Google Scholar 

  • McCarragher, B. J., and Asada, H. 1995. The discrete event modeling and trajectory planning of robitic assembly tasks. Transactions of the ASME—Journal of Dynamic Systems, Measurement, and Control 117(3): 394–400.

    Google Scholar 

  • Memmi, G., and Roucairol, G. 1980. Linear algebra in net theory. Lecture Notes in Computer Science, vol. 84, Springer, pp. 213–223.

  • Moody, J. O., and Antsaklis, P. J. 1995. Petri net supervisors for des in the presence of uncontrollable and unobservable transitions. Proceedings of 33rd Annual Allerton Conference on Communications, Control, and Computing, Monticello, IL.

  • Moody, J. O., Yamalidou, K., Lemmon, M. D., and Antsaklis, P. J. 1994. Feedback control of Petri nets based on place invariants. Proc. 33rd IEEE Conf. on Decision and Control, Lake Buena Vista, Florida, pp. 3104–3109.

    Google Scholar 

  • Moody, J. O., Antsaklis, P. J., and Lemmon, M. D. 1996. Petri net feedback controller design for a manufacturing system. Proceedings of IFAC World Congress 1996, vol. B, San Francisco: Pergamon/Elsvier Science Limited, pp. 67–72.

    Google Scholar 

  • Murata, T. 1977. State equation, controllability and maximal matching of Petri nets. IEEE Trans. on Automatic Control AC-22(3): 412–415.

    Google Scholar 

  • Murata, T. 1989. Petri nets: Propeties, analysis and applications. Proceedings of the IEEE 77(4): 541–580.

    Google Scholar 

  • Ostroff, J. S., and Wonham, W. M. 1990. A framework for real-time discrete event control. IEEE Trans. on Automatic Control 35(4): 386–397.

    Google Scholar 

  • Pelz, E. 1987. Closure properties of deterministic Petri net languages. Proc. STACS 1987, Lecture Notes in Computer Sciences, vol. 247, New York: Springer Verlag, pp. 373–382.

    Google Scholar 

  • Peterson, J. L. 1981. Petri Net Theory and the Modeling of Systems. Englewood Cliffs, NJ: Prentice-Hall.

    Google Scholar 

  • Ramadge, P. J. 1989. Some tractable supervisory control problems for discrete-event systems modeled by buchi automata. IEEE Trans. on Automatic Control 34(1): 10–19.

    Google Scholar 

  • Ramadge, P. J., and Wonham, W. M. 1987a. Modular feedback logic for discrete-event systems. SIAM J. of Control and Optimization 25(5): 1202–1218.

    Google Scholar 

  • Ramadge, P. J., and Wonham, W. M. 1987b. Supervisory control of a class of discrete-event processes. SIAM J. of Control and Optimization 25(1): 206–230.

    Google Scholar 

  • Ramadge, P. J., and Wonham, W. M. 1989. The control of discrete event systems. Proceedings of IEEE 77(1): 81–98.

    Google Scholar 

  • Reisig, W. 1982. Petri nets. Monographs on Theoretical Computer Science. New York: Springer Verlag.

    Google Scholar 

  • Reutenauer, C. 1990. The Mathematics of Petri Nets. Masson and Prentice-Hall.

  • Sathaye, A. S., and Krogh, B. H. Synthesis of real-time supervisors for controlled time Petri nets. Proc. 32nd IEEE Conf. on Decision and Control, vol. 1, San Antonio, pp. 235–238.

  • Sifakas, J. 1980. Deadlocks and livelocks in transition systems. Mathematical Foundations of Computer Science 88: 587–600.

    Google Scholar 

  • Sifakis, J. 1978. Structural properties of Petri nets. Mathematical Foundations of Computer Science, (Winkowski, J., ed.), Springer, pp. 474–483.

  • Smedinga, R. 1988. Using trace theory to model discrete event systems. Discrete Event Systems: Models and Applications, (Varaiya, P., and Kurzhanski, A. B., eds.), Lecture Notes in Control and Information Sciences, New York: Springer Verlag, pp. 81–99.

    Google Scholar 

  • Sreenivas, R. S. 1993a. A note on deciding the controllability of a language K with respect to a language L. IEEE Trans. on Automatic Control 38(4): 658–662.

    Google Scholar 

  • Sreenivas, R. S. 1993b. On a weaker notion of controllability of a language K with respect to language L. IEEE Trans. on Automatic Control 38(9): 1446–1447.

    Google Scholar 

  • Sreenivas, R. S. 1996. Enforcing liveness via supervisors control in discrete event dynamic systems modeled by completely controlled petri nets. IEEE Transactions on Automatic Control, submitted.

  • Sreenivas, R. S., and Krogh, B. H. 1992. On Petri net models of infinite state supervisory. IEEE Trans. on Automatic Control 37(2): 274–277.

    Google Scholar 

  • Stiver, J. A., and Antsaklis, P. J. 1993. On the controllability of hybrid control systems. Proc. 32nd IEEE Conf. on Decision and Control, IEEE Control Systems Society, pp. 294–299.

  • Suziki, I., and Murara, T. 1983. A method for stepwise refinement and abstraction of Petri nets. Journal of Computer and System Sciences 27(1): 51–76.

    Google Scholar 

  • Takae, A., Takai, S., Ushio, T., Kumagai, S., and Kodama, S. 1996. Maximally permissive controllers for controlled time Petri nets. Proceedings 33rd Conf. on Decision and Control, Lake Buena Vista, FL, pp. 1058–1059.

  • Takai, S., Ushio, T., and Kodama, S. 1994. Concurrency and maximally permissive feedback in Petri nets with external input places. International Journal of Control 60(4): 617–629.

    Google Scholar 

  • Ushio, T. 1989. On the controllability of controlled Petri nets. Control-Theory and Advanced Technology 5(3): 265–275.

    Google Scholar 

  • Ushio, T. 1990. Maximally permissive feedback and modular control synthesis in Petri nets with external input places. IEEE Trans. on Automatic Control 35(7): 844–848.

    Google Scholar 

  • Ushio, T., and Matsumoto, R. 1988. State feedback and modular control synthesis in controlled Petri nets. Proc. 27th IEEE Conf. on Decision and Control, Austin, Texas, pp. 1502–1507.

  • Valette, R. 1983. A petri net based programmable logic controller. Computer Applications in Production and Engineering (CAPE '83), (Warman, E. A., ed.), North-Holland Publishing, pp. 103–116.

  • Viswanadham, N., Narahari, Y., and Johnson, T. L. 1990. Deadlock prevention and deadlock avoidance in flexible manufacturing systems using petri net models. IEEE Trans. on Robotics and Automation 6(6): 713–722.

    Google Scholar 

  • Wang, F. Y. 1992. Supervisory control for concurrent discrete event dynamic systems based on Petri nets. Proc. 31st IEEE Conf. on Decision and Control, Tuscon, Arizona, pp. 1196–1197.

  • Wang, H. 1993. Trace model for concurrent DEDS. Proc. 12th IFAC World Congress, Sidney, Australia, pp. V:1–4.

    Google Scholar 

  • Watson, J. F., and Derochers, A. A. 1994. State-spae size estimation of Petri nets: a bottom-up perspective. IEEE Trans. on Robotics and Automation 10(4): 555–561.

    Google Scholar 

  • Wong-Toi, H., and Hoffmann, G. 1991. The control of dense real-time discrete event systems. Proc. 30th IEEE Conf. on Decision and Control, Brighton, UK, pp. 1527–1528.

  • Wonham, W. M, and Ramadge, P. J. 1987. On the supremal controllable sublanguage of a given language. SIAM J. on Control and Optimization 25(3): 637–659.

    Google Scholar 

  • Xing, K.-Y., Hu, B.-S., and Chen, H.-X. 1996. Deadlock avoidance policy for Petri-net modeling of flexible manufacturing systems with shared resources. IEEE Transactions on Automatic Control 41(2): 289–295.

    Google Scholar 

  • Xing, K.-Y., Li, J. M., Hu, B. S. 1996. A new method for synthexizing state avoidance policies for controlled petri nets. Proceedings of IFAC World Congress 1996, vol. J, San Francisco: Pergamon/Elsevier Science Limited, pp. 377–382.

    Google Scholar 

  • Yamalidou, K., Moody, J., Lemmon, M., and Antsaklis, P. 1996. Feedback control of petri nets based on place invariants. Automatica 32(1): 15–28.

    Google Scholar 

  • Zhou, M. C., and DiCesare, F. 1993. Petri Net Synthesis for Discrete Event Control of Manufacturing Systems. Kluwer.

  • Zhou, M. C., DiCesare, F., and Desrochers, A. 1992. Hybrid methodology for the synthesis of Petri nets models for manufacturing systems. IEEE Trans. on Robotics and Automation 8(3): 350–361.

    Google Scholar 

  • Zhou, M. C., DiCesare, F., and Rudolph, D. L. 1992. Design and implementation of a petri net based supervisor for a flexible manufacturing system. Automatica 28(6): 1199–1208.

    Google Scholar 

  • Zurawski, R., and Zhou, M. 1994. Petri nets and industrial applications: a tutorial. IEEE Trans. on Industrial Electronics 41(6): 576–583.

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints and permissions

About this article

Cite this article

Holloway, L.E., Krogh, B.H. & Giua, A. A Survey of Petri Net Methods for Controlled Discrete Event Systems. Discrete Event Dynamic Systems 7, 151–190 (1997). https://doi.org/10.1023/A:1008271916548

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1008271916548

Navigation