On-the-fly diagnosability analysis of bounded and unbounded labeled Petri nets using verifier nets

Li, B. ; Khlif-Bouassida, M. ; Toguéyni, A.

International Journal of Applied Mathematics and Computer Science, Tome 28 (2018) no. 2, pp. 269-281.

Résumé

This paper considers the problem of diagnosability analysis of discrete event systems modeled by labeled Petri nets (LPNs). We assume that the LPN can be bounded or unbounded with no deadlock after firing any fault transition. Our approach is novel and presents the on-the-fly diagnosability analysis using verifier nets. For a given LPN model, the verifier net and its reachability graph (for a bounded LPN) or coverability graph (for an unbounded LPN) are built on-the-fly and in parallel for diagnosability analysis. As soon as a diagnosability decision is established, the construction is stopped. This approach achieves a compromise between computation limitations due to efficiency and combinatorial explosion and it is useful to implement an engineering approach to the diagnosability analysis of complex systems.

Détail

Keywords: fault diagnosis, discrete event system, labeled Petri nets, on-the-fly diagnosability analysis, verifier nets
Mots-clés : diagnostyka błędu, układ zdarzeń dyskretnych, sieci Petriego

Bibliographie

[1] Basile, F., Chiacchio, P. and De Tommasi, G. (2012). On K-diagnosability of Petri nets via integer linear programming, Automatica 48(9): 2047–2058.

[2] Basile, F., Chiacchio, P. and Tommasi, G. (2009). An efficient approach for online diagnosis of discrete event systems, IEEE Transactions on Automatic Control 54(4): 748–759.

[3] Boussif, A., Ghazel, M. and Klai, K. (2015). Combining enumerative and symbolic techniques for diagnosis of discrete-event systems, 9th International Workshop on Evaluation of Computer and Communication Systems, Bucharest, Romania, pp.1–11.

[4] Cabasino, M., Giua, A., Lafortune, S. and Seatzu, C. (2012). A new approach for diagnosability analysis of Petri nets using verifier nets, IEEE Transactions Automatic Control 57(12): 3104–3117.

[5] Cabasino, M., Giua, A. and Seatzu, C. (2014). Diagnosis of discrete event systems using labeled Petri nets, IEEE Transactions on Automation Science and Engineering 11(1): 144–153.

[6] Cabral, F., Moreira, M., Diene, O. and Basilio, J. (2015). A Petri net diagnoser for discrete event systems modeled by finite state automata, IEEE Transactions on Automatic Control 60(1): 59–71.

[7] Cormen, T., Leiserson, C. and Rivest, R. (1990). Introduction of Algorithms, MIT Press, Cambridge, MA.

[8] Jiang, S., Huang, Z., Chandra, V. and Kumar, R. (2001). A polynomial algorithm for testing diagnosability of discrete event systems, IEEE Transactions on Automatic Control 46(8): 1318–1321.

[9] Karp, R. and Miller, R. (1969). Parallel program schemata: A mathematical model for parallel computation, Journal of Computer and System Sciences 3(2): 147–195.

[10] Lefebvre, D. and Delherm, C. (2007). Diagnosis of DES with Petri net models, IEEE Transactions on Automation Science and Engineering 4(1): 114–118.

[11] Li, B., Khlif-Bouassida, M. and Toguyéni, A. (2015a). On-the-fly Diagnosability analysis of labeled Petri nets using T-invariants, 5th International Workshop on Dependable Control of Discrete Systems, DCDS’2015, Cancun, Mexico, pp. 64–70.

[12] Li, B., Khlif-Bouassida, M. and Toguyéni, A. (2016). On-the-fly diagnosability analysis of LPN using verifier nets, 3rd International Conference on Control and Fault-Tolerant Systems, SYSTOL’16, Nice, France, pp. 305–312.

[13] Li, B., Liu, B. and Toguyéni, A. (2015b). On-the-fly diagnosability analysis of labeled Petri nets using minimal explanations, 9th IFAC Symposium on Fault Detection, Supervision and Safety for Technical Processes, SAFEPROCESS’2015, Paris, France, pp. 326–331.

[14] Liu, B., Ghazel,M. and Toguyéni, A. (2014). Toward an efficient approach for diagnosability analysis of DES modeled by labeled Petri nets, 13th European Control Conference, ECC’2014, Strasbourg, France, pp. 1293–1298.

[15] Moreira, M., Jesus, T. and Basilio, J. (2011). Polynomial time verification of decentralized diagnosability of discrete event systems, IEEE Transactions on Automatic Control 56(7): 1679–1684.

[16] Rushton, A. (2012). STLplus C++ Library Collection, stlplus.sourceforge.net.

[17] Sampath, M., Sengupta, R. and Lafortune, S. (1995). Diagnosability of discrete-event systems, IEEE Transactions an Automatic Control 40(9): 1555–1575.

[18] Schwoon, S. and Esparza, J. (2005). A note on on-the-fly verification algorithms, 11th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, Edinburgh, UK, pp. 174–190.

[19] Yoo, T. and Lafortune, S. (2002). Polynomial-time verification of diagnosability of partially observed discrete-event systems, IEEE Transactions on Automatic Control 47(9): 1491–1495.