Efficient Model Based Diagnosis with Maximum Satisfiability
Model-Based Diagnosis (MBD) is a critical task in identifying malfunctions within complex systems by comparing observed behaviors against theoretical models. While Maximum Satisfiability (MaxSAT) solvers offer a powerful framework for finding minimal cardinality diagnoses, they often encounter scalability bottlenecks in large-scale circuits. This paper introduces Dominator-Oriented Encoding (DOE), a novel approach that leverages structural circuit analysis to simplify MBD problems before logical solving. By integrating graph dominators and value propagation, DOE achieves performance improvements of up to three orders of magnitude over existing state-of-the-art tools.
The Challenge of Model-Based Diagnosis
MBD aims to find the smallest set of components whose failure explains the discrepancy between a system's expected and observed outputs. In a logical framework, this is typically modeled by assuming all components are healthy (represented as "soft clauses") and requiring the model to be consistent with observations (hard clauses). A MaxSAT solver then attempts to satisfy the maximum number of health assumptions, effectively minimizing the number of diagnosed faults.
As systems grow, the number of soft clauses—and thus the search space—increases dramatically. Previous SAT-based diagnostic tools often struggle with the sheer volume of variables and clauses required to represent complex modern circuits.
Dominator-Oriented Encoding (DOE)
The core contribution of this work is the Dominator-Oriented Encoding (DOE) method. Rather than passing a raw logical model to a solver, DOE performs structural preprocessing to prune the problem space.
The preprocessing involves several key techniques:
- Dominator Analysis: In circuit topology, if every path from component $A$ to an output passes through component $B$, then $B$ dominates $A$. For top-level diagnoses, dominated gates can be assumed healthy ("hardened"), reducing the number of soft clauses the solver must evaluate.
- Backbone Node Identification: Components with fixed output values (constants) given specific inputs and observations are identified and encoded as hard unit clauses.
- Edge Blocking and Filtering: If a component's output is insensitive to a specific input due to "controlling" values elsewhere, that connection is considered "blocked." Nodes with all outgoing paths blocked are "filtered" and removed from the encoding.
- Iterative Simplification: These steps are applied iteratively. A discovered backbone node might reveal a new blocked edge, which in turn might expose a new dominator, leading to a highly compressed logical model.
Experimental Evaluation and Results
The authors evaluated DOE using two benchmark suites: ISCAS85 (standard baseline circuits) and ITC99 (challenging circuits with up to 50 concurrent faults).
The structural preprocessing provided by DOE leads to massive efficiency gains. On the ISCAS85 benchmarks, the DOE-based solver, wboinc, outperformed the previous state-of-the-art tool, scrypto, in 99.9% of test cases, frequently achieving speedups of 100x to 1000x.
On the more rigorous ITC99 suite, the performance gap was even more pronounced. While the previous state-of-the-art could only solve approximately 62.4% of instances within a 600-second timeout, the DOE approach successfully solved over 90% of the problems. This success is attributed to the significant reduction in encoding size; in many instances, the number of variables was halved, and the number of critical soft clauses was reduced by two-thirds.
Conclusion
By bridging the gap between structural graph analysis and logical MaxSAT solving, Dominator-Oriented Encoding offers a significant leap forward for Model-Based Diagnosis. The synergy between topological pruning and core-guided MaxSAT solvers allows for the efficient diagnosis of large-scale systems that were previously computationally intractable. Future work will focus on integrating these optimizations directly into unified diagnostic frameworks to create even more robust tools.
Summary updated