CS计算机代考程序代写 prolog chain algorithm If-then Reasoning: Back-chaining Algorithm

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