Abstract
Model-based diagnosis is a principled and broadly applicable AI-based approach to tackle debugging problems in a wide range of areas including software, knowledge bases, circuits, cars, and robots. Whenever the sound and complete computation of fault explanations in a given preference order (e.g., cardinality or probability) is required, all existing diagnosis algorithms suffer from an exponential space complexity. This can prevent their application on memory-restricted devices and for memory-intensive problem cases. As a remedy, we propose RBF-HS, a diagnostic search based on Korf’s seminal RBFS algorithm which can enumerate an arbitrary fixed number of fault explanations in best-first order within linear space bounds, without sacrificing other desirable properties. Evaluations on real-world diagnosis cases show that RBF-HS, when used to compute minimum-cardinality fault explanations, in most cases saves substantial space while requiring only reasonably more or even less time than Reiter’s HS-Tree, one of the most influential diagnostic algorithms with the same properties.
Keywords
- Knowledge Representation and Reasoning: KRR: Diagnosis and abductive reasoning
- Knowledge Representation and Reasoning: KRR: Applications
- Knowledge Representation and Reasoning: KRR: Automated reasoning and theorem proving
- Knowledge Representation and Reasoning: KRR: Semantic Web
- Search: S: Applications
- Search: S: Combinatorial search and optimisation
- Search: S: Heuristic search
- Uncertainty in AI: UAI: Sequential decision making
