A Polynomial-Time Algorithm for Model-Based Diagnosis

We present IDA --- an Incremental Diagnostic Algorithm which computes minimal diagnoses from diagnoses, and not from conflicts. As a consequence, by using a `weak' fault model, the worst-case complexity of the algorithm to compute the k+1-st minimal diagnosis is O(n 2k ), where n is the number of components. On the practical side, an experimental evaluation indicates that the algorithm can efficiently diagnose devices consisting of a few thousand components. IDA separates model interpretation from the search for minimal diagnoses in the sense that the model interpreter is replaceable. This fits well into the Constraint Logic Programming modeling paradigm where, for example, combinatorial circuits are modeled by CLP(B), analog circuits by CLP(!), and physiological models in medicine by constraints over finite domains. 1 Introduction Model-based diagnosis is the activity of locating malfunctioning components of a system solely on the basis of its structure and behavior. There are two..