How is automated planning different from general search?

Automated planning is a form of search, but it works from a declarative, factored description of actions (preconditions and effects) rather than an opaque successor function. This structure lets planners automatically derive heuristics and reason about which actions are relevant, which generic search cannot do.

PDDL, the Planning Domain Definition Language, is a standard language for describing planning domains and problems—objects, predicates, actions, the initial state, and the goal. It lets domain-independent planners be compared on a common benchmark, as in the International Planning Competitions.

Automated Planning

Automated planning is the branch of artificial intelligence concerned with computing sequences of actions that transform an initial state of the world into a desired goal state, given a formal description of the available actions.

Definition

Automated planning is the computation of a plan—an ordered (or partially ordered) set of actions—that provably achieves a goal from an initial state, given a model of how each action changes the state of the world.

Scope

This area covers the representation of planning problems (states, actions with preconditions and effects, goals) and the algorithms that solve them: classical planning in deterministic, fully observable domains, planning-graph and heuristic-search methods, hierarchical task network planning, and the extension to time, resources, and scheduling. It treats standard formalisms such as STRIPS and PDDL and the complexity of planning. Planning under probabilistic uncertainty connects to reasoning under uncertainty, and learning action models or policies from data belongs to the machine-learning subfield.

Sub-topics

Core questions

How are actions, states, and goals represented compactly enough to describe large domains?
How is the planning problem searched efficiently despite an exponentially large state space?
How are admissible and informative heuristics derived automatically from a domain description?
How can plans be structured hierarchically, and how are time and resource constraints incorporated?

Key concepts

states, actions, goals
preconditions and effects
STRIPS and PDDL
forward and backward state-space search
planning graphs
domain-independent heuristics
hierarchical task networks
temporal planning and scheduling

Key theories

STRIPS action representation: The STRIPS formalism describes actions by preconditions and add/delete effects over a set of propositions, providing a compact, factored representation that makes planning a search through symbolic states rather than an enumeration of explicit world states.
Domain-independent heuristic search for planning: Modern planners cast planning as heuristic search and derive heuristics automatically from the problem description, for example by ignoring delete effects or exploiting causal structure, enabling strong general-purpose performance.
Planning as a hierarchy of problem classes: Planning spans a spectrum from classical deterministic planning to hierarchical, temporal, and resource-constrained variants, each with characteristic representations and complexity, organized in the standard theory of automated planning.

Clinical relevance

Automated planning is applied in robotics and autonomous systems, spacecraft and mission operations, logistics and supply chains, manufacturing, and game and narrative generation; planners derived from these techniques have controlled real autonomous spacecraft and coordinate complex workflows.

History

Automated planning began with STRIPS for the Shakey robot at SRI around 1971, framing planning as theorem-proving over action descriptions. The field progressed through partial-order planning, the Graphplan breakthrough (1995), and the rise of fast domain-independent heuristic-search planners and the PDDL standard from the late 1990s onward, tracked through the International Planning Competitions.

Key figures

Richard E. Fikes
Nils J. Nilsson
Malik Ghallab
Dana Nau
Paolo Traverso
Malte Helmert

Seminal works

fikes1971
ghallab2004
helmert2006

Frequently asked questions

How is automated planning different from general search?: Automated planning is a form of search, but it works from a declarative, factored description of actions (preconditions and effects) rather than an opaque successor function. This structure lets planners automatically derive heuristics and reason about which actions are relevant, which generic search cannot do.
What is PDDL?: PDDL, the Planning Domain Definition Language, is a standard language for describing planning domains and problems—objects, predicates, actions, the initial state, and the goal. It lets domain-independent planners be compared on a common benchmark, as in the International Planning Competitions.