On-line fault detection in discrete event systems by Petri nets and integer linear programming. (English) Zbl 1180.93066

Summary: The paper addresses the fault detection problem for discrete event systems in a Petri Net (PN) framework. Assuming that the structure of the PN model and the initial marking are known, faults are modelled by unobservable transitions. Moreover, we assume that there may be additional unobservable transitions associated with the system legal behaviour and that the marking reached after the firing of any transition is unknown. The proposed diagnoser works on-line: it waits for the firing of an observable transition and employs an algorithm based on the definition and solution of some integer linear programming problems to decide whether the system behaviour is normal or exhibits some possible faults. The results characterize the properties that the PN modelling the system fault behaviour has to fulfill in order to reduce the on-line computational effort.


93C65 Discrete event control/observation systems
90C10 Integer programming
90B25 Reliability, availability, maintenance, inspection in operations research


Full Text: DOI


[1] Basile, F.; Chiacchio, P.; De Tommasi, G., An efficient approach for on-line diagnosis of discrete event systems, () · Zbl 1257.93064
[2] Benveniste, A.; Fabre, E.; Haar, S.; Jard, C., Diagnosis of asynchronous discrete event systems: A net unfolding approach, IEEE transactions on automatic control, 48, 714-727, (2003) · Zbl 1364.93452
[3] Cabasino, M. P. (2005). Diagnosi di un sistema ad eventi discreti mediante automi e reti di Petri
[4] Cabasino, M.P.; Giua, A.; Seatzu, C., Identification of Petri nets from knowledge of their language, Discrete event dynamic systems, 17, 4, 447-474, (2007) · Zbl 1125.93332
[5] Cassandras, C.G.; Lafortune, S., Introduction to discrete event systems, (2008), Kluwer Academic Boston · Zbl 1165.93001
[6] Corona, D., Giua, A., & Seatzu, C. (2004). Marking estimation of Petri nets with silent transitions. In Proc. 43th IEEE. conf. on decision and control and 2004 European control conf. · Zbl 1368.68261
[7] Dotoli, M., Fanti, M. P., & Mangini, A. M. (2008). Fault monitoring of discrete event systems by first order hybrid Petri nets. In Proc. of workshop on Petri nets and Agile manufacturing, a satellite event of the 29th int. conf. on application and theory of Petri nets and other models of concurrency · Zbl 1283.93187
[8] Dotoli, M.; Fanti, M.P.; Mangini, A.M., Real time identification of discrete event systems using Petri nets, Automatica, 44, 5, 1209-1219, (2008) · Zbl 1283.93187
[9] Genc, S., & Lafortune, S. (2003). Distributed diagnosis of discrete event systems using Petri nets. In Proc. of inter. conf. of application and theory of Petri nets · Zbl 1274.68234
[10] Genc, S.; Lafortune, S., Distributed diagnosis of place-bordered Petri nets, IEEE transactions on automation science and engineering, 4, 2, 206-219, (2007)
[11] Ghazel, M., Togueni, A., & Bigang, M. (2005). A monitoring approach for discrete events systems based on a time Petri net model. In Proc. of 16th IFAC world congress
[12] Giua, A., & Seatzu, C. (2005). Fault detection for discrete event systems using Petri nets with unobservable transitions. In Proc. 44th IEEE. conf. on decision and control and 2005 European control conf. (pp. 6326-6328)
[13] Hadjicostis, C. N., & Verghese, G. C. (1999). Monitoring discrete event systems using Petri nets embeddings. In Proc. application theory Petri nets (pp. 188-208) · Zbl 0934.93046
[14] Jiroveanu, G.; Boel, R.K., A distributed approach for fault detection and diagnosis based on time Petri nets, Mathematics and computers in simulation, 70, 1, 287-313, (2006) · Zbl 1098.93024
[15] Jiroveanu, G.; Boel, R.K.; Bordbar, B., On-line monitoring of large Petri net models under partial observation, Discrete event dynamical systems, 18, 2, 323-354, (2008) · Zbl 1171.93356
[16] Lefebvre, D.; Delherm, C., Diagnosis of DES with Petri net models, IEEE transactions on automation science and engineering, 4, 1, 114-118, (2007)
[17] GLPK, (0000). Reference manual. Available at: http://www.gnu.org/software/glpk/glpk.html
[18] Nemhauser, G.L.; Wolsey, L.A., Integer and combinatorial optimization, (1988), John Wiley and Sons USA · Zbl 0469.90052
[19] Peterson, J.L., Petri net theory and the modeling of systems, (1981), Prentice Hall Englewood Cliffs, NJ, USA
[20] Prock, J., A new technique for fault detection using Petri nets, Automatica, 27, 2, 239-245, (1991)
[21] Ramirez-Trevino, A.; Ruiz-Beltrán, E.; Rivera-Rangel, I.; Lopez-Mellado, E., Online fault diagnosis of discrete event systems. A Petri net-based approach, IEEE transactions on automation science and engineering, 4, 1, 31-39, (2007)
[22] Sampath, M.; Sengupta, R.; Lafortune, S.; Sinnamohideen, K.; Teneketzis, D., Diagnosability of discrete-event systems, IEEE transactions on automatic control, 40, 1555-1575, (1995) · Zbl 0839.93072
[23] Shanthi, P., & Parthasarathi, R. (2003). Exploring FPGA structures for evolving fault tolerant hardware. In Proc. 2003 NASA/DoD conference on evolvable hardware
[24] Srinivasan, V.S.; Jafari, M.A., Fault detection and monitoring using time Petri nets, IEEE transactions on systems, man and cybernetics, 23, 4, 1155-1162, (1993)
[25] Wu, Y.; Hadjicostis, C.N., Algebraic approaches for fault identification in discrete-event systems, IEEE transactions on robotics and automation, 50, 12, 2048-2053, (2005) · Zbl 1365.93534
[26] Hashtrudi Zad, S.; Kwong, R.H.; Wonham, W.M., Fault diagnosis in discrete-event systems: framework and model reduction, IEEE transactions on automatic control, 48, 7, 1199-1212, (2003) · Zbl 1364.93464
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.