UNI-MB - logo
UMNIK - logo
 
(UM)
  • Controlling the complexity in model-based diagnosis
    Mozetič, Igor ; Holzbauer, Christian
    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 behaviour, the worst-case complexity of the algorithm to compute the k + 1st minimal diagnosis is 0(n[up]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 behaviour 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 dioagnoses in the sense that the model intepreter is replaceable. In particular, we show that in some domains it is advantageous to use the constraint logic programming system CLP(B) instead of a logic programming system like Prolog.
    Type of material - article, component part
    Publish date - 1994
    Language - english
    COBISS.SI-ID - 43126273