UOB Open
Artificial Intelligence: Logic Programming III
Oliver Ray
base case
Translation From Haskell: Example
recursive case
length([],X) :- X =0 .
UOB Open
%length[] =0
% length (_:l) = 1 + length l
length([_|L], X) :- X is 1 + Y , length(L, Y) .
length([], 0).
length([_|L], X) :- length(L, Y) , X is 1 + Y .
Note: we must place the recursive “length” call before the “is” call since the latter requires its right argument to be ground at call time
Computing Answers: Intuition
• Prolog’s execution mechanism returns computed answer substitutions by repeatedly resolving query literals with (user-defined) database clauses until there are no literals left to prove:
• A query literal is chosen by a selection rule (which, in standard Prolog returns the left-most call)
• A database clause is chosen by a search rule (which, in standard Prolog , returns clauses top-to-bottom)
• In fact, a fresh variant of the database clause is created by renaming all of the variables to ones not yet in play and alternative clauses are considered, in order (known as backtracking and visualized in an SLD or search tree)
• A most general unifier (mgu) is computed for the selected literal and the head of the chosen clause
• The resolvent of the query and the clause (on that literal under that mgu) is formed by applying the mgu and
replacing the selected literal by the body of clause in order to leave a new query
• This is repeated until we derive a query with no literals, known as the empty clause and written
• At that point the composition of all the mgus is taken and applied to the original query to yield an answer
• If there are no resolvents, the branch is a failed dead end denoted by # or an underlined goal UOB Open
Substitutions and MGUs: Formalised
• A substitution is a set of bindings of (distinct) variables to terms (distinct from themselves): ={X1/t1, … Xn/tn} where is used to denote the empty substitution ={}
• The application of a substitution to an expression E is denoted E and obtained by replacing any (free) variable Xi in E by the corresponding term ti from , if one exists
• The composition of two substitutions 1 and 2 denoted 12 is defined as follows:
12 = {X/(t2) | X/t1 ^ Xt2 } {Y/s2 | YX for all X/t1} so E(12)=(E1)2
• A substitution 1 is (as or) more general than a 2 iff there exists some 3 such that 13 =2
• A substitution is a unifier of two expressions E1 and E2 iff E1=E2
• A substitution is a most general unifier (mgu) of two expressions E1 and E2 iff is a unifier of E1 and E2 that is more general than all other unifiers of E1 and E2 (and is unique up to renaming)
• Given two expressions E1,E2 and an (initially empty) substitution , we can compute an mgu as follows: mgu(E1,E2,)=mgu(E1{X/t}, E2 {X/t}, {X/t}) where X is a variable from one expression at the first syntactic position where the two expressions differ and t is corresponding term in the other (nb. if neither is a variable then there is no mgu; if both are variables then we can bind either to the other; strictly we should fail if t mentions X but this ‘occurs check’ is usually omitted in Prolog)
UOB Open
Example: substitutions
given and and and and and
t1 = p( W, f(W , X)) t2 = p(Y,f(a,Z))
1 = { W/X , X/W}
2 = { W/a, Y/a, Z/X }
3 = {W/a,Y/a,X/Z}
4 = { W/a, Y/a, Z/V, X/V }
t11 = p(W, f(W,X)) {W/X, X/W} = p(X, f(X,W))
t21 = p(Y, f(a,Z)) {W/X, X/W} = p(Y, f(a,Z))
Thus 1 is NOT a unifier of t1and t2
But 2 and 3and 4 all ARE unifiers of t1and t2 (EASY EXERCISE!)
2 is more general than 3 as { W/a, Y/a, Z/X} {X/Z} = {W/a, Y/a, X/Z} – since Z/Z is excluded from composition 3 is more general than 4 as { W/a, Y/a, X/Z} {Z/V} = {W/a, Y/a, X/V, Z/V}
4 is NOT more general than 3 as { W/a, Y/a, Z/V, X/V} = {W/a, Y/a, X/Z} implies V/Z in order to exclude Z/. from the composition, but then V/Z would be in the composition, which is a contradiction
UOB Open
Example: MGU (and common errors!)
given and
naively trying
plus( X plus( s(V)
X/s(V)
, Y , , W ,
Y/W or W/Y
s(Y) ) s(s(V)) )
Y/s(V)
gives { X/s(V), Y/W, Y/s(V) } or { X/s(V), W/Y, Y/s(V) } either
But these are both incorrect as the first is not even a substitution (as it contains two different bindings for Y) and the second is not a unifier (as the instantiated terms disagree on the second argument)!
Thus, correctly applying the mgu algorithm means applying the computed binding to the two expressions as we proceed and composing it with the other bindings computed thus far. For example
UOB Open
mgu(plus(X,Y,s(Y)), plus(s(V),W,s(s(V))), )
= mgu(plus(s(V),Y,s(Y)), plus(s(V),W,s(s(V))), {X/s(V)} )
= mgu(plus(s(V),W,s(W)), plus(s(V),W,s(s(V))), {X/s(V),Y/W} )
= mgu(plus(s(V),W,s(s(V))), plus(s(V),W,s(s(V))), {X/s(V),Y/s(V), W/s(V)} )
Giving a correct answer {X/s(V),Y/s(V), W/s(V)}
% you can also use W/Y
Example: MGU (and common confusion!)
these slides
https://cs.stackexchang e.com/questions/10967 3/how-can-i-compute- the-most-general- unifier-for-these-two- expressions
(After translating this into Prolog notation) How would you answer this query?
UOB Open
Translation: MGU (and common confusion!)
Given these two expressions
t1 = f(g(a,h(b)) , g(X,Y))
t2 = f(g(Z,Y), g(Y,Y))
a student computes their mgu as
σ = { Z/a, Y/h(b), X/h(b) }
but then suggests the following would be more general σ’ = { Z/a, Y/h(b), X/Y }
and finds this is actually what Prolog returns
https://cs.stackexchang e.com/questions/10967 3/how-can-i-compute- the-most-general- unifier-for-these-two- expressions
Which of these substitutions is a unifier and which is more general than the other? What mgu(s) are computed by our algorithm and what mistakes has the student made?
UOB Open
Solution: MGU (and common confusion!)
Given these two expressions
t1 = f(g(a,h(b)) , g(X,Y))
t2 = f(g(Z,Y), g(Y,Y))
a student computes their mgu as
σ = { Z/a, Y/h(b), X/h(b) }
but then suggests the following would be more general σ’ = { Z/a, Y/h(b), X/Y }
and finds this is actually what Prolog returns
is indeed an mgu (and is also returned by our alg.!)
’ is indeed more general than (strictly) as ’ {Y/h(b)} =
but ’ is not returned by our alg. (if you do not forget to compose subs.!) and is not a unifier as f(g(a,h(b)),g(Y,h(b))) f(g(a,h(b)),g(h(b),h(b)))
this actually means Prolog binds both X and Y to h(b) and Z to a!
UOB Open
Unification & Resolution: Example
for convenience: use . for ‘[|]’
length( .(a, .(b, .(c, []))) , N) length( .(H1, T1) , N1)
length( .(a, .(b, .(c, []))) , N) length( .(a, T1) , N1)
length( .(a, .(b, .(c, []))) , N) length( .(a, .(b, .(c, []))) , N1)
H1/a
H1/a, T1/[b,c]
H1/a, T1/[b,c], N1/N
Selected query literal
Selected clause variant
?- length([a,b,c], N).
length([H1|T1], N1) :- length(T1, M1), N1 is 1+M1.
?- length([a,b,c],N).
length([a,b,c], N) :- length([b,c],M1), N is 1+M1.
knowledge base
most general unifier (mgu)
{H1/a, T1/[b,c], N1/N}
UOB Open
resolvent
?- length([b,c], M1), N is 1+M1.
length([], 0).
length([_|T], N) :- length(T, M), N is 1+M.
Proof Tree: Example
?- length([a,b,c],N).
{H1/a, T1/[b,c], N1/N}
{H2/b, T2/[c], N2/M1}
{H3/c, T3/[], N3/M2}
{M3/0}
{M2/1}
{M1/2}
?- length([b,c],M1), N is 1+M1.
length([H1|T1],N1) :- length(T1,M1), N1 is 1+M1.
length([H2|T2],N2) :- length(T2,M2), N2 is 1+M2.
?- length([c],M2), M1 is 1+M2, N is 1+M1.
length([H3|T3],N3) :- length(T3,M3), N3 is 1+M3.
?- length([],M3), M2 is 1+M3, M1 is 1+M2, N is 1+M1.
?- M2 is 1+0, M1 is 1+M2, N is 1+M1.
?- M1 is 1+1, N is 1+M1.
?- N is 1+2.
length([],0).
UOB Open
{N/3} computed answer substitution empty clause
length([], 0).
length([_|T], N) :- length(T, M), N is 1+M.
Accumulators and Tail Recursion
• You may have noticed the definition of length/2 on the previous slide results in an unnecessarily inefficient memory footprint (which is linear with respect to the length of the list) by gradually collecting together all of the “is” literals before actually starting to evaluate them (at least under Prolog’s default left-most selection strategy)
• A deterministic tail recursive definition (like the original Haskell) will often be more memory efficient – but that possibility was ruled out here due to the use of a moded arithmetic operator (which requires all its input arguments to be ground at the time of a call)
• But, it is often relatively easy to obtain an efficient tail recursive Prolog definition using an auxiliary argument called an accumulator (which stores the intermediate result of the computation up until this point, starting from some initial given value)
% length(+List, -Len)
% Len is length of List
length([], 0).
length([_|T], N) :- length(T, M), N is 1+M.
% length(+List, +Acc, -Len)
% length(List, 0, Len) length(List, Len) length([], A, A).
length([_|T], A, N) :- M is 1+A, length(T, M, N).
UOB Open
?- length([a,b,c],0,N).
?- M1 is 1+0, length([b,c],M1,N).
Proof Tree: Revisited
{H1/a, T1/[b,c], A1/0, N1/N}
{M1/1}
{H2/b, T2/[c], A2/1, N2/N}
{M2/2}
{H3/c, T3/[], A3/2, N3/N}
{M3/3}
?- length([b,c],1,N).
length([H2|T2], A2, N2) :- M2 is 1+A2, length(T2, M2, N2).
M2 is 1+1, length([c],M2,N).
?- length([c],2,N).
M3 is 1+2, length([],M3,N).
?- length([],3,N).
length([H3|T3], A3, N3) :- M3 is 1+A3, length(T3, M3, N3).
length([], A4, A4).
UOB Open
{A4/3, N/3}
length([H1|T1], A1, N1) :- M1 is 1+A1, length(T1, M1, N1).
length([], A, A).
length([_|T], A, N) :- M is 1+A, length(T, M, N).
Memory Usage: Implications
UOB Open
library implementation: length (?List,?Len)
case handling
type checking
accumulator
fast list access (“swiss army knife”)
error handling
UOB Open
• Shows search space reachable through backtracking
• Nodes are queries: the root is the initial query and children are the resolvents of the parent on its first literal • Leaves represent success branches (empty clause []) or failure branches with no resolvents (underlined )
• A proof tree can be obtained for each success branch by reconstructing the resolved clauses and mgus
?-student_of(S,peter)
Search (SLD) Tree
student_of(X,T):-
follows(X,C),teaches(T,C).
follows(paul,computer_science).
follows(paul,expert_systems).
follows(maria,ai_techniques).
teaches(adrian,expert_systems).
teaches(peter,ai_techniques).
teaches(peter,computer_science).
:-follows(S,C),teaches(peter,C)
:-teaches(peter,computer_science) :-teaches(peter,ai_techniques) :-teaches(peter,ai_techniques)
:-teaches(peter,expert_systems)
UOB Open
[]
[]
Infinite Search Trees
brother_of(X,Y) :- brother_of(Y,X).
brother_of(paul,peter).
?-brother(peter,B)
:-brother(B,peter)
:-brother(peter,B) [] :-brother(B,peter)
brother_of(paul,peter).
brother_of(X,Y):-
brother_of(Y,X).
?-brother(peter,B)
:-brother(B,peter)
[] :-brother(peter,B) :-brother(B,peter)
brother(X,Y):- brother(X,Z),
brother(Z,Y).
:-brother(peter,B)
:-brother(paul,Z1),brother(Z1,Z),brother(Z,
[] • •• ••
?-brother(paul,B)
• []
brother(paul,peter).
brother(peter,adrian).
[]
:-brother(paul,Z),brother(Z,B)
•
• •
[]
:-brother(peter,Z),brother(Z,B)
• • •
UOB Open
B
Pruning the search with cut (!)
• Sometimes we want to control which part of the SLD-tree is searched • efficiency: to avoid searching a particular region
• correctness: to avoid unwanted answers
• Prolog offers a pruning mechanism called “cut” and written “!”
• should primarily be used for efficiency reasons
• for correctness, higher-level constructs such as not/1 and if-then-else are available (defined in terms of cut)
• Cut and derived constructs are non-declarative, make programs harder to understand, and should be used judiciously!
UOB Open
The effect of cut
?- Q
?- p, S
?- L, !, R, S’
?- !, R’, S’’ ?- R’, S’’
…
p :- L, !, R …
UOB Open
pruned by cut !
ASCII notation for SLD trees (in online exams)
“?-” precedes each goal, “+” is a choice point, “X” marks a subtree pruned by cut, “#” is a failure branch, “:” is an infinite branch, “[]” is a success branch, and {..} represents any computed answer):
?- goal.
|
?- resolvent.
|
+——————–+———-X———-. |||
?- branch_1 ?- branch_2 ?- branch_n |||
… .!. … |||
?- success ?- failure ?- infinite ||:
[] # :
{..}
UOB Open
[] {Z=5}
Example: max(+Int, +Int, ?Int)
?- max(3,5,Z).
|
+——X——. ||
?- 3=<5,!. ?- 3>5. ||
!# |
?- max(3,5,5).
|
+——X——. ||
?- 3=<5,!. ?- 3>5. ||
!# |
[]
?- max(3,5,3). ?- max(3,5,4). ||
?- 3>5. |
#
#
max(X,Y,Y) :- X=
http://www.learnprolognow.org /lpnpage.php?pagetype=html& pageid=lpn-htmlse44
The cut can prune away some redundant failure branches, to give better computational efficiency
?- max(5,3,3). ||
+————-. +————-. ||||
?- 5=<3,!. ?- 5>3. ?- 5=<3,!. ?- 5>3. | | | |
# [] # [] {Z=5}
?- max(5,3,Z).
UOB Open
The “cut-fail” definition of negation
Negation-as-Failure can be defined in terms of cut as shown by the following definitions of the operators \\+ and \\\+ which are both equivalent to Prolog’s built-in \+ operator:
:- op(900, fy, \\+).
\\+ X :- X, !, fail. \\+ _.
:- op(900, fy, \\\+).
\\\+ X :- X, !, fail ; true.
UOB Open
UOB Open
P :- \+q, r.
P :- q.
q.
r.
Example: negation as failure
?- p.
|
+————————–. ||
?- \+q, r. ?- q. ||
+———X——–. [] ||
?- q, !, fail, r. ?- r. ||
?- !, fail, r. [] |
?- fail, r.
|
#
Vanilla meta-interpreter (using cut)
UOB Open
Implied by cuts !
Depth-bounded meta-interpreter
UOB Open
Interactive User Shell
UOB Open
Graph search
• Many AI problems reduce to searching for goals in a graph structure
• Search space is a graph, with partial solutions or states as nodes and possible transitions as arcs
• search space may contain cycles
• often approximated by a tree: easier algorithm, requires less memory, but is less efficient
because of repetitions
• or can add loop detection by keeping a list of visited nodes
• transitions may have costs associated with them
• Blind search methods look for goals in a systematic way, but do not take the quality of partial solutions into account (e.g. using heuristics)
• Backtracking search can be modelled with the notion of an agenda (which is simply a list of the nodes we plan to search next)
UOB Open
Agenda-based search
UOB Open
search(Agenda,Goal):-
next(Agenda,Goal,Rest),
goal(Goal).
search(Agenda,Goal):- next(Agenda,Current,Rest), children(Current,Children), add(Children,Rest,NewAgenda), search(NewAgenda,Goal).
• This code makes an abstraction of the order in which search nodes are added and removed from the agenda
• Given an Agenda, which is a set of nodes representing the frontier of the search process (initially set to start node), it will returns a Goal node accessible from those on the agenda
Depth-first vs Breadth-first
search_df([Goal|Rest],Goal):-
goal(Goal).
search_df([Current|Rest],Goal):-
children(Current,Children),
append(Children,Rest,NewAgenda),
search_df(NewAgenda,Goal).
search_bf([Goal|Rest],Goal):-
goal(Goal).
search_bf([Current|Rest],Goal):-
children(Current,Children),
append(Rest,Children,NewAgenda),
search_bf(NewAgenda,Goal).
children(Node,Children):- findall(C,arc(Node,C),Children).
in depth-first, children are added to front of agenda
in breadth-first, children are added to back of agenda
Note that “next” has been implicitly implemented here by simply taking the first goal from head of a list representing the agenda to leave rest in the tail
Note that in case of cyclic graphs, we may want to only take children we’ve not previously visited!
UOB Open
• Depth-firstsearch
Memory Requirements
n=0
n=1 n=2
• agenda = stack (last-in first-out)
• incomplete: may get trapped in infinite branch n=3
• no shortest-path property
• requires O(Bn) memory
• Breadth-firstsearch
• agenda = queue (first-in first-out)
• complete: will find all solutions
• first solution found along shortest path
• requires O(Bn) memory
n=0
B is branching factor (av. number of children) n is the depth
1+(B-1)n
n=1 n=2
n=3
UOB Open
Bn
Best-First Search
When adding children into the agenda, we want to order them with respect to some metric eval that tries to evaluate the quality of each node (in terms of how easily it might to lead to goal state). This is extra information known as a heuristic (function). If the heuristic estimates the distance to a goal, we put nodes with low scores fat the front of the agenda (a.k.a priority queue)
],Goal):
Current|Rest
Current,Children
add_bstf
search_bstf
• Best-firstsearch
• agenda = priority queue (preferentially ordered )
• Behaviour depends on heuristic employed
• Guarantee can be obtained if the heuristic satisfies certain properties
• E.g. A* search always finds least cost paths using a monotonic heuristic…
search_bstf
goal(Goal).
([
Goal|Rest
–
search_bstf
children(
([
],Goal):
– ),
(
Children,Rest,NewAgenda
(
), ).
NewAgenda,Goal
n=0
n=1 n=2
n=3
UOB Open
A Search
An “A” algorithm is a best-first search algorithm that aims at minimising the total cost along a path from start to goal.
estimate of total cost along path through n
f(n) = g(n) + h(n)
actual cost to reach n
from start
estimate of cost to reach goal from n
UOB Open
Global and local optimism
A heuristic
reaching a goal
estimate of cost to reach goal from n
is (
globally
the estimated cost of :
)
is always less than the actual
optimistic
or
cost
admissible
if
(from any node n)
h(n) ≤ h*(n)
actual (unknown) cost to reach goal from n
A heuristic is
decreases
h(n
(or
by more than the cost c of an edge from a node n
monotonic
locally optimistic
or
consistent
) 1
if
to a child n
it
never
: 2
e.g.
or Euclidean distance in grid world!
1
)
–
h(n
2
)≤c
Manhattan Distance
UOB Open
A* Algorithm
heuristic
first time a node is put on the agenda it is reached along the cheapest path
•
•
•
• • •
•
A* (A
star): an A algorithm with an
–
always reaches a goal along the cheapest path first
admissible out
assumes ties are ordered first
–
breadth
–
in first first is a special case
– Monotonicity makes search more efficient
•
called monotonicity because f
–
in the absence of monotonicity, agenda may contain multiple copies of the same node reached along different paths
values are never decreasing along a path
UOB Open
Non-monotonic transition
A Non-Monotonic (but admissible) Heuristic
search graph (node-hScore) where all transitions have cost=1
A* agenda (node-fScore) [start-3]
[p-2, r-3] [q-2, r-3] [r-3, s-4] [s-3, s-4] [goal-3, s-4]
start:3 p:1
r:2
q-0
s:1
Non-optimal initial path to node s
UOB Open
goal:0
Path Finding (in grid world)
Breadth
–
First
Best
–
First
A* (Manhattan)
https://cs.stanford.edu/people/abisee/tutorial/astar.html
UOB Open
Path Finding (in grid world)
UOB Open
Example of path finding in a grid with walls (green Xs) from start in top left to goal in 4th row of last column where moves can be made immediately S, E, N, W (with any ties broken in that order). Numbers show the order in which cells are added to the agenda, computed path is shown in red
The Prolog and Search part of the exam will comprise
• 10 of 30 multiple choice questions (answer all)
• 1 of 3 long questions (answer 2) The exam will assume
• a working knowledge of logic programs obtained by studying Chapters 1-6 & 10-11 of the recommended Learn Prolog Now! tutorial.
• a familiarity with the relevant content in the slides and videos for the Prolog I-III lectures (including material in the relevant lab intros and Q&A sessions)
The multiple choice and long answer questions in the mock unit paper are all highly representative of the type and style of question in the real exam
A topic-by-topic breakdown of the examinable Prolog and Search material is now given
Examination Hints
UOB Open
Examinable Prolog Content
• Lecture 1 – Syntax of basic Prolog – variables, atoms, compound terms, facts, rules and queries Lab/Q&A: Practice writing simple facts rules and queries involving simple terms and arithmetic operators NOTE: You should know that in the standard order of terms: VARs @< ATOMICs @< COMPOUNDs
• Lecture 2 - Semantics of basic Prolog - standard translation to FOL - but being aware of the non-classicality of negation as failure), list notation and the built-in predicates length, member, append, findall, bagof and setof - but you only need to know how to use them, not how they are implemented
Lab/Q&A: Practice writing more complex facts, rules and queries involving recursion and structured terms NOTE: You should understand reflexivity, irreflexivity, symmetry, transitivity and transitive closure
• Lecture 3 Proof theory of basic Prolog - bindings, substitutions, application, composition, unifiers, mgus, resolution, proof-trees, sld-trees, selection-rule, search-rule, computed-answer, cut, the "cut-fail" definition of negation as failure (you need to know the definitions be able to apply them, including computing mgus and drawing sld-trees with cuts and negation
Lab/Q&A: Practice writing programs with cuts and higher-order predicates
NOTE: You should be familiar with the basic argument modes indicators: +, - and ? UOB Open
(Non-)Examinable Prolog Concepts
EXAMINABLE
• OPERATORS: ‘ “ ( ) [ ] | ‘[|]’ :- , ; . is + - * / = < @= @< ! \+ ^
• PREDICATES: true, false, fail, length, member, append, findall bagof setof
• MODE IDICATORS: + - ?
• CONCEPTS: bindings, substitutions, application, composition, unifiers, mgus, resolution, proof-trees, sld- trees, selection-rule, search-rule, computer answer, cut, the "cut-fail" definition of negation as failure
NON-EXAMINABLE
• OPERATORS: == =:= =@= #= ->
• PREDICATES: forall, foreach, maplist, include, exclude, between, format, write, writeln, read, repeat
• MODE IDICATORS: ++ — @ : ! (https://www.swi-prolog.org/pldoc/man?section=preddesc)
• CONCEPTS: accumulators, tail-recursion, failure-driven-loops, meta-interpreters, interactive-shells, user- defined-operators, debugger-commands
UOB Open
Examinable Search Content
• Part 1 – Blind Search – agendas, depth-first-search, depth-bounded-search, breadth- first-search (you need to know their general properties, abstract data structures and be able to simulate their operation at a high-level, but you won’t be asked to code them)
• Part 2 – Heuristic Search – admissable heuristics, monotonic heuristics, Euclidean & Manhattan distance metrics in GridWorld-style problems, best-first-search, A*-search (you need to know their definitions and how to apply them within A* search)
UOB Open
UOB Open
Thank you