What are the assumptions of classical planning?

Classical planning assumes a single agent acting in a deterministic, fully observable, and static environment, with actions taking unit time and a fully known initial state. Relaxing any of these assumptions, for example allowing uncertainty or concurrency, leads to richer planning problems beyond the classical model.

What does the STRIPS add list and delete list mean?

When a STRIPS action is applied, the propositions in its add list become true and those in its delete list become false; all other propositions are unchanged. This simple update rule is what makes STRIPS a compact and computationally convenient representation of how actions change the world.

Classical Planning and STRIPS

Classical planning addresses the problem of finding a sequence of actions to reach a goal in a deterministic, fully observable, static environment, using the factored STRIPS-style representation of actions by preconditions and effects.

Definition

Classical planning seeks a sequence of deterministic actions that transforms a fully known initial state into a state satisfying the goal, where each action is described by the conditions that must hold for it to apply and the changes it makes.

Scope

This topic covers the classical planning model and its assumptions (deterministic actions, full observability, a single agent, atomic time), the STRIPS and ADL/PDDL representations of states and actions, the basic solution methods of forward (progression) and backward (regression) state-space search and partial-order planning, and the computational complexity of propositional planning. Heuristic guidance and planning graphs are treated in the related topic, and nondeterministic or probabilistic variants are out of scope.

Core questions

What assumptions define the classical planning model, and when are they appropriate?
How does the STRIPS representation factor a state into propositions and an action into preconditions and add/delete effects?
How do progression and regression search differ as planning strategies?
How computationally hard is classical planning in general?

Key concepts

deterministic, fully observable model
STRIPS preconditions and effects
add and delete lists
PDDL and ADL
progression (forward) search
regression (backward) search
partial-order planning
plan existence complexity

Key theories

STRIPS representation: STRIPS describes the world as a set of true propositions and each action by a precondition list plus add and delete lists, so applying an action simply adds and removes propositions; this factored model is the foundation of nearly all classical planners.
Progression and regression search: Classical plans can be found by searching forward from the initial state applying applicable actions (progression) or backward from the goal computing regressed subgoals (regression), with partial-order planning relaxing the commitment to a total action ordering.
Complexity of planning: Deciding whether a propositional STRIPS plan exists is PSPACE-complete in general, formally explaining why planning is hard and motivating heuristic and structural methods to make it practical.

Clinical relevance

Classical planning representations are the common interface for robot task planning, automated assembly and logistics, and any application where deterministic actions must be sequenced to reach a goal; PDDL-based classical planners are the workhorses of the field and of the International Planning Competitions.

History

STRIPS was developed at SRI around 1971 to control the Shakey robot, introducing the precondition/effect action model that defines classical planning. Partial-order planning matured in the 1970s-80s, Bylander established the PSPACE-completeness of propositional planning in 1994, and the PDDL standard later unified the field's benchmarks.

Key figures

Richard E. Fikes
Nils J. Nilsson
Tom Bylander
Earl D. Sacerdoti

Seminal works

fikes1971
bylander1994

Frequently asked questions

What are the assumptions of classical planning?: Classical planning assumes a single agent acting in a deterministic, fully observable, and static environment, with actions taking unit time and a fully known initial state. Relaxing any of these assumptions, for example allowing uncertainty or concurrency, leads to richer planning problems beyond the classical model.
What does the STRIPS add list and delete list mean?: When a STRIPS action is applied, the propositions in its add list become true and those in its delete list become false; all other propositions are unchanged. This simple update rule is what makes STRIPS a compact and computationally convenient representation of how actions change the world.