COMPUTER SCIENCE TRIPOS Part IB – 2019 – Paper 6
Artificial Intelligence (sbh11)
(a) Describe the state-variable representation for planning by discussing the
following, giving specific examples of each concept:
(i) Rigid relations and state variables. [2 marks]
(ii) Actions. [2 marks]
(iii) The representation of state. [2 marks]
(iv) Goals and solutions. [2 marks]
(b) Your boss has suggested using heuristic search to solve a planning problem
expressed in the state-variable representation. Explain how this might be
achieved. You do not need to suggest a specific heuristic at this stage.
[3 marks]
(c) Comment on whether or not heuristic search is a good approach to solving
planning problems in the state-variable representation, compared with the
alternative of using a constraint satisfaction solver. [5 marks]
(d) Suggest an admissible heuristic that could be used when applying A?
search to
solving a planning problem in the state-variable representation. Show that it is
admissible. [4 marks]