If-then Reasoning: Back-chaining Algorithm ⃝c
CPS721: Artificial Intelligence (CS/RU)
CPS721: Artificial Intelligence
Acknowledgement:
Copyright By PowCoder代写 加微信 powcoder
based on the slides prepared by
September 7, 2021
If-then Reasoning: Back-chaining Algorithm
September 7, 2021
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 iscar and X iselectric then X isev. If X isasuv then X isacar.
If X isasedan then X isacar.
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
to establish an atomic sentence Q (b) find a conditional sentence of the form
(If P1 and … and Pn then Q) and then establish each of the Pi
(a) locate Q itself
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
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
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
/* 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
establish (tesla123 is electric)
part (a): succeeds succeeds
CPS721: Artificial Intelligence (CS/RU) If-then Reasoning: Back-chaining Algorithm September 7, 2021 5 / 11
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
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? */
successfor Z=rav456 successfor Z=rav456
establish (rav456 is electric) part (a): fails
part (b): 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 ←
part (b): fails fail
/*Backtrack: No other value for Z */
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 isaparentof Y and X isfemalethen X isamother)
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
CPS721: Artificial Intelligence (CS/RU) If-then Reasoning: Back-chaining Algorithm September 7, 2021 11 / 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 isagirl then X isagirl
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
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com