CSci 4511 - Homework 5

# Homework 5 -- due Thursday April 26

This homework will be graded out of 100 points. It will count 5% of the grade.
1. [30 points] You are given a train engine and three boxcars, which are all at the Chicago train station. There are two boxcars in Milwaukee. There is a train track connecting Minneapolis to Milwaukee, and one connecting Milwaukee to Chicago.
Your goal is to couple the five boxcars with the engine, move them all to Minneapolis, and take the engine back to Chicago.
You can couple a boxcar with an engine if they are both at the same train station. You can couple one boxcar at a time with an engine. You can connect as many boxcars as you want to an engine. Boxcars can be moved only if coupled with an engine. An engine can move from a station to another as long as there is a track connecting the stations, either directly or indirectly through another city.
1. Define the action schemas for this train domain. Provide a description of the predicates you use sufficient to understand them unequivocally.
2. Define the initial state and the goal state.
3. Show a plan that can be obtained using your action schemas to accomplish the goal.
2. [30 points] Consider the following variation to the block stacking domain; blocks are arranged on a table in N^2 locations corresponding to the cells of a N x N grid. At most one block can be located in any given location and no more than H blocks can be stacked.
1. Define action schemas for moving blocks between locations, between blocks, and between locations and blocks. Define the predicates you use and make sure the notation you use for writing the schemas is clearly defined.
2. Assume the initial state and goal state are completely specified (i.e. you know where each block is), and assume the number of blocks is less or equal to N^2. Propose a trivial algorithm (not a planning algorithm) for solving any problem in this domain.
3. Is your algorithm guaranteed to find an optimal solution in terms of number of steps?
4. Discuss briefly the advantages, if any, of using a planning system compared to your solution.
3. [20 points]
Your goal is to have RightShoeOn ∧ LeftShoeOn, using these actions:

Action(RightShoe,
Precond: RightSockOn
Effect: RightShoeOn
Action(RightSock,
Precond:
Effect:RightSockOn
Action(LeftShoe,
Precond: LeftSockOn
Effect: LeftShoeOn
Action(LeftSock,
Precond:
Effect:LeftSockOn

Goal: RightShoeOn ∧ LeftShoeOn

Show the planning graph marking the mutexes. At what level is the problem solved? Show a solution. Is there more than one solution?

4. [20 points]
1. How does the closed world assumption affect planning? Be precise.
2. Why preconditions in action schemas are conjunctions and not disjunctions?
3. Why variables that appear in the effects of an action schema have to be in the preconditions?
4. Why an initial state for planning needs to have ground atoms (no variables)?