On \(\mathcal K\)-diagnosability of Petri nets via integer linear programming.

*(English)*Zbl 1257.93064Summary: This paper deals with the problem of diagnosability of a fault after the firing of a finite number events (i.e., \(\mathcal K\)-diagnosability). This problem corresponds to diagnosability of a fault within a finite delay in the context of discrete event systems. The main contribution of this paper is a necessary and sufficient condition for \(\mathcal K\)-diagnosability of bounded nets. The proposed approach exploits the mathematical representation of Petri nets and the Integer Linear Programming optimization tool. In particular no specific assumptions are made on the structure of the net induced by the unobservable transitions, since the proposed approach permits to detect also the undiagnosability due to the presence of unobservable cycles.

##### MSC:

93C65 | Discrete event control/observation systems |

93C05 | Linear systems in control theory |

90C10 | Integer programming |

Full Text:
DOI

##### References:

[1] | Basile, F., Chiacchio, P., & De Tommasi, G. (2008). Sufficient conditions for diagnosability of Petri nets. In Proc. of the 9th international workshop on discrete event systems, WODES’08. Göteborg, Sweden. May (pp. 436-442). |

[2] | Basile, F.; Chiacchio, P.; De Tommasi, G., An efficient approach for online diagnosis of discrete event systems, IEEE transactions on automatic control, 54, 4, 748-759, (2009) · Zbl 1367.93358 |

[3] | Basile, F., Chiacchio, P., & De Tommasi, G. (2009b). Online diagnosis of discrete events systems based on Petri nets and integer linear programming. In Proc. 2nd IFAC workshop on dependable control of discrete systems, DCDS’09. Bari, Italy. June (pp. 111-116). |

[4] | Boel, R. K., & Jiroveanu, G. (2004). Contextual distributed diagnosis for very large systems. In 16th int. symp. on mathematical theory of networks and systems. Leuven, Belgium. July. · Zbl 1098.93024 |

[5] | Cabasino, M. P., Giua, A., Lafortune, S., & Seatzu, C. (2009a). Diagnosability analysis of unbounded Petri nets. In Proc. of the 48th IEEE conf. on decision and control. Shangai, China. December (pp. 1267-1272). · Zbl 1369.93373 |

[6] | Cabasino, M. P., Giua, A., & Seatzu, C. (2009b). Diagnosability analysis of bounded Petri nets. In Proc. of the 48th IEEE conf. on decision and control. Shangai, China. December (pp. 1254-1260). |

[7] | Cabasino, M.P.; Giua, A.; Seatzu, C., Fault detection for discrete event systems using Petri nets with unobservable transitions, Automatica, 46, 9, 1531-1539, (2010) · Zbl 1201.93074 |

[8] | Cassandras, C.G.; Lafortune, S., Introduction to discrete event systems, (1999), Springer · Zbl 0934.93001 |

[9] | Cassez, F., Tripakis, S., & Altisen, K. (2007). Sensor minimization problems with static or dynamic observers for fault diagnosis. In 7th Int. conf. application of concurrency to system design. Bratislava, Slovak Republic. July. |

[10] | Chung, S.L., Diagnosing PN-based models with partial observable transitions, International journal of computer integrated manufacturing, 18, 2-3, 158-169, (2005) |

[11] | Debouk, R.; Lafortune, S.; Teneketzis, D., Coordinated decentralized protocols for failure diagnosis of discrete event systems, Discrete event dynamic systems, 10, 1, 33-86, (2000) · Zbl 0959.93039 |

[12] | Dideban, A.; Alla, H., Reduction of constraints for controller synthesis based on safe Petri nets, Automatica, 44, 7, 1697-1706, (2008) · Zbl 1149.93311 |

[13] | Dotoli, M.; Fanti, M.P.; Mangini, A.M., Fault detection of discrete event systems by Petri nets and integer linear programming, Automatica, 45, 11, 2665-2672, (2009) · Zbl 1180.93066 |

[14] | García Vallés, F. (1999). Contributions to the structural and symbolic analysis of place/transition nets with applications to flexible manufacturing systems and asynchronous circuits. Ph.D. Thesis. Universidad de Zaragoza. |

[15] | GLPK, (2008). GNU linear programming kit. http://www.gnu.org/software/glpk/. |

[16] | Góra, P., Graph theoretic bound on number of A.C.I.M. for random transformation, Proceedings of the American mathematical society, 116, 2, 401-410, (1992) · Zbl 0761.28010 |

[17] | Hruz, B.; Zhou, M.C., Modeling and control of discrete event dynamic systems, (2007), Springer London, UK |

[18] | Jiroveanu, G.; Boel, R.K., The diagnosability of Petri net models using minimal explanations, IEEE transactions on automatic control, 55, 7, 1663-1668, (2010) · Zbl 1368.68265 |

[19] | Lefebvre, D.; Delherm, C., Diagnosis of DES with Petri net models, IEEE transactions on automation science and engineering, 4, 1, 114-118, (2007) |

[20] | Lunze, J.; Schröder, J., State observation and diagnosis of discrete-event systems described by stochastic automata, Discrete event dynamic systems, 11, 4, 319-369, (2001) · Zbl 1055.93056 |

[21] | Murata, T., Petri nets: properties, analysis and applications, Proceedings of the IEEE, 77, 4, 541-580, (1989) |

[22] | Netlab, (2011). http://www.irt.rwth-aachen.de/en/fuer-studierende/downloads/petri-net-tool-netlab/. |

[23] | Paoli, A.; Lafortune, S., Safe diagnosability for fault-tolerant supervision of discrete-event systems, Automatica, 41, 8, 1335-1347, (2005) · Zbl 1086.93043 |

[24] | Sampath, M.; Sengupta, R.; Lafortune, S.; Sinnamohideen, K.; Teneketzis, D., Diagnosability of discrete event systems, IEEE transactions on automatic control, 40, 9, 1555-1575, (1995) · Zbl 0839.93072 |

[25] | Sampath, M.; Sengupta, R.; Lafortune, S.; Sinnamohideen, K.; Teneketzis, D.C., Failure diagnosis using discrete-event models, IEEE transactions on control systems technology, 4, 2, 105-124, (1996) |

[26] | Silva, M.; Teruel, E.; Colom, J.M., Linear algebraic and linear programming techniques for the analysis of place/transition net systems, (), 309-373 · Zbl 0926.68086 |

[27] | Teruel, E.; Silva, M., Liveness and home states in equal conflict systems, (), 415-432 |

[28] | Trevino, A.R.; Ruiz-Beltran, 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) |

[29] | Ushio, T., Onishi, L., & Okuda, K. (1998). Fault detection based on Petri net models with faulty behaviors. In Proc. of the 1998 IEEE conf. on systems, man, and cybernetics. San Diego, CA, USA. October (pp. 113-118). |

[30] | Wen, Y., Li, C., & Jeng, M. (2005). A polynomial algorithm for checking diagnosability of Petri nets. In Proc. of the 2005 IEEE conf. on systems, man, and cybernetics, SMC’05. Vol. 3. October (pp. 2542-2547). |

[31] | Wu, Y.; Hadjicostis, C.N., Algebraic approaches for fault identification in discrete-event systems, IEEE transactions on automatic control, 50, 12, 2048-2053, (2005) · Zbl 1365.93534 |

[32] | Zad, S.H.; 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 |

[33] | Zad, S.H.; Kwong, R.H.; Wonham, W.M., Diagnosis in discrete-event systems: incorporating timing information, IEEE transactions on automatic control, 50, 7, 1010-1015, (2005) · Zbl 1365.93292 |

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.