OFAI

Technical Reports - Query Results

Your query term was 'number = 91-03'
1 report found
OFAI-TR-91-03 ( 73kB g-zipped PostScript file)

Controlling the Complexity in Model-Based Diagnosis

Igor Mozetic, Christian Holzbaur

We present IDA --- an Incremental Diagnostic Algorithm which computes minimal diagnoses from diagnoses, and not from conflicts. As a consequence of this, and by using different models, one can control the computational complexity. In particular, we show that by using a model of the normal behavior, 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. We propose to use a hierarchy of models: first a structural model to compute all minimal diagnoses, then a normal behavior model to find the additional diagnoses if needed, and only then a fault model for their verification. IDA separates model interpretation from the search for minimal diagnoses in the sense that the model interpreter is replaceable. In particular, we show that in some domains it is advantageous to use the Constraint Logic Programming system CLPB instead of a logic programming system like Prolog.

Citation: Mozetic I., Holzbaur C.: Controlling the Complexity in Model-Based Diagnosis, Annals of Mathematics and Artificial Intelligence 11 (1-4), pp. 297-314, 1994.