程序代写代做代考 AI prolog CMP2020M Artificial Intelligence

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!