Understanding the meta symbols and

3-16. ARTIFICIAL INTELLIGENCE — MODEL ANSWERS

1. The question tests basic understanding of Prolog, data structures and recursion. It should have been relatively straightforward for anyone who and been to the lectures and done all the lab exercises. The ‘nasty’ was in Part (b), where the question does not specify what to do with the country. There were various different solutions, all of which were acceptable: either hardwire it, with country( C ) before check eligible( S, C, R ); define check team/3 rather than /2, as here, which makes part (c) slightly easier; or leave it as an instantiated variable when you first call it, and it will be instantiated if the call succeeds (and in part(c) check the value that it is instantiated to is the country you want). Part (d) required the >= checks and to terminate when points was zero.

countgps( [], Country, Sum ) :-
Sum >= 2.

countgps( [GP|GPs], Country, SoFar ) :-person( GP, Country, _, _ ), !, SoFar1 is SoFar + 1,
countgps( GPs, Country, SoFar1 ).

length( Squad1, L ),
L < 26, !.

check_length( _, [too_big] ).

check_eligible( [H|T], C, R ) :-
eligible( H, C ), !,
check_eligible( T, C, R ).

check_eligible( _, [ineligible_player] ).

d) points2scores( 0, [] ).

points2scores( N, [goal|L] ) :-
N >= 7,
NewN is N - 7,
points2scores( NewN, L ).

a) state – Prolog term
Node = state plus possibly some more information Path = list of nodes
Graph = list of Paths

search( Graph, [Node|Path], _ ) :-

choose( [Node|Path], Graph, _ ),

one_step_extensions( Path, NewPaths ),

add_to_paths( NewPaths, OtherPaths, GraphPlus, Beam ),

prune( AllGraph, GraphPlus, Beam ).

insert_in_order( [], Graph, Graph ).

insert_one( Path, [], [Path] ).

prune( [], _, [] ) :- !.

3. The question was a gift for going to the lectures and doing the labs. The tricky part was actually having an extra bit of Prolog to write with some mathematical operations in it, but anything sensible that looked Prolog would have been acceptable, for example sqrt( XX, X) rather than X is sqrt( XX ), for example. The other issue was making sure that the right justification for the behaviour of A* was given for part (f), and a proper example was given for part (g).

∞
PG′ = i=0�P′i

P′0= {[(S,0)]}
P′i+1= {[(n,c+e) | p] | ∃p ∈ P′i.∃op ∈ Op.op(frontier(p)) = (n,e)∧gcost(p) = c}

straight-line, go this distance, and maybe more, therefore never over-estimate

manhattan, go at least X1-X2 in X direction and Y1-Y2 in y-direction, and maybe more, therefore never over-estimate

sld( (X1,Y1), (X2,Y2), H ) :-

Dx is (X1 - X2) * (X1 - X2),

(Y1 > Y2 -> Dy is Y1 - Y2 ; Dx is Y2 - Y1),

H is Dx + Dy.

So straight-line distance is likely to be more efficient, since hstraight−line ≤ hmanhattan

Example: any sensible correct example will do

b) yes X bound to a, Y bound to a

yes X bound to Z, Y bound to Z

property2(b)
property3(c)
prerelation1(a,b)
prerelation2(a,c)

5. Understanding the meta symbols ⊢ and |= can be a conceptually a bit tricky. Part (b) was manageable for anyone who had been to the lectures and tried out the KE proofs in the tutorials and tried to implement the KE proof engine in the labs. Part (c) was trickier because firstly, it required thinking about open branches rather than closed KE- trees, and secondly it required an exhaustive analysis of the various combinations. The insight was to understand that saying yes or no to a question meant either adding the formula or its negation (respectively) to the root of the tree, and that there were eight such combinations, from yes-yes-yes to no-no-no. Then, for each of the combinations, see if there was a KE tree with an open branch, if there was, then you had an assignment of truth values to the variables that made all the assertions true (and therefore consistent). The reasoning used here is just a short cut for that. Finally, in part (d), full marks required keeping track of the worlds labelling the formulas in the application of the modal rules, and taking care of the order in which they were applied, i.e. possibility before necessity (i.e. you can’t just go around making up worlds you want propositions to be true in, unless you’re a Brexit fantasist).

no, yes or no, no

To see this, suppose we say yes to q∨¬(p∨r). Then we must say yes to p → q.