Efficient Sequential Model-Based Fault-Localization with Partial Diagnoses

Kostyantyn M. Shchekotykhin, Thomas Schmitz, Dietmar JannachIJCAI 2016

Abstract

Model-Based Diagnosis (MBD) is a critical framework for identifying faults in complex systems, yet its application in sequential diagnosis is often limited by the computational cost of generating optimal queries. This paper introduces MXP-HS-DFS, an algorithm that leverages "partial diagnoses" to accelerate the localization process. By focusing on a subset of minimal conflicts rather than the entire search space, MXP-HS-DFS achieves significant speedups—up to 98% in some cases—while maintaining the soundness and completeness required to identify the true preferred diagnosis. Evaluations on ontology and digital circuit benchmarks demonstrate the algorithm's ability to handle complex systems that were previously computationally intractable.

Introduction

In complex systems like software architectures or large-scale digital circuits, identifying the root cause of unexpected behavior is a significant challenge. Model-Based Diagnosis (MBD) provides a logical framework for this task, but the search space for potential diagnoses can be overwhelming. Sequential diagnosis addresses this by iteratively querying an oracle (e.g., a human expert) to narrow down possibilities. However, the standard requirement to compute a set of "leading diagnoses" before each query often leads to significant latency, making interactive sessions unusable for large-scale problems.

Methodology: The MXP-HS-DFS Approach

The authors propose a paradigm shift from computing full diagnoses to utilizing partial diagnoses. The MXP-HS-DFS algorithm incorporates three primary innovations:

  1. Partial Diagnoses: Utilizing the MergeXplain tool, the algorithm identifies a small subset of minimal conflicts. It then calculates hitting sets (partial diagnoses) for only this subset, drastically reducing the initial search space.
  2. Iterative Refinement: These partial diagnoses are used to generate the next best query. As the oracle provides answers, the system updates its knowledge and refines the diagnoses, only searching for additional conflicts when the current set is insufficient.
  3. Guaranteed Correctness: Despite the use of incomplete information at intermediate steps, the authors provide mathematical proof that the method is complete and will always converge on the correct preferred diagnosis.

Experimental Evaluation

The effectiveness of MXP-HS-DFS was tested on two distinct "hard" problem domains: ontologies from the OAEI Conference benchmark and digital circuits from the DX Competition (DXC) 2011 Synthetic Track.

Key Results

The performance improvements were dramatic across both datasets. In the ontology domain, the method achieved an average 83% speedup in computation time. For the most complex ontology tested, the calculation time dropped from approximately 16 minutes to just 23 seconds.

Table 3: Performance comparison of INV-HS-DFS and MXP-HS-DFS on ontology benchmarks.

In the digital circuit domain, the average performance improvement was 57%. The scalability of the partial diagnosis approach was particularly evident in the most difficult circuit test (c7552), where the previous state-of-the-art method (INV-HS-DFS) failed to find a diagnosis within 24 hours, while MXP-HS-DFS successfully localized the fault.

Table 4: Performance comparison of INV-HS-DFS and MXP-HS-DFS on digital circuit benchmarks.

Importantly, the reduction in computation time did not negatively impact the interaction quality; the number of queries (#Q) required remained comparable to exhaustive methods, ensuring a win-win for both system efficiency and user experience.

Conclusion and Future Work

MXP-HS-DFS demonstrates that "less is more" when it comes to diagnostic search spaces. By focusing on a small window of conflicts, the algorithm maintains high-quality query generation while bypassing the computational bottlenecks of exhaustive search. Future research will focus on incorporating prior probabilities to further enhance query informativeness and exploring domain-specific structural optimizations to refine the conflict splitting process.

Summary updated

BibTeX
@inproceedings{shchekotykhin2016efficient,
  author = {Kostyantyn M. Shchekotykhin and Thomas Schmitz and Dietmar Jannach},
  title = {{Efficient Sequential Model-Based Fault-Localization with Partial Diagnoses}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure