Active diagnosis for probabilistic systems

Nathalie Bertrand 1 Eric Fabre 1 Stefan Haar 2, 3 Serge Haddad 2, 3 Loïc Hélouët 1
1 SUMO - SUpervision of large MOdular and distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL
2 MEXICO - Modeling and Exploitation of Interaction and Concurrency
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
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 {\em 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.
Type de document :
Communication dans un congrès
Anca Muscholl. 17th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS'14), Apr 2014, Grenoble, France. Springer, 2014, Proceedings of FOSSACS 2014. 〈10.1007/978-3-642-54830-7_2 〉
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00930919
Contributeur : Loic Helouet <>
Soumis le : mardi 14 janvier 2014 - 16:34:14
Dernière modification le : jeudi 11 janvier 2018 - 06:25:25
Document(s) archivé(s) le : mardi 15 avril 2014 - 16:27:05

Fichier

long.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Nathalie Bertrand, Eric Fabre, Stefan Haar, Serge Haddad, Loïc Hélouët. Active diagnosis for probabilistic systems. Anca Muscholl. 17th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS'14), Apr 2014, Grenoble, France. Springer, 2014, Proceedings of FOSSACS 2014. 〈10.1007/978-3-642-54830-7_2 〉. 〈hal-00930919〉

Partager

Métriques

Consultations de la notice

459

Téléchargements de fichiers

166