Sound, Complete, Linear-Space, Best-First Diagnosis Search
This addresses memory-intensive diagnosis scenarios, enabling use on memory-restricted devices, though it is incremental as it builds on existing algorithms like RBFS and HS-Tree.
The paper tackles the problem of computing the most preferred fault explanations in model-based diagnosis, which existing sound and complete algorithms require exponential space for. The result is RBF-HS, a method that enumerates fault explanations in best-first order within linear space bounds, saving up to 98% space in evaluations while maintaining soundness and completeness.
Various 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 method based on Korf's well-known RBFS algorithm. RBF-HS can enumerate an arbitrary fixed number of fault explanations in best-first order within linear space bounds, without sacrificing 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, a commonly used and as generally applicable sound, complete and best-first diagnosis search.