COMPUTER SCIENCE TRIPOS Part IB – 2019 – Paper 6
Artificial Intelligence (sbh11)
Evil Robot has been kidnapped by experimental psychologists, who are forcing him
to solve problems involving the stacking of blocks. For example, given the start state
on the left, he is asked to re-arrange the blocks into the state shown on the right.
=⇒
B
D
D
C
B
A
C A
You are to help him solve these problems by designing a system using planning graphs.
A block can only be moved if it does not have another block on top of it. Only one
block can be placed directly on top of another, although stacks of multiple blocks are
allowed.
(a) Explain how this problem can be represented as a planning problem, such that
it can be analyzed using a planning graph. Describe how state should be
represented, and how actions should be represented, giving a specific example
relevant to the stated problem in each case. [5 marks]
(b) Using the start state in the diagram above, draw the initial planning graph for
the problem, including the initial state level, the first action level, and the state
level resulting from the first action level. Do not add any mutex links at this
stage. [4 marks]
(c) Define an inconsistent effects mutex and an interfering actions mutex. Add to
your diagram for Part (b) a single example of each, or explain why this is not
possible. [4 marks]
(d) Define a competing for preconditions mutex. By adding a small number of actions
to the second action level of your planning graph, give a single example of such
a mutex, or explain why this is not possible. [2 marks]
(e) How many more action levels would you expect to need before a valid plan could
be extracted to solve the problem stated? Explain your answer. [2 marks]
(f ) Give two examples of the difficulties that might arise if we also wish to include
long blocks as follows:
B
E
B
D
D
A
C A
=⇒
E C
In each case explain why it might be difficult to address such an extension using
planning graphs. [3 marks]