Computation of projections for the abstraction-based diagnosability verification
Discrete Event Systems, Volume # 10 | Part# 1
Digital Object Identifier (DOI)
discrete event systems,failure diagnosis,language-diagnosability,abstraction
The verification of language-diagnosability (LD) for discrete event systems (DES) generally requires the explicit evaluation of the overall system model which is infeasible for practical systems. In order to circumvent this problem, our previous work proposes the abstraction-based LD verification using natural projections that fulfill the loop-preserving observer (LPO) property. In this paper, we develop algorithms for the verification and computation of such natural projections. We first present a polynomial-time algorithm that allows to test if a given natural projection is a loop-preserving observer. Then, we show that, in case the LPO property is violated, finding a minimal extension of the projection alphabet such that the LPO condition holds is NP-hard. Finally, we adapt a polynomial-time heuristic algorithm by Feng and Wonham for the efficient computation of loop-preserving observers.
 (2009). libFAUDES - software library for discrete event systems. URL http://www.rt.eei. uni-erlangen.de/FGdes/faudes/index.html.  Cassandras, C.G. and Lafortune, S. (2006). Introduction to Discrete Event Systems. Springer-Verlag New York, Inc., Secaucus, NJ, USA.  Contant, O., Lafortune, S., and Teneketzis, D. (2006). Diagnosability of discrete event systems with modular structure. Discrete Event Dynamic Systems: Theory and Applications, 16, 9-17.  Debouk, R., Malik, R., and Brandin, B. (2002). A modular architecture for diagnosis of discrete event systems. In Decision and Control, IEEE Conference on, 417-422.  Feng, L. and Wonham, W. (2010). On the computation of natural observers in discrete-event systems. Discrete Event Dynamic Systems: Theory and Applications, 20(1), 63-102.  Hopcroft, J.E. and Ullman, J.D. (1975). The design and analysis of computer algorithms. Addison-Wesley.  Jiang, S., Huang, Z., Chandra, V., and Kumar, R. (2001). A polynomial algorithm for testing diagnosability of discrete-event systems. Automatic Control, IEEE Transactions on, 46(8), 1318-1321.  Qiu, W. and Kumar, R. (2006). Decentralized failure diagnosis of discrete event systems. Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on, 36(2), 384-395.  Sampath, M., Sengupta, R., Lafortune, S., Sinnamo-hideen, K., and Teneketzis, D. (1995). Diagnosability of discrete-event systems. Automatic Control, IEEE Transactions on, 40(9), 1555-1575.  Schaefer, T.J. (1978). The complexity of satisfiability problems. In Proceedings of the tenth annual ACM symposium on Theory of computing, 216-226.  Schmidt, K. (2010a). Abstraction-based failure diagnosis for discrete event systems. System & Control Letters, 59, 42-47.  Schmidt, K. (2010b). Abstraction-based verification of codiagnosability for discrete event systems. to appear in Automatica. doi:10.1016/j.automatica.2010.06.010.  Sipser, M. (2006). Introduction to the Theory of Computation. 2nd edition, Course Technology.  Su, R. and Wonham, W.M. (2005). Global and local consistencies in distributed fault diagnosis for discrete-event systems. Automatic Control, IEEE Transactions on, 50(12), 1923-1935.  Wang, Y., Yoo, T.S., and Lafortune, S. (2007). Diagnosis of discrete event systems using decentralized architectures. Discrete Event Dynamic Systems, 17(2), 233-263.  Wong, K.C. and Wonham, W.M. (2004). On the computation of observers in discrete-event systems. Discrete Event Dynamic Systems, 14(1), 55-107.  Yoo, T.S. and Garcia, H.E. (2008). Diagnosis of behaviors of interest in partially-observed discrete-event systems. System & Control Letters, 57(12), 1023-1029.  Yoo, T.S. and Lafortune, S. (2002). Polynomial time verification of diagnosability of partially observed discrete-event systems. Automatic Control, IEEE Transactions on, 47(9), 1491-1495.