Recap

Classical planning problem

• States defined by logical combinations of predicates (e.g. AND, OR, NOT), e.g. open(fridge) AND NOT open(breadbag)
• Actions take objects as arguments, e.g. Take-out(butter,fridge)
• Actions have preconditions and effects (postconditions)

Plan space (partial order) planning

So far, we've used a "situation space" approach to planning, in which our search space looks like:

• Each state is a complete model of the world.
• Each edge is an action that changes the state of the world.

Searching in situation space has a massive branching factor. Patches such as backwards planning and hierarchical planning don't properly address this problem.

When looking at the edit distance problem near the start of the term, we built a much more efficient solution by replacing a search through complete matches with a search through partial matches. A similar idea is used in "plan space" planning (also called "partial order" planning). Our search space now looks like:

• Each state is a partial plan, perhaps missing some actions or ordering links.
• Each edge adds detail to the partial plan.

Specifically, in plan space planning, each node in the search graph contains a partial plan. A partial plan includes

• actions
• orderings between actions

This reformulation of the planning problem gives us a search problem with a more manageable set of options at each step.

Plan space example

For example, a partial plan for making tea might look like this:

                start--------------
                 |                |
                 V                V
            heat(water,kettle   put-in(teabag,teapot)
                 |                |
                 V                |
                finish <-----------
 

Start and finish are special actions:

• "start": no preconditions, its effects are the information that is true at start of the plan
• "finish": no effects, preconditions are what needs to be true at the end of the plan

The initial state in the planning process looks like this: the start and finish actions, with start ordered before finish.

                start
                 |
                 V
                finish

The preconditions and effects are invisible in this diagram. For our tea example, they might be

• effects of start: cold(water), not(in(teabag,teapot)), not(tasty(water), not(in(water,teapot))
• pre-conditions of finish: tasty(water), not(in(teabag,teapot))

Each edge in the planning graph adds more actions and/or ordering constraints. Finish has a precondition tasty(water). We might try to satisfy this using the steep action:

                start
                 |   
                 V    
             steep(teabag,water,teapot)
                 |      
                 V      
                finish 
 

But steeping requires that the water be hot and everything put in the teapot. And then we need to also ensure that the teabag is out of the water at the end. So we add more actions and orderings until we reach a complete plan.

                        start
                     /         \
                    /           \
                   V             V
        put-in(water,kettle)    put-in(teabag,teapot)
                   |                |
                   V                |
        heat(water,kettle)          |
               |                    |
               V                    | 
           put-in(water,teapot)     |
                   |                |
                   V                V
                  steep(teabag,water,teapot)
                        |
                        V
                  remove(teabag,teapot)
                        |
                        V
                      finish 
 

Notice that our path from start to finish may require undoing some properties that we have made true. For example, the teabag is put into the teapot and then later removed.

Improving incomplete plans

A key idea in partial order planning is to add actions and orderings of actions only when they are required to ensure that the plan will succeed. The output plan is typically a partial order, in which some pairs of actions are left unordered. When the plan is executed, these pairs can be scheduled in either order or done in parallel. In our example, our final plan leaves several choices for when to put the teabag into the teapot.

What could be wrong with a partial plan? There are two basic problems for the planner to detect and resolve:

• "open precondition": an action (including finish) has a precondition with no guarantee that it will be true when the action is executed
• "threat": P is true at some point, but an (unordered) action might cause not(P)

For example, suppose that our partial plan looks as below.

                start
                 |   \
                 |    V
                 |    put-in(water,teapot)
                 |     |
                 V     V
             steep(teabag,water,teapot)
                 |      
                 V      
                finish 
 

The preconditions of the steep action require that the water be hot. That's an open precondition. We can fix this defect by adding another action that makes the water hot, ordered before the steep action:

                       start
                     /        \
                    /          \
                   V            V
           heat(water,kettle)    put-in(water,teapot)
                   |                |
                   V                V
                  steep(teabag,water,teapot)
                        |
                        V
                      finish 
 

We now notice an open precondition on the heat(water,kettle) action, i.e. that the water needs to be in the kettle. So let's add an action to fix that bug.

                       start
                     /        \
                    /          \
                   V            \
        put-in(water,kettle)     \
                   |              \  
                   V               V
        heat(water,kettle)    put-in(water,teapot)
                   |                |
                   V                V
                  steep(teabag,water,teapot)
                        |
                        V
                      finish 
 

Now the heat action has in(water,kettle) as a precondition. As our plan stands right now, this is possible but not guaranteed. Putting the water into the teapot threatens to "clobber" that precondition, if we were do put-in(water,teapot) before heat(water,kettle). We can fix this bug in the plan by adding an ordering link between the two actions.

                       start
                         |
                         V
                put-in(water,kettle)
                         |
                         V
                heat(water,kettle)    
                         |
                         V
                put-in(water,teapot)
                         |
                         V
                steep(teabag,water,teapot)
                        |
                        V
                      finish 
 

In general, we have the following set of plan modification operations

• To fix an open precondition
  • add an ordering link to an existing action
  • add a new action

• To fix X threatening to "clobber" Y's preconditions
  • order X after Y
  • order Y after X (leaving Y with an explicitly open precondition)

It's reasonable to expect that a partial plan has only a small set of immediately visible defects. Although our knowledge base may contain a large number of actions, it's reasonable to hope that only a small set would be relevant to filling in an open prerequisite. So our search graph has a much smaller fan-out (typical number of successors to each state) than the search graphs in situation space.

Better Algorithms

In general, classical planning can get very difficult. Consider the Towers of Hanoi puzzle. (Also see demo.) Solutions to this puzzle have length exponential in the number of disks. When modelling realistic situations, planning constraints and background knowledge (e.g. action pre- and post-conditions) can get very large. So it's essential to exploit all available domain constraints. For practical tasks (e.g. robot assembly, face recognition) folks often engineer the task/environment to make the AI problem doable.

A faster algorithm for this type of planning is the the GraphPlan algorithm. Details beyond the scope of this course. See the paper by Blum and Furst (1997) ( on the web). Graphplan uses a more complex planning graph with alternating layers of facts and actions. Edges link either facts to actions (preconditions), or actions to facts (effects).

There is also recent work on learning STRIPS-style representations from observations (which may be noisy and/or incomplete). A recent example is Mourao et al 2012 paper (also at Xarchiv).