UI logo
CS 440/ECE 448
Margaret Fleck

Classical Planning 2


History

Classical planning is called that because it goes back to the early days of AI. A simple version popularized by the STRIPS planner, created by Richard Fikes and Nils Nilsson 1971 at SRI. (STRIPS is short for Stanford Research Institute Problem Solver.)

These days, a planner would most likely be used to manage the high-level goals and constraints of a complex planning problem. For example, it might set the main way points for a mobile robot or a robot doing assembly/disassembly tasks. A neural net or specialized robotics code would then be used to fill in the details.

Stories

A planner can also be used to generate stories. These may be freestanding stories (e.g. like a novel). More often, these systems also include human interaction.

Neural nets can do a good job of filling in details, e.g. generating sentences given a sketch of what they should say. But they aren't (at least so far) good at keeping the high-level plot under control. E.g. see this article on automatically-generated Harry Potter stories.

A closely-related problem is story understanding. To understand stories written for a human audience, it helps to have models of what typically happens in them. The observation goes back to Roger Schank's work in the 1970's and 80's. E.g.

Understanding a story often requires filling in missing details that are obvious to humans. E.g. two people leave a store and the cashier runs out after them. Why? Well maybe to return a forgotten credit card. A human knows the payment script well enough to realize that it involves returning the card.

The frame problem

Classical planning representations quickly get complex as you move beyond toy problems, so we have to make some simplifying assumptions. For example, the high-level vision of action representations is that they describe how the action changes the world. However, a complete logical representation also requires "frame axioms" that specify which predicates an action does not change. For example

heat(substance,pan) has in(substance,pan) as both a precondition and effect

If we handle such constraints explicitly, our action descriptions end up needing a lot of frame axioms. This is a waste of memory. But, much more important, it is an invitation to bugs: writing out long lists of frame axioms means that some will inevitably be left out. 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.)

Extending our representation

The representation of objects in classical planning leaves much to be desired. Extensions of this framework are beyond the scope of this class. But it's worth thinking about some of the issues, because they continue to be problems even when planning is combined with more modern technology.

First, we need ways to represent type hierarchies for objects, e.g. pie is a type of desert and deserts are a type of food. For example, washing a tablecloth should use the same action as washing a napkin. Eating an apple is similar to, but not identical to, eating rice. So perhaps they should inherit some of their representation from a shared ancestor. Then we might define actions that can be used on any object from a broad range of types.

A closely-related problem is making it possible to have multiple objects of the same type (e.g. two napkins).

Some object properties should be called out as predicates. In a kitchen scenario, many types of object are movable (e.g. eggs, kettle) but some are not (e.g. the counters) and some (e.g. the stove) should be considered non-movable for most routine planning. However, it's not immediately obvious when we should create an explicit predicate (e.g. movable) vs. having rules that target only certain types of objects.

We might want to specify relationships among predicates. For example, how are cold and hot related? Also might want a "Truth Maintenance System" to spell out the consequences of each proposition. For example, automatically account for the fact that the teabag cannot be in two places at once. Such knowledge and inference would allow more succinct (and likely more correct) state and action definitions.

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

But we need to keep the overall representation simple enough to do planning at a reasonable speed.

Harder environments

A final issue is that planning may need to work in less tightly managed environments. These might include:

This might be best handled by a combination of a classical planning and an adaptive technology such as reinforcement learning. But it's not always clear how to make them work well together.