Making toast

We'd like to end up with a toasted and buttered slice of bread. So our main goals are holding(slice) AND toasted(slice) AND buttered(slice)

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 states

Previously: small set of variables bound to values

e.g. Q1 = 3

Upgrade:

• Predicates that take objects as inputs

  open(fridge), in(slice,toaster)

• States defined by logical combinations of predicates (e.g. AND, OR, NOT)

  open(fridge) AND NOT open(breadbag)

Upgraded representation of actions

Previously: action just resets the value of one variable.

Upgraded model

• Actions take objects as arguments Take-out(butter,fridge)
• Preconditions = logical conditions required for an action to happen
• Effects (postconditions) = changes that the action makes to the state of the world

STRIPS

Applications

Setting and ordering goals for robot systems:

• assembly
• disassembly
• moving through complex environments

The output high-level robot plans would then be implemented in detail using low-level path planning algorithms.

Stories

• Storytelling for entertainment, e.g. Automated storytelling projects by Mark Riedl, GA Tech.
• Stories and non-player characters for computer games
• Personalization and randomization of training scenarios (e.g. military exercises, online ethics training)

Closely-related problem: story understanding. E.g. summarizing the content of newswire stories. Requires an understanding of how individual actions fit together in a complex event, e.g. earthquakes cause landslides, emergency responses, expressions of sympathy.

Key features

Action order only partly constrained. In our toast example, one draft had

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

And the final draft had

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

Modelling realistic situations requires complex combinations of predicates. So we'd like to use a hierarchical approach (as example at the start of lecture). That is, identify the major subgoals and tackle each one individually.

Sussman anomaly

Sussman anomaly (1975)

Blocks world: robot can move only one block at a time, a block can be put on the (infinite) table or on another block (which must be clear).

                                                  A
    Start state            C              goal    B
                     B     A                      C

Intended solution:

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

Suppose we try to do on(A,B) first.

                                A
            B  C  A   ===>      B   C    

We can't finish the problm without unpiling A and B, thus undoing on(A,B).

Suppose we try to do on(B,C) first.

           B
           C    
           A

We can't put A onto B without unpiling all three blocks, thus undoing on(B,C).

Interleaved plans

So strictly hierarchical planning doesn't work.

Interleaved planning: 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.