Model-based diagnosis using causal networks
Adnan Y. Darwiche · 1995
This paper rests on several contributions. First, we introduce the notion of a consequence, which is a boolean expression that characterizes consistency-based diagnoses. Second, we introduce a basic algorithm for computing consequences when the system description is structured using a causal network. We show that if the causal network has no undirected cycles, then a consequence has a linear size and can be computed in linear time. Finally, we show that diagnoses characterized by a consequence and meeting some preference criterion can be extracted from the consequence in time linear in its size. A dual set of results is provided for abductive diagnosis. 1 Introduction This paper presents an approach for computing diagnoses [ Reiter, 1987; de Kleer et al., 1992 ] when the system description is structured using a causal network --- Figures 1 and 2 depict examples of structured system descriptions. The most common approach for computing diagnoses has been the use of Assumption-Based Tr...