Sequential Diagnosis by Abstraction
  When a system behaves abnormally, sequential diagnosis takes a sequence of
measurements of the system until the faults causing the abnormality are
identified, and the goal is to reduce the diagnostic cost, defined here as the
number of measurements. To propose measurement points, previous work employs a
heuristic based on reducing the entropy over a computed set of diagnoses. This
approach generally has good performance in terms of diagnostic cost, but can
fail to diagnose large systems when the set of diagnoses is too large. Focusing
on a smaller set of probable diagnoses scales the approach but generally leads
to increased average diagnostic costs. In this paper, we propose a new
diagnostic framework employing four new techniques, which scales to much larger
systems with good performance in terms of diagnostic cost. First, we propose a
new heuristic for measurement point selection that can be computed efficiently,
without requiring the set of diagnoses, once the system is modeled as a
Bayesian network and compiled into a logical form known as d-DNNF. Second, we
extend hierarchical diagnosis, a technique based on system abstraction from our
previous work, to handle probabilities so that it can be applied to sequential
diagnosis to allow larger systems to be diagnosed. Third, for the largest
systems where even hierarchical diagnosis fails, we propose a novel method that
converts the system into one that has a smaller abstraction and whose diagnoses
form a superset of those of the original system; the new system can then be
diagnosed and the result mapped back to the original system. Finally, we
propose a novel cost estimation function which can be used to choose an
abstraction of the system that is more likely to provide optimal average cost.
Experiments with ISCAS-85 benchmark circuits indicate that our approach scales
to all circuits in the suite except one that has a flat structure not
susceptible to useful abstraction.
