CSE630 Homework 4: Partial-order Planning

Due: Must be submitted by Sunday, November 12 at 11:59
1 point late penalty for each minute late

You may choose to hand it in manually by putting it in my mailbox by 5 pm Thursday, November 9 (or when the mailboxes close, which may be sooner), since Friday is a holiday.

Submit instructions:

Write up all of your answers in a text editor so that it can be submitted electronically. Put all of the files you want to submit in a directory on STDSUN, and submit it using the command:

> submit c630aa lab4 (lab4_dir)

Where lab4_dir is the directory containing the files you want to submit.

  1. (34 points) Problem 11.11 depicts a limitation of non-interleaved planners, known as the Sussman Anomaly. This problem is traditionally formulated as:

    Start: On(C,A) On(A,T) On(B,T) Clear(C) Clear(B)
    Block(A) Block(C) Block(B) Table(T)
    Goal: On(A,B) & On(B,C)

    Action Schema: Stack(block1,block2)
    Precond: Clear(block2) & Block(block2) & Clear(block1)
    Effect: On(block1,block2) & ~Clear(block2)

    Action Schema: UnStack(block1,block2,t)
    Precond: On(block1,block2) & Table(t) & Clear(block1)
    Effect: ~On(block1,block2) & Clear(block2) & On(block1,t)

    Action Schema: Stack(block1,t)
    Precond: Table(t) & Block(block1)
    Effect: On(block1,t)

    This problem statement has two subgoals. A planner that solves subgoals separately (solving one or the other first, then solving the other), cannot derive a plan to go from this start state to the goal state.

    1. Explain why adding goal protection to a planner allows it to get to a goal state with both of these goals solved
    2. Show the fully-ordered plan that turns this start state into the goal state.

  2. (50 points) Create STRIPS-style operators for the following problem: You are in charge of the emergency response center for a small airport and there has been a severe snow storm. Several emergency situations need to be handled:
    1. There are two gates (G1,G2) that both need to be plowed before they can be used.
    2. There are three planes waiting on the tarmac (T1) that have increasingly annoyed passengers that need to be unloaded at a gate.
    3. There is a plane in the air waiting to land but the runway (R1) is covered in snow. (Fortunately, there's plenty of fuel, so time isn't a huge factor.) It will also need to be unloaded.
    4. There are two snowplows for the airport (S1 and S2), that start out fueled. Each snowplow has to refuel after plowing the runway or a gate (you can assume a true/false predicate Fueled(x) rather than having to measure levels of fuel).
    You will want to decide on a set of predicates to use in solving the problem. Hint: you will need At(object,place) and Fueled(snowplow), among many others.
    1. Describe the goal situation, in which all the objectives are completed, planes are in the hangar (H1) and the snowplows all return to their base.
    2. Write out STRIPS action schemas for the following actions:
      1. Plow(snowplow,location): plow out a location with a particular snowplow
      2. Refuel(snowplow): refuels a snowplow if it's at the fueling station.
      3. Move(object,from,to): moves an object from a location to a location.
      4. Unload(plane,gate): unloads passengers from plane at gate.
      5. Land(plane,runway): lands a plane on the runway.
    3. Show a plan that satisfies all of the objectives listed above. Your plan should show fully instantiated actions and indicate what order the actions should be executed in. Also, for every precondition of the actions, indicate which action supplied that precondition. You can draw out boxes for actions and arrows for the dependencies, or you can use a text editor and give the actions identifiers, like so:
      Plan: A1 < A2 ...
      A1: Go(Door3,LIGHT3)
      Preconditions: At(Shakey,Room3) Supplied by: Start
      In(Door3,Room3) Supplied by: Start
      In(Light3,Room3) Supplied by: Start
      Effects: At(Shakey,LIGHT3)
      A2: LightOff(LIGHT3)
      Preconditions: At(Shakey,LIGHT3) Supplied by: A1

  3. (16 points) Explain what parts of the following STRIPS formulation for buying a car are wrong. Assume that the actions themselves are complete (i.e., there are no missing actions). The idea here is to look for syntactically incorrect expressions in the STRIPS language or inappropriate (possibly missing) parts of actions. You should find at least four different types of errors for full credit.