Abstract
Model-based diagnosis (MBD) traditionally treats faulty component behavior as entirely unknown, which often leads to weak diagnostic discrimination. This paper formalizes the "non-intermittency" assumption—the principle that a faulty component's output remains a consistent function of its inputs over time. By incorporating this axiom into an Assumption-based Truth Maintenance System (ATMS), the authors enable the generation of cross-time logical conflicts. Experimental results on digital circuits demonstrate that this approach can eliminate over 20% of incorrect diagnoses and drastically reduce the number of physical probes needed to isolate a fault.
Introduction: The Problem of Intermittency
In model-based diagnosis, the General Diagnostic Engine (GDE) typically assumes that a faulty component can exhibit any behavior. While robust, this "unknown mode" assumption fails to leverage the repeatable nature of many physical failures. Without a consistency assumption, observations at different time steps remain isolated, lacking the "temporal glue" necessary to narrow down potential causes. For instance, if a logic gate consistently produces the same incorrect output for a given input across multiple trials, a human expert would quickly identify it as the culprit, whereas a standard GDE might maintain a large set of possible candidates.
Formalizing Non-Intermittency
The authors extend the MBD framework by introducing a specific axiom: a component’s output is a fixed (though unknown) function of its inputs.
- Functional Representation: They define a function $F$ such that for a non-intermittent component $c$, the output at any time $t$ is $Out(c, t) = F(c, In_1(c, t), ..., In_k(c, t))$.
- ATMS Integration: To implement this, "time-tokens" are introduced as ATMS assumptions. These tokens represent specific observation moments, allowing the system to track state across time.
- Inference and Substitution: New inference rules allow the ATMS to perform "substitution of equals." If a component receives identical inputs at $T_1$ and $T_2$, the system infers that the outputs must also be identical. Any deviation creates a logical conflict that can eliminate the component from the set of consistent diagnoses.
Experimental Evaluation
The methodology was evaluated using simulated digital circuits, focusing on "stuck-at" faults where a signal line is permanently held at 0 or 1. The primary test cases included:
- Or-Xor Circuit: A simple structure used for initial logical verification.
- A2 (Adder Circuit): A small-scale adder used to measure diagnostic precision.
- P3 (Parity Circuit): A small parity checker circuit.
Key Results and Insights
The inclusion of the non-intermittency assumption yielded significant improvements in diagnostic efficiency. In the A2 adder circuit, the engine eliminated approximately 20% of incorrect diagnoses after six sets of observations, while the P3 circuit saw a 24% reduction.
More impressively, the average number of external probes required to identify a fault in the A2 circuit dropped from 10.0 to 3.6. Beyond quantitative metrics, the paper offers several conceptual insights:
- The "Middle Ground": Non-intermittency provides a bridge between complete ignorance (unknown modes) and perfect knowledge (predictive fault models).
- Consistency as a Modeling Choice: Intermittency is often a symptom of an incomplete model (e.g., ignoring temperature or internal state).
- Defeasibility: The authors treat non-intermittency as a retractable assumption, allowing the system to revert to intermittent models if no consistent explanation is found.
Limitations and Future Directions
While effective for combinational logic, the current formalization does not yet account for components with internal memory, such as flip-flops. Additionally, the computational overhead of managing cross-time conflicts in the ATMS must be balanced against the savings in physical probing. Future work aims to extend these principles to sequential circuits and larger, more complex systems.
Summary updated