Making toast

We'd like to end up with a toasted and buttered slice of bread. So our goal is something like holding(slice) AND toasted(slice) AND buttered(slice). The individual conjuncts, e.g. toasted(slice), are the main subgoals.

To get toasted(slice) AND buttered(slice), we might decide we need to do this:

Heat(slice,toaster).
Spread-on(butter,slice)

But each of these actions requires some set-up:

Put-in(slice,toaster)
Heat(slice,toaster).
Take-out(slice,toaster)
Spread-on(butter,slice)

But, we can't do any of this without first getting the slice of bread and the butter. So before anything else we should do

Open(fridge)
Open(breadbag)
Take-out(slice,breadbag)
Take-out(butter,fridge)

Here's a more-or-less final plan:

Make-Open(breadbag) --> achieves open(breadbag)
Take-out(slice,breadbag) ---> requires open(breadbag), achieves holding(slice)
Make-Open(fridge) --> achieves open(fridge)
Take-out(butter,fridge) ---> requires open(fridge), achieves holding(butter)
Put-in(slice,toaster) --> requires holding(slice), achieves in(slice,toaster)
Heat(slice,toaster) --> requires slice in toaster, achieves toasted(slice)
Take-out(slice, toaster) --> achieves holding(slice)
Put-on(slice,plate) --> requires holding(slice)
Spread(butter,slice) --> requires slice on plate, holding(butter), achieves buttered(toast)

Upgraded representation of the world

Plan construction is yet another application of search, but this time with a more powerful representation of states and actions. Previously our world was represented by a small set of variables bound to concrete values such as numbers. E.g.

Q1 = 3 (The queen in column 1 is in row 3.)

In classical planning, features of the world are encoded using predicates that take states as objects, e.g.

open(fridge)
in(slice,toaster)

The state of the world is represented by a logical combination of predicates (e.g. AND, OR, NOT)

open(fridge) AND NOT open(breadbag)

This style of representation makes our planner look smarter than it is. By writing "spread," we've implied that the computer has some ability to recognize or execute the corresponding real-world action. That connection would have to be made by other parts of our AI system, e.g. the image recognition system and the low-level robotics system. Frequently those systems are a lot less general and robust than one might hope.

Upgraded representation of actions

In our previous search examples, each action set or reset the value of one variable. Actions now take objects as parameters, e.g.

Take-out(butter,fridge)

Each action has two sets of predicates:

• Preconditions: logical conditions required for an action to happen
• Effects (postconditions): changes that the action makes to the state of the world

So the action take-out(butter,fridge) might have

• Preconditions: in(butter,fridge), is-open(fridge)
• Effects: holding(butter)

The preconditions and postconditions determine how actions can fit together into a coherent plan. They also encode some very limited real-world knowledge about the meaning of each action.

Partial Ordering

Another source of difficulty in classical planning is that the action order is only partly constrained. In our toast example, we could have this ordering:

Open(fridge)
Open(breadbag)
Take-out(slice,breadbag)
Take-out(butter,fridge)

But this ordering works just as well.

Open(breadbag)
Take-out(slice,breadbag)
Open(fridge)
Take-out(butter,fridge)