King’s College London
This paper is part of an examination of the College counting towards the award of a degree. Examinations are governed by the College Regulations under the authority of the Academic Board.
Degree Programmes
Module Code Module Title Examination Period
MSc
7CCSMAIN
Artificial Intelligence January 2016 (Period 1)
Time Allowed Rubric
Two hours
ANSWER THREE OF FIVE QUESTIONS.
All questions carry equal marks. If more than three questions are answered, clearly indicate which answers you would like to be marked. Write this clearly in the dedicated section on the front page of the answer booklet.
If you fail to indicate which answers you would like to be marked, only the answers to the first three questions in exam paper order will count.
Calculators are not permitted
Books, notes or other written material may not be brought into this examination
Calculators Notes
PLEASE DO NOT REMOVE THIS PAPER FROM THE EXAMINATION ROOM
2016 King’s College London
January 2016 7CCSMAIN
1. a. Consider the design of an agent program intended to play chess against an adversary and answer the questions that follow.
Justify your answers carefully.
i. Is the environment of the agent discrete or continuous?
[5 marks]
ii. What type of search technique is appropriate in the modelling of this type of agent activity?
[5 marks]
iii. Discuss two aspects that are important in the representation of the agent’s state in the game.
QUESTION 1 CONTINUES ON NEXT PAGE
Page 2
SEE NEXT PAGE
[5 marks]
January 2016 7CCSMAIN
b. Consider the vacuum world problem in which the world contains exactly the two rooms left and right, next to each other. Each room is either clean or contains some dirt. In each state of the world, a vacuum cleaning agent is in exactly one of the two rooms.
The agent can execute three actions as described below:
• L: causes the agent to move to the room left, unless it is already there
• R: causes the agent to move to the room right, unless it is already there; and
• S: causes the agent to suck all of the dirt (if any) in the agent’s current room, leaving the room clean.
Answer the questions that follow.
i. Are any of the actions above reversible? Explain what effect reversible actions have on the search.
[10 marks]
ii. Draw a diagram representing the search space for this problem in- cluding all possible state transitions.
[10 marks]
c. Why would evolution tend to result in systems that act rationally? What goals are such systems designed to achieve?
[15 marks]
Page 3
SEE NEXT PAGE
January 2016 7CCSMAIN
2. a. Consider the following graph, where the nodes represent cities and the edges are annotated with the real cost of moving between cities.
A 140 E 99 C
75 151 80 211
B 71 D
F 97 G 101 H
Suppose that for every node n in the graph, the heuristic functions h1 and h2 below are used to estimate the cost of reaching the goal node G from n.
h1(A) = 280 h1(B) = 362 h1(C) = 110 h1(D) = 256
h1(E) = 152 h1(F) = 80 h1(G) = 0 h1(H) = 95
h2(A) = 0 h2(B) = 0 h2(C) = 0 h2(D) = 0
h2(E) = 0 h2(F) = 0 h2(G) = 0 h2(H) = 0
Answer the questions that follow.
i. Check whether h1 and h2 are admissible. Justify your answer clearly.
[5 marks]
ii. Suppose that the function h2 is used in an A∗ search. Would the search be complete? Would the search be optimal? Justify your answers.
[5 marks]
iii. Show how an A∗ search would expand the graph using heuristic func- tion h1, starting at node A until it finds the goal node G.
At each step, show the values of all nodes expanded as calculated by all functions used by the algorithm. Give the total cost of the solution found.
QUESTION 2 CONTINUES ON NEXT PAGE Page 4
[10 marks]
SEE NEXT PAGE
January 2016 7CCSMAIN
b.
i. Describe how the alpha-beta pruning technique works, specifying the conditions under which pruning can occur.
[10 marks]
ii. Given the tree below, with the partial results of a search using alpha- beta pruning written in some of the nodes, give values for the nodes X and Y such that pruning can occur where indicated in the tree. Justify your answer.
MAX
3
23 Prune
Prune
232
52X 32Y
[10 marks]
c. State which algorithm results from each of the following particular cases of local search techniques. Justify your answers.
i. Local beam search with beam width 1.
ii. Simulated annealing with temperature T = 0 at all times.
Page 5
SEE NEXT PAGE
[5 marks] [5 marks]
January 2016 7CCSMAIN
3. Consider the following variation of the blocks world problem, in which we have one robotic arm and three blocks a, b, c which are painted a particular colour.
In the initial situation, blocks a, c are painted white and block b is painted red. Blocks a and b are on the table and block c is on top of block b.
This situation is depicted in the figure below.
a, c are white b is red
The arm has three actions at its disposal: paint a block with a particular colour; stack a block on top of another block; and unstack a block from another block. The following assumptions are given about the actions.
• The action paint can only be executed if the colour to be painted is different from the original colour of the block.
• The action stack stacks one block on top of another. It can be executed if the block being moved is on the table and both blocks involved in the action are free (i.e., there is no other block on them).
• The action unstack removes one block from the top of another block and places it on the table. It can only be executed if the block being moved is free (i.e., there is no other block on it).
• Further assume that the actions stack and unstack can only manipu- late blocks with the colour red (both source and target blocks). There are no restrictions on the number of blocks on the table.
Answer the questions that follow:
a. Represent the initial scenario in the situation calculus, including some mechanism to keep track of whether a block is free to be moved or not. [10 marks]
c
a
b
QUESTION 3 CONTINUES ON NEXT PAGE Page 6
SEE NEXT PAGE
January 2016 7CCSMAIN
b. Formalise the positive and negative effects of the action stack, making sure to include all pre-conditions of the action.
i. What is a frame axiom?
ii. Write the frame axioms for the action paint and any fluent of your
choice that is not affected by the action’s execution.
[5 marks]
d. Consider the successor-state axiom below.
holds(F, do(A, S)) ↔ causes(A, F, S)∨(holds(F, S)∧¬cancels(A, F, S))
Explain how the axiom is used to formalise the following elements of the situation calculus:
c.
1. The pre-conditions of actions.
2. The negative effects of action execution.
You may wish to illustrate your answers with an example.
Page 7
SEE NEXT PAGE
[10 marks]
[5 marks]
[20 marks]
January 2016 7CCSMAIN
4. Let S be the set of arguments S = {x, y, w, z}, with attack relation R given by the arrows in the graph below.
xywz
The argumentation framework ⟨S, R⟩ thus defined will be used in items 4.a– 4.b below.
a. In argumentation theory, what extra condition does an admissible set of arguments have over a conflict-free set of arguments? Illustrate your answer by giving 1) one admissible subset of S and 2) two subsets of S that are conflict-free but not admissible.
[10 marks]
b. What requirement does a complete extension add to an admissible set of arguments? Illustrate your answer by giving 1) a subset of S that is a complete extension and 2) an admissible subset of S that is not a complete extension.
QUESTION 4 CONTINUES ON NEXT PAGE
Page 8
SEE NEXT PAGE
[10 marks]
January 2016 7CCSMAIN
c. Let ⟨S, R⟩ be the argumentation framework with S = {a1, a2 . . . , a10}, and attack relation R as depicted in the graph below.
a9 a10 a8 a7
a6 a5 a1a2 a4
a3
Answer the questions that follow.
i. Compute the grounded extension of ⟨S, R⟩.
d.
ii. Give one complete extension of ⟨S, R⟩ that is not the grounded ex- tension. Is the complete extension that you gave also preferred? Justify your answer.
[10 marks]
i. What is a strongly connected component?
ii. Give two strongly connected components of the graph below.
[5 marks]
[5 marks]
a1 a2 a3 a4
a5 a6 a7 a8
Page 9
SEE NEXT PAGE
[10 marks]
January 2016 7CCSMAIN
5. a. Assuming that the concepts “Red”; “White”; and “Rose” are disjoint and provide an exhaustive decomposition of the concept “Wine”, express in first-order logic all of the information represented in the semantic network below.
Winery
memberOf
Louis Jadot
is-a
is-a
Thing
is-a
is-a
Wine
is-a
White Rose Red
gold
is-a is-a
Beaujolais
Chianti
made_in
memberOf
Combe-aux-Jacques
[20 marks]
QUESTION 5 CONTINUES ON NEXT PAGE
Page 10
SEE NEXT PAGE
has_colour
January 2016 7CCSMAIN
b. Given the table below, where a cell (row i, col j) has value 1 if and only if the concept in row i is subsumed by the concept in row j, answer the questions that follow.
i. Draw the corresponding subsumption graph. ii. List the immediate successors of c3.
iii. List the immediate predecessors of c5.
≤
c1
c2
c3
c4
c5
c6
c1 c2 c3 c4 c5 c6
1 1 1 1 1 1
0 1 0 0 1 0
0 0 1 0 1 1
0 0 0 1 0 1
0 0 0 0 1 0
0 0 0 0 0 1
QUESTION 5 CONTINUES ON NEXT PAGE
Page 11
SEE NEXT PAGE
[15 marks]
January 2016 7CCSMAIN
c. Consider the subsumption graph corresponding to the subsumption re- lationship given in Question 5.b above and the insertion of the new concept c7 in it.
The list below gives the results that would be returned if a subsumption check were to performed between c7 and c1,. . . ,c6:
•c7 ≤c1,c7 ≤c2,c7 ≤c3,c7 ̸≤c4,c7 ̸≤c5,c7 ̸≤c6. •c1 ̸≤c7,c2 ̸≤c7,c3 ̸≤c7,c4 ̸≤c7,c5 ≤c7,c6 ̸≤c7.
Now answer the questions that follow.
i. Using negative check propagation in a breadth-first traversal of the
graph, how many concept subsumption checks would need to be
made to compute c7’s immediate predecessors? Justify your answer. [5 marks]
ii. Proceeding to the bottom-phase, what is the minimum number of checks that would need to be made to calculate c7’s immediate suc- cessors?
[5 marks]
iii. Draw the subsumption graph for c1, . . . , c7 resulting from the inser- tion of c7.
[5 marks]
Page 12
FINAL PAGE