Abstract
Diagnosis is the task of explaining the abnormal behavior of a system based on a symptom. In a discrete-event system (DES), the symptom is a temporal sequence of observations. At the occurrence of each observation, the diagnosis engine has to output a set of candidate diagnoses, each candidate being a set of faults. This process requires deep (and costly) model-based reasoning, hence a variety of knowledge compilation techniques have been proposed to speed it up. A novel technique for DES diagnosis that exploits knowledge compilation is presented, which is sound and complete irrespective of the diagnosability of the DES. The DES model is compiled offline into a temporal dictionary, a deterministic finite automaton whose regular language equals the (possibly infinite) set of symptoms of the DES. When the DES is being monitored online, a temporal explanation is generated efficiently at the occurrence of each observation. The correctness of the diagnosis results is supported by abduction-based backward-pruning.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
More specifically, the set of candidate diagnoses produced by the diagnoser approach may be neither sound nor complete in case the DES cannot be affected by multiple faults of the same type and the system can follow distinct trajectories leading to the same global state, all producing the same symptom while being characterized by distinct sets of faults.
- 2.
Implicitly, all states of \({\mathcal {X}}^*\) are also accepting (final) states.
- 3.
Hence, the notion of a trajectory is applicable to the strings in the regular language of \({\mathcal {X}}^+\) also.
- 4.
According to the Subset Construction determinization algorithm [7], each state of the DFA is identified by a subset of the states of the NFA.
- 5.
It should be clear that the consistent expansion of the sets of candidate diagnoses is only a necessary condition for a temporal explanation, not a sufficient one.
- 6.
Ironically, Yamamoto did not approve the decision to go to war with the United States because he was convinced that Japan would lose this war.
References
Baroni, P., Lamperti, G., Pogliano, P., Zanella, M.: Diagnosis of large active systems. Artif. Intell. 110(1), 135–183 (1999). https://doi.org/10.1016/S0004-3702(99)00019-3
Brand, D., Zafiropulo, P.: On communicating finite-state machines. J. ACM 30(2), 323–342 (1983). https://doi.org/10.1145/322374.322380
Cassandras, C., Lafortune, S.: Introduction to discrete event systems. In: The Kluwer International Series in Discrete Event Dynamic Systems, vol. 11. Kluwer Academic, Boston (1999). https://doi.org/10.1007/978-0-387-68612-7
Cimatti, A., Pecheur, C., Cavada, R.: Formal verification of diagnosability via symbolic model checking. In: Eighteenth International Joint Conference on Artificial Intelligence (IJCAI 2003), pp. 363–369 (2003)
Console, L., Picardi, C., Ribaudo, M.: Diagnosis and diagnosability using PEPA. In: Fourteenth European Conference on Artificial Intelligence (ECAI 2000), pp. 131–135. IOS Press, Amsterdam (2000)
Hamscher, W., Console, L., de Kleer, J. (eds.): Readings in Model-Based Diagnosis. Morgan Kaufmann, San Mateo (1992)
Hopcroft, J., Motwani, R., Ullman, J.: Introduction to Automata Theory, Languages, and Computation, 3rd edn. Addison-Wesley, Reading (2006)
Jiang, S., Huang, Z., Chandra, V., Kumar, R.: A polynomial algorithm for testing diagnosability of discrete event systems. IEEE Trans. Autom. Control 46(8), 1318–1321 (2001)
Klein, G.: Seeing What Others Don’t. PublicAffairs, New York (2013)
Lamperti, G., Quarenghi, G.: Intelligent monitoring of complex discrete-eventsystems. In: Czarnowski, I., Caballero, A., Howlett, R., Jain, L. (eds.) Intelligent Decision Technologies 2016, Smart Innovation, Systems and Technologies, vol. 56, pp. 215–229. Springer, Basel (2016).https://doi.org/10.1007/978-3-319-39630-9_18
Lamperti, G., Zanella, M.: Diagnosis of discrete-event systems from uncertain temporal observations. Artif. Intell. 137(1–2), 91–163 (2002). https://doi.org/10.1016/S0004-3702(02)00123-6
Lamperti, G., Zanella, M.: Diagnosis of Active Systems: Principles and Techniques. Springer International Series in Engineering and Computer Science, vol. 741. Springer, Dordrecht (2003). https://doi.org/10.1007/978-94-017-0257-7
Lamperti, G., Zanella, M.: EDEN: an intelligent software environment for diagnosis of discrete-event systems. Appl. Intell. 18, 55–77 (2003)
Lamperti, G., Zanella, M.: A bridged diagnostic method for the monitoring of polymorphic discrete-event systems. IEEE Trans. Syst. Man Cybern. Part B: Cybern. 34(5), 2222–2244 (2004)
Lamperti, G., Zanella, M.: Monitoring of active systems with stratified uncertain observations. IEEE Trans. Syst. Man Cybern. Part A: Syst. Hum. 41(2), 356–369 (2011). https://doi.org/10.1109/TSMCA.2010.2069096
Lamperti, G., Zanella, M., Zhao, X.: Abductive diagnosis of complex active systems with compiled knowledge. In: Thielscher, M., Toni, F., Wolter, F. (eds.) Principles of Knowledge Representation and Reasoning: Proceedings of the Sixteenth International Conference (KR2018), pp. 464–473. AAAI Press, Tempe (2018)
Lamperti, G., Zanella, M., Zhao, X.: Introduction to Diagnosis of Active Systems. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-92733-6
Lamperti, G., Zanella, M., Zhao, X.: Knowledge compilation techniques for model-based diagnosis of complex active systems. In: Holzinger, A., Kieseberg, P., Tjoa, A.M., Weippl, E. (eds.) Machine Learning and Knowledge Extraction. Lecture Notes in Computer Science, vol. 11015, pp. 43–64. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-99740-7_4
Lamperti, G., Zhao, X.: Diagnosis of complex active systems with uncertain temporal observations. In: Buccafurri, F., Holzinger, A., Tjoa, A.M., Weippl, E. (eds.) Availability, Reliability, and Security in Information Systems. Lecture Notes in Computer Science, vol. 9817, pp. 45–62. Springer (2016). https://doi.org/10.1007/978-3-319-45507-5_4
Lamperti, G., Zhao, X.: Viable diagnosis of complex active systems. In: IEEE International Conference on Systems, Man, and Cybernetics (SMC 2016), Budapest, pp. 457–462 (2016). https://doi.org/10.1109/SMC.2016.7844282
Liu, F., Qiu, D.: Diagnosability of fuzzy discrete-event systems: a fuzzy approach. IEEE Trans. Fuzzy Syst. 17, 372–384 (2009). https://doi.org/10.1109/TFUZZ.2009.2013840
Paoli, A., Lafortune, S.: Diagnosability analysis of a class of hierarchical state machines. J. Discrete Event Dyn. Syst.: Theor. Appl. 18(3), 385–413 (2008)
Pencolé, Y.: Diagnosability analysis of distributed discrete event systems. In: Sixteenth European Conference on Artificial Intelligence (ECAI 2004), Valencia, Spain, pp. 43–47 (2004)
Pencolé, Y., Steinbauer, G., Mühlbacher, C., Travé-Massuyès, L.: Diagnosing discrete event systems using nominal models only. In: 28th International Workshop on Principles of Diagnosis (DX 2017), Brescia, Italy, pp. 169–183 (2017)
Reiter, R.: A theory of diagnosis from first principles. Artif. Intell. 32(1), 57–95 (1987)
Rintanen, J., Grastien, A.: Diagnosability testing with satisfiability algorithms. In: 20th International Joint Conference on Artificial Intelligence (IJCAI 2007), Hyderabad, India, pp. 532–537 (2007)
Sampath, M., Lafortune, S., Teneketzis, D.: Active diagnosis of discrete-event systems. IEEE Trans. Autom. Control 43(7), 908–929 (1998)
Sampath, M., Sengupta, R., Lafortune, S., Sinnamohideen, K., Teneketzis, D.: Diagnosability of discrete-event systems. IEEE Trans. Autom. Control 40(9), 1555–1575 (1995)
Sampath, M., Sengupta, R., Lafortune, S., Sinnamohideen, K., Teneketzis, D.: Failure diagnosis using discrete-event models. IEEE Trans. Control Syst. Technol. 4(2), 105–124 (1996)
Schumann, A., Huang, J.: A scalable jointree algorithm for diagnosability. In: Twenty-Third National Conference on Artificial Intelligence (AAAI 2008), Chicago, IL, pp. 535–540 (2008)
Su, X., Zanella, M., Grastien, A.: Diagnosability of discrete-event systems with uncertain observations. In: 5th International Joint Conference on Artificial Intelligence (IJCAI 2016), New York, NY, pp. 1265–1571 (2016)
Thorsley, D., Teneketzis, D.: Diagnosability of stochastic discrete-event systems. IEEE Trans. Autom. Control 50, 476–492 (2005). https://doi.org/10.1109/TAC.2005.844722
Ye, L., Dague, P., Yan, Y.: An incremental approach for pattern diagnosability in distributed discrete event systems. In: 21st IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2012), Newark, NJ, pp. 123–130 (2009). https://doi.org/10.1109/ICTAI.2009.75
Yoo, T., Lafortune, S.: Polynomial-time verification of diagnosability of partially observed discrete-event systems. IEEE Trans. Autom. Control 47(9), 1491–1495 (2002)
Acknowledgments
This work was supported in part by Lombardy Region (Italy) within the project Smart4CPPS, Linea Accordi per Ricerca, Sviluppo e Innovazione, POR-FESR 2014-2020 Asse I.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Bertoglio, N., Lamperti, G., Zanella, M., Zhao, X. (2020). Escaping Diagnosability and Entering Uncertainty in Temporal Diagnosis of Discrete-Event Systems. In: Bi, Y., Bhatia, R., Kapoor, S. (eds) Intelligent Systems and Applications. IntelliSys 2019. Advances in Intelligent Systems and Computing, vol 1038. Springer, Cham. https://doi.org/10.1007/978-3-030-29513-4_62
Download citation
DOI: https://doi.org/10.1007/978-3-030-29513-4_62
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-29512-7
Online ISBN: 978-3-030-29513-4
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)