Memory-Limited Model-Based Diagnosis (Extended Abstract)

Patrick RodlerIJCAI 2023 · DOI

TL;DR

This paper introduces RBF-HS, a novel diagnostic search algorithm that significantly reduces memory requirements for model-based diagnosis problems, making it suitable for memory-constrained devices. RBF-HS achieves this by adapting Korf's linear-space best-first search algorithm, offering a practical solution to a long-standing memory bottleneck in the field.

What Problem Does This Paper Address?

Model-based diagnosis (MBD) is a powerful AI technique for identifying faults in complex systems, from software to hardware. A core challenge in MBD is efficiently finding "diagnoses" – sets of components that, if faulty, explain observed system behavior. When we need to find all minimal diagnoses, or find them in a specific order (e.g., by likelihood or cardinality), existing algorithms often suffer from exponential space complexity. This makes them impractical for memory-limited environments like IoT devices or for diagnosing very large systems. The paper aims to bridge this gap by developing a diagnostic algorithm that maintains desirable properties like completeness and best-first ordering while operating within linear space bounds.

Methods

The paper proposes RBF-HS (Recursive Best-First Hitting Set Search), an algorithm that adapts Richard Korf's seminal RBFS algorithm for pathfinding to the domain of diagnosis. RBFS is known for its ability to perform best-first search in linear space by intelligently managing its search frontier and backtracking.

RBF-HS modifies RBFS to handle the specific needs of diagnosis:

  • Diagnosis-Specific Node Labeling: Instead of just paths, RBF-HS deals with sets of components as potential diagnoses.
  • Multiple Solutions: It's designed to find multiple diagnoses, not just a single path.
  • Best-First Ordering: It enumerates diagnoses in a preferred order (e.g., minimal cardinality first).
  • Soundness and Completeness: It guarantees that all minimal diagnoses are found and that no incorrect diagnoses are reported.

The core idea is to leverage RBFS's memory-efficient search strategy while incorporating the principles of hitting-set-based diagnosis algorithms. This allows RBF-HS to explore the diagnosis search space without the exponential memory blow-up.

Datasets

The evaluation was conducted on 12 real-world diagnosis problems (DPIs) from benchmark collections commonly used in knowledge-based systems. These problems are representative of those encountered in critical applications like medical systems, where soundness, completeness, and generality are crucial. No new datasets were introduced.

Key Insights and Ideas

  • Linear Space is Achievable for Best-First Diagnosis: The paper demonstrates that the memory limitations of existing best-first diagnosis algorithms are not inherent to the problem but can be overcome by adapting efficient search strategies like RBFS.
  • Trade-off Between Space and Time: RBF-HS often trades a small increase in computation time for substantial memory savings, a highly desirable trade-off in memory-constrained scenarios.
  • Broad Applicability Beyond Diagnosis: The core technique of RBF-HS is a general optimal hitting-set computation algorithm. This means it can be applied to a wide range of other NP-hard problems beyond MBD, including (Max)SAT, constraint satisfaction, and optimization problems.

Key Results

Experiments comparing RBF-HS to HS-Tree (a prominent state-of-the-art algorithm with similar properties) showed:

  • Significant Space Savings: RBF-HS achieved an average space saving of 93% and up to 98% compared to HS-Tree.
  • Reasonable Time Overhead: While RBF-HS sometimes took longer, the time overhead was generally modest.
  • Improved Performance in Some Cases: In 38% of the cases, RBF-HS was both faster and used less memory than HS-Tree.
  • Solves Previously Intractable Problems: In several instances, HS-Tree ran out of memory (even with 32GB), while RBF-HS successfully solved the problem with negligible memory usage.

Limitations and Future Work

  • Extended Abstract Scope: The authors note that this is an extended abstract and the full paper contains more details, including a second algorithm (HBF-HS) that combines RBF-HS with HS-Tree to optimize computation time while still preserving memory solvability.
  • Further Evaluation: The full paper includes more comprehensive evaluations, different heuristics, and discussions on particularly hard diagnostic problem cases.
  • Debugging Tool Integration: The authors are working on integrating RBF-HS and HBF-HS into the OntoDebug tool for ontology debugging.

Summary updated

BibTeX
@inproceedings{rodler2023memory,
  author = {Patrick Rodler},
  title = {{Memory-Limited Model-Based Diagnosis (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/789},
}
Figure