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)

Asymptotic complexity

Abandon hope:

Towers of Hanoi takes exponential time. (The shortest solution requires a number of moves exponential in the number of disks.)

More seriously, these problems get difficult very quickly, 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.

Situation space planning

Each node contains predicates completely describing the world.

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

An edge in planning graph updates the state of the world.

Example: suppose we need to have flour, eggs, and a cakepan. Our next action might be to buy the eggs, so the world state changes to

start: 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), have(cakepan), ...

Issues with situation space planning

• very large branching factor
• unnecessarily definite 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

Planning is a good domain for backwards or bidirectional search. 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

goal #2: make a birthday cake

We probably don't have the ingredients. Check recipe first so we can plan what to go out and buy.

Goal is often very specific compared to possible successors of starting state. So it makes sense to do backwards or bidirectional planning.

Plan space (partial-order) planning

Each node contains a partial plan, i.e.

• actions
• orderings between actions

Each edge in the planning graph adds more actions and/or ordering constraints.

Idea: we only add orderings where required to ensure that plan will work

Start with largely empty plan, just the "start" and "finish" actions

• "start": no preconditions, sets up information true at start of plan
• "finish": no effects, preconditions are what needs to be true at end of plan
• ordering: start < finish

Add more actions and orderings until plan is complete

Improving incompete plans

What could be wrong with a partial plan?

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

Plan modification operations

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

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

Example: setting table

Problem setup:

tc = tablecloth
start: is-on(tc,table), not(clean(tc)), clear(tc), not(holding(tc), not(on(plates,tc)) ...
goals: is-on(tc,table), clean(tc), is-on(plates, tc) ...

is-on(tc,table) is apparently already achieved

Let's deal with the plates first, by adding a put-on action. This requires is-on(tc,table), so also add an ordering link.

                start
                 |
                 V
     put-on(plates, tc)  
                 |
                 V
                finish

Now let's deal with the dirty tablecloth, by adding a shake(tc) action to remove the crumbs

                start--------------
                 |                |
                 V                V
     put-on(plates, tc)       shake(tc)
                 |                |
                 V                |
                finish <-----------
 

Shaking requires holding the object, so we have to add a removal operation

                start--------------
                 |                |
                 |                V
                 |            remove(tc)    
                 |                |
                 V                V
     put-on(plates, tc)       shake(tc)
                 |                |
                 V                |
                finish <-----------
 

Now we have a threat. put-on(plates,tc) needs tc to be on the table, but remove(tc) makes that not true. Also, remove(tc) needs tc to be clear, but put-on(plates,tc) makes that not true. So we need to add an ordering link between the two actions. We'll then patch up any further issues with the preconditions, e.g. by adding an action put-on(tc,table) to put the tablecloth back in place.

The frame problem and friends

Notice how complicated our representations are already getting. We might wish to make some simplifying assumptions.

A strict logical representation would require "frame axioms" to specify all the predicates that an action does not change. We need a lot of these, so it's easy for some to be missing. This nuisance is called the "frame problem." It's usually solved by incorporating a default assumption that properties don't change unless actions explicitly change them. (We've been tacitly assuming that.) There are places where this doesn't work right, e.g. milk left in the fridge eventually spoils.

Also might want a "Truth Maintenance System" to spell out the consequences of each proposition. So if we say that on(plates,tc), we can infer that not(clear(tc)). This would allow more succinct (and likely more correct) state and action definitions.

GraphPlan

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) ..

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).

Extending our representation

In the tablecloth example above: shaking doesn't really cut it. How about changing the tablecloth? If so, how to represent two objects of the same type?

Washing a tablecloth should use the same action as washing a napkin. Eating a salad is similar to eating a casserole. So object types should be put in a hierarchy, like types in programming languages. Then we could have actions that can be used on any object from a broad range of types.

We also have no way to represent substances that must be measured:

• liquids and substances (e.g. flour)
• multiple objects of the same type (e.g. ten gig sticks)
• actions that take time to finish (e.g. cooking oatmeal)

Harder environments

Planning also needs to work in difficult environments

• Incomplete knowledge of environment (e.g. via sensors)
• Obstacles, other actors might move/change
• What if actions fail?
• How long before I have to finish planning and act?

Videos etc

Udacity A* car video illustrating A* adapted to a car learning about a changing world via sensors.

AI in action

Robat, a robot that navigates by echolocation.