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.
    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:

         Precond: RightSockOn
        Effect: RightShoeOn
         Precond: LeftSockOn
        Effect: LeftShoeOn

    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.