A necessary and sufficient condition for diagnosability of stochastic discrete event systems. (English) Zbl 1374.93242
Summary: Stochastic discrete event systems (SDES) are systems whose evolution is described by the occurrence of a sequence of events, where each event has a defined probability of occurring from each state. The diagnosability problem for SDES is the problem of determining the conditions under which occurrences of a fault can be detected in finite time with arbitrarily high probability. In [IEEE Trans. Autom. Control 50, No. 4, 476–492 (2005; Zbl 1365.93478)], the author with D. Teneketzis proposed a class of SDES and proposed two definitions of stochastic diagnosability for SDES called \(A\)- and \(AA\)-diagnosability and reported a necessary and sufficient condition for \(A\)-diagnosability, but only a sufficient condition for \(AA\)-diagnosability. In this paper, we provide a condition that is both necessary and sufficient for determining whether or not an SDES is \(AA\)-diagnosable. We also show that verification of \(AA\)-diagnosability is equivalent to verification of the termination of the cumulative sum (CUSUM) procedure for hidden Markov models, and that, for a specific class of SDES called fault-immediate systems, the sequential probability ratio test (SPRT) minimizes the expected number of observable events required to distinguish between the normal and faulty modes.
MSC:
| 93C65 | Discrete event control/observation systems |
| 93E03 | Stochastic systems in control theory (general) |
| 60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |
Keywords:
stochastic discrete event systems; diagnosability; hidden Markov models; change point detectionCitations:
Zbl 1365.93478Software:
UMDESReferences:
| [1] | Athanasopoulou E, Li L, Hadjicostis C (2010) Maximum likelihood failure diagnosis in finite state machines under unreliable observations. IEEE Trans Autom Control 555(3):579-593 · Zbl 1368.93365 · doi:10.1109/TAC.2009.2039548 |
| [2] | Bertrand N, Fabre E, Haar S, Haddad S, Helout L (2014a) Active diagnosis for probabilistic systems. In: Proceedings of the FoSSaCS ’14, LNCS 8412, pp 29-42 · Zbl 1405.68223 |
| [3] | Bertrand N, Haddad S, Lefaucheux E (2014b) Foundation of diagnosis and predictability in probabilistic systems. In: Proceedings of the FSTTCS’14, Leibniz International Proceedings in Informatics 29, pp 417-429 · Zbl 1360.68627 |
| [4] | Brémaud P (1999) Markov Chains: Gibbs Fields Monte Carlo Simulation and Queues. Springer, New York · Zbl 0949.60009 · doi:10.1007/978-1-4757-3124-8 |
| [5] | Cassandras C, Lafortune S (1999) Introduction to Discrete Event Systems, Kluwer Academic Publishers, Boston, MA · Zbl 0934.93001 |
| [6] | Fabre E, Jezequel L (2010) On the construction of probabilistic diagnosers. In: Proceedings of the 10th International Workshop on Discrete Event Systems · Zbl 0060.30207 |
| [7] | Fuh CD (2003) SPRT and CUSUM in hidden Markov models. Ann Stat 31 (3):942-977. http://www.jstor.org/stable/3448426 · Zbl 1036.60005 |
| [8] | Grossi E, Lops M (2008) Sequential detection of Markov targets with trajectory estimation. IEEE Trans Inf Theory 54(9):4144 -4154. doi:10.1109/TIT.2008.928261 · Zbl 1322.94044 |
| [9] | Lin F, Ying H (2002) Modeling and control of fuzzy discrete event systems. IEEE Trans Syst Man Cybern B Cybern 32(4):408-415 · doi:10.1109/TSMCB.2002.1018761 |
| [10] | Liu F, Qiu D (2008) Safe diagnosability of stochastic discrete event systems. IEEE Transactions on Automatic Control 53(5):1291-1296 · Zbl 1367.93620 · doi:10.1109/TAC.2008.921035 |
| [11] | Liu F, Qiu D (2009) Diagnosability of fuzzy discrete-event systems: A fuzzy approach. IEEE Trans Fuzzy Syst 17(2):372-384 · doi:10.1109/TFUZZ.2009.2013840 |
| [12] | Liu F, Qiu D, Xing H, Fan Z (2008) Decentralized diagnosis of stochastic discrete event systems. IEEE Trans Autom Control 53(2):535-546 · Zbl 1367.93621 · doi:10.1109/TAC.2007.915172 |
| [13] | Lunze J, Schröder J (2001) State observation and diagnosis of discrete-event systems described by stochastic automata. Discrete Event Dynamic Systems: Theory and Applications 11(4):319-369 · Zbl 1055.93056 · doi:10.1023/A:1011273108731 |
| [14] | Qiu D, Liu F (2009) Fuzzy discrete event systems under fuzzy observability and a test-algorithm. IEEE Trans Fuzzy Syst 17(3):578-589 · doi:10.1109/TFUZZ.2008.924212 |
| [15] | Qiu D W (2005) Supervisory control of fuzzy discrete event systems: A formal approach. IEEE Trans Syst Man Cybern B 35(1):72-88 · doi:10.1109/TSMCB.2004.840457 |
| [16] | Sampath M, Sengupta R, Lafortune S, Sinnamohideen K, Teneketzis D (1995) Diagnosability of discrete-event systems. IEEE Trans Autom Control 40 (9):1555-1575 · Zbl 0839.93072 · doi:10.1109/9.412626 |
| [17] | Smyth P (1994) Hidden Markov models for fault detection in dynamic systems. Pattern Recogn 21(1):149-164 · doi:10.1016/0031-3203(94)90024-8 |
| [18] | Thorsley D (2010) Diagnosability of stochastic chemical kinetic systems: a discrete event systems approach. In: Proceedings of the 2010 American Control Conference, pp 2623-2630 · Zbl 1365.93478 |
| [19] | Thorsley D, Teneketzis D (2005) Diagnosability of stochastic discrete-event systems. IEEE Trans Autom Control 50(4):476-492 · Zbl 1365.93478 · doi:10.1109/TAC.2005.844722 |
| [20] | Thorsley D, Yoo TS, Garcia H (2008) Diagnosability of stochastic discrete-event systems under unreliable observations. In: Proceedings of the 2008 American Control Conference, pp 1158-1165 · Zbl 1055.93056 |
| [21] | Wald A (1945) Sequential tests of statistical hypotheses. Ann Math Stat 16 (2):117-186. http://www.jstor.org/stable/2235829 · Zbl 0060.30207 · doi:10.1214/aoms/1177731118 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
