Abstract
Model-based diagnosis of analog circuits faces a significant challenge: the combinatorial explosion of predictions when reasoning with inequalities. This paper introduces Skordos, a system that manages this complexity through two primary mechanisms: hibernation, which deactivates redundant predictions, and interaction restructuring, which transforms the computational complexity of Kirchhoff’s Current Law (KCL) from exponential to quadratic.
Introduction
In digital circuit diagnosis, state variables are discrete (0 or 1). However, in the analog domain, values are continuous and often uncertain, leading to predictions expressed as inequalities (e.g., $v < 3.2$). When using a Truth Maintenance System (TMS) for diagnosis, every prediction is tied to a set of assumptions about component health. A major challenge arises: a single variable can have dozens of valid but overlapping inequality predictions. This leads to a "prediction explosion," especially when applying Kirchhoff’s Current Law (KCL) at a circuit node.
The Problem: Prediction Explosion
If a node has $n$ terminals and each terminal has $m$ active predictions, calculating all possible combinations results in $n \times m^{n-1}$ computations—a disastrous number for even small circuits. For example, if we know $v < 5$ (based on component A) and $v < 6$ (based on component B), we cannot simply discard the latter. If component A is later found to be faulty, the $v < 5$ prediction vanishes, and the system must rely on the $v < 6$ prediction.
Methods for Complexity Control
The author proposes two primary techniques to regain control over these computations:
1. Hibernation and Subsumption
Hibernation is a process where the system "deactivates" less precise predictions. A prediction is put into hibernation if it is mathematically weaker than an existing active prediction and does not provide new diagnostic information. These hibernated predictions are stored but not propagated, reactivating only if the stronger predictions they rely on are retracted. A specific case is subsumption, where a prediction $\Psi_1$ subsumes $\Psi_2$ if $\Psi_1$ is mathematically stronger and its set of assumptions is a subset of $\Psi_2$’s.
2. Restructuring Interactions
To solve the KCL bottleneck, the author restructures the $n$-terminal node into a network of intermediate "symbolic" nodes that converge in groups of three. This allows hibernation to act as an "early filter." Instead of combining all terminals at once, the system combines them incrementally, pruning useless intermediate results at each step.
Key Results and Insights
The restructuring of circuit nodes transforms the computational cost of KCL from exponential ($O(n \cdot m^{n-1})$) to quadratic ($O(n \cdot m^2)$). For a typical node with 6 inputs and 6 predictions per terminal, the number of computations drops from 46,656 down to 432. This represents a roughly 100-fold increase in efficiency, making real-time analog diagnosis significantly more plausible.
The core philosophy is the "Just-in-Case" Principle: weak information cannot be discarded because stronger information might be retracted if a component is found faulty. Hibernation provides a middle ground, keeping weak info available without wasting CPU cycles until it is actually needed.
Conclusion
Skordos demonstrates that the computational explosion of KCL is not an inherent law of analog diagnosis but a result of representation. By breaking complex multi-way interactions into a series of 3-way interactions and applying diagnosis-driven activation, the system maintains efficiency even in complex analog environments. Future work may extend these techniques to Kirchhoff’s Voltage Law (KVL) and specific faulty behavioral modes.
Summary updated