Memory-limited model-based diagnosis

摘要

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, and to enable successful diagnosis both on memory-restricted devices and for memory-intensive problem cases, we propose two novel diagnostic search algorithms which build upon tried and tested techniques from the heuristic search domain. The first method, dubbed Recursive Best-First Hitting Set Search (RBF-HS), is based on Korf's well-known Recursive Best-First Search (RBFS) algorithm. We show that RBF-HS can enumerate an arbitrary predefined finite number of fault explanations in best-first order within linear space bounds, without sacrificing the desirable soundness or completeness properties. The second algorithm, called Hybrid Best-First Hitting Set Search (HBF-HS), is a hybrid between RBF-HS and Reiter's seminal HS-Tree. The idea is to find a trade-off between runtime optimization and a restricted space consumption that does not exceed the available memory. Notably, both suggested algorithms are generally applicable to any model-based diagnosis problem, regardless of the used (monotonic) logical language to describe the diagnosed system and of the used reasoning mechanism.