Exploiting System Hierarchy to Compute Repair Plans in Probabilistic
Model-Based Diagnosis
Sampath Srinivas
Computer Science Department
Stanford University
Stanford, California 94305
Eric Horvitz
Decision Theory & Adaptive Systems Group
Microsoft Research
Redmond, Washington 98052-6399
Author Email: srinivas@cs.stanford.edu, horvitz@microsoft.com
Abstract:
The goal of model-based diagnosis is to isolate causes of anomalous system behavior and recommend cost-effective repair actions. In general, precomputing optimal repair policies is intractable. To date, investigators addressing this problem have
explored approximations that either impose restrictions on the system model, such as a single fault assumption,
or that compute an immediate best action with limited lookahead. In this paper, we develop a formulation of repair in model-based diagnosis and
a repair algorithm that computes optimal sequences of actions. This optimal approach is costly but can be applied to precompute an optimal repair strategy for compact systems. We show how we can exploit a
hierarchical system specification to make this approach tractable for larger systems.
When introducing hierarchy, we also consider the tradeoff between simply replacing a component and decomposing it to repair its subcomponents. The hierarchical repair algorithm is suitable for off-line
precomputation of an optimal repair strategy.
A modification of the algorithm takes advantage of an iterative-deepening scheme to trade off inference time and the quality of the computed strategy.
Click here to access postscript file.
Keywords: Theorem proving, time-critical reasoning, Bayesian methods, decision making under bounded resources, decision-theoretic methods
In: Proceedings of Eleventh Conference on Uncertainty in Artificial Intelligence, Montreal, August 1995, pages 523-531. Morgan Kaufmann: San Francisco.