Abstract Model-Based Diagnosis (MBD) is a fundamental technique for identifying faulty components in complex systems, such as digital circuits, by comparing observed behavior against a theoretical model. While utilizing multiple system observations can significantly improve diagnostic accuracy, it often introduces a "state explosion" problem where the logical model becomes too bloated for standard solvers. This paper introduces two novel compacted models—CMMO (Compacted Model with Multiple Observations) and D-CMMO (Dominated-based CMMO)—designed to handle multiple observations efficiently. By sharing variables across observations and leveraging gate dominance to prune the search space, these models achieve runtimes up to five orders of magnitude faster than existing state-of-the-art algorithms.
The Challenge of Multi-Observation Diagnosis
In Model-Based Diagnosis, the goal is to find a minimal set of components whose failure explains the discrepancy between expected and observed system outputs. When multiple sets of inputs and outputs (observations) are available, the diagnostic task becomes more precise but computationally harder.
Traditional approaches often fall into one of two traps. First, "bloated models" replicate the entire system description for every single observation, leading to a massive number of logical constraints (clauses) that overwhelm SAT and MaxSAT solvers. Second, hitting-set algorithms like HSD, while effective for single faults, struggle to scale as the number of injected faults increases. The researchers sought a way to capture the information from multiple observations without this exponential growth in complexity.
CMMO and Selective Re-encoding
The first proposed solution, CMMO, addresses the redundancy inherent in multiple observations. In most cases, different observations of a failing system share a vast amount of identical internal state. CMMO identifies the specific inputs that differ between observations and only re-encodes the "Propagation Edges" and "Nodes"—the logic cones directly affected by those changes.
By using a variable mapping technique called VarMapping, CMMO allows the majority of the system model to share variables across all observations. This selective encoding allows a single MaxSAT formula to represent dozens or hundreds of observations with only a fraction of the memory and logic required by traditional replication.
D-CMMO and Gate Dominance
Building upon CMMO, the authors introduced D-CMMO, which incorporates the concept of gate dominance. In digital circuits, certain gates "dominate" others; if a dominant gate fails, its failure can explain observed symptoms more broadly than the failure of the gates it dominates.
D-CMMO computes a Top-Level Diagnosis (TLD) by encoding dominated components as "hard clauses" (assumed to be healthy unless proven otherwise). This strategy effectively prunes the search space for the MaxSAT solver, preventing it from getting bogged down in redundant sub-diagnoses that do not contribute to identifying the root cause.
Performance Benchmarks
The researchers evaluated CMMO and D-CMMO using the ISCAS-85 benchmark, a standard set of combinational circuits. They generated 300 test cases per fault model (Stuck-at-0, Stuck-at-1, and Flipped) with 20 to 50 injected faults and up to 234 observations per case.
The experimental results demonstrated a clear advantage for the compacted models:
- Success Rate: D-CMMO solved 92.1% of all instances within a 1000-second time limit, compared to only 64.9% for the state-of-the-art HSD algorithm.
- Speedup: Both CMMO and D-CMMO were frequently 1 to 5 orders of magnitude faster than HSD and IHSD.
- Scalability: While traditional algorithms like DC and DC* failed on almost all large-scale instances, the proposed models handled complex circuits with dozens of faults effectively.
Conclusion
The introduction of CMMO and D-CMMO represents a significant step forward in making Model-Based Diagnosis practical for large-scale systems with multiple observations. By eliminating logical redundancy and using structural properties like gate dominance to prune the search space, these models allow for rapid and accurate fault identification. Future work will focus on refining variable selection strategies and exploring even more aggressive pruning techniques for extremely complex circuits.
Summary updated