Homework 5 -- due Thursday April 26

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.
   Answer the following questions:
   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)?
   Copyright: © 2018 by the Regents of the University of Minnesota
   Department of Computer Science and Engineering. All rights reserved.
   Comments to: Maria Gini
   Changes and corrections are in red.