8.3. Abduction and diagnostic reasoning#
Abduction extends default reasoning by not only making assumptions about what is false, but also about what is true. For instance, in the light bulb example given earlier, we know that if the light bulb is broken, the light doesn’t switch on. If we observe that the light doesn’t switch on, a possible explanation is that the light bulb is broken. Since this is only one of the possible explanations, it cannot be guaranteed to be true. For instance, there might be a problem with the power supply instead, or the switch might be broken.
The general problem of abduction can be stated as follows. Given a \(Theory\) and an \(Observation\), find an \(Explanation\) such that
i.e. the \(Observation\) follows logically from the \(Theory\) extended with the \(Explanation\). For instance, if \(Theory\) consists of the following clauses
likes(peter,S):-student_of(S,peter).
likes(X,Y):-friend(Y,X).
and we have the \(Observation\) likes(peter,paul), then possible \(Explanations\) are { student_of(paul,peter) } and { friend(paul,peter) }.
Other \(Explanations\) which satisfy the problem specification are { likes(X,paul) } and { likes(X,Y):-friendly(Y), friendly(paul) }. However, abductive explanations are usually restricted to ground literals with predicates that are undefined in \(Theory\) (such literals are called abducibles). Inferring general rules from specific observations is called induction, and is discussed in the next chapter.
Procedurally, we can construct an abductive explanation by trying to prove the \(Observation\) from the initial \(Theory\) alone: whenever we encounter a literal for which there is no clause to resolve with, we add the literal to the \(Explanation\). This leads to the following abductive meta-interpreter.
% abduce(O,E) <- observation O follows by SLD-resolution
% from the theory defined by clause/2,
% extended with a list of unit clauses E
abduce(O,E):-
abduce(O,[],E).
% with accumulator for explanations
abduce(true,E,E):-!.
abduce((A,B),E0,E):-!,
abduce(A,E0,E1),
abduce(B,E1,E).
abduce(A,E0,E):-
cl(A,B), % query clauses enumerated by cl/2
abduce(B,E0,E).
abduce(A,E,E):-
element(A,E).
abduce(A,E,[A|E]):-
not element(A,E),
abducible(A).
abducible(A):-
not cl(A,_B).
The last two clauses of abduce/3 extend the original depth-first meta-interpreter. The program uses an accumulator containing the partial explanation found so far, such that literals are not unnecessarily duplicated in the final explanation. The query
?-abduce(likes(peter,paul),Explanation).
results in the answers
Explanation = [student_of(paul,peter)];
Explanation = [friend(paul,peter)]
Interestingly, this abductive meta-interpreter also works for general clauses, but it does not always produce correct explanations. For instance, suppose the initial \(Theory\) contains a general clause:
flies(X):-bird(X),not abnormal(X).
abnormal(X):-penguin(X).
bird(X):-penguin(X).
bird(X):-sparrow(X).
If asked to explain flies(tweety), the above program will try to find a clause explaining not(abnormal(tweety)); since there is no such clause, this negated literal will be added to the explanation. As a result, the program will give the following explanations:
Explanation = [not abnormal(tweety),penguin(tweety)];
Explanation = [not abnormal(tweety),sparrow(tweety)]
There are two problems with these explanations. First of all, the first explanation is inconsistent with the theory. Secondly, abnormal/1 is not an abducible predicate, and should not appear in an abductive explanation. For these reasons, we have to deal explicitly with negated literals in our abduction program.
As a first try, we can extend our abductive meta-interpreter with negation as failure, by adding the following clause (see also Section 3.8):
abduce(not(A),E,E):- % E explains not(A)
not abduce(A,E,E). % if E doesn't explain A
In order to prevent the query abducible(not(A)) from succeeding, we change the definition of abducible/1 to
abducible(A):-
A \= not(B),
not cl(A,B).
With this extended abductive meta-interpreter, the query
?-abduce(flies(tweety),Explanation).
now results in the following, correct answer:
Explanation = [sparrow(tweety)]
The explanation [penguin(tweety)] is found to be inconsistent, since
?-abduce(not(abnormal(tweety)),
[penguin(tweety)],[penguin(tweety)]).
will fail, as it should.
However, this approach relies on the fact that negated literals are checked after the abductive explanation has been constructed. To illustrate this, suppose that \(Theory\) is extended with the following clause:
flies1(X):-not abnormal(X),bird(X).
Since
?-abduce(not(abnormal(tweety)),[],[]).
succeeds, any explanation of bird(tweety) will also be an explanation of flies1(tweety), which is of course wrong. The problem here is that the fact that abnormal(tweety) is considered to be false is not reflected in the explanation. Thus, we need a separate predicate abduce_not/3 for building explanations for literals assumed to be false.
The full program is given below. There are two changes in abduce/3: in the fifth clause, an abducible A is only added to the explanation E if it is consistent with it; i.e. if E does not explain not(A). In the sixth clause, an explicit explanation for not(A) is constructed.
% abduce(O,E0,E) <- E is abductive explanation of O, given
% E0 (works also for general programs)
abduce(true,E,E):-!.
abduce((A,B),E0,E):-!,
abduce(A,E0,E1),
abduce(B,E1,E).
abduce(A,E0,E):-
clause(A,B),
abduce(B,E0,E).
abduce(A,E,E):-
element(A,E). % already assumed
abduce(A,E,[A|E]):- % A can be added to E
not element(A,E), % if it's not already there,
abducible(A), % if it's abducible,
not abduce_not(A,E,E). % and E doesn't explain not(A)
abduce(not(A),E0,E):- % find explanation for not(A)
not element(A,E0), % should be consistent
abduce_not(A,E0,E).
The definition of abduce_not/3 closely mirrors the clauses for abduce/3:
a negated conjunction
not((A,B))is explained by either explainingnot(A)ornot(B);if there are clauses for
A, thennot(A)is explained by constructing an explanation fornot(B), for every bodyB;not(A)is explained if it is already part of the explanation;otherwise,
not(A)is explained by itself, ifAis abducible and not explained;not(not(A))is explained by explainingA.
There is no clause for true, since not(true) cannot be explained.
% abduce_not(O,E0,E) <- E is abductive expl. of not(O)
abduce_not((A,B),E0,E):-!,
abduce_not(A,E0,E); % disjunction
abduce_not(B,E0,E).
abduce_not(A,E0,E):-
setof(B,clause(A,B),L),
abduce_not_l(L,E0,E).
abduce_not(A,E,E):-
element(not(A),E). % not(A) already assumed
abduce_not(A,E,[not(A)|E]):- % not(A) can be added to E
not element(not(A),E), % if it's not already there,
abducible(A), % if A is abducible
not abduce(A,E,E). % and E doesn't explain A
abduce_not(not(A),E0,E):- % find explanation for A
not element(not(A),E0), % should be consistent
abduce(A,E0,E).
abduce_not_l([],E,E).
abduce_not_l([B|Bs],E0,E):-
abduce_not(B,E0,E1),
abduce_not_l(Bs,E1,E).
We illustrate the program on the following set of clauses. Notice that there are several explanations for abnormal(tweety).
cl(flies1(X),(not(abnormal(X)),bird(X))).
cl(flies(X),(bird(X),not(abnormal(X)))).
cl(abnormal(X),penguin(X)).
cl(abnormal(X),dead(X)).
cl(bird(X),penguin(X)).
cl(bird(X),sparrow(X)).
The following queries show that the order of unnegated and negated literals in a clause only influences the order in which abducibles are added to the explanation, but not the explanation itself:
?-abduce(flies(tweety),Explanation).
Explanation =
[not penguin(tweety),not dead(tweety),sparrow(tweety)]
?-abduce(flies1(tweety),Explanation).
Explanation =
[sparrow(tweety),not penguin(tweety),not dead(tweety)]
Exercise 8.4 #
The abductive meta-interpreter will loop on the program
wise(X):-not teacher(X).
teacher(peter):-wise(peter).
with the query ?-abduce(teacher(peter),E) (see Section 8.2). Change the interpreter such that this query is handled correctly, by adding all literals collected in the proof to the abductive explanation.
Abduction can be used for formulating hypotheses about faulty components in a malfunctioning system. Here, the \(Theory\) is a description of the operation of the system, an \(Observation\) is a combination of input values and the observed output values, and \(Explanation\) is a diagnosis, telling us which components are malfunctioning. As an example we consider a logical circuit for adding three binary digits. Such a circuit can be built from two XOR-gates, two AND-gates, and an OR-gate (Figure 8.3). Its behaviour can be described logically as follows:
adder(X,Y,Z,Sum,Carry):-
xor(X,Y,S),
xor(Z,S,Sum),
and(X,Y,C1),
and(Z,S,C2),
or(C1,C2,Carry).
xor(0,0,0). and(0,0,0). or(0,0,0).
xor(0,1,1). and(0,1,0). or(0,1,1).
xor(1,0,1). and(1,0,0). or(1,0,1).
xor(1,1,0). and(1,1,1). or(1,1,1).
Figure 8.3 A 3-bit adder.#
These clauses describe the normal operation of the system. However, since diagnosis deals with faulty operation of components, we have to extend the system description with a so-called fault model. Such a fault model describes the behaviour of each component when it is in a faulty state. We distinguish two faulty states: the output of a component can be stuck at 0, or it can be stuck at 1. Faulty states are expressed by literals of the form fault(Name=State), where State is either s0 (stuck at 0) or s1 (stuck at 1). The Name of a component is given by the system that contains it. Since components might be nested (e.g. the adder might itself be part of a circuit that adds two 8-bits binary numbers), the names of the components of a sub-system are prefixed by the name of that sub-system. This results in the following system description:
adder(N,X,Y,Z,Sum,Carry):-
xorg(N-xor1,X,Y,S),
xorg(N-xor2,Z,S,Sum),
andg(N-and1,X,Y,C1),
andg(N-and2,Z,S,C2),
org(N-or1,C1,C2,Carry).
xorg(N,X,Y,Z):-xor(X,Y,Z).
xorg(N,0,0,1):-fault(N=s1).
xorg(N,0,1,0):-fault(N=s0).
xorg(N,1,0,0):-fault(N=s0).
xorg(N,1,1,1):-fault(N=s1).
andg(N,X,Y,Z):-and(X,Y,Z).
andg(N,0,0,1):-fault(N=s1).
andg(N,0,1,1):-fault(N=s1).
andg(N,1,0,1):-fault(N=s1).
andg(N,1,1,0):-fault(N=s0).
org(N,X,Y,Z):-or(X,Y,Z).
org(N,0,0,1):-fault(N=s1).
org(N,0,1,0):-fault(N=s0).
org(N,1,0,0):-fault(N=s0).
org(N,1,1,0):-fault(N=s0).
Such a fault model, which includes all possible faulty behaviours, is called a strong fault model.
In order to diagnose the system, we declare fault/1 as the (only) abducible predicate, and we make a call to abduce/2:
diagnosis(Observation,Diagnosis):-
abduce(Observation,Diagnosis).
abducible(fault(_X)).
For instance, suppose the inputs X=0, Y=0 and Z=1 result in the outputs Sum=0 and Carry=1 (a double fault). In order to diagnose this behaviour, we formulate the following query:
?-diagnosis(adder(a,0,0,1,0,1),D).
D = [fault(a-or1=s1),fault(a-xor2=s0)];
D = [fault(a-and2=s1),fault(a-xor2=s0)];
D = [fault(a-and1=s1),fault(a-xor2=s0)];
D = [fault(a-and2=s1),fault(a-and1=s1),fault(a-xor2=s0)];
D = [fault(a-xor1=s1)];
D = [fault(a-or1=s1),fault(a-and2=s0),fault(a-xor1=s1)];
D = [fault(a-and1=s1),fault(a-xor1=s1)];
D = [fault(a-and2=s0),fault(a-and1=s1),fault(a-xor1=s1)];
No more solutions
The first diagnosis is very obvious: it states that or1 (which calculates Carry) is stuck at 1, and xor2 (which calculates Sum) is stuck at 0. But the fault in the output of or1 might also be caused by and2 or and1, and even by both! The fifth diagnosis is an interesting one: if xor1 is stuck at 1, this accounts for both faults in the outputs of the adder. The remaining three diagnoses are considerably less interesting, since each of them makes unnecessary assumptions about additional faulty components.
The predicate diagnosis/2 generates every possible diagnosis; it does not make any assumptions about the relative plausibility of each of them. Several such assumptions can be made. For instance, we might be interested in the diagnoses with the least number of faulty components (there is only one smallest diagnosis in the example, but there may be several in general). Alternatively, we might want to consider only non-redundant or minimal diagnoses: those of which no proper subset is also a diagnosis. This is readily expressed in Prolog:
min_diagnosis(O,D):-
diagnosis(O,D),
not((diagnosis(O,D1),proper_subset(D1,D))).
?-min_diagnosis(adder(a,0,0,1,0,1),D).
D = [fault(a-or1=s1),fault(a-xor2=s0)];
D = [fault(a-and2=s1),fault(a-xor2=s0)];
D = [fault(a-and1=s1),fault(a-xor2=s0)];
D = [fault(a-xor1=s1)];
No more solutions
It should be noted that the predicate min_diagnosis/2 is quite inefficient, since it needs time quadratic in the number of diagnoses (for each possible diagnosis, it generates in the worst case each possible diagnosis to see if the second is a proper subset of the first). In turn, the number of diagnoses is exponential in the number of components. More efficient ways of generating minimal diagnoses can be found in the literature; they fall outside the scope of this book.