This 1982 classic from the early days of AI research marks a pivotal shift in machine diagnosis. Instead of relying on a "cheat sheet" of empirical rules, the authors propose a system that understands how a machine is built and how it is supposed to behave, allowing it to deduce what is wrong when things deviate from the design.
The Shift to Model-Based Reasoning
In the early 1980s, expert systems (like MYCIN) were largely built on "empirical associations"—essentially a massive collection of rules derived from human experience. While effective for some tasks, this approach struggles with complex hardware because it doesn't "understand" the underlying machine. The authors identify two main failures in the status quo: rule-based systems are brittle (if a fault isn't in the rulebook, the system is blind), and traditional test generation is designed to detect if a specific fault exists, not to diagnose what the fault is based on observed misbehavior.
The challenge was to create a system that could reason from misbehavior to structural defect by comparing what a machine is doing against what its design says it should be doing.
Representing Structure and Behavior
The authors propose a framework built on three pillars:
- Structure Description: They developed a language to describe hardware hierarchically using modules, ports, and terminals. Crucially, they represent both the functional hierarchy (how logic flows) and the physical hierarchy (which gates are on which chips).
- Behavior Description: Behavior is modeled using constraints. For an adder, a constraint might say:
sum = input1 + input2. These are not just one-way functions; they are relationships. If you know the sum and one input, the system can infer what the other input should have been.
Diagnosis via Violated Expectations
Diagnosis happens by looking for contradictions. If the model expects a specific value at an output but measures something else, the system uses dependency tracking to look upstream. It identifies every component that contributed to that expected value and marks them as suspects.
As shown in the diagnostic scenario above, the system successfully narrows down suspects in a multi-stage circuit by identifying which components' outputs are consistent with the observed error and which are not. For example, if output F is expected to be 12 but is measured as 10, the system traces the inputs back through ADD-1 to MULT-1 and MULT-2.
Key Insights and Limitations
A core contribution of the paper is the distinction between the flow of electricity (how the device works) and the flow of inference (how we reason about the device). For example, an adder doesn't "do" subtraction, but a debugger can infer an input by subtracting the other input from the output.
However, the authors demonstrate that the "violated expectations" method fails when faced with bridging faults (wires touching that shouldn't) or power failures. These faults violate the "closed world" assumption of the schematic. The paper concludes that the next step for expert systems is explicit assumption management—the ability to list and retract simplifying assumptions when a diagnosis hits a dead end. This realization paved the way for more advanced Truth Maintenance Systems (TMS) and robust model-based diagnosis in the decades that followed.
Summary updated