Hierarchical Model-Based Diagnosis based on Structural Abstraction

Abstraction has been advocated as one of the main remedies for the computational complexity of model-based diagnosis. However, after the seminal work published in the early nineties, little research has been devoted to this topic. In this paper, we consider one of the types of abstraction commonly used in diagnosis, i.e., structural abstraction, investigating it both from a theoretical and practical point of view. First, we provide a new formalization for structural abstraction that generalizes and extends previous ones. Then, we present two new different techniques for model- based diagnosis that automatically derive easier-to-diagnose versions of a (hierarchical) diagnosis problem on the basis of the available observations. The two proposed techniques are formulated as extensions of the well-known Mozetic’s algorithm [I. Mozetic, Hierarchical diagnosis, in: W.H.L. Console, J. de Kleer (Eds.), Readings in Model-Based Diagnosis, Morgan Kaufmann, San Mateo, CA, 1992, pp. 354–372], and experimentally contrasted with it to evaluate the obtained efficiency gains.