Abstract
The diagnosis problem amounts to deciding whether some specific “fault” event occurred or not in a system, given the observations collected on a run of this system. This system is then diagnosable if the fault can always be detected, and the active diagnosis problem consists in controlling the system in order to ensure its diagnosability. We consider here a stochastic framework for this problem: once a control is selected, the system becomes a stochastic process. In this setting, the active diagnosis problem consists in deciding whether there exists some observation-based strategy that makes the system diagnosable with probability one. We prove that this problem is EXPTIME-complete, and that the active diagnosis strategies are belief-based. The safe active diagnosis problem is similar, but aims at enforcing diagnosability while preserving a positive probability to non faulty runs, i.e. without enforcing the occurrence of a fault. We prove that this problem requires non belief-based strategies, and that it is undecidable. However, it belongs to NEXPTIME when restricted to belief-based strategies. Our work also refines the decidability/undecidability frontier for verification problems on partially observed Markov decision processes.
This work was supported by project ImpRo ANR-2010-BLAN-0317 and the European Union Seventh Framework Programme [FP7/2007-2013] under grant agreement 257462 HYCON2 NOE.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Baier, C., Bertrand, N., Grösser, M.: Probabilistic ω-automata. Journal of the ACM 59(1), 1–52 (2012)
Bertrand, N., Genest, B., Gimbert, H.: Qualitative determinacy and decidability of stochastic games with signals. In: Proceedings of LICS 2009, pp. 319–328. IEEE Computer Society (2009)
Cabasino, M., Giua, A., Lafortune, S., Seatzu, C.: Diagnosability analysis of unbounded Petri nets. In: Proceedings of CDC 2009, pp. 1267–1272. IEEE (2009)
Cassez, F., Tripakis, S.: Fault diagnosis with static and dynamic observers. Fundamenta Informaticae 88, 497–540 (2008)
Chanthery, E., Pencolé, Y.: Monitoring and active diagnosis for discrete-event systems. In: Proceedings of SP 2009, pp. 1545–1550. Elsevier (2009)
Chatterjee, K., Doyen, L., Gimbert, H., Henzinger, T.A.: Randomness for free. In: Hliněný, P., Kučera, A. (eds.) MFCS 2010. LNCS, vol. 6281, pp. 246–257. Springer, Heidelberg (2010)
Fabre, E., Jezequel, L.: On the construction of probabilistic diagnosers. In: Proceeeding of WODES 2010, pp. 229–234. Elsevier (2010)
Haar, S., Haddad, S., Melliti, T., Schwoon, S.: Optimal constructions for active diagnosis. In: Proceedings of FSTTCS 2013. LIPIcs, vol. 24, pp. 527–539. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013)
Morvan, C., Pinchinat, S.: Diagnosability of pushdown systems. In: Namjoshi, K., Zeller, A., Ziv, A. (eds.) HVC 2009. LNCS, vol. 6405, pp. 21–33. Springer, Heidelberg (2011)
Sampath, M., Lafortune, S., Teneketzis, D.: Active diagnosis of discrete-event systems. IEEE Transactions on Automatic Control 43(7), 908–929 (1998)
Sampath, M., Sengupta, R., Lafortune, S., Sinnamohideen, K., Teneketzis, D.: Diagnosability of discrete-event systems. IEEE Trans. Aut. Cont. 40(9), 1555–1575 (1995)
Thorsley, D., Teneketzis, D.: Diagnosability of stochastic discrete-event systems. IEEE Transactions on Automatic Control 50(4), 476–492 (2005)
Thorsley, D., Teneketzis, D.: Active acquisition of information for diagnosis and supervisory control of discrete-event systems. Journal of Discrete Event Dynamic Systems 17, 531–583 (2007)
Vardi, M.Y.: Automatic verification of probabilistic concurrent finite-state programs. In: Proceedings of FOCS 1985, pp. 327–338. IEEE Computer Society Press (1985)
Yoo, T.-S., Lafortune, S.: Polynomial-time verification of diagnosability of partially observed discrete-event systems. IEEE Trans. Automat. Contr. 47(9), 1491–1495 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bertrand, N., Fabre, É., Haar, S., Haddad, S., Hélouët, L. (2014). Active Diagnosis for Probabilistic Systems. In: Muscholl, A. (eds) Foundations of Software Science and Computation Structures. FoSSaCS 2014. Lecture Notes in Computer Science, vol 8412. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-54830-7_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-54830-7_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-54829-1
Online ISBN: 978-3-642-54830-7
eBook Packages: Computer ScienceComputer Science (R0)