MergeXplain: Fast Computation of Multiple Conflicts for Diagnosis

Kostyantyn M. Shchekotykhin, Dietmar Jannach, Thomas SchmitzIJCAI 2015

Introduction

Model-Based Diagnosis (MBD) is a critical technique for identifying the root causes of failures in complex systems, ranging from digital circuits to large-scale software applications. At its core, MBD identifies conflicts—subsets of system components that cannot simultaneously function correctly given the observed errors. For years, Junker’s QuickXplain (QXP) has been the industry standard for identifying these conflicts. However, QXP is limited by its ability to find only one minimal conflict per execution. In systems with multiple overlapping faults, diagnosis engines must restart the search repeatedly, leading to significant computational redundancy.

The MergeXplain Algorithm

To address this inefficiency, the authors introduce MergeXplain (MXP), a "non-intrusive" algorithm designed to identify multiple minimal conflict sets in a single run. MXP evolves the classic divide-and-conquer approach into a "decompose-and-merge" strategy.

Decompose-and-Merge Strategy

Unlike QXP, which narrows down a single conflict, MXP recursively partitions the set of components into smaller, independent subproblems.

  1. Divide and Conquer: The problem is split into two halves ($C_1$ and $C_2$), and the algorithm recursively searches for conflicts within each.
  2. The Merge Step: While conflicts entirely contained within $C_1$ or $C_2$ are easily identified, some conflicts may "straddle" the boundary. MXP employs a specific loop and a modified QXP function to resolve these cross-boundary conflicts.
  3. Reasoner Independence: MXP is "non-intrusive," meaning it functions as a wrapper around any consistency checker (e.g., SAT solvers or constraint solvers) without requiring internal modifications.
Figure 1: Execution trace of the MergeXplain algorithm showing recursive decomposition and conflict identification.

Empirical Evaluation

The performance of MXP was evaluated against QXP using a diverse set of benchmarks, including synthetic systems from the DX Competition (DXC) 2011, challenging instances from the CSP Solver Competition 2008, and real-world spreadsheets with injected faults. The study also introduced PMXP, a parallelized version of the algorithm designed to leverage multi-core processors by searching independent subproblems simultaneously.

Key Results and Performance Gains

Empirical results demonstrate that MXP consistently outperforms QXP when multiple diagnoses are required. By identifying multiple conflicts early, MXP enables better "conflict reuse," preventing diagnosis trees from growing unnecessarily large. Furthermore, because consistency checks are computationally cheaper on smaller component subsets, MXP's decomposition strategy reduces overall processing time.

  • DXC Benchmarks: MXP achieved diagnosis speedups ranging from 15% to 45%.
  • CSP and Spreadsheets: In complex scenarios, such as the costasArray-13 benchmark, MXP achieved speedups of up to 54%.
  • Robustness: Unlike QXP, which is sensitive to the initial ordering of components, MXP provides more stable performance by exploring the search space more uniformly.
Figure 5: Performance comparison between QXP and MXP across CSP and spreadsheet scenarios, highlighting significant speedups.

Conclusion and Future Work

MergeXplain represents a significant advancement in diagnostic efficiency, particularly for complex systems with numerous faults. While MXP may introduce slight overhead in systems with only a single conflict, its ability to handle multiple conflicts simultaneously makes it superior for most real-world applications. Future research aims to refine "elimination strategies" to balance the speed of conflict resolution with the number of conflicts returned, further optimizing the diagnosis process for various domains.

Summary updated

BibTeX
@inproceedings{shchekotykhin2015mergexplain,
  author = {Kostyantyn M. Shchekotykhin and Dietmar Jannach and Thomas Schmitz},
  title = {{MergeXplain: Fast Computation of Multiple Conflicts for Diagnosis}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure