CS 440/ECE 448
Margaret Fleck

## Recap

In a classical planning problem, we have

• States defined by logical combinations of predicates, 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)

## Situation space planning

The most obvious approach to classical planning is "situation space planning". In this method

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

Suppose that we're using situation space planning to make a cake. Our starting state might look like

start: have(flour), not(have(eggs)), number-of(spoons,3), not(have(cakepan)), ...

What action should we take first? Perhaps we should go buy the eggs. Then the start of our plan might look like:

start: have(flour), not(have(eggs)), number-of(spoons,3), not(have(cakepan )), ...
next: have(flour), have(eggs), number-of(spoons,3), not(have(cakepan)), ...

Or we might buy the cakepan next, in which case the next state would be

start: have(flour), not(have(eggs)), number-of(spoons,3), not(have(cakepan )), ...
next: have(flour), not(have(eggs)), number-of(spoons,3), have(cakepan), ...

Issues with situation space planning

• very large branching factor
• unnecessarily specific about ordering of unrelated actions

Any planner will eventually need to pin down the order of all actions, so that it can execute the plan. However, it makes sense to make unimportant ordering decisions as late as possible.

## Forward and backward planning

We saw that situation space planning can get into trouble because there's too many possible actions at each step. We might try applying backwards or bidirctional search. For example:

start: typical student apartment
goal #1: make dinner

It's sensible to see what we can make with available ingredients. (Not ramen AGAIN!!!) But suppose we switch to

start: typical student apartment
goal #2: make a birthday cake

We probably don't have the ingredients. So we should start by checking the recipe, so we can plan what to go out and buy.

In planning problems, the goal is often very specific compared to possible successors of the starting state. So it makes sense to do backwards or bidirectional planning. However, we'll see a different approach (partial order planning) that makes a more significant difference.

## Hierarchical Planning

Hierarchical planning is another useful idea that doesn't work as well as you might hope. The idea here is that planning problems often have a natural arrangement of tasks into main goals and subgoals. In a complex problem, there might be a multi-layer hierarchy of tasks.

For example, you might sketch out the overall plan for buying groceries:

• Make a list
• Drive to the store
• Buy everything on the list
• Drive home
• Put everything away

However, actually doing each of these tasks requires quite a bit more detail. E.g. buying the items might require

• Enter the store
• Get a cart
• Go through the aisles picking up items
• Wait for a cashier
• Pay for the items
• Go to the car
• Return the cart

And obviously we could go into even more detail. At the lowest levels, e.g. moving the car around the produce displays, we might wish to switch control over to a neural net or a reinforcement learning model. But some of these details (e.g. making sure we bought everything on the list) might be best handled symbolically.

It is tempting to think that we can base our planning algorithm on this hierarchical structure. That is true to some extent. Unfortunately, strictly hierarchical planning doesn't always work A famous example is the Sussman anomaly (Gerry Sussman, 1975) This comes from a variant of the blocks world. Blocks can be put on an (infinite) table or stacked on top of one another. The robot can move only one block at a time. Suppose we have the following starting state and goal:

                                                  A
Start state            C              goal    B
B     A                      C


The intended solution is

• move(C,table)
• move(B,C)
• move(A,B)

Let's try to do this hierarchically. We have two subgoals: on(A,B) AND on(B,C). Let's first deal with one subgoal and then deal with the other.

Attempt #1: Suppose we try to deal with on(A,B) first. To do this, we clear the block A (so we can pick it up) and then put it on top of B.

            C                                A
B    A    ===>    B  C  A   ===>      B   C


Now we turn to goal on(B,C). But we can't put B onto C without unpiling A and B. So we've wasted all our previous work putting A onto B.

Attempt #2: Suppose we try to deal with on(B,C) first. So we make the following move:

                                B
C        ====>      C
B     A                   A


Now we turn to goal on(A,B). But we can't put A onto B without unpiling all three blocks, thus undoing on(B,C).

So strictly hierarchical planning doesn't work. We need a more flexible approach to planning. For example, expand what's required to meet subgoals, then try to order all the little tasks. So you can "interleave" sub-tasks from more than one main goal.