COMPUTER SCIENCE TRIPOS Part IB – 2017 – Paper 4
Artificial Intelligence (SBH)
EvilRobot has two dogs called Fido and Fifi. All three of them enjoy pie and
sausages so much that they like to steal them. At the beginning of the day the
butcher has some sausages and the pieShop has some pie. Also, EvilRobot and
his pets are at home, but they aim to end the day having relieved the local businesses
of their products.
(a) Give a detailed definition of a Constraint Satisfaction Problem (CSP). Include
in your answer a definition of what it means for an assignment to be consistent
and to be complete, and for an assignment to be a solution. [4 marks]
(b) Consider the constraint C on four variables {V1, V2, V3, V4} each of which has
the domain {true, false}, with
C = {(true, true, true, true)
(true, false, true, false)
(false, true, false, false)
(false, false, false, true)
(false, false, true, true)}.
Explain how this constraint can be replaced by a collection of binary constraints
having an identical effect. [3 marks]
(c) Describe the state-variable representation for planning problems. Illustrate your
answer by showing how the action of EvilRobot (or one of his pets) stealing
something could be represented in the scenario set out at the beginning of this
question. [5 marks]
(d) Explain how the state of a planning problem can be represented in the
state-variable representation. [2 marks]
(e) Using your example of the stealing action provided in part (c), explain how this
planning problem might be translated into a CSP. You should include in your
explanation examples of the translation for actions, state variables, and action
preconditions and action effects, but you need not describe the translation for
frame axioms. [6 marks]