» Download Article

Authors
Schmidt, Klaus

Digital Object Identifier (DOI)
10.3182/20100830-3-DE-4013.00034

Page Numbers:
199-204

Index Terms
discrete event systems,failure diagnosis,language-diagnosability,abstraction

Abstract
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.

References

[1] (2009). libFAUDES - software library for discrete
    event systems. URL http://www.rt.eei.
    uni-erlangen.de/FGdes/faudes/index.html.
[2] Cassandras, C.G. and Lafortune, S. (2006). Introduction
    to Discrete Event Systems. Springer-Verlag New York,
    Inc., Secaucus, NJ, USA.
[3] 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.
[4] 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.
[5] 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.
[6] Hopcroft, J.E. and Ullman, J.D. (1975). The design and
    analysis of computer algorithms. Addison-Wesley.
[7] 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.
[8] 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.
[9] 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.
[10] Schaefer, T.J. (1978). The complexity of satisfiability
     problems. In Proceedings of the tenth annual ACM
     symposium on Theory of computing, 216-226.
[11] Schmidt, K. (2010a). Abstraction-based failure diagnosis
     for discrete event systems. System & Control Letters,
     59, 42-47.
[12] Schmidt, K. (2010b). Abstraction-based verification of
     codiagnosability for discrete event systems. to appear
     in Automatica. doi:10.1016/j.automatica.2010.06.010.
[13] Sipser, M. (2006). Introduction to the Theory of Computation.
     2nd edition, Course Technology.
[14] 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.
[15] 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.
[16] 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.
[17] 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.
[18] 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.