On–The–Fly Diagnosability Analysis of Bounded and Unbounded Labeled Petri Nets Using Verifier Nets

Li, Ben; Khlif-Bouassida, Manel; Toguyéni, Armand

doi:10.2478/amcs-2018-0019

Abstract

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.

References

Basile, F., Chiacchio, P. and De Tommasi, G. (2012). On K-diagnosability of Petri nets via integer linear programming, Automatica 48(9): 2047-2058.10.1016/j.automatica.2012.06.039
Search in Google Scholar Back to article
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.10.1109/TAC.2009.2014932
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.10.1109/TAC.2012.2200372
Search in Google Scholar Back to article
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.10.1109/TASE.2013.2289360
Search in Google Scholar Back to article
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.10.1109/TAC.2014.2332238
Search in Google Scholar Back to article
Cormen, T., Leiserson, C. and Rivest, R. (1990). Introduction of Algorithms, MIT Press, Cambridge, MA.
Search in Google Scholar Back to article
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.10.1109/9.940942
Search in Google Scholar Back to article
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.1016/S0022-0000(69)80011-5
Search in Google Scholar Back to article
Lefebvre, D. and Delherm, C. (2007). Diagnosis of DES with Petri net models, IEEE Transactions on Automation Science and Engineering 4(1): 114-118.10.1109/TASE.2006.872122
Search in Google Scholar Back to article
Li, B., Khlif-Bouassida, M. and Toguy´eni, 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.10.1016/j.ifacol.2015.06.474
Search in Google Scholar Back to article
Li, B., Khlif-Bouassida, M. and Toguy´eni, 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.10.1109/SYSTOL.2016.7739768
Search in Google Scholar Back to article
Li, B., Liu, B. and Toguy´eni, 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.10.1016/j.ifacol.2015.09.548
Search in Google Scholar Back to article
Liu, B., Ghazel,M. and Toguy´eni, 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.10.1109/ECC.2014.6862505
Search in Google Scholar Back to article
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.10.1109/TAC.2011.2124950
Search in Google Scholar Back to article
Rushton, A. (2012). STLplus C++ Library Collection, stlplus.sourceforge.net.
Search in Google Scholar Back to article
Sampath, M., Sengupta, R. and Lafortune, S. (1995). Diagnosability of discrete-event systems, IEEE Transactions an Automatic Control 40(9): 1555-1575.10.1109/9.412626
Search in Google Scholar Back to article
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.10.1007/978-3-540-31980-1_12
Search in Google Scholar Back to article
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.10.1109/TAC.2002.802763
Search in Google Scholar Back to article

On–The–Fly Diagnosability Analysis of Bounded and Unbounded Labeled Petri Nets Using Verifier Nets

Abstract

Paradigm

My account