If-then Reasoning: Back-chaining Algorithm
c©Hector Levesque
CPS721: Artificial Intelligence
Acknowledgement:
based on the slides prepared by Hector Levesque
September 7, 2021
CPS721: Artificial Intelligence (CS/RU) If-then Reasoning: Back-chaining Algorithm September 7, 2021 1 / 11
If-then reasoning
A special but very common case
Knowledge bases consisting of two sorts of sentences:
atomic sentences: simple primitives (e.g., subject-verb-object)
conditional sentences: of the form
If P1 and … and Pn then Q
where the Pi and Q are atomic sentences. In both cases, the sentences may
contain variables (written in caps) as well as constants (lower case).
Example (abbreviation ev means electricVehicle)
Constant tesla123 is a name of a specific vehicle manufactured by Tesla.
Constant rav456 is a name of a RAV4 vehicle manufactured by Toyota.
tesla123 is a sedan.
rav456 is a suv.
tesla123 is electric.
If X is car and X is electric then X is ev.
If X is a suv then X is a car.
If X is a sedan then X is a car.
CPS721: Artificial Intelligence (CS/RU) If-then Reasoning: Back-chaining Algorithm September 7, 2021 2 / 11
Back-chaining
Can use a simple procedure to derive new conclusions
Procedure to establish an atomic sentence Q
Either (a) locate Q itself
or (b) find a conditional sentence of the form
(If P1 and … and Pn then Q)
and then establish each of the Pi
End
One minor complication: variables
May want to establish (nissanLeaf789 is ev.)
Find a conditional (If −− then Z is ev.)
Can use this conditional, provided that we replace Z
by nissanLeaf789 in the Pi
CPS721: Artificial Intelligence (CS/RU) If-then Reasoning: Back-chaining Algorithm September 7, 2021 3 / 11
Tracing some examples
1. establish (tesla123 is a sedan)
part (a):succeeds
succeeds
2. establish (rav456 is a car)
part (a): fails
part (b): have (If ¯¯ then X is a car)
establish (rav456 is a suv)
part (a):succeeds
succeeds
succeeds
3. establish (rav456 is japanese)
part (a): fails
part (b): fails
fails
Note: the conclusion is probably true. It is just not entailed by the KB
CPS721: Artificial Intelligence (CS/RU) If-then Reasoning: Back-chaining Algorithm September 7, 2021 4 / 11
A longer trace
4. establish (tesla123 is ev)
part (a): fails
part (b): have (If −− then X is ev)
establish (tesla123 is a car)
part (a): fails
part (b): have (If X is a suv then X is a car)
establish (tesla123 is a suv)
part (a): fails
part (b): fails
fails
/* Backtrack: use 2nd rule */
part (b): have (If X is a sedan then X is a car)
establish (tesla123 is a sedan)
part (a): succeeds
succeeds
succeeds
establish (tesla123 is electric)
part (a): succeeds
succeeds
succeeds
CPS721: Artificial Intelligence (CS/RU) If-then Reasoning: Back-chaining Algorithm September 7, 2021 5 / 11
Retrieval
Can also use back-chaining to locate individuals that satisfy a given property
establish (tesla123 is a car) means confirm that tesla123 is a car
establish (Z is a car) means locate an individual Z that is a car.
establish (Z is a car)
part (a): fails
part (b): have (If −− then X is a car)
establish (Z is a suv)
part (a): succeeds for Z=rav456
succeeds for Z=rav456
succeeds for Z=rav456
/* and would also for tesla123 if we would try to retrieve another answer */
In the case where there are individuals that satisfy the current goal, we select one and
continue.
But we may have to reconsider the choice later in the procedure: this is called
back-tracking
CPS721: Artificial Intelligence (CS/RU) If-then Reasoning: Back-chaining Algorithm September 7, 2021 6 / 11
A back-tracking trace
5. establish (Z is ev)
part (a): fails
part (b): have (If −− then X is ev)
establish (Z is a car)
part (a): fails
part (b): have (If X is a suv then X is a car)
establish (Z is a suv)
part (a): success Z=rav456 /*Anybody else? */
success for Z=rav456
success for Z=rav456
establish (rav456 is electric)
part (a): fails
part (b): fails
fails
Back-track and try to retrieve something else instead of rav456
Perhaps the goal failed because of the choice of Z as rav456.
Need to reconsider . . .
CPS721: Artificial Intelligence (CS/RU) If-then Reasoning: Back-chaining Algorithm September 7, 2021 7 / 11
The trace continued …
5. establish (Z is a ev)
part (a): fails
part (b): have (If −− then X is a ev)
establish (Z is a car)
part (a): fails
part (b): have (If X is a suv then X is a car)
establish (Z is a suv)
part (a): fails ←↩ /*Backtrack: No other value for Z */
part (b): fails
fail
2nd: have (If X is a sedan then X is a car)
establish (Z is a sedan)
part (a): succeeds for Z=tesla123
succeeds for Z=tesla123
succeeds (Z=tesla123)
establish (tesla123 is electric)
part (a): succceeds
succeeds
succeeds for Z=tesla123
CPS721: Artificial Intelligence (CS/RU) If-then Reasoning: Back-chaining Algorithm September 7, 2021 8 / 11
Variable collision
One final complication due to variables:
We may have a conditional:
(If X is a parent of Y and X is female then X is a mother)
and facts about who is a parent of whom.
If we want to establish (sue is a mother),
then things will work fine (using retrieval):
establish (sue is a parent of Y ), (sue is female)
If we want to establish (Z is a mother),
then things will work (maybe with backtracking):
establish (Z is a parent of Y ), (Z is female)
But if we want to establish ( Y is a mother),
then things do not work:
establish ( Y is a parent of Y ), ( Y is female)
The solution: before using a conditional, we rename its variables so that they are
always different from those in the query.
CPS721: Artificial Intelligence (CS/RU) If-then Reasoning: Back-chaining Algorithm September 7, 2021 9 / 11
Some properties
Back-chaining has some desirable features:
1) it is sound, i.e., anything that can be established is logically entailed
2) it is complete for simple sentences,
i.e., all atomic entailments can be established assuming you eventually get to try all
applicable alternatives that can be found. The latter means no cyclic rules such as
If X is a girl then X is a girl
3) it is goal-directed,
i.e., work your way back from what you are trying to establish towards what you know
Contrast with the undirected “forward-chaining” procedure in the “keys and coat”
example
4) it forms the basis of declarative programming in PROLOG.
In PROLOG:
knowledge base→ program
back-chaining (with back-tracking)→ program execution.
CPS721: Artificial Intelligence (CS/RU) If-then Reasoning: Back-chaining Algorithm September 7, 2021 10 / 11
CPS721: Artificial Intelligence (CS/RU) If-then Reasoning: Back-chaining Algorithm September 7, 2021 11 / 11