CS 440/ECE 448
Margaret Fleck

## 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