---
title: "An Improved Constraint-Propagation Algorithm for Diagnosis"
authors:
  - "Hector Geffner"
  - "Judea Pearl"
doi: ""
url: "https://ijcai.org/proceedings/1987/224"
pdf: "https://ijcai.org/proceedings/1987/0224.pdf"
venue: "Proceedings of the Tenth International Joint Conference on Artificial Intelligence"
year: 1987
pages: "1105-1110"
track: "Reasoning"
keywords:
---

# An Improved Constraint-Propagation Algorithm for Diagnosis

Hector Geffner, Judea Pearl

*Proceedings of the Tenth International Joint Conference on Artificial Intelligence*, pages 1105-1110.

## Abstract

Diagnosing a system requires the identification of a set of components whose abnormal behavior could explain the faulty system behavior. Previously, model-based diagnosis schemes have proceeded through a cycle of assumptions -+ predictions -+ observations -+ assumptions-adjustment, where the basic assumptions entail the proper functioning of those components whose failure is not established. Here we propose a scheme in which every component's status is treated as a variable; therefore, predictions covering all possible behavior of the system can be generated. Remarkably, the algorithm exhibits a drastic reduction in complexity for a large family of system-models. Additionally, the intermediate computations provide useful guidance for selecting new tests. The proposed scheme may be considered as either an enhancement of the scheme proposed in [de Kleer, 1986) or an adaptation of the probabilistic propagation scheme proposed in [Pearl, 1986) for the diagnosis of deterministic systems.