When a complex system breaks down—whether it is a space robot, a digital circuit, or the human body—identifying the root cause is fundamentally a search problem. In a system with dozens or hundreds of interacting components, the number of potential multi-fault combinations grows exponentially. If every component can either be healthy or faulty, a system with $n$ components yields $2^n$ possible states.
Early diagnostic AI systems attempted to explicitly list or evaluate these combinations to find the most likely explanation. However, this approach quickly hits a computational wall. To make diagnosis tractable in large-scale systems, researchers realized they needed to change how the system "thinks" about the space of possibilities. Instead of explicitly enumerating every individual combination of faults, modern diagnostic frameworks use compact, factored, and implicit representations to manage massive hypothesis spaces efficiently.
The Core Intuition: Volumes Instead of Points
The fundamental breakthrough in this domain is shifting from representing a diagnosis as a collection of individual points (specific combinations of faults) to representing them as structured volumes.
Consider a patient with two unrelated symptoms: a broken arm and a cough. The causes for the broken arm (e.g., a fall, a sports injury) are completely independent of the causes for the cough (e.g., a cold, allergies). If there are 3 possible causes for the arm injury and 3 for the cough, there are $3 \times 3 = 9$ possible joint diagnoses.
In an ad-hoc rule-based system, an algorithm might evaluate all 9 combinations. But as Reggia et al. demonstrated in A New Inference Method for Frame-Based Expert Systems, we can represent this differential diagnosis compactly using generators—the Cartesian products of sets of alternative causes. Instead of storing 9 distinct pairs, the system stores two small sets and multiplies them implicitly.
Explicit Representation (9 items):
{(Fall, Cold), (Fall, Allergies), (Fall, Flu), (Sports, Cold), ...}
Factored Representation (1 item, implicit space):
{Fall, Sports, Accident} × {Cold, Allergies, Flu}
This factored approach exploits the "lumpy," modular structure of real-world domains. As Wu proved in Domain Structure and the Complexity of Diagnostic Problem Solving, real-world data naturally clusters into independent sub-problems. By representing the solution space as a Cartesian product of these independent local differentials, the space complexity can be reduced to a fraction of what explicit generation requires.
In Efficient Diagnosis of Multiple Disorders Based on a Symptom Clustering Approach, Wu noted that managing solution sets as structured volumes allows algorithms to prune entire aggregates of candidates simultaneously. If a new piece of evidence rules out "Fall," the system eliminates an entire dimension of the Cartesian product at once, avoiding the need to touch individual combinations. This exact mechanism is what enables large-scale industrial applications; for instance, Guo et al. applied Cartesian products of suspicious component sets in Large Scale Diagnosis Using Associations between System Outputs and Components to maintain a compact memory footprint when diagnosing massive digital circuits.
Exploiting Indeterminacy: The "Don't Care" Component
Another way to compress a massive hypothesis space is to avoid specifying the status of components that have no bearing on the observed symptoms.
In a seminal paper, de Kleer et al. introduced this concept via "kernel diagnoses" in Characterizing Diagnoses. Traditional model-based diagnosis often looked for minimal diagnoses—the smallest set of broken parts that could explain a failure. However, this breaks down when we have information about how components behave when they fail.
Instead of forcing a binary choice (healthy vs. faulty) on every single component in a system, the authors proposed using partial assignments. A kernel diagnosis only specifies the status of components that are strictly necessary to explain the observations, leaving all other components uncommitted or designated as "don't care."
For example, if a space robot's arm fails to move, and we determine that the joint motor is broken, the status of the camera on the robot's head is irrelevant to this specific failure. A partial assignment states: [Motor = Broken, Camera = Uncommitted]. This single partial assignment implicitly represents both fully specified states ([Motor = Broken, Camera = Healthy] and [Motor = Broken, Camera = Broken]). By focusing only on essential assignments, the system completely bypasses the exponential explosion of listing irrelevant component permutations.
Symbolic Compilation: Boolean Consequences and Scenarios
If Cartesian products represent the space as a geometric volume, and partial assignments represent it by dropping dimensions, symbolic compilation represents the space as a logical formula.
In Model-Based Diagnosis using Causal Networks, Darwiche showed that system failure states can be mapped directly to compact boolean expressions, termed "consequences." By leveraging the topological structure of causal networks, the author demonstrated that these symbolic expressions can encode the entire set of possible diagnoses. Because these boolean formulas can be simplified using standard logical identities (like $A \lor \neg A = \text{True}$), they remain highly compact, preventing the computational bottlenecks typical of traditional assumption-based labels while retaining all information needed to extract the most likely faults.
A parallel approach was developed by Portinale et al. in Diagnosis as a Variable Assignment Problem: A Case Study in a Space Robot Fault Diagnosis. Framing diagnosis as a variable assignment problem, the authors grouped individual diagnoses into scenarios formulated as Conjunctive Normal Form (CNF) expressions.
Instead of overwhelming a human operator or a downstream planning system with a massive list of individual fault combinations, a CNF scenario packages consistent states together. This explicitly highlights remaining areas of uncertainty or indeterminacy within the system without enumerating every permutation, making the diagnostic output highly tractable for complex domains like space robotics.
Why It Works: The Power of Factored Inputs
The unifying thread across these diverse techniques is that they replace explicit, flat representations with structured, implicit ones. This insight is so powerful that its mathematical utility extends beyond diagnosis into pure computer science. For example, in the field of fine-grained complexity, Dalirrooyfard et al. demonstrated in New Techniques for Proving Fine-Grained Average-Case Hardness that representing problem inputs in a factored form allows a single structured element to represent a massive set of standard inputs. This maintains high expressivity while simplifying complex algorithmic reductions.
In diagnostic reasoning, compact representations work because they align perfectly with the physics of the systems being diagnosed. Real-world systems are not fully connected webs of chaos; they are structured networks of localized interactions. By using Cartesian products, partial assignments, and boolean expressions, our diagnostic representations mirror this underlying structure—allowing us to reason about vast, combinatorial spaces of failure by only ever calculating the pieces that matter.
Key Foundational Work
A New Inference Method for Frame-Based Expert Systems (1983) — contributed 2 concept elements to this direction.
Specialized Strategies: An Alternative to First Principles in Diagnostic Problem Solving (1988) — contributed 2 concept elements to this direction.