Technical Reports - Query Results

Your query term was 'number = 92-26'
1 report found
OFAI-TR-92-26 ( 76kB g-zipped PostScript file)

A Polynomial-Time Algorithm for Model-Based Diagnosis

Igor Mozetic

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 CLPB, analog circuits by CLPR, and physiological models in medicine by constraints over finite domains.

Citation: Mozetic I.: A Polynomial-Time Algorithm for Model-Based Diagnosis, Extended version of a paper in Proc. 10th European Conf. on Artificial Intelligence, ECAI-92, pp. 729-733, Vienna, Austria, John Wiley and Sons, 1992.