Automated planning is a branch of artificial intelligence concerned with computing actions that transform an initial situation into one satisfying specified objectives. A planning system receives some representation of the world, the actions available to an agent, and the desired outcomes, then constructs a plan or policy. Depending on the problem, its output may be a sequence of actions, a partially ordered collection of activities, a timed schedule, or a strategy that selects actions in response to observations.
Planning is distinguished by reasoning explicitly about the consequences and interactions of actions. A delivery task, for example, may require deciding which vehicle should carry a package, whether it must first refuel, and which activities can occur concurrently. The field connects knowledge representation and reasoning, search, mathematical optimization, and decision-making under uncertainty. Its methods support applications ranging from spacecraft operations and industrial workflows to autonomous robots and software agents.
Classical planning provides a particularly influential foundation: it assumes a known initial state, deterministic actions, and a world that changes only through the actions represented in the model. Other forms introduce time, resources, incomplete information, stochastic outcomes, interacting agents, or hierarchical procedures. Across these variants, a central distinction separates finding a plan that is correct according to a model from ensuring that its execution succeeds in the physical or computational environment.
Historical development and intellectual foundations
Automated planning emerged from early work on problem solving and symbolic artificial intelligence. The General Problem Solver, developed beginning in the late 1950s by Allen Newell, Herbert A. Simon, and J. C. Shaw, explored means–ends analysis: comparing a current situation with a goal, selecting an operator that reduces a difference, and establishing the conditions needed to apply that operator. Although its representations and performance were limited, it established a durable view of intelligent action as the construction of intermediate subgoals rather than the direct selection of an isolated response.
An important alternative foundation came from logic. In the situation calculus, associated with John McCarthy and subsequent work by Patrick Hayes and others, actions are represented as producing new situations, and logical statements describe what holds in those situations. This exposed the frame problem: specifying what remains unchanged when an action occurs. Moving a box changes its location but normally does not change its color, the location of every other box, or the contents of an unrelated room. Efficient planning representations need to capture such persistence without enumerating every unaffected fact for every action.
The STRIPS system, introduced by Richard Fikes and Nils Nilsson in 1971 in connection with the Shakey robot project, supplied an especially influential operational representation. Actions were described by preconditions and lists of facts to add or delete. This restricted language made state transitions straightforward to compute and became a foundation for later theoretical analysis and benchmark planning. Work on interacting subgoals also showed why simply solving each goal separately could fail: an action achieving one condition might destroy another condition already established. Blocks-world examples became standard illustrations of these dependencies.
Research subsequently diversified into plan-space methods, hierarchical decomposition, constraint reasoning, and more effective state-space search. The 1990s brought several major advances. Kautz and Selman’s 1992 work connected planning with propositional satisfiability; Blum and Furst introduced Graphplan in 1995; and heuristic planners such as HSP and FF helped establish efficient forward search as a leading approach around the turn of the century. These developments were not successive replacements of a single technique. They offered different ways to exploit action structure, represent interactions, and control combinatorial search.
The Planning Domain Definition Language (PDDL), introduced in 1998 alongside the first International Planning Competition, gave researchers a common language for exchanging domains and problem instances. Later versions added features including durative actions, numeric quantities, preferences, and trajectory constraints. Shared representations and competitions made comparisons more systematic, while also revealing that planning performance depends strongly on the supported language fragment, the optimization criterion, and the structural properties of the benchmark domain.
Formal models, plans, and computational difficulty
A common finite classical planning model is a tuple
where is a set of propositional facts, is a set of actions, is the initial state, and is the goal. A state records the facts currently true. Under the usual closed-world convention, facts absent from the state are false. An action has preconditions , add effects , and delete effects . If its preconditions hold, its successor state is
This representation makes action applicability and state update explicit.
A sequential plan is an action sequence executable from , with . Consider a package initially at depot , a truck at , and a destination . Loading requires the package and truck to be colocated; driving changes the truck’s location; unloading transfers the package from the truck to its current location. The goal “package at ” does not itself specify these intermediate steps. A planner derives them from the transition model and must avoid sequences such as unloading before loading.
Finding any valid plan is different from optimizing one. Actions may carry nonnegative costs, giving a plan cost
Other objectives include minimizing elapsed time, fuel consumption, missed deadlines, or combinations of competing criteria. A shortest action sequence need not be cheapest or fastest: one long-duration action can have lower action count but greater execution time than several concurrent activities. Some formulations also distinguish hard constraints, which every acceptable plan must satisfy, from preferences whose violations incur penalties.
The apparent simplicity of the classical model conceals substantial computational complexity. With independent Boolean facts there can be states, even when actions and the initial state have compact descriptions. For standard propositional STRIPS planning, deciding whether any plan exists is PSPACE-complete. Plans can require exponentially many actions in the input size. Consequently, a planner that quickly handles large practical instances does not establish that arbitrary planning problems are easy; it may be exploiting favorable structure, accepting suboptimal solutions, or both.
Complexity also depends on representation. Explicitly listing every state gives a different input size from describing states through variables and action schemas. Fixing a polynomial action horizon changes the decision problem, and restricting action effects or dependencies can produce easier subclasses. Conversely, adding sufficiently expressive numeric operations or unrestricted hierarchical mechanisms can make some planning formulations undecidable. Meaningful claims about tractability therefore specify the language, objective, horizon, and assumptions rather than treating “planning” as a single computational problem.
Domain languages and knowledge engineering
Practical planning descriptions usually separate a reusable domain from individual problems. A domain defines object types, predicates, and action schemas; a problem supplies the objects, initial conditions, and goals for a particular instance. A schema such as load(package, truck, location) abbreviates many concrete actions. Substituting actual objects for its parameters is called grounding. Types and static relations can eliminate impossible substitutions, but naive grounding may still generate enormous action sets when schemas contain many parameters or the object population is large.
PDDL became a standard interchange language partly because this separation supports reusable modeling and controlled extensions. Its syntax identifies required features, allowing planners to reject unsupported constructs rather than silently interpret them incorrectly. Basic STRIPS-style descriptions use predicates and action effects, while richer fragments include negative preconditions, quantification, conditional effects, and derived predicates. A conditional effect specifies a change that occurs only if an additional condition holds at execution time. A derived predicate is inferred from other facts rather than changed directly by an action, making it useful for relations such as reachability.
An alternative internal representation uses finite-domain variables rather than independent Boolean propositions. A truck’s location can be represented by one variable whose values are the available depots, avoiding combinations in which the truck is simultaneously at several places. Planners can discover invariants such as “each package has exactly one location,” then compile propositional descriptions into more compact variable-based forms. Domain transition graphs describe how individual variables change, while causal graphs record dependencies between variables. These structures support both preprocessing and heuristic estimation.
The knowledge base embodied in a domain model is often as important as the search algorithm. An omitted precondition may permit physically impossible actions; a missing effect may prevent a real solution from being represented. Resource constraints, exclusivity conditions, and assumptions about persistence must all be encoded consistently. For example, a loading action that does not require the truck to be at the package’s location may yield short but meaningless plans. Invariants can expose such errors, while small diagnostic problems make it easier to identify whether a failure arises from search or modeling.
Model validation is distinct from plan validation. A validator checks that a particular plan obeys the formal action semantics and achieves the stated goals. It cannot, by itself, establish that the domain accurately represents the intended environment. Connections with formal verification and ontologies help clarify specifications, but abstraction remains unavoidable. A logistics model may ignore tire wear, road gradients, or loading geometry because those details are irrelevant at its planning level. Its adequacy depends on whether omitted details can invalidate decisions delegated to that level.
State-space search and heuristic guidance
Classical planning can be understood as finding a path through an implicitly defined state graph. In forward search, the initial node is , successors result from applicable actions, and a goal test checks whether the required conditions hold. Backward search instead reasons from goals toward sufficient predecessor conditions, often through regression. Forward search benefits from concrete states and straightforward applicability checks; regression can focus attention on actions relevant to goals but may encounter complicated combinations of conditions. Neither direction eliminates the need to handle interacting subgoals.
Uninformed methods such as breadth-first search can find shortest unit-cost plans but often explore too many states. Modern planners therefore rely heavily on a heuristic , an estimate of the effort remaining from state . A* search prioritizes states using , where is the cost already incurred. Under appropriate conditions, including an admissible heuristic that never overestimates the optimal remaining cost, A* can find optimal plans. Greedy best-first search prioritizes alone and often finds satisfactory plans more quickly, without generally preserving optimality.
A major family of planning heuristics comes from delete relaxation. Removing delete effects makes facts accumulate monotonically: loading a package no longer removes its previous location, and using a resource may no longer make it unavailable. This relaxed problem is easier to reason about and provides information about which actions could contribute to the goal. Different approximations produce different estimates. The maximum-cost heuristic combines prerequisites conservatively and can be admissible under standard assumptions; the additive heuristic sums prerequisite estimates and can overcount shared work. The FF heuristic extracts a relaxed plan, producing useful guidance without generally being admissible.
Other methods derive lower bounds by abstraction. A pattern database stores exact solution costs for a reduced problem that retains only selected state variables. Cost partitioning can distribute action costs across abstractions so that their estimates may be added without double-counting. Landmarks identify facts or actions that every solution must achieve or execute, although computing and exploiting them requires attention to ordering and alternative ways of achieving them. These methods capture different aspects of a problem, which is why combinations and portfolios often outperform a single universal heuristic.
Search performance also depends on duplicate detection, tie-breaking, preferred operators, and memory management. An action sequence that revisits a previously reached state may add no useful information in a deterministic classical task. State hashing and closed lists suppress such repetition, while pruning techniques eliminate provably redundant alternatives. Nevertheless, heuristic plateaus and local minima can remain: many states may appear equally promising, or every route toward a solution may initially increase the estimate. Search enhancements must therefore balance stronger reasoning per state against the cost of evaluating vastly more states.
Planning graphs, satisfiability, and constraint encodings
Planning need not proceed by explicitly searching one world state at a time. Graphplan constructs a layered planning graph alternating between propositions and actions. Starting with the initial facts, each action layer contains actions whose prerequisites are supported at the preceding proposition layer. Persistence actions carry facts forward, and mutual-exclusion relations record incompatible actions or propositions. Actions may conflict because one deletes another’s precondition, because their effects disagree, or because their supporting conditions cannot coexist at the relevant layer.
The graph is a compact structure for reasoning about reachability, not a complete enumeration of reachable world states. Facts that appear together in a proposition layer are not necessarily jointly achievable, because pairwise exclusion information cannot capture every higher-order dependency. Graphplan therefore performs a backward extraction search after building enough layers to support the goals without pairwise exclusion. Failed subgoal combinations can be recorded to avoid repeating unsuccessful reasoning. This architecture separates inexpensive forward propagation from more selective backward search.
Another influential approach translates bounded planning into the Boolean satisfiability problem. For a horizon , propositional variables describe facts and action occurrences at time steps . Clauses encode the initial state, goal conditions, action preconditions, effects, and persistence. Explanatory frame constraints ensure that a fact cannot change truth value without an action accounting for the change. Depending on the encoding, additional constraints either enforce sequential actions or allow compatible actions to occur in parallel. A satisfying assignment can then be decoded into a plan.
The horizon is commonly increased until a satisfiable encoding is found, although alternative strategies and lower-bound techniques are possible. Failure at horizon proves only that no plan exists within that encoding’s bound; it does not ordinarily prove that the unbounded planning task is unsolvable. Moreover, a minimum parallel horizon differs from minimum sequential length or minimum cost. The definition of parallel compatibility matters because some encodings allow several actions in one layer only when they admit a suitable sequential execution.
Constraint-based planning extends this idea beyond propositional variables. Integer programming can express action choices and resource balances, while satisfiability modulo theories combines logical structure with theories such as linear arithmetic. Temporal and numeric tasks often benefit from these richer languages. Their attraction is the ability to use powerful general-purpose solvers with propagation, conflict learning, and optimization machinery. Their limitation is that the encoding itself may become large or obscure useful planning structure. Comparing such approaches requires accounting for preprocessing, encoding time, solver time, and the semantics of the decoded result.
Partial-order and hierarchical planning
A sequential plan commits to an ordering between every pair of actions, even when many activities are independent. Partial-order planning instead represents only the orderings needed for correctness. A plan may specify that a package must be loaded before transport and unloaded afterward, without determining whether an unrelated inspection occurs before or after loading. Any linearization satisfying the ordering constraints must preserve the intended plan semantics. This least-commitment approach can expose concurrency and postpone decisions that would otherwise multiply search alternatives.
Causal-link planning makes action dependencies explicit. A link states that action establishes condition for action . Another action threatens this link if it can negate between the producer and consumer. The threat can be resolved by ordering the threatening action before the producer or after the consumer, or sometimes by restricting variable bindings. Search proceeds by repairing flaws such as unsupported preconditions and unresolved threats. This differs from forward state-space search because the search nodes are incomplete plans rather than fully specified world states.
Hierarchical task network planning introduces another form of structure: tasks may be decomposed into smaller tasks using domain-specific methods. A high-level task such as delivering a shipment might decompose into obtaining a vehicle, collecting the shipment, transporting it, and handing it over. Primitive tasks correspond to executable actions; compound tasks are refined through methods whose conditions describe when they are applicable. A solution must both execute correctly and conform to an allowed decomposition of the initial task network.
Hierarchy can encode procedural knowledge that a purely goal-based planner would otherwise have to rediscover. It can also restrict the solution space deliberately. A company may permit only certain approval and dispatch procedures even when other action sequences would achieve the same final state. SHOP, introduced by Dana Nau and colleagues in 1999, exemplified hierarchical planning that reasons through tasks in execution order, enabling method conditions to be evaluated against a known current state. Other hierarchical systems permit partially ordered task networks and more flexible decomposition strategies.
The additional knowledge is not free. Methods must be authored, checked, and maintained, and an incomplete method library may exclude valid solutions. Unrestricted recursive hierarchical formulations can have very different decidability and complexity properties from classical planning. Hierarchy also differs from merely placing macros into a classical domain: decomposition can define which action sequences are admissible, not just accelerate their discovery. In practical systems, hierarchical structure and causal reasoning can be combined, allowing prescribed procedures to coexist with search over alternative actions, resource assignments, and execution orderings.
Time, resources, and continuous processes
Classical planning abstracts away action duration, but many applications depend on when activities occur and how long they overlap. Temporal planning models durative actions with conditions and effects associated with their starts, ends, or intervening intervals. A transport action may require a vehicle at its origin when it begins, consume fuel, and place the vehicle at its destination when it ends. A safety condition might have to remain true throughout execution. Correctness therefore requires reasoning not only about action order but also about the intervals during which conditions hold.
PDDL2.1, published by Maria Fox and Derek Long in 2003, established influential semantics for numeric and durative planning constructs. Its treatment of concurrent actions includes restrictions on simultaneous access to changing values, commonly described through the “no moving targets” principle. Such details prevent ambiguous interpretations in which an action depends on a value at exactly the same instant another action changes it. Temporal planners must respect their chosen semantics rather than treating every nonconflicting-looking overlap as automatically valid.
Temporal constraints are frequently represented using a simple temporal network. Its variables are time points, and its constraints bound differences:
These bounds can express action durations, deadlines, and precedence requirements. Consistency checking reduces to graph-based difference-constraint reasoning, connecting temporal planning with algorithms for the shortest-path problem. A consistent temporal network can represent many possible schedules rather than a single fully fixed timetable. When durations are partly controlled by the environment, stronger notions such as dynamic controllability ask whether execution decisions can adapt to observed completion times while preserving constraints.
Resources introduce additional interactions. Renewable resources, such as a machine or loading dock, become available again after use; consumable resources, such as fuel, diminish unless replenished. Capacity constraints can prohibit two activities from overlapping even when their logical preconditions do not conflict. Conversely, concurrency may be necessary: one agent may have to hold a component while another attaches it. Planning determines which activities are needed, while scheduling allocates times and resources to them, but many realistic tasks require these decisions to be solved together rather than in a strict pipeline.
Hybrid models combine discrete actions with continuous change. Battery charge, temperature, or tank level may evolve during an activity, and autonomous processes may continue without explicit agent actions. Checking only start and end values can miss an invariant violation between them. Richer models therefore need reasoning about rates, intermediate states, and events triggered by conditions. Such expressiveness creates substantial computational difficulty, so practical systems often use restricted dynamics, conservative approximations, or specialized numerical solvers coupled to symbolic planning.
Incomplete information and stochastic outcomes
Classical planning assumes that the initial state is known and actions have predictable effects. When information is incomplete, the planner may instead reason over a belief state: a set of possible world states, or a probability distribution over them. If a package may be in either of two warehouses, its location cannot be treated as one known fact. An action must be evaluated against the possibilities consistent with the agent’s information, and an observation may reduce uncertainty without directly advancing the physical delivery task.
Conformant planning seeks a plan that succeeds despite the specified uncertainty without relying on new observations during execution. A conformant solution might visit both possible pickup sites, provided the action semantics make this valid. Contingent planning allows branching on observations, such as checking a warehouse and selecting a route based on the result. The output is then a conditional plan or policy rather than one fixed sequence. Sensing must itself be modeled: what can be observed, under which conditions, with what reliability, and whether acquiring the information changes the world.
Nondeterministic planning represents actions with several possible outcomes but need not assign probabilities to them. Different solution concepts impose different guarantees. A strong solution reaches the goal for every possible outcome path. A strong-cyclic solution can permit retries and cycles, with eventual success depending on an appropriate fairness assumption. For example, repeatedly attempting an action with a success outcome may be acceptable under fairness, but not if the environment is allowed to choose failure forever. These distinctions determine what a claimed solution actually guarantees.
When outcomes have probabilities and costs or rewards matter, planning connects to the Markov decision process. For a discounted reward formulation, an optimal value function satisfies
where . The result is typically a policy mapping states to actions. Dynamic programming methods exploit this recursive structure, while heuristic search can focus computation on states relevant to a particular initial condition. Goal-directed stochastic shortest-path formulations use related ideas but require their own assumptions about termination and costs.
Partial observability leads to the partially observable Markov decision process, in which observations update a probability distribution over states. Even a finite physical state space then induces a generally continuous belief space. Exact solution can be expensive, motivating point-based approximations, sampling, and online search. Choosing a simpler model is often decisive: worst-case nondeterministic planning, probabilistic expected-cost optimization, and risk-constrained planning answer different questions. A policy with good average performance does not automatically provide a worst-case safety guarantee.
Execution architectures and practical applications
A plan is a prediction about how actions will change a modeled world; execution tests that prediction against events. An execution architecture therefore needs to dispatch actions, observe their outcomes, and check whether the assumptions supporting future steps still hold. Monitoring can detect a failed action, a missed deadline, a depleted resource, or an external change. The appropriate response may be to retry, repair a local fragment, reschedule remaining actions, or solve a new planning problem from the observed state.
Replanning is not simply running the original planner again without context. Some actions may already be underway, commitments may have been communicated to other agents, and abandoning a partial plan may incur costs. Plan repair attempts to retain useful structure while adapting to changed conditions. Execution-time flexibility also matters: a partially ordered or temporally flexible plan can absorb some disturbances without any new planning. A system that fixes every start time unnecessarily may be more brittle than one that preserves permissible timing intervals.
Robotics makes the boundary between symbolic and physical reasoning especially visible. A high-level action such as “pick up the cup” requires a reachable grasp, a collision-free arm trajectory, and suitable geometric relationships. Task and motion planning couples symbolic action selection with continuous geometric feasibility. A symbolic plan may need revision when motion planning discovers that an object blocks a path, while moving the obstacle may create new manipulation options. Perception and simultaneous localization and mapping add uncertainty about the very state on which planning depends.
Space operations supplied prominent demonstrations. NASA’s Remote Agent experiment operated aboard Deep Space 1 in 1999, combining planning and scheduling with execution and model-based diagnosis. The Earth Observing-1 mission later used the Autonomous Sciencecraft Experiment to connect onboard science analysis with planning and execution. Such systems illustrate why a planner alone is insufficient: resource constraints, communications opportunities, fault handling, and the execution layer determine whether abstract activity choices can be carried out reliably.
Other applications include manufacturing, maintenance, transport, workflow composition, and automated configuration. In multi-agent settings, plans must account for shared resources, coordination, and the effects of other participants’ actions. A cooperative fleet can optimize joint deliveries, whereas self-interested agents introduce strategic questions beyond ordinary single-agent planning. Connections to distributed computing become relevant when knowledge and decision authority are distributed. In all these applications, deployment depends on the boundary of the model: independent checks, monitoring, and fallback behavior address failures that a formally valid plan cannot rule out.
Learning, language models, and empirical evaluation
Planning traditionally assumes that action models and control knowledge are supplied explicitly. Machine learning can instead infer preconditions and effects from observed transitions, predict action durations, estimate costs, or guide search. Learning an action model differs from learning a heuristic: the former changes the planner’s account of what actions do, while the latter changes which possibilities are explored first. Errors in a learned model can invalidate plans, whereas errors in a guidance mechanism may primarily reduce efficiency or compromise optimality, depending on how the mechanism is used.
The relationship with reinforcement learning is especially close but not one of identity. A model-free learning system can acquire an action policy without explicitly constructing a plan. A model-based system learns or receives transition dynamics and uses planning to select behavior. Planning methods may supply training targets, generate synthetic experience, or solve local decision problems inside a learned controller. Conversely, learned value estimates and action preferences can guide symbolic search. Their usefulness depends on whether the training tasks capture the structural variation encountered at deployment.
Large language models provide additional interfaces for translating natural-language requests, proposing action sequences, and helping construct domain descriptions. Their generated text is not automatically an executable or valid plan. A plausible sequence may omit a precondition, reference an unavailable object, or use a resource twice. Architectures that connect language models to symbolic planners or validators separate proposal generation from explicit checking. This is one form of neuro-symbolic artificial intelligence, although successful checking still depends on having an adequate formal model of the task.
Empirical evaluation therefore measures more than whether an output appears reasonable. Common criteria include coverage—the number of instances solved within resource limits—runtime, peak memory, plan cost, and distance from known lower bounds or optimal solutions. Optimal planners and satisficing planners pursue different objectives and should not be compared as if they offered identical guarantees. Independent validation checks correctness under the benchmark semantics. Reporting must also distinguish search time from domain translation and grounding, which can dominate the total computational cost.
Generalization remains a central issue for learned planning components. Training and testing on nearly identical problem instances can conceal difficulty with larger object sets, unfamiliar goal combinations, or altered action dynamics. Distribution shift may affect both performance and correctness when learned models are involved. Classical planners face a related but distinct challenge: performance on established benchmark families does not ensure efficiency on new structures. Current research consequently examines lifted reasoning that avoids full grounding, stronger unsolvability proofs, verified planning components, learned abstractions, and interfaces that preserve formal guarantees while accepting less formal descriptions of tasks.