tutorial3.dvi
COMP9414: Artificial Intelligence
Tutorial 3: Constraint Satisfaction/Planning
1. Formulate the 8-Queens problem as a constraint satisfaction problem with 8 variables (one
for each column) whose domain is the set of possible row positions. Then trace forward
checking and domain splitting with arc consistency. A (near-solution) state is shown below.
2. Formulate the blocks world using STRIPS planning operators. The actions are stack (move
one block to the top of another) and unstack (move one block to the table). The robot can
hold only one block at a time.
To simplify the world, assume the only objects are the blocks and the table, and that the
only relations are the on relation between (table and) blocks and the clear predicate on table
and blocks. Also assume that it is not possible for more than one block to directly support
another block (and vice versa).
3. The Sussman anomaly, shown below, is a simple planning problem that could not be solved
by the early linear planners. Show how a partial order planner would solve this problem
with the blocks world operators defined above.
Start State Goal State
B A
C
A
B
C
4. There is a close analogy between plans and computer programs. Standard AI planners work
with sequencing, conditional and alternation constructs. The only thing missing is iteration,
allowing actions such as ‘walk up one step until the top of the stairs is reached’. How could
iterative actions be modelled within a standard planning framework? Would there be any
technical complications in verifying the correctness of plans containing iterative actions?