Linear-Space Best-First Diagnosis Search
Keywords:Search-based Diagnosis, Time, Memory, And Solution Quality Trade-offs, Real-life Applications, Search In Boolean Satisfiability
AbstractVarious model-based diagnosis scenarios require the computation of the most preferred fault explanations. Existing algorithms that are sound (i.e., output only actual fault explanations) and complete (i.e., can return all explanations), however, require exponential space to achieve this task. As a remedy, to enable successful diagnosis on memory-restricted devices and for memory-intensive problem cases, we propose RBF-HS, a diagnostic search based on Korf’s seminal RBFS algorithm. RBF-HS can enumerate an arbitrary ﬁxed number of fault explanations in best-ﬁrst order within linear space bounds, without sacriﬁcing the desirable soundness or completeness properties. Evaluations using real-world diagnosis cases show that RBF-HS, when used to compute minimum-cardinality fault explanations, in most cases saves substantial space (up to 98 %) while requiring only reasonably more or even less time than Reiter’s HS-Tree, one of the most widely used diagnostic algorithms with the same properties.