Chapter 11
Planning  

powered by FreeFind

Modified: 

 

      Planning Graphs

 

11.1 THE PLANNING PROBLEM

Consider only environments that are:

 

 

 

The language of planning problems

    Syntax

Representation of states

state:    At(Plane1, Melbourne) Ù At(Plane2, Sydney)

 

Representation of goals

Representation of actions

Semantics

Describe how actions affect states.

For the goal of:

    At(P1,JFK) Ù At(P2,SFO) Ù Plane(P1) Ù Plane(P2) Ù Airport(JFK) Ù Airport(SFO)

action:

Action( Fly( p, from, to),
  Precondition: At(p,from) Ù Plane(p) Ù Airport(from) Ù Airport(to),
  Effect:         ØAt(p,from) Ù At(p,to)

and the current state of:

     At(P1,SFO) Ù At(P2,JFK) Ù Plane(P1) Ù Plane(P2) Ù Airport(JFK) Ù Airport(SFO)

what sequence of actions produce a solution?

 

Example: Blocks world

Consists of:

Operators

Actions

Plan

  1. Action( Move(b, x, y),
        Precond: On(b, x) Ù Clear(b) Ù Clear(y) Ù Block(b)
                                  Ù (b≠x) Ù (b≠y) Ù (x≠y),
        Effect:    On(b, y) Ù Clear(x) Ù ØOn(b, x) Ù ØClear(y))
     
  2. Action( MoveToTable(b, x),    Move block b to Table
        Precond: On(b, x) Ù Clear(b) Ù Block(b) Ù (b≠x),
        Effect:    On(b, Table) Ù Clear(x) Ù ØOn(b, x))
     

Solution

  1. Move(B, Table, C)   {b/B, x/Table, y/C}
  2. Move(A, Table, B)   {b/A, x/Table, y/B}
Initial:

  On(A, Table) Ù On(B, Table) Ù On(C, Table)
                     Ù Block(A) Ù Block(B) Ù Block(C)
                     Ù Clear(A) Ù Clear(B) Ù Clear(C)

Substitutions for: Move(B, Table, C)

             { b/B, x/Table, y/C }

Effects:

      On(B, C) Ù Clear(Table) Ù ØOn(B, Table) Ù ØClear(C)

New state:

  On(A, Table) Ù On(B, Table) Ù On(C, Table)
  Ù Block(A) Ù Block(B) Ù Block(C)
  Ù Clear(A) Ù Clear(B) Ù Clear(C)
  Ù On(B, C) Ù Clear(Table) Ù ØOn(B, Table) Ù ØClear(C)

  • Give the next state resulting from:

    Move(A, Table, B)
     

  • Is Move(A, B, B) allowed under the Move preconditions?

 

  1. Action( Move(b, x, y),
        Precond: On(b, x) Ù Clear(b) Ù Clear(y) Ù Block(b)
                                  Ù (b≠x) Ù (b≠y) Ù (x≠y),
        Effect:    On(b, y) Ù Clear(x) Ù ØOn(b, x) Ù ØClear(y))
     
  2. Action( MoveToTable(b, x),    Move block b to Table
        Precond: On(b, x) Ù Clear(b) Ù Block(b) Ù (b≠x),
        Effect:    On(b, Table) Ù Clear(x) Ù ØOn(b, x))

 

 

 

 

 

11.2 PLANNING WITH STATE-SPACE SEARCH

Forward state-space search

The figure at right is a partial state-space for the blocks world with only three blocks. It indicates some of the problems with planning:

  • Initial state
    On(A, Table) Ù On(B, Table) Ù On(C, Table)
            Ù Block(A) Ù Block(B) Ù Block(C)
            Ù Clear(A) Ù Clear(B) Ù Clear(C)
  • What are the possible valid states from the given initial state under the action:
    • Move(b, x, y)

    Remember that the preconditions for the actions must be met.

  • What is the branching factor for 3 blocks at level 1?
  • What is the minimum solution depth for stacking 3 blocks?
  • What is wrong with the figure at right?

Action( Move(b, x, y),
    Precond: On(b, x) Ù Clear(b) Ù Clear(y) Ù Block(b)
                   Ù (b≠x) Ù (b≠y) Ù (x≠y),
    Effect:    On(b, y) Ù Clear(x) Ù ØOn(b, x) Ù ØClear(y))

 

Backward state-space search

Forward search must examine many irrelevant actions that also lead to goal state as illustrated in the above diagram.

Backward search reduces the state space by allowing only relevant states leading from the goal back to the initial state.

Regression - actions are selected that achieve some part of the goal, the goal is regressed through the actions back to the initial state.

Relevant and consistent requirements:

  1. Action must achieve some part of the goal.
  2. Predecessor state must include action preconditions.
  3. Action must not undo any desired literal in goal.

Algorithm

Given a goal G and action A that is relevant and consistent:

  1. Delete positive effects of A from G; ignore negative effects.
  2. Add each new precondition literal from A to G.
  3. Terminate when G is satisfied by initial state.

Example - Develop plan to move to

  1. Action( Move(b, x, y),
        Precond: On(b, x) Ù Clear(b) Ù Clear(y) Ù Block(b)
                  Ù (b≠x) Ù (b≠y) Ù (x≠y),
        Effect:    On(b, y) Ù Clear(x) Ù ØOn(b, x) Ù ØClear(y))
     
  2. Action( MoveToTable(b, x),    Move block b to Table
        Precond: On(b, x) Ù Clear(b) Ù Block(b) Ù (b≠x),
        Effect:    On(b, Table) Ù Clear(x) Ù ØOn(b, x))
  1. What is the initial state for the diagram at right?
  2. For the goal state below, regress actions that produce the initial state.

     

    • Action( Move(b, x, y),
          Precond: On(b, x) Ù Clear(b) Ù Clear(y) Ù Block(b)
          Effect:    On(b, y) Ù Clear(x) Ù ØOn(b, x) Ù ØClear(y))
       
    • Action( MoveToTable(b, x),    Move block b to Table
          Precond: On(b, x) Ù Clear(b) Ù Block(b),
          Effect:    On(b, Table) Ù Clear(x) Ù ØOn(b, x))

 

11.3 PARTIAL-ORDER PLANNING

 

 

Example:

A partial-order plan for putting on shoes and socks and the six corresponding linearizations.

 

State and plan spaces

 

Example

Graphical representation of Move(b,x,y)

Action( Move(b, x, y),
    Preconditions: On(b, x) Ù Clear(b) Ù Clear(y)
    Effect:            On(b, y) Ù Clear(x) )

 

Operators:

 

Graphical representation of finish and initial operators in an unfinished plan.

 

  • Extend disjoint plan consisting of finish and initial by adding rule Move(A, x, B) to achieve one precondition conjunct of finish rule - On(A,B).

  • Link Move effect to finish precondition.

  • No commitment yet to x where A is being moved from.

    • {b/A, y/B}

Action( Move(A, x, B),
    Preconditions: On(A, x) Ù Clear(A) Ù Clear(B)
    Effect:            On(A, B) Ù Clear(x) )

 

  • What type of planning is this? Forward or backward?
  • We now need to satisfy 3 preconditions for Move(A,x, B).
  • initial operation effects can be used to satisfy the preconditions. Which ones can be satisfied?
  • What must we do when the effects of an operation do not meet all preconditions of another?

 

 

  • Several possible plan transformations, presented graphically below:

    1. {x/Table}

    2. Link On(A, Table) precondition and initial state.

    3. Link Clear(B) precondition and initial state.

    4. Establish Clear(A) precondition of Move(A, x, B) by inserting:
           Move(u, A, v)
      move something from A to somewhere.

      • {u/C, v/Table}

Action( Move(C, A, Table),
    Preconditions: On(C, A) Ù Clear(C) Ù Clear(Table)
    Effect:            On(C, Table) Ù Clear(A) )

  • What can we do about On(B,C) finish precondition?
  • What is the ordering of the operation so far?
  • On(C, Table) is an effect of operation b.
    Clear(Table) is an effect of operation a.
    Can we ignore these?

 

  • Preconditions of two Move operations, a and b, satisfied.
  • Implied ordering b < a; b occurs before a.
  • Clear(Table) and On(C, Table) products of operations that do no harm in this case.
  • To satisfy finish precondition On(B,C)
    • Move(B,x,C)
    • {b/B, x/Table, y/C}

Action( Move(B, Table, C),
    Preconditions: On(B, Table) Ù Clear(B) Ù Clear(C)
    Effect:            On(B, Table) Ù Clear(Table) )

  • Is the plan complete? How do we know?
  • Why does operation b implicitly occur before a?
  • Does it matter when c occurs?

 

  • Plan is partially-ordered
    • b < a by implication
    • but c is not ordered with respect to a and b.
  • Threat arcs (grayed arrows) are from operators to preconditions that are removed by effect of operator.
    • Operation c effect removes Clear(C), a precondition of b; order must be b < c.

      Action( Move(B, Table, C),
          Preconditions: On(B, Table) Ù Clear(B) Ù Clear(C)
          Effect:            On(B, Table) Ù Clear(Table) 
                               Ù ØOn(B,Table) Ù ØClear(C))

       

    • Operation a effect removes Clear(B), a precondition of c; order must be c < a.

      Action( Move(A, x, B),
          Preconditions: On(A, Table) Ù Clear(A) Ù Clear(B)
          Effect:            On(A, B) Ù Clear(x)
                               Ù ØOn(B,Table) Ù ØClear(B))

       

    • Total ordering must be b < c < a.
  • Plan not complete until all threat arcs removed by ordering operations.

 

  • Final plan is:
    • b = Move(C, A, Table),
    • c = Move(B, Table, C),
    • a = Move(A, Table, B).

 

   b c a

 

 

 

 

 

11.4 PLANNING GRAPHS

Planning graphs

 

Example - "have cake and eat cake too"

Initial( Have(Cake) Ù ØEaten(Cake) )

Goal( Have(Cake) Ù Eat(Cake) )

Action: (Eat(Cake),
   Precondition: Have(Cake),
   Effect:          ØHave(Cake) Ù Eaten(Cake) )

Action: (Bake(Cake),
   Precondition: ØHave(Cake),
   Effect:          Have(Cake) )

 

Action mutex - holds if any of the following three conditions hold at the same action level:

  1. Inconsistent effects: one action effect negates the an effect of another action.

    Eat(Cake) and persistence Have(Cake) have inconsistent effects because disagree on effect Have(Cake).
     

  2. Interference: effect of one action is a negation of a precondition of the other.

    Eat(Cake) effect ØHave(Cake) interferes with persistence of Have(Cake) by negating precondition Have(Cake).
     

  3. Competing needs: precondition of one action is mutually exclusive with precondition of another.

    Bake(Cake) and Eat(Cake) compete over precondition Have(Cake).

     

 

Literal mutex - holds at a level where either:

  1. two literals are negation of the other, Have(Cake) and ØHave(Cake)
  2. or each possible pair of actions that could achieve the two literals are mutually exclusive.

    In S1 Have(Cake) and Eaten(Cake) are mutually exclusive because the persistence action Have(Cake) is mutex with Eat(Cake), the only way of achieving Eaten(Cake).

    In S2 Have(Cake) and Eaten(Cake) are not mutually exclusive because there are actions for achieving them are not mutex, action Bake(Cake) achieves Have(Cake) and persistence of Eaten(Cake) are not mutex.