Planning

In industry in general, the term planning has been used to describe a wide variety of problems, including problems referred to by the artificial intelligence community as scheduling or bin packing.

In AI, the term planning is used to describe the construction of a sequence of formally-described world-states, as follows: A planning domain consists of a set of operators or action types. Each operator may be executed only in some particular set of world states (its preconditions), and has some particular set of effects on its world state (its effects). A planning problem consists of a planning domain together with an initial state of the world, and a desired goal state (or set of goal states) of the world. A planner solves a planning problem by producing a sequence of actions (operator instances), each of which is legal in its starting world state, which takes the initial state to a goal state.

In AI planning systems, world states are often described in terms of boolean state variables (fluents). The best-known version of this is STRIPS planning, in which operator effects are defined by an add list of fluents which become true when the operator is executed, and a delete list of fluents which become false when the operator is executed. In the original STRIPS system, world states and operator preconditions and effects were described using first-order logic, which makes planning difficult for tractability reasons. More common these days are predicate STRIPS, in which all formulae are quantifier-free, and propositional STRIPS, in which all formulae are ground.

An often cited example of a planning domain is the infamous blocks world, a model of stacks of blocks on an infinite table. In a typical predicate STRIPS formulation, the fluents are predicates over a domain of blocks:

clear(B)
There is no block on block B
on-table(B)
Block B is on the table.
on(B1,B2)
Block B2 is on block B2.
The operators move a clear block onto another clear block (or the table).
move-bb(B1,B2,B3) (move B1 from atop B2 to atop B3)
preconditions
  • clear(B1)
  • clear(B3)
  • on(B1,B2)
adds
  • clear(B2)
  • on(B1,B3)
deletes
  • clear(B3)
  • on(B1,B2)
move-tb(B1,B3) (move B1 from the table to atop B3)
preconditions
  • clear(B1)
  • clear(B3)
  • on-table(B1)
adds
  • on(B1,B3)
deletes
  • clear(B3)
  • on-table(B1)
move-bt(B1,B2) (move B1 from atop B2 to the table)
preconditions
  • clear(B1)
  • on(B1,B2)
adds
  • on-table(B1)
  • clear(B2)
deletes
  • on(B1,B2)

A famous planning problem in the blocks world domain is the Sussman anomaly. This problem has this initial state:

[c] on [a] on table, [b] on table

and this final state:

[a] on [b] on [c] on table

A shortest sequence of move operators that solves this problem is Note that the shortest plan for achieving the goal cannot begin with the shortest plan for achieving either of the obvious subgoals on(a,b) and on(b,c): this is what is ``anomalous'' about the problem. Current open issues in planning concern efficient planning and efficient and expressive domain representations, using such techniques as hierarchy and probabilistic methods.

CIRL

Different approaches to planning have been developed by researchers at CIRL. Work has been centered on hierarchical planners, tractable planning using a multi-valued logic, planning as satisfiability, and fundamental planning issues such as directionality.

Pointers

Unsolved Problems in Planning as Constraint Satisfaction
This paper describes the problems that are encountered when encoding planning as constraint satisfaction. Written by Tania Bedrax-Weiss, Ari Jónsson, and Matt Ginsberg. Compressed postscript document.
A New Algorithm for Generative Planning
This paper describes a new algorithm for generative planning that solves subgoals in isolation and then appeals to a separate NP-complete scheduling test to determine whether the actions that have been selected can be combined in a useful way. Written by Matt Ginsberg and appeared in Proc. KR in 1996. Compressed postscript document.
Approximate Planning
This paper describes approximate planning. Written by Matt Ginsberg and appeared in Artificial Intelligence. Compressed postscript document.

Parent areas:
General Purpose Tools

Application Programs:
O-Plan

References

Blackbox is a planning system that works by converting problems specified in STRIPS notation into Boolean satisfiability problems and using state-of-the-art satisfiability engines to find solutions to the problem.

Austin Tate, Brian Drabble and Richard Kirby, "O-Plan2: An Open Architecture for Command, Planning and Control", in Intelligent Scheduling, (eds. Monte Zweben, Mark Fox), Morgan Kaufmann Publishers, San Francisco, 1994.

Back to the CIRL Overview Page.