Abstract
Model-based diagnosis centers on the use of a behavioral model of a system to infer diagnoses of anomalous behavior. For model-based diagnosis techniques to become practical, some serious problems in the modeling of uncertainty and in the tractability of uncertainty management have to be addressed. These questions include: How can we tractably generate diagnoses in large systems? Where do the prior probabilities of component failure come from when modeling a system? How do we tractably compute low-cost repair plans? How can we do diagnosis even if only partial descriptions of device operation are available? This dissertation seeks to bring model-based diagnosis closer to being a viable technology by addressing these problems.
We address the tractability of model-based diagnosis in two complementary ways. We show how the structure of a hierarchical system specification can be exploited to yield an efficient diagnosis algorithm. We also develop polynomial-time algorithms to generate candidate diagnoses in decreasing order of likelihood. These candidates are then tested for consistency with observations. In effect, this gives us a generate-and-test scheme for enumerating diagnoses in decreasing order of plausibility. To help with modeling, we relate the prior probability of failure of a component to a temporal model of the failure process of the component. This work also gives us a principled way of modeling possible state changes in the system when performing diagnosis with multiple observations where each observation occurs at a different time. Turning to the repair problem, we develop a general-purpose algorithm for computing optimal repair plans. The algorithm makes no assumptions about the structure of the system model and hence has to exhaustively search through all possible plans. We go on to demonstrate an interesting and useful restriction on the system model which allows the optimal repair plan to be computed in polynomial time. To perform diagnosis when only partial device descriptions are available, we develop a way of ``completing'' the model such that repair cost estimates computed from the completed model are conservative upper bounds of the actual repair cost. We conclude with a discussion about promising extensions of this work.