3-16. ARTIFICIAL INTELLIGENCE — MODEL ANSWERS
1. The question tests basic understanding of Prolog, data structures, and recursion. The first three parts should be relatively straightforward for anyone who and been to the lectures and done all the lab exercises. The last two parts require some application to convert the algorithmic specification given into declarative form.
a) Empty tree
[]
Non-empty tree
node( Key, LeftSubTree, RightSubTree )
b) lookup( _,[]):-!,fail.
lookup( Key, node(Key, _, _ ) ) :- !.
lookup( Item, node(Key,LT,_) ) :-
Item @< Key, !,
lookup( Item, LT ).
lookup( Item, node(Key,_,RT) ) :-
%Item @> Key,
lookup( Item, RT ).
c) insert( Item, [], node(Item, [], []) ).
insert( Item, node(Key, LT, RT), node(Key, NewLT, RT) ) :-
Item @< Key, !,
insert( Item, LT, NewLT ).
insert( Item, node(Key, LT, RT), node(Key, LT, NewRT) ) :-
%Item @> Key, !,
insert( Item, RT, NewRT ).
d) delete( _,[],[]).
delete( Item, node(Item, [], []), [] ) :- !.
delete( Item, node(Item, LT, []), LT ) :- !.
delete( Item, node(Item, [], RT), RT ) :- !.
delete( Item, node(Item, LT, RT), node(NextItem, LT, NewRT) ) :-
inorder_successor( RT, NextItem ),
delete( NextItem, RT, NewRT ).
delete( Item, node(Key, LT, RT), node(Key, NewLT, RT) ) :-
Item @< Key, !,
delete( Item, LT, NewLT ).
3-16. Artificial Intelligence — MODEL ANSWERS ⃝c Imperial College London 1/12
Answers
delete( Item, node(Key, LT, RT), node(Key, LT, NewRT) ) :-
%Item @> Key,
delete( Item, RT, NewRT ).
inorder_successor( node(NextItem, [], _), NextItem ) :- !.
inorder_successor( node(_, LT, _), NextItem ) :-
inorder_successor( LT, NextItem ).
e) verify_bst( [], _, _ ).
verify_bst( node(Key, LT, RT), MinKey, MaxKey ) :-
MinKey @=< Key,
Key @=< MaxKey,
verify_bst( LT, MinKey, Key ),
verify_bst( RT, Key, MaxKey ).
Note: the use of @ >, @ =>, etc are the comparison operators for the standard order of Prolog terms, It is perfectly acceptabele in this context to use ¿, ¡, ¿= etc. if we assume that the keys are integers.
3-16. Artificial Intelligence — MODEL ANSWERS ⃝c Imperial College London 2/12
Answers
2. The question is concerned with the the General Graph Search Engine studied in lectures and used in the Prolog labs. Parts (a)-(d) are an application of state space formulation. Part (b) tests understanding of one of the algorithms studied in the lectures.
a) Three tuple (Bank of boat ∈ {l,r}, LeftBank, RightBank) where each of Left- Bank and RightBank are also three-tuples (Number of Missionaries on Bank 0 ≤ n ≤ 3, Number of Rowing Cannibals on Bank 0 ≤ n ≤ 1, Number of Non- Rowing Cannibals on Bank 0 ≤ n ≤ 2)
b) movable( (B1,B2,B3), (2,0,0) ) :- B1 >= 2.
movable( (B1,B2,B3), (1,0,0) ) :-
B1 >= 1.
movable( (B1,B2,B3), (1,1,0) ) :-
B1 >= 1,
B2 >= 1.
movable( (B1,B2,B3), (1,0,1) ) :-
B1 >= 1,
B3 >= 1.
movable( (B1,B2,B3), (0,1,0) ) :-
B2 >= 1.
movable( (B1,B2,B3), (0,1,1) ) :-
B2 >= 1,
B3 >= 1.
It is movable that returns multiple answers, so that on backtracking, Prolog finds all valid states that can be reached from the state of frontier node, when the GGSE calls findall from one-step-extensions.
c) satisfiable( (0,_,_) ) :- !. satisfiable( (M,C1,C2) ) :-
C is C1 + C2,
M >= C.
d) state_change( changebanks, (B,L,R), (NewB,NewL,NewR) ) :- opposite( B, NewB ),
change_banks( B, L, R, NewL, NewR ).
change_banks( l, L, R, NewL, NewR ) :-
do_change_banks( L, R, NewL, NewR ).
change_banks( r, L, R, NewL, NewR ) :-
do_change_banks( R, L, NewR, NewL ).
do_change_banks( (B1,B2,B3), (O1,O2,O3), (B1m,B2m,B3m), (O1m,O2m,O3m) ) :-
movable( (B1,B2,B3), (M1,M2,M3) ),
vector_sub( (B1,B2,B3), (M1,M2,M3), (B1m,B2m,B3m) ),
vector_add( (O1,O2,O3), (M1,M2,M3), (O1m,O2m,O3m) ),
satisfiable( (B1m,B2m,B3m) ),
satisfiable( (O1m,O2m,O3m) ).
vector_sub( (X1,Y1,Z1), (X2,Y2,Z2), (X3,Y3,Z3) ) :-
X3 is X1 – X2,
Y3 is Y1 – Y2,
3-16. Artificial Intelligence — MODEL ANSWERS ⃝c Imperial College London 3/12
Answers
Z3 is Z1 – Z2.
vector_add( (X1,Y1,Z1), (X2,Y2,Z2), (X3,Y3,Z3) ) :-
X3 is X1 + X2,
Y3 is Y1 + Y2,
Z3 is Z1 + Z2.
opposite( l, r ).
opposite( r, l ).
e) Do depth-limited depth-first search at successively incremented depths d, d = 0, d = 1, d = 2, . . . until a solution is found. Depth limited search means when a path is of length d, it is discarded.
Needs to add a a depth argument to search/3 (for all heads and recursive calls) a wrapper predicate to do the successive increments of search, and a second clause to search to check for and discard paths is they are of the depth-limit
search( +Graph, ?SolnPath, +Depth )
search( Graph, SolnPath, Depth ) :-
choose( Path, Graph, GraphMinus ),
length( Path, PathLength ),
PathDepth is PathLength – 1,
PathDepth = Depth, !, %Note the ‘cut’ here
search( GraphMinus, SolnPath, Depth ).
id search( Paths, SolnPath, Depth ) :- search( Paths, SolnPath, Depth ).
id search( Paths, SolnPath, Depth ) :- Depth1 is Depth + 1,
id search( Paths, SolnPath, Depth1 ).
Complete – yes: it does exhaustive search, so if there is a path, it will be found Optimal – yes, if the best path is the shortest path
Time complexity O(bd ) – may have to expand all nodes
Space complexity O(b ∗ d) – only need b nodes at each depth d for depth-first search.
ID-DF search has completeness and optimality of breadth-first search and com- plexity of depth-first. Note that although it looks like work is being repeated at lower depths, repeating expanding root node d times (d depth of the solution) is inconsequential to bd nodes at that depth.
Since there are loops and we are expecting long solution path, difficult to offer a heuristic for best-first or A* search, this is efffective choice.
3-16. Artificial Intelligence — MODEL ANSWERS ⃝c Imperial College London 4/12
Answers
3. This question tests a broad range of knowledge and understanding of different aspects and variations of search algorithms studied in the course. The pure ‘bookwork’ ques- tions are part (c) and part (e), the other parts require either understanding (e.g. why heuristics are important and choosing between them) or application (how the alphabeta algorithm prunes trees. The question therefore trades depth for breadth.
a) A heuristic is a function which computes an estimate of the cost of getting from a frontier node to a goal node.
An admissible heuristic is one which never over-estimates this cost.
It is essential to A* search because the proof of optimality relies on admissibil- ity.
•
– – –
S
Expanding the node with the lowest f -cost
If we estimate ho > hactual, so g(n) + ho > g(n′) + h(n′), then we
might find a path from S to a sub-optimal goal G′ through n′
If we estimate hu < hactual, at some point g(n) + hu < g(n′) + h(n′),
so n will be expanded
If we always under-estimate, at some point we will expand the solu-
tion path ending in G before any solution path ending in G′ ho
hu
n′
g(n) n g(n′ )
hactual G G′ h(n′ )
b) Three possible criteria: (1) choose the heuristic which maximises h(n) without over-estimating, as this might minimise the number of nodes expanded:
Suppose with h1 n4
n3 n6 n8 n2 n5 n7
But with h2
n3 n6 n8 n2 n5 n7 n4
f∗ f∗ (2) Consider the computational complexity of the heuristics.
(3) Consider combining the heuristics, by normalising them and putting weights on them.
c) Paths defined by G = ⟨S, Op⟩ ∞
P =P′ Gi
i=0
3-16. Artificial Intelligence — MODEL ANSWERS
⃝c Imperial College London 5/12
Answers
P′ = {[S]} 0
P′ = {[n | p] | ∃p ∈ P′.∃op ∈ Op.op(frontier(p)) = (n,e)} i+1 i
Now, the edge e represents the f -cost of of this node f (n) = g(n) + h(n), where g is the path cost function and h is the heuristic.
A* search will choose to expand whichever path p, in whatever subset of Pi, to whichever depth i it has explored, which has lowest e.
d) X will be selected over Y as the value of the left-branch MIN node. This is passed up the tree to the possible value of the root MAX node. This value is offered as a cut off to the right-branch MIN node.
Searching the left tree of this node, it returns Z
Now, if X > Z then: if the value ? returned by searching branch B ? > Z, it will be discarded at the MIN layer by the MIN rule. However, if the value returned by searching branch B ? < Z, it will be discarded at the top MAX layer by the MAX rule. Therefore there is no point searching this branch, therefore it is pruned.
If X < Z then we need to search branch B as normal. If ? > Z it will be discarded at the MIN layer, but if X r), ((p&q)<->(q&r)), p], [], [], [], 0 ). br 1 p&q
eta q&r
alpha q
alpha r
alpha p
alpha q
open [q,p,r,q,p]
br 2 – (p&q)
eta – (q&r)
beta -q
open [-q,p]
true.
?- ke( [(q->r), ((p&q)<->(q&r)), -p], [], [], [], 0 ).
br 1 p&q
eta q&r
alpha q
alpha r
alpha p
alpha q
close p,-p
br 2 – (p&q)
eta – (q&r)
br 1 -q
open [-q,-p]
br 2 q
beta r
beta -r
close -r,r
true.
?- ke( [(q->r), -((p&q)<->(q&r)), p], [], [], [], 0 ).
br 1 p&q
eta – (q&r)
alpha p
alpha q
beta r
beta -r
close -r,r
br 2 – (p&q)
eta q&r
alpha q
alpha r
beta -q
close -q,q
true.
?- ke( [(q->r), -((p&q)<->(q&r)), -p], [], [], [], 0 ).
br 1 p&q
eta – (q&r)
alpha p
alpha q
3-16. Artificial Intelligence — MODEL ANSWERS ⃝c Imperial College London 8/12
Answers
close p,-p
br 2 – (p&q)
eta q&r
alpha q
alpha r
open [r,q,-p]
true.
?- ke( [-(q->r), ((p&q)<->(q&r)), p], [], [], [], 0 ).
alpha q
alpha -r
br 1 p&q
eta q&r
alpha q
alpha r
close r,-r
br 2 – (p&q)
eta – (q&r)
beta -q
close -q,q
true.
?- ke( [-(q->r), ((p&q)<->(q&r)), -p], [], [], [], 0 ).
alpha q
alpha -r
br 1 p&q
eta q&r
alpha q
alpha r
close r,-r
br 2 – (p&q)
eta – (q&r)
open [-p,-r,q]
true.
?- ke( [-(q->r), -((p&q)<->(q&r)), p], [], [], [], 0 ).
alpha q
alpha -r
br 1 p&q
eta – (q&r)
alpha p
alpha q
open [q,p,p,-r,q]
br 2 – (p&q)
eta q&r
alpha q
alpha r
close r,-r
true.
?- ke( [-(q->r), -((p&q)<->(q&r)), -p], [], [], [], 0 ).
alpha q
alpha -r
3-16. Artificial Intelligence — MODEL ANSWERS ⃝c Imperial College London 9/12
Answers
br 1 p&q
eta – (q&r)
alpha p
alpha q
close p,-p
br 2 – (p&q)
eta q&r
alpha q
alpha r
close r,-r
true.
So acceptable sequences are
yes, yes, yes yes, yes, no yes, no, no no, yes, no no, no, yes
3-16. Artificial Intelligence — MODEL ANSWERS
⃝c Imperial College London
10/12
Answers
5. This question tests some advanced concepts concerning Modal Logic and the Event Calculus, and draws together the ‘search’ and ‘reasoning’ parts of the course.
a) {f,w,g,c}↔{¬f,w,¬g,c}↔{f,w,¬g,c}↔{¬f,¬w,¬g,c}or{¬f,w,¬g,¬c}
b) Labelling the worlds 1, 2, 3, 4 and 5
W = {1,2,3,4,5}
R = {(1,2),(2,1),(2,3),(3,2),(3,4),(4,3),(3,5),(5,3)} [[f]]={1,3}
[[w]]={1,2,3,5}
[[g]] = {1}
[[c]]={1,2,3,4}
c) It is symmetric
d) InK
1 1 : ¬(P → ♦P) 1,negated conclusion 2 1: P 1,α
3 1: ¬(♦P) 1,α
4 1,1: ¬♦P 3,♦
open In S5
1 1:
2 1:
3 1:
4 2:
5 1:
close
¬(P → ♦P) P ¬(♦P) ¬♦P
¬P
1,negated conclusion 1,α
1,α
3,♦
4,
e) A fluent is a proposition whose truth value can change over time
moveFarmer initiates NewF at T if
F holdsAt T and
opposite( F, NewF ) and
W holdsAt T and
G holdsAt T and
C holdsAt T and
opposite( W, G ) and
opposite( G, C )
moveFarmerWolf initiates NewF at T if
F holdsAt T and
W holdsAt T and
F = W and
opposite( F, NewF ) and
G holdsAt T and
C holdsAt T and
opposite( G, C )
moveFarmerWolf initiates NewW at T if
F holdsAt T and
W holdsAt T and
F = W and
3-16. Artificial Intelligence — MODEL ANSWERS ⃝c Imperial College London 11/12
Answers
opposite( W, NewW ) and
G holdsAt T and
C holdsAt T and
opposite( G, C )
moveFarmerGoat initiates NewF at T if
F holdsAt T and
G holdsAt T and
F = G and
opposite( F, NewF )
moveFarmerGoat initiates NewG at T if
F holdsAt T and
G holdsAt T and
F = G and
opposite( G, NewG )
moveFarmerCabbage initiates NewF at T if
F holdsAt T and
C holdsAt T and
F = C and
opposite( F, NewF ) and
W holdsAt T and
G holdsAt T and
opposite( W, G )
moveFarmerCabbage initiates NewC at T if
F holdsAt T and
C holdsAt T and
F = C and
opposite( C, NewC ) and
W holdsAt T and
G holdsAt T and
opposite( W, G )
opposite( -X, X ) :- !.
opposite( X, -X ).
A narrative is represented by initially F statements and events “E happensAt T”, ie,
initially f.
initially w.
initially g.
initially c.
moveFarmerGoat happensAt 1.
moveFarmer happensAt 2.
moveFarmerWolf happensAt 3.
We can check if a narrative ends with all the fluents false.
3-16. Artificial Intelligence — MODEL ANSWERS ⃝c Imperial College London 12/12
Answers