Characterizing Diagnoses

Johan de Kleer, Alan K. Mackworth, Raymond ReiterAAAI 1990

Abstract

This seminal paper addresses a fundamental flaw in traditional model-based diagnosis: the assumption that any superset of a diagnosis is also a valid diagnosis. The authors demonstrate that this "subset/superset" property fails when systems include detailed fault models or exoneration rules. To resolve this, they introduce kernel diagnoses, a robust characterization based on the prime implicants of logical conflicts, providing a complete and parsimonious way to describe all possible system states.

The Failure of the Subset/Superset Assumption

In early diagnostic reasoning, researchers assumed that if a set of broken components explained a symptom, any larger set containing those components would also be a valid explanation. For example, if a car won't start because of a dead battery, it is technically true that it won't start if the battery is dead and the radio is broken.

However, the authors show that as soon as you add "fault models" (specific descriptions of how a part behaves when it fails) or "exoneration" (rules stating a part must be working if a certain signal is observed), this logic collapses. In complex systems, assuming too many parts are broken can create a logical contradiction with the observations. The "minimal diagnosis" approach is therefore inadequate for modern, detailed system descriptions.

The Two-Inverter Circuit used to demonstrate how specific fault models (e.g., "shorted" vs "stuck-at-0") break the minimal diagnosis assumption.

Methodology: Kernel Diagnoses

The authors utilize a first-order logic framework to redefine the diagnostic task. A system is defined as a triple $(SD, COMPS, OBS)$—the system description, the components, and the observations.

The core of their approach involves "conflicts," which are disjunctions of abnormality literals ($AB(c)$ or $ eg AB(c)$) logically entailed by the system. Unlike minimal diagnoses, which only look at positive literals (what is broken), kernel diagnoses are the prime implicants of the set of all minimal conflicts. This allows the system to handle "partial" information, leaving the status of certain components uncommitted if their state does not affect the diagnosis.

Benchmark Evaluations

As a theoretical paper, the authors evaluate their logic using classic benchmark circuits common in symbolic AI:

  • The Two-Inverter Circuit: Used to demonstrate how fault models break the minimal diagnosis assumption (see Figure 1).
  • The Polybox (Adder/Multiplier) Circuit: A standard diagnostic benchmark used to show how kernel diagnoses correspond to traditional minimal diagnoses when only "correct behavior" is modeled.
The Polybox (Adder/Multiplier) Circuit, a standard diagnostic benchmark used to demonstrate the correspondence between kernel and minimal diagnoses in simplified models.

Key Insights and Results

  • The Death of the Superset Assumption: A superset of a diagnosis is not necessarily a diagnosis. If we know a component cannot behave a certain way when failed, assuming it is failed might contradict observations.
  • Generalization: If all conflicts in a system are "positive" (only containing $AB$ literals), then kernel diagnoses and minimal diagnoses are identical. The kernel approach is a true generalization.
  • Parsimony through Partiality: A kernel diagnosis is "partial"—it only specifies the status of components that must be known to explain the observations. This is more efficient than listing every possible combination of "don't care" components.
  • Logical Mapping: By framing diagnosis as finding prime implicants, the authors connected AI diagnosis to decades of research in hardware logic minimization (Boolean algebra).

Conclusion and Future Work

The authors prove that any valid diagnosis for a system is "covered" by at least one kernel diagnosis, making the kernel set a complete characterization. While mathematically sound, finding these diagnoses is computationally equivalent to finding prime implicants, which is NP-hard. The paper suggests that future work must involve "focusing strategies"—using probabilities or structural hierarchies to identify the most relevant conflicts first, rather than attempting to find all of them in a brute-force manner.

Summary updated

BibTeX
@inproceedings{kleer1990characterizing,
  author = {Johan de Kleer and Alan K. Mackworth and Raymond Reiter},
  title = {{Characterizing Diagnoses}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1990},
}
Figure