CMP2020M Artificial Intelligence
Dr. Bashir Al-Diri
Dr. Marc Hanheide
Dr. Patrick Dickinson
Lincoln School of Computer Science
CM2020M Artificial Intelligence
Introduction to AI
Knowledge Representation
Planning
Logic Programming(3/3) Games AI
Probabilistic Reasoning
Lecture 7: Logic Programming for AI
• Review of Prolog Rules and Facts • Prolog
• Matching
• Backtracking
• Recursion
CMP2020M: Lecture 7 – Logic Programming
Prolog Basics – Revisited
Prolog program consists of facts and rules. animal(lion).
animal(sparrow).
hasfeathers(sparrow).
bird(X) :- animal(X), hasfeathers(X).
“Run” by asking questions or queries. Or by setting a goal for Prolog to try to prove: To find out if something is true:
?- bird(sparrow). yes
Or to find values for a variable that makes it true: ?- bird(What).
What = sparrow
Prolog Execution
A Prolog rule consists of a head and a body.
a(X) :- b(X), c(X).
head body
When Prolog tries to answer a query (prove a goal) it tries to match the goal to the head of the rule. This might result in binding variables to other variables or values.
?- a(thing).
a(thing) MATCHES a(X) so X is bound to the value “thing”.
Now it tries to prove the goals in the body of the rule, using these variable bindings::
b(thing) and c(thing)
Prolog Matching
With more complex terms, we have to look more carefully
at how Prolog matches expressions.
Consider:
likes(fatherOf(fred), motherOf(joe)).
?- likes(fatherOf(fred), motherOf(X)). Whose mother does fred’s father like?
MATCHING the expressions gives X=joe.
But:
?- likes(fatherOf(fred), X).
Who does fred’s father like?
X = motherOf(joe)
Prolog must find variable bindings that make the two matched expressions identical.
Prolog Matching
We can try out Prolog matching at the prompt by using the “=“ operator, which
in Prolog means “matches”.
?- a(X) = a(1).
X= 1 ?
Yes
?- likes(f(A), m(A)) = likes(f(john), m(john)).
A=john?
Yes
?- likes(f(A), m(A)) = likes(f(john), m(mary)).
No Doesn’t match as can’t have A = john AND A = mary.
?- 1+1 = 2.
No Doesn’t match
?- 1+1 is 2.
yes
Example
likes(mary, X) :-
strong(X), handsome(X).
strong(Y) :- tall(Y). tall(john). handsome(john).
?- likes(mary, john).
MATCHES likes(mary, john) to head of rule 1, with X=john.
Sets strong(john), handsome(john) as new goals.
Tries to prove strong(john). MATCHES head of rule 2.
Tries to prove tall(john).
MATCHES a fact. So proved.
Tries to prove handsome(john).
MATCHES a fact. So proved.
CMP2020M: Lecture 7 – Logic Programming
Y=john.
Example: prolog
likes(mary, X) :-
strong(X), handsome(X).
strong(Y) :- tall(Y). tall(john). handsome(john).
?- likes(mary, john).
?- likes(mary, john).
1) 1 Call: likes(mary,john)
CMP2020M: Lecture 7 – Logic Programming
2) 2
3) 3
4)3
5) 2
6) 2
7) 2
8) 1 Exit: likes(mary,john)
yes
Call: strong(john) Call: tall(john) Exit: tall(john)
Exit: strong(john) Call: handsome(john) Exit: handsome(john)
Can also represent this as a “proof tree”.
Using rule 1
5
yes
18
likes(mary, john)
?- likes(mary, john).
1) 1 Call: likes(mary,john) 2) 2 Call: strong(john)
3) 3 Call: tall(john)
4) 3 Exit: tall(john)
5) 2 Exit: strong(john)
6) 2 Call: handsome(john) 7) 2 Exit: handsome(john) 8) 1 Exit: likes(mary,john) yes
1
Using rule 2
43
tall(john)
True fact
2
3
strong(john)
2
6
7
handsome(john)
True fact
CMP2020M: Lecture 7 – Logic Programming for AI
Backtracking
Backtracking is the process that Prolog systematically go through rules and facts to answer queries.
Prolog goes through facts/rules top to bottom looking for facts or rule heads which match the goal.
If a rule fails as can’t prove body, Prolog will try next rule/fact matching current goal.
If can’t find ANY way to prove current goal, Prolog will retry the previous goal, to see if it can be solved another way.
CMP2020M: Lecture 7 – Logic Programming
Example: Simple example, facts only
bird(type(sparrow), name(steve)). bird(type(penguin), name(tweety)). bird(type(penguin), name(percy)).
?- bird(type(penguin), name(X)).
X = tweety X = percy no
Note: Here we say “Yes” to ask the system to look for other solutions, which forces backtracking.
CMP2020M: Lecture 7 – Logic Programming
Example: Two rules
carriesUmbrella(X) :- rainingOn(X). carriesUmbrella(X) :- inScotland(X). inScotland(fred).
?- carriesUmbrella(fred).
First tries rule 1. This doesn’t work out, as rainingOn(fred) can not be
proved,
The system continues through Prolog rules/facts and tries rule 2. This succeeds.
CMP2020M: Lecture 7 – Logic Programming
One rule, several facts.
likes(mary, X) :- tall(X), handsome(X). tall(john).
tall(jim). handsome(jim).
?- likes(mary, Who).
Matches head of rule with X=Who (binding two variables to same value). Tries to satisfy tall(Who).
tall(john); succeeds.
Tries to satisfy handsome(john); fails.
So backtracks and retries tall(Who) with Who=jim;
tall(jim); succeeds.
Tries to satisfy handsome(jim).
Success with Who=jim
CMP2020M: Lecture 7 – Logic Programming
Another Example
animal(leo). animal(tweety). animal(percy). animal(peter). hasFeathers(percy). hasFeathers(peter). bird(X) :-
animal(X),
hasFeathers(X). bird(freddy).
?- bird(B).
Matches with head of first rule.
Tries to satisfy animal(B).
Matches animal(leo).
Tries to satisfy hasFeathers(leo).
FAILS, so GOES BACK to try; Matches animal(tweety)… animal(B) again.
Matches animal(percy).
Tries hasFeathers(percy).
Succeeds, so bird(B) succeeds.
B = percy ;
Going back and trying later animal facts:
B = peter;
And trying later “bird” fact:
B = freddy.
CMP2020M: Lecture 7 – Logic Programming
Exercise: What are the solutions to the following, and what order are they given?
aeroplane(concorde). aeroplane(jumbo).
on(fred, concorde).
on(jim, no18bus).
bird(percy).
animal(leo).
animal(tweety).
animal(peter).
hasFeathers(tweety). hasFeathers(peter).
flies(X) :- bird(X).
flies(X) :- areoplane(X).
flies(X) :- on(X, Y), aeroplane(Y). bird(X) :- animal(X), hasFeathers(X).
Query:
?- flies(X).
?- flies(X). X = percy X = tweety X = peter X = fred no
CMP2020M: Lecture 7 – Logic Programming
Recursion
Recursive rules are simply rules that call themselves.
Example,
ancestor(X, Y) :- father(X, Y).
ancestor(X, Y) :- father(X, Z),
ancestor(Z, Y).
X is Y’s ancestor if X is Y’s father, or there is someone who X is the father of, who is the ancestor of Y.
CMP2020M: Lecture 7 – Logic Programming
Example
is_integer(0). is_integer(N):-
N1 is N – 1, is_integer(N1).
?- is_integer(2).
Integer includes:
• the counting numbers {1, 2, 3, …}, • zero {0},
MATCHES integer(2) to head of rule, with N=2.
Sets N1 to 2 – 1 = 1
Tries to prove is_integer(1).
MATCHES integer(1) to head of rule, with N=1.
Sets N1 to 1 – 1 = 0
Tries to prove is_integer(0). MATCHES a fact. So proved.
CMP2020M: Lecture 7 – Logic Programming
Example
is_integer(0). is_integer(N):-
N1 is N – 1, is_integer(N1).
?- is_integer(2).
?- is_integer(2).
1 Call: is_integer(2) 2 Call:_4103 is 2 – 1 2 Exit:1is2-1
2 Call: is_integer(1)
Call:_4114 is 1 -1 Exit:0 is 1 – 1
3
3
3
3 Exit:is_integer(0) 2 Exit:is_integer(1) 1 Exit:is_integer(2) yes
Call:is_integer(0)
CMP2020M: Lecture 7 – Logic Programming
Recursion
sums(N,S):- N>0,
N1 is N-1, sums(N1,S1), S is N+S1.
sums(0,0).
sums(4): 4+3+2+1+0 = 10
CMP2020M: Lecture 7 – Logic Programming
Recursion
sums(N,S):- N>0,
N1 is N-1, sums(N1,S1), S is N+S1.
sums(0,0).
N=4; sums(4) = 4+3+2+1+0 = 10
sums(4,S):- 4>0,
N1 is 4-1 = 3, sums(3,S1), S is 4+S1.
sums(3,S):- 3>0,
N1 is 3-1 = 2, sums(2,S1), S is 3+S1.
sums(2,S):- 2>0,
N1 is 2-1 = 1, sums(1,S1), S is 2+S1.
sums(1,S):- 1>0,
N1 is 1-1 = 0, sums(0,S1), S is 1+S1.
sums(0,0).
S=10
S=4
S=3
S=1
S1=0
CMP2020M: Lecture 7 – Logic Programming
Summary
Matching:
Prolog tries to prove goals by matching them with rules/facts. Tries to find variable bindings making expressions identical.
Backtracking
Prolog goes through facts/rules from top to bottom to try to find
matching rules or facts.
But keeps track of where it has got to, and when anything fails it goes back and re-tries the last goal it proved, finding another way to prove it using facts/rules later in the program.
CMP2020M: Lecture 7 – Logic Programming
Thankyou for listening!