COMP9414: Artificial Intelligence Tutorial Week 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
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?
A
C
B
B
A
C