  The goal of model-based diagnosis is to isolate causes of anomalous system
behavior and recommend inexpensive repair actions in response. 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 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 large 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.
