Diagnosing Tree Structured Systems

Abstract

This paper introduces the algorithm TREE DIAG for computing minimal diagnoses for tree structured systems. Diagnoses are computed by descending into the tree, enumerating the input combinations that might be reponsible for a given incorrect observation, and combining the diagnoses for the subtrees generating these inputs into diagnoses for the whole system. We prove soundness and correctness of the algorithm and show experimental results that indicate that it compares favorably to Reiter's hitting-set-based algorithm and El Fattah and Dechter's SAB. Extensions of the algorithm related to general acyclic systems, use of fault modes and the practical application to the software diagnosis domain are discussed. Keywords: Model-Based Diagnosis, Algorithms 1 Introduction Since the beginning of model-based diagnosis research, several attempts have been made to make model-based diagnosis of large systems feasible. This has been done by introducing probability measurements ([dK91]), by comput...