Approximate model-based diagnosis using greedy stochastic search

DOI10.1613/JAIR.3025zbMATH Open1210.68036arXiv1401.3848OpenAlexW3102281800WikidataQ129559910 ScholiaQ129559910MaRDI QIDQ3579359FDOQ3579359

Authors: Alexander Feldman, Gregory M. Provan, Arjan J. C. van Gemund 

Publication date: 6 August 2010

Published in: Journal of Artificial Intelligence Research (Search for Journal in Brave)

Abstract: We propose a StochAstic Fault diagnosis AlgoRIthm, called SAFARI, which trades off guarantees of computing minimal diagnoses for computational efficiency. We empirically demonstrate, using the 74XXX and ISCAS-85 suites of benchmark combinatorial circuits, that SAFARI achieves several orders-of-magnitude speedup over two well-known deterministic algorithms, CDA* and HA*, for multiple-fault diagnoses; further, SAFARI can compute a range of multiple-fault diagnoses that CDA* and HA* cannot. We also prove that SAFARI is optimal for a range of propositional fault models, such as the widely-used weak-fault models (models with ignorance of abnormal behavior). We discuss the optimality of SAFARI in a class of strong-fault circuit models with stuck-at failure modes. By modeling the algorithm itself as a Markov chain, we provide exact bounds on the minimality of the diagnosis computed. SAFARI also displays strong anytime behavior, and will return a diagnosis after any non-trivial inference time.

Full work available at URL: https://arxiv.org/abs/1401.3848

Recommendations

• Diagnosing multiple faults
• Controlling the complexity in model-based diagnosis
• Diagnosing tree-structured systems
• scientific article; zbMATH DE number 1168533
• How many diagnoses do we need?

zbMATH Keywords

SAFARIStochAstic Fault diagnosis AlgoRIthm

Mathematics Subject Classification ID

Reliability, testing and fault tolerance of networks and computer systems (68M15)

Cited In (7)

• Sensor selection for fault diagnosis in uncertain systems
• Batch repair actions for automated troubleshooting
• How many diagnoses do we need?
• Efficient suspect selection in unreachable state diagnosis
• A model-based active testing approach to sequential diagnosis
• From causes for database queries to repairs and model-based diagnosis and back
• Model-based diagnosis with probabilistic models

Uses Software

• MiniSat

This page was built for publication: Approximate model-based diagnosis using greedy stochastic search

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3579359)