A Unified Method to Decentralized State Detection and Fault Diagnosis/prediction of Discrete-event Systems

• Autorzy: Zhang Kuize

Identyfikatory

DOI

10.3233/FI-2021-2062

• Języki publikacji: EN

Abstrakty

EN

The state detection problem and fault diagnosis/prediction problem are fundamental topics in many areas. In this paper, we consider discrete-event systems (DESs) modeled by finite-state automata (FSAs). There exist plenty of results on decentralized versions of the latter problem but there is almost no result for a decentralized version of the former problem. In this paper, we propose a decentralized version of strong detectability called co-detectability which means that if a system satisfies this property, for each generated infinite-length event sequence, in at least one location the current and subsequent states can be determined by observations in the location after a common observation time delay. We prove that the problem of verifying co-detectability of deterministic FSAs is coNP-hard. Moreover, we use a unified concurrent-composition method to give PSPACE verification algorithms for co-detectability, co-diagnosability, and co-predictability of FSAs, without any assumption on or modification of the FSAs under consideration, where co-diagnosability is first studied by [Debouk & Lafortune & Teneketzis 2000], co-predictability is first studied by [Kumar & Takai 2010]. By our proposed unified method, one can see that in order to verify co-detectability, more technical difficulties will be met compared with verifying the other two properties, because in co-detectability, generated outputs are counted, but in the latter two properties, only occurrences of events are counted. For example, when one output was generated, any number of unobservable events could have occurred. PSPACE-hardness of verifying co-diagnosability is already known in the literature. In this paper, we prove PSPACE-hardness of verifying co-predictability.

Słowa kluczowe

EN

discrete event system; finite-state automata; co-detectability; co-diagnosability; co-predictability; concurrent composition; complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 181, nr 4
• Strony: 339--371
• Opis fizyczny: Bibliogr. 67 poz., rys., tab.

Twórcy

autor

Zhang Kuize

• Control Systems Group, Technical University of Berlin, Berlin, Germany

Bibliografia

• [1] Moore E. Gedanken-experiments on sequential machines. Automata Studies, Annals of Math. Studies, 1956. 34:129-153.
• [2] Broy M, Jonsson B, Katoen JP, Martin L, Pretschner A. Model-Based Testing of Reactive Systems: Advanced Lectures (Lecture Notes in Computer Science). Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2005. ISBN 3540262784.
• [3] Kalman R. Mathematical description of linear dynamical systems. Journal of the Society for Industrial and Applied Mathematics Series A Control, 1963. 1(12):152-192.
• [4] Wonham W. Linear Multivariable Control: a Geometric Approach, 3rd Ed. Springer-Verlag New York, 1985.
• [5] Sontag E. On the observability of polynomial systems, I: Finite-time problems. SIAM Journal on Control and Optimization, 1979. 17:139-151.
• [6] Conte G, Moog C, Perdon A. Algebraic Methods for Nonlinear Control Systems, 2nd Ed. Springer-Verlag London, 2007.
• [7] Isidori A. Nonlinear Control Systems. Communications and Control Engineering. Springer-Verlag London, 1995.
• [8] Tanwani A, Shim H, Liberzon D. Observability for switched linear systems: characterization and observer design. IEEE Transactions on Automatic Control, 2013. 58(4):891-904. doi:10.1109/TAC.2012.2224257.
• [9] Kibangou AY, Garin F, Gracy S. Input and state observability of network systems with a single unknown Input. IFAC-PapersOnLine, 2016. 49(22):37-42. doi:https://doi.org/10.1016/j.ifacol.2016.10.369. 6th IFAC Workshop on Distributed Estimation and Control in Networked Systems NECSYS 2016, URL http://www.sciencedirect.com/science/article/pii/S2405896316319565.
• [10] Angulo MT, Aparicio A, Moog CH. Structural accessibility and structural observability of nonlinear networked systems. IEEE Transactions on Network Science and Engineering, 2019. p. online. doi:10.1109/TNSE.2019.2946535.
• [11] Liu YY, Slotine JJ, Barabási AL. Observability of complex systems. Proceedings of the National Academy of Sciences, 2013. 110(7):2460-2465. doi:10.1073/pnas.1215508110. http://www.pnas.org/content/110/7/2460.full.pdf, URL http://www.pnas.org/content/110/7/2460.abstract.
• [12] Shu S, Lin F, Ying H. Detectability of Discrete Event Systems. IEEE Transactions on Automatic Control, 2007. 52(12):2356-2359. doi:10.1109/TAC.2007.910713.
• [13] Fornasini E, Valcher ME. Observability, reconstructibility and state observers of Boolean control networks. IEEE Transactions on Automatic Control, 2013. 58(6):1390-1401. doi:10.1109/TAC.2012.2231592.
• [14] Zhang K, Zhang L, Su R. A weighted pair graph representation for reconstructibility of Boolean control networks. SIAM Journal on Control and Optimization, 2016. 54(6):3040-3060. doi:10.1137/140991285. http://dx.doi.org/10.1137/140991285, URL http://dx.doi.org/10.1137/140991285.
• [15] Sandberg S. Homing and Synchronizing Sequences, pp. 5-33. Springer Berlin Heidelberg, Berlin, Heidelberg. ISBN 978-3-540-32037-1, 2005. doi:10.1007/11498490_2.
• [16] Kari J. Synchronizing finite automata on Eulerian digraphs. Theoretical Computer Science, 2003. 295(1):223-232. doi:https://doi.org/10.1016/S0304-3975(02)00405-X. Mathematical Foundations of Computer Science, URL http://www.sciencedirect.com/science/article/pii/S030439750200405X.
• [17] Eppstein D. Reset sequences for monotonic automata. SIAM Journal on Computing, 1990. 19(3):500-510. doi:10.1137/0219033. https://doi.org/10.1137/0219033, URL https://doi.org/10.1137/0219033.
• [18] Cassandras CG, Lafortune S. Introduction to Discrete Event Systems. Springer Publishing Company, Incorporated, 2nd edition, 2010. ISBN 1441941193, 9781441941190.
• [19] Wonham W, Cai K. Supervisory Control of Discrete-Event Systems. Springer International Publishing, 2019.
• [20] Lin F. Diagnosability of discrete event systems and its applications. Discrete Event Dynamic Systems, 1994. 4(2):197-212. doi:10.1007/BF01441211. URL https://doi.org/10.1007/BF01441211.
• [21] Sampath M, Sengupta R, Lafortune S, Sinnamohideen K, Teneketzis D. Diagnosability of discrete-event systems. IEEE Transactions on Automatic Control, 1995. 40(9):1555-1575. doi:10.1109/9.412626.
• [22] Genc S, Lafortune S. Predictability of event occurrences in partially-observed discrete-event systems. Automatica, 2009. 45(2):301-311. doi:https://doi.org/10.1016/j.automatica.2008.06.022. URL http://www.sciencedirect.com/science/article/pii/S0005109808003828.
• [23] Boussif A, Ghazel M. Diagnosability analysis of intermittent faults in discrete event systems using a twin-plant structure. International Journal of Control, Automation and Systems, 2019. 17(X):1-14. doi:10.1007/s12555-018-0682-9. URL https://doi.org/10.1007/s12555-018-0682-9.
• [24] Shu S, Lin F. Generalized detectability for discrete event systems. Systems & Control Letters, 2011. 60(5):310-317. doi:http://dx.doi.org/10.1016/j.sysconle.2011.02.001.
• [25] Caines PE, Greiner R, Wang S. Dynamical logic observers for finite automata. In: Proceedings of the 27th IEEE Conference on Decision and Control. 1988 pp. 226-233 vol.1. doi:10.1109/CDC.1988.194300.
• [26] Caines PE, Greiner R, Wang S. Classical and Logic-Based Dynamic Observers for Finite Automata. IMA Journal of Mathematical Control and Information, 1991. 8(1):45-80. doi:10.1093/imamci/8.1.45. https://academic.oup.com/imamci/article-pdf/8/1/45/6767102/8-1-45.pdf, URL https://doi.org/10.1093/imamci/8.1.45.
• [27] Özveren CM, Willsky AS. Observability of discrete event dynamic systems. IEEE Transactions on Automatic Control, 1990. 35(7):797-806. doi:10.1109/9.57018.
• [28] Sipser M. Introduction to the Theory of Computation. International Thomson Publishing, 1st edition, 1996. ISBN 053494728X.
• [29] Zhang K. The problem of determining the weak (periodic) detectability of discrete event systems is PSPACE-complete. Automatica, 2017. 81:217-220. doi:http://doi.org/10.1016/j.automatica.2017.03.023. URL http://www.sciencedirect.com/science/article/pii/S0005109817301462.
• [30] Masopust T. Complexity of deciding detectability in discrete event systems. Automatica, 2018. 93:257-261. doi:https://doi.org/10.1016/j.automatica.2018.03.077. URL https://www.sciencedirect.com/science/article/pii/S0005109818301730.
• [31] Zhang K, Giua A. Weak (approximate) detectability of labeled Petri net systems with inhibitor arcs. IFAC-PapersOnLine, 2018. 51(7):167-171. doi:https://doi.org/10.1016/j.ifacol.2018.06.296. 14th IFAC Workshop on Discrete Event Systems WODES 2018, URL http://www.sciencedirect.com/science/article/pii/S2405896318306268.
• [32] Masopust T, Yin X. Deciding detectability for labeled Petri nets. Automatica, 2019. 104:238-241. doi: https://doi.org/10.1016/j.automatica.2019.02.058. URL http://www.sciencedirect.com/science/article/pii/S000510981930113X.
• [33] Zhang K, Giua A. On detectability of labeled Petri nets and finite automata. Discrete Event Dynamic Systems, 2020. 30(3):465-497. doi:10.1007/s10626-020-00311-3. URL https://doi.org/10.1007/s10626-020-00311-3.
• [34] Zhang K, Zhang L, Xie L. Discrete-Time and Discrete-Space Dynamical Systems. Communications and Control Engineering. Springer International Publishing, 2020.
• [35] Zhang K, Giua A. K-delayed strong detectability of discrete-event systems. In: Proceedings of the 58th IEEE Conference on Decision and Control (CDC). 2019 pp. 7647-7652. doi:10.1109/CDC40024.2019.9028873.
• [36] Jiang S, Huang Z, Chandra V, Kumar R. A polynomial algorithm for testing diagnosability of discrete-event systems. IEEE Transactions on Automatic Control, 2001. 46(8):1318-1321. doi:10.1109/9.940942.
• [37] Yoo TS, Lafortune S. Polynomial-time verification of diagnosability of partially observed discrete-event systems. IEEE Transactions on Automatic Control, 2002. 47(9):1491-1495. doi:10.1109/TAC.2002.802763.
• [38] Cassez F, Tripakis S. Fault diagnosis with static and dynamic observers. Fundamenta Informaticae, 2008. 88(4):497-540.
• [39] Viana GS, Basilio JC. Codiagnosability of discrete event systems revisited: A new necessary and sufficient condition and its applications. Automatica, 2019. 101:354-364. doi:https://doi.org/10.1016/j.automatica.2018.12.013. URL http://www.sciencedirect.com/science/article/pii/S0005109818306198.
• [40] Ye L. Optimized diagnosability of distributed discrete event systems through abstraction. Ph.D. thesis, Université Paris-Sud, 2011.
• [41] Su R. Distributed diagnosis for discrete-event systems. Ph.D. thesis, University of Toronto, 2004.
• [42] Ye L, Dague P. Undecidable case and decidable case of joint diagnosability in distributed discrete event systems. International Journal on Advances in Systems and Measurement, 2013. 6(3&4):287-299.
• [43] Ye L, Dague P, He L. Manifestability verification of discrete event systems. In: Proceedings of the 30th International Workshop on Principles of Diagnosis DX’19. 2019 pp. 1-9.
• [44] Seatzu C, Silva M, van Schuppen J. Control of Discrete-Event Systems: Automata and Petri-Net Perspectives, volume 433 of Lecture Notes in Control and Information Sciences. Springer, London, 2013.
• [45] Hadjicostis CN. Estimation and Inference in Discrete Event Systems. Communications and Control Engineering. Springer Nature Switzerland AG, 2020.
• [46] Cabasino MP, Giua A, Lafortune S, Seatzu C. A new approach for diagnosability analysis of Petri nets using verifier nets. IEEE Transactions on Automatic Control, 2012. 57(12):3104-3117. doi:10.1109/TAC.2012.2200372.
• [47] Bérard B, Haar S, Schmitz S, Schwoon S. The complexity of diagnosability and opacity verification for Petri nets. Fundamenta Informaticae, 2018. 161(4):317-349.
• [48] Yin X, Lafortune S. On the decidability and complexity of diagnosability for labeled Petri nets. IEEE Transactions on Automatic Control, 2017. 62(11):5931-5938. doi:10.1109/TAC.2017.2699278.
• [49] Haar S. What topology tells us about diagnosability in partial order semantics. Discrete Event Dynamic Systems, 2012. 22(4):383-402. doi:10.1007/s10626-011-0121-z. URL https://doi.org/10.1007/s10626-011-0121-z.
• [50] Debouk R, Lafortune S, Teneketzis D. Coordinated decentralized protocols for failure diagnosis of discrete event systems. Discrete Event Dynamic Systems, 2000. 10(1):33-86. doi:10.1023/A:1008335115538. URL https://doi.org/10.1023/A:1008335115538.
• [51] Qiu W, Kumar R. Decentralized failure diagnosis of discrete event systems. IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 2006. 36:384-395.
• [52] Wang Y, Yoo TS, Lafortune S. Diagnosis of discrete event systems using decentralized architectures. Discrete Event Dynamic Systems, 2007. 17(2):233-263. doi:10.1007/s10626-006-0006-8. URL https://doi.org/10.1007/s10626-006-0006-8.
• [53] Moreira MV, Jesus TC, Basilio JC. Polynomial time verification of decentralized diagnosability of discrete event systems. IEEE Transactions on Automatic Control, 2011. 56(7):1679-1684. doi:10.1109/TAC.2011.2124950.
• [54] Cassez F. The complexity of codiagnosability for discrete event and timed systems. IEEE Transactions on Automatic Control, 2012. 57(7):1752-1764. doi:10.1109/TAC.2012.2183169.
• [55] Liu F. Predictability of failure event occurrences in decentralized discrete-event systems and polynomial-time verification. IEEE Transactions on Automation Science and Engineering, 2019. 16(1):498-504. doi:10.1109/TASE.2018.2868330.
• [56] Kumar R, Takai S. Decentralized prognosis of failures in discrete event systems. IEEE Transactions on Automatic Control, 2010. 55(1):48-59. doi:10.1109/TAC.2009.2034216.
• [57] Yin X, Li Z. Decentralized fault prognosis of discrete-event systems using state-estimate-based protocols. IEEE Transactions on Cybernetics, 2019. 49(4):1302-1313. doi:10.1109/TCYB.2018.2799961.
• [58] Ye L, Dague P, Nouioua F. Predictability analysis of distributed discrete event systems. In: 52nd IEEE Conference on Decision and Control. 2013 pp. 5009-5015. doi:10.1109/CDC.2013.6760675.
• [59] Shu S, Lin F. Co-detectability of multi-agent discrete event systems. In: 2011 Chinese Control and Decision Conference (CCDC). 2011 pp. 1708-1713. doi:10.1109/CCDC.2011.5968471.
• [60] Tripakis S. Undecidable problems of decentralized observation and control on regular languages. Information Processing Letters, 2004. 90(1):21-28. doi:https://doi.org/10.1016/j.ipl.2004.01.004. URL http://www.sciencedirect.com/science/article/pii/S0020019004000158.
• [61] Giua A, Mahulea C, Seatzu C. Decentralized observability of discrete event systems with synchronizations. Automatica, 2017. 85:468-476. doi:https://doi.org/10.1016/j.automatica.2017.08.009. URL http://www.sciencedirect.com/science/article/pii/S0005109817304302.
• [62] Keroglou C, Hadjicostis CN. Distributed fault diagnosis in discrete dvent systems via set intersection refinements. IEEE Transactions on Automatic Control, 2018. 63(10):3601-3607. doi:10.1109/TAC.2018.2799519.
• [63] Rampersad N, Shallit J. Detecting patterns in finite regular and context-free languages. Information Processing Letters, 2010. 110(3):108-112. doi:https://doi.org/10.1016/j.ipl.2009.11.002. URL http://www.sciencedirect.com/science/article/pii/S0020019009003238.
• [64] Kozen D. Lower Bounds for Natural Proof Systems. In: Proceedings of the 18th Annual Symposium on Foundations of Computer Science, SFCS ’77. IEEE Computer Society, Washington, DC, USA, 1977 pp. 254-266. doi:10.1109/SFCS.1977.16. URL http://dx.doi.org/10.1109/SFCS.1977.16.
• [65] Kari J. A Lecture Note on Automata and Formal Languages. http://users.utu.fi/jkari/automata/, 2016.
• [66] Ramadge PJ, Wonham W. Supervisory Control of a Class of Discrete Event Processes. SIAM Journal on Control and Optimization, 1987. 25(1):206-230. doi:10.1137/0325013. http://dx.doi.org/10.1137/0325013, URL http://dx.doi.org/10.1137/0325013.
• [67] Savitch WJ. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 1970. 4(2):177-192. doi:https://doi.org/10.1016/S0022-0000(70)80006-X. URL http://www.sciencedirect.com/science/article/pii/S002200007080006X.