3-16. ARTIFICIAL INTELLIGENCE
1. The International Sport Board (ISB) has regulations which specify whether or not a player is eligible to play Sport for a particular country. One regulation states that a player is eligible to play for a country if:
The player was born in the country, or
Either of the player’s parents were born in the country, or
At least two of the player’s grandparents were born in the country.
Assume there is a complete genealogical database consisting of Prolog facts of the form person(P,C,M,F) where P is a person’s name uniquely identifying someone in the database, C is the country of his/her birth, M is his/her mother, and F is his/her father.
a) Write Prolog clauses defining a predicate eligible/2 such that goals of the form eligible(P,C) succeed if and only if player P is eligible to play for country C according to the above regulation.
[6]
b) The squad named to represent a country in an international Sport match must consist of at most 25 different players all of whom must be eligible to play for that country. Write Prolog clauses defining a predicate checkteam/2 such that goals of the form checkteam(T,R) succeed if and only if T is a valid squad and R is [] (the empty list), or T is not a valid squad and R is a list of reasons why not.
[6]
c) An international Sport match is valid if it is played between two valid squads from two different countries. Write Prolog clauses that check if two squads named for an international match are valid and returns [] (the empty list) if so, otherwise a list of the offending team(s) and their offence(s).
[4]
d) Points in a Sport match are awarded by: 7 for scoring a ‘goal’, 5 for a ‘try’, and 3 for a ‘penalty’. Write Prolog clauses that for a given number of points, will return all the different ways that number of points could have been scored. It is permissible to generate these one by one on backtracking, for example:
?- points2scores( 11, L ).
L = [try, penalty, penalty] ;
L = [penalty, try, penalty] ;
L = [penalty, penalty, try] ;
false
[4]
Note that in parts (a)-(c) the examiners will pay attention to the use of the anonymous
variable ( ), and the use of cut (!) to ensure that only one correct answer is returned.
3-16. Artificial Intelligence c Imperial College London 1/5
2. Consider the General Graph Search Engine (GGSE) shown below in Prolog.
search( Graph, [Node|Path] ) :- choose([Node|Path],Graph, ), state of( Node, State ),
goal state( State ).
search( Graph, SolnPath ) :-
choose( Path, Graph, OtherPaths ),
one step extensions( Path, NewPaths ),
add to paths( NewPaths, OtherPaths, GraphPlus ), search( GraphPlus, SolnPath ).
a) i)
b)
c)
Explain how problem states, nodes, paths and graphs are represented in Prolog for use in the GGSE.
[2]
ii) With reference to the answer in part i), explain the operation of each line of the GGSE.
[6]
Write a Prolog program to use the GGSE to perform “Iterative Broadening Beam Search” (IBBS). The answer will require the ‘wrapper’ for the GGSE, any modifications required to the GGSE itself, and the definition of choose/3 and add to paths/3.
[8]
What assumption has to be made about the search space for IBBS to be ef- fective? Given this assumption, evaluate the IBBS algorithm with respect to completeness, optimality and complexity criteria.
[4]
3-16. Artificial Intelligence c Imperial College London
2/5
3. A graph G is defined as a 3-tuple G = hN,E,Ri, where N is the set of nodes, E is the set of edges, and R is the incidence relation.
a) Suppose the edge between two nodes represents the cost of changing state from one node to the other. Give an inductive definition of the paths and the path costs in a graph G, starting from an identified node S.
[2]
b) Given an implicit definition of a graph G0 as a 2-tuple G0 = hS,Opi, give an inductive definition of the paths and path costs in a graph G0, starting from an identified node S. What condition needs to be satisfied for the paths in G0 rooted on S to be the same as the paths in G rooted on S.
[3]
c) Explain the difference in operation between the uniform cost, best first and A⇤ search algorithms.
[3]
d) Explain why, in situations with (x,y) coordinates, ‘straight-line’ distance and
‘Manhattan’ distance are admissible heuristics for A⇤ search.
[2]
e) Write Prolog clauses defining a predicate h/4 such that goals of the form h(Heuristic,C1,C2,H) compute the h-value for two coordinates C1 and C2, where Heuristic can be instantiated to either ‘straightline’ or ‘manhattan’.
[3]
f) In the context of A⇤ search, explain why, for a given search problem, one heuris- tic might be ‘better’ (more efficient) than another. Which of the two heuristics, ‘straight-line’ distance and ‘Manhattan’ distance, is likely to be more efficient in A⇤ search?
[3]
g) With the use of an example, explain how the alpha-beta algorithm works, and in particular show how the search space is pruned.
[4]
3-16. Artificial Intelligence c Imperial College London
3/5
4. a) b)
In the context of knowledge representation and reasoning, define the terms uni- fication, resolution and skolemisation.
[3]
For each of the following pairs of formulas, state whether or not unification succeeds. If unification succeeds, give the unifier; it it fails, state why:
c)
d)
f(X,a) f(a,Y)
f(X,Y) f(Z,Z)
f(a,X) f(Y,Y)
f(X,a,Y,Z) f(Z,Y,X,b)
Skolemise the formulas:
9z.8x.8y.relation(x, y, z) 8x.8y.9z.relation(x, y, z)
Explain the difference between the two.
Consider the following statements of first-order logic:
8x.8y.property1(x) ^ property2(y) ^ relation1(x, y) ! state1(x) 8x.8y.property1(x) ^ property3(y) ^ relation2(x, y) ! state2(x) 8x.state1(x) ^ state2(x) ! result(x)
8x.8y.prerelation1(x, y) ! relation1(x, y) 8x.8y.prerelation2(x, y) ! relation2(x, y)
property1(a) property2(b) property3(c) prerelation1(a, b) prerelation2(a, c)
Express these statements as a set of Horn clauses.
[4]
[3]
e)
Prove, using resolution and proof by refutation, that result(a). The proof should show all the unifiers.
[6]
3-16. Artificial Intelligence c Imperial College London
4/5
[4]
5. In answering this question, it is essential that any KE-trees (proofs) are properly anno- tated to show the inference steps (i.e. showing the inference rule used, line number of the major and minor premises, and in the case of modal proofs, the label for the world).
a) Explain the relations for entailment |= and proves `, and how they are involved in the definitions of soundness and completeness.
b) Consider the following sentences of English:
If Alan did not lock the door then he either forgot or lost the key If he lost the key then he will be in trouble
If he has a good memory then he did not forget
Alan has a good memory
Therefore, either Alan locked the door or he will be in trouble
Transform these sentences into propositional logic and, using the KE calculus, prove that the argument is valid.
[4]
c) In the Obligatio Game, a finite number n of rounds is chosen, depending on the severity of the exam. The examiner then gives the candidate successive asser- tions, f1,f2,…,fn that she has to either ‘accept’ or ‘reject’ as each one is put forward. In the former case, fi is added to the candidate’s stock of commit- ments; in the latter case, the negation ¬fi is added.
The candidate passes the exam if she maintains the consistency of her stock of commitments throughout all n assertions.
Suppose the candidate is exposed (successively) to the following three asser- tions:
1. q_¬(p_r) 2. p ! q
3. q
Using the KE calculus, show what sequences of answers will ensure that the student passes the exam. (Hint: use KE for model building, adding the asser- tions one at a time.)
[8] d) Using the KE calculus for propositional modal logic, prove that the following
formulas are all theorems of modal logic S5: ⌃⇤p!⇤p
⌃⌃p!⌃p
[4]
3-16. Artificial Intelligence c Imperial College London
5/5
[4]