COMPUTER SCIENCE TRIPOS Part IB – 2022 – Paper 6
Artificial Intelligence (sbh11)
You are solving a planning problem using the GraphPlan algorithm. The problem
has the following actions:
a1(S) a1(B) a2(M) a2(S)
¬A(S), H(M) ¬A(B) ¬H(M), A(B) ¬H(C), H(M), A(S)
A(S) A(B) H(M) H(C), ¬H(M)
The start state is ¬H(M), ¬H(C), ¬A(S), ¬A(B) and the goal is H(C).
(a) Draw the state levels Si and action levels Ai of the planning graph up to and
including S2. Do not add any mutexes at this stage. [3 marks]
(b) Explain why it is not possible at this stage to attempt to extract a plan.
[1 mark]
(c) What is the smallest i for which it might make sense to try to extract a plan,
starting from Si
. Explain your answer. [2 marks]
(d) For the value of i identified in Part (c), draw levels Si−1, Ai−1 and Si of the
planning graph. [4 marks]
(e) On the diagram you have produced for Part (d), mark four mutexes, each of
which arises for a different reason. In each case explain what kind of mutex you
have included. [6 marks]
(f ) Give a general description of how the extraction of a plan from a planning graph
can be addressed as a heuristic search problem. [4 marks]