AGRE%MIT-OZ@MIT-MC.ARPA (12/12/83)
From: Philip E. Agre <AGRE%MIT-OZ@MIT-MC.ARPA>
[Reprinted from the MIT-AI bboard.]
AI Revolving Seminar
Walter Hamscher
Diagnostic reasoning for digital devices with static storage elements
Wendesday 14 December 83 4PM
545 Tech Sq 8th floor playroom
We view diagnosis as a process of reasoning from anomalous observations to a
set of components whose failure could explain the observed misbehaviors. We
call these components "candidates." Diagnosing a misbehaving piece of
hardware can be viewed as a process of generating, discriminating among, and
refining these candidates. We wish to perform this diagnosis by using an
explicit representation of the hardware's structure and function.
Our candidate generation methodology is based on the notions of dependency
directed backtracking and local propagation of constraints. This
methodology works well for devices without storage elements such as
flipflops. This talk presents a representation for the temporal behavior of
digital devices which allows devices with storage elements to be treated
much the same as combinatorial devices for the purpose of candidate
generation.
However, the straightforward adaptation requires solutions to subproblems
that are severely underconstrained. This in turn leads to an overly
conservative and not terribly useful candidate generator. There exist
mechanism-oriented solutions such as value enumeration, propagation of
variables, and slices; we review these and then demonstrate what domain
knowledge can be used to motivate appropriate uses of those techniques.
Beyond this use of domain knowledge within the current representation, there
are alternative perspectives on the problem which offer some promise of
alleviating the lack of constraint.