/*-------------------------------------------------------------*/
/* Model-Based Diagnosis in NCL */
/* (C) 1993 Zdravko Markov, II-BAS */
/*-------------------------------------------------------------*/
/*
DESCRIPTION:
-----------
This program illustrates the use of the NCL spreading activation
mechanism for a typical constraint solving task - model-based
diagnosis. We use the definition of the problem as described by
Reiter (Reiter, R., A Theory of Diagnosis from First Principles,
Artificial Intelligence, 32:57-95, 1987). A model of a system is
a triple , where SD is a system description, COMPS
is an n-tuple of the states (normal or abnormal) of
the system components, and OBS, observations, is an m-tuple
, containing the system inputs and outputs.
We discuss a binary adder built out of five functional elements -
two XOR gates (X1, X2), two AND gates (A1, A2) and an OR gate
(O1), and has three inputs (In1, In2, In3), and two outputs
(Out1, Out2). The system description comprises a net-clause and
Prolog procedures (defining the functional elements used).
Each system component is represented by a spreading activation
node, where the node procedure defines its functionality. The
component connectors are represented by net-variables. Each
component is activated when two of its three input/outputs are
bound (the threshold is 2). Thus a component can both calculate
a Boolean function and check the consistency of the values
supplied at its input/outputs. The states of the system
components (COMPS = ) are represented by
net-variables bound by the corresponding Prolog predicates
"xorg", "andg" and "org". Each one of the latter is defined by
three clauses, and thus each component can have three states -
normal (ok), abnormal (ab), and don't care state (free state
variable). A component is in a normal state, when the
corresponding Boolean function (xor, and, or) is satisfied,
otherwise it is in an abnormal state (strong fault model).
The third state happens when at least one of the component
input/output variables is free (unbound).
The advantage of this model is that it can infer diagnoses
(COMPS) from the observations (OBS). An important feature of
these diagnoses is that they are minimal (a minimal diagnosis
is such that, changing a status of any abnormal component to
normal would make the diagnosis inconsistent with the
observations). This feature is due to the use of a third state
of the components. Usually the components used in the model-based
diagnosis has two states (normal and abnormal) and the system
description (e.g. a constraint logic program) is used to test
whether an observation is consistent with a diagnosis. Then the
problem is to find a proper algorithm for searching through the
space of possible diagnoses (usually viewed as a lattice). Our
approach extends the system description so that it can infer
minimal diagnoses directly. The basic idea is that when a
component is in a normal or in an abnormal state its
input/outputs are fully determined (bound), and hence no change
of the component state is possible, without a change of the
states of the neighboring components. (This property is ensured
by the global consistency of the net-clauses.) The state
variables X1, X2, A1, A2, O1 are bound only in these cases, and
since the spreading activation node indicating the diagnoses is
activated only when all state variables are bound (its threshold
is equal to the number of variables), it is clear that only
minimal diagnoses are inferred.
*/
/*-------------------------------------------------------------*/
/*------------------------ Net-clause -------------------------*/
obs(In1,In2,In3,Out1,Out2): /* OBS */
node(In1,In2,A,2,xorg(In1,In2,A,X1)): /* X1 */
node(In3,A,Out1,2,xorg(In3,A,Out1,X2)): /* X2 */
node(In1,In2,B,2,andg(In1,In2,B,A1)): /* A1 */
node(In3,A,C,2,andg(In3,A,C,A2)): /* A2 */
node(B,C,Out2,2,org(B,C,Out2,O1)): /* O1 */
node(X1,X2,A1,A2,O1,5,assertz(comps(X1,X2,A1,A2,O1))). /*COMPS */
/*----------------- Delivering the diagnoses ------------------*/
diagnoses(A,B,C,D,E,_):-top(T),obs(A,B,C,D,E),spread(T),fail.
diagnoses(A,B,C,D,E,L):-setof(comps(X1,X2,A1,A2,O1),
comps(X1,X2,A1,A2,O1),L),
delete(comps).
/*--------------------- System Components ---------------------*/
/* XOR gate */
xorg(X,Y,Z,ok):-xor(X,Y,Z).
xorg(X,Y,Z,ab):-not xor(X,Y,Z).
xorg(X,Y,Z,_):-var(X);var(Y);var(Z).
/* AND gate */
andg(X,Y,Z,ok):-and(X,Y,Z).
andg(X,Y,Z,ab):-not and(X,Y,Z).
andg(X,Y,Z,_):-var(X);var(Y);var(Z).
/* OR gate */
org(X,Y,Z,ok):-or(X,Y,Z).
org(X,Y,Z,ab):-not or(X,Y,Z).
org(X,Y,Z,_):-var(X);var(Y);var(Z).
/*--------------------- Boolean Functions ---------------------*/
/* XOR function */
xor(0,0,0).
xor(0,1,1).
xor(1,0,1).
xor(1,1,0).
/* AND function */
and(0,0,0).
and(0,1,0).
and(1,0,0).
and(1,1,1).
/* OR function */
or(0,0,0).
or(0,1,1).
or(1,0,1).
or(1,1,1).
/*--------------------------------------------------------------*/
/* EXAMPLES: */
/*--------------------------------------------------------------*/
?- netmode(0). /* Breadth-first mode only ! */
?- diagnoses(1,0,1,1,0,COMPS). /* Infer all diagnoses */
/*
COMPS=[comps(ab,ok,ok,ok,ok),comps(ok,ab,ok,ab,ok),
comps(ok,ab,ok,ok,ab)]
*/