Introduction
Model-Based Diagnosis (MBD) is a fundamental framework for identifying the root causes of malfunctions in complex systems, ranging from digital circuits to software architectures. By comparing observed faulty behavior against a formal model of intended system operation, MBD generates a set of potential fault hypotheses, known as diagnoses. In many real-world scenarios, the initial diagnostic process yields multiple competing hypotheses. To isolate the true cause, practitioners employ sequential diagnosis, which involves posing a series of queries to an oracle—such as a physical probe, a software test, or a human expert.
However, determining the "optimal" query—the one that maximizes information gain while minimizing cost—is an NP-hard problem. This paper presents a novel systematic search technique designed to overcome the computational bottlenecks of existing sequential diagnosis methods.
The Challenge of Query Selection
Existing approaches to sequential diagnosis often suffer from three primary limitations:
- Computational Bottlenecks: Most methods rely on frequent and expensive calls to logical reasoners (e.g., SAT or SMT solvers) to validate potential queries.
- Lack of Generality: Many algorithms are tailored to specific logic formalisms or system types, limiting their utility across diverse domains.
- Scalability Issues: When the space of possible queries is massive or not explicitly defined, traditional methods often fail to find optimal solutions within reasonable timeframes.
Proposed Methodology: Systematic Search
The author introduces a one-step lookahead query computation technique based on systematic search. While one-step lookahead is a common heuristic, this approach optimizes the process through several key innovations:
Systematic Exploration and Implicit Spaces
Unlike myopic heuristics that may overlook optimal queries, this algorithm systematically explores the query space. Crucially, it operates over an implicit query space, allowing it to navigate vast numbers of potential tests without the need to enumerate them beforehand. This ensures that the search remains exhaustive yet computationally feasible.
Inference Minimization
The primary innovation lies in the reduction of logical inference calls. Since logical reasoning is the most computationally expensive part of the diagnostic process, the algorithm is specifically structured to minimize these calls, performing only the bare necessity required to guarantee query optimality.
Logic-Agnostic Framework
Built upon Reiter’s classic theory of diagnosis, the proposed framework is "logic-agnostic." It is compatible with any monotonic knowledge representation language, allowing it to be integrated into various existing diagnosis engines without requiring a rewrite of the underlying system model.
Performance and Results
The approach was evaluated using a benchmark of real-world diagnosis problems. The results demonstrate significant improvements over the previous state-of-the-art in three key areas:
- Speed: The method outperforms existing techniques by orders of magnitude in terms of computation time. The time required to find an optimal query remained consistently low, regardless of the complexity of the benchmark problem.
- Quality: Despite the increase in speed, the method maintains or improves the quality of the selected queries, ensuring that the sequential diagnosis process remains as efficient as possible in terms of the number of tests required.
- Scalability: The performance characteristics suggest that this method is highly suitable for large-scale industrial applications where previous methods would typically time out.
Conclusion
By decoupling the search process from the underlying logic and focusing on the minimization of expensive inferences, this paper provides a highly efficient and universal tool for the MBD community. While the current work focuses on one-step lookahead, the efficiency gains achieved here lay the groundwork for future exploration into multi-step lookahead strategies, which could further optimize the path to system recovery.
Summary updated