Automated planning

Also known as: AI planning

On this page 7

Automated planning, also called AI planning, is the branch of Artificial intelligence that computes a sequence or policy of actions that transforms a given initial state into a state that satisfies a stated goal, using an explicit model of what each action requires and what it changes. Among the AI fundamentals, it represents the deliberative side of intelligence: instead of reacting to inputs or predicting labels, a planner reasons about consequences before acting.

A planning problem is defined declaratively, so the same general domain-independent planner can solve logistics, robotics, scheduling or game problems without task-specific code. This separation of model and solver is the central idea of the field, and it distinguishes automated planning from hand-written control logic and from purely learned behavior.

How automated planning models a problem

Automated planning models a problem as a state-transition system: a set of states, a set of actions, and a transition function that says which state results when an action is applied. In the classical formulation, states are sets of logical facts (propositions such as at(truck1, depot)), and each action has preconditions that must hold before it runs and effects that add or delete facts afterward.

This representation descends from STRIPS, the Stanford Research Institute Problem Solver of 1971, and is standardized today in PDDL, the Planning Domain Definition Language introduced for the International Planning Competition in 1998. A PDDL description is split into a domain file, which defines types, predicates and action schemas, and a problem file, which lists the objects, the initial state and the goal.

The table below lists the components every classical planning task contains and the role each one plays.

ComponentWhat it specifiesExample in a delivery domain
ObjectsEntities the plan can refer toTrucks, packages, cities
PredicatesFacts that can be true or falsePackage in truck, truck at city
Action schemasParameterized operators with preconditions and effectsLoad, unload, drive
Initial stateFacts true at the startPackage at warehouse A
GoalCondition the final state must satisfyPackage at customer site B
Cost functionPrice of each action, if optimizedFuel or time per drive
Components of a classical planning task

How planners search for a solution

Planners find solutions mainly through heuristic search over the space of states or partial plans. The number of reachable states grows exponentially with the number of facts, so exhaustive enumeration fails on all but toy problems; plan existence for classical STRIPS planning is PSPACE-complete in general.

Modern forward state-space planners therefore compute domain-independent heuristics automatically from the model. A common technique is the delete relaxation, which ignores the negative effects of actions and estimates the remaining cost from the relaxed problem. Systems such as Fast Downward combine these estimates with algorithms like greedy best-first search or A-star search, which guarantees optimal plans when the heuristic is admissible.

Other families take a different route, as the following comparison shows.

ApproachCore ideaTypical strength
Forward state-space searchExpand states from the initial state using heuristicsFast on most benchmark domains
Planning as satisfiabilityEncode a plan of bounded length as a SAT formulaStrong on tightly constrained problems
Partial-order planningOrder actions only where neededFlexible plans with parallel steps
Hierarchical task networkDecompose abstract tasks into methodsEncodes expert procedures directly
Graph-based planningBuild a layered reachability graphCompact reachability analysis
Main families of planning algorithms

Variants beyond classical planning

Classical planning assumes a fully observable, deterministic, static world with instantaneous actions and a single agent. Real applications relax these assumptions, and each relaxation defines a recognized variant with its own models and solvers.

VariantRelaxed assumptionForm of solution
Temporal planningActions take time and may overlapTimed schedule of actions
Probabilistic planningEffects are uncertainPolicy mapping states to actions
Conformant planningInitial state is not fully knownPlan that works in every possible state
Contingent planningAgent senses during executionBranching plan with observations
Multi-agent planningSeveral agents act togetherCoordinated joint plan
Numeric planningResources have continuous valuesPlan respecting resource bounds
Planning variants and the assumption each relaxes

Probabilistic planning is usually formalized as a Markov decision process, which connects planning to dynamic programming and to model-based reinforcement learning. PDDL extensions such as PDDL2.1 for durative actions and PPDDL for probabilistic effects express several of these variants in a common syntax.

Automated planning differs from neighboring techniques mainly in where the knowledge comes from and when the reasoning happens. A planner receives an explicit action model and reasons at decision time, whereas learning methods acquire behavior from data or experience in advance.

TechniqueSource of knowledgeKey difference from planning
Reinforcement learningReward signals from interactionLearns a policy without an explicit model
Constraint satisfactionVariables, domains and constraintsAssigns values, usually without action sequences
SchedulingGiven tasks and resourcesOrders known activities instead of choosing them
Expert systemsIf-then rules from specialistsReacts to facts instead of chaining future actions
LLM-based agentsPatterns learned from textProposes plans without guaranteed validity
Automated planning and neighboring techniques

The last row matters in current practice. Large language models produce plausible step lists but do not verify preconditions, and empirical studies on PDDL benchmarks show frequent invalid plans. A growing neuro-symbolic pattern uses the language model to translate a request into PDDL and a classical planner to produce and validate the plan.

Where automated planning is used and where it struggles

Automated planning is used where actions have clear preconditions and costly consequences. Established applications include spacecraft operations, warehouse and logistics robotics, manufacturing process planning, military and emergency logistics, network configuration, and the generation of penetration-testing attack paths in cybersecurity.

  • Modeling effort is the main bottleneck: writing a correct domain model requires knowledge engineering, and a single missing precondition yields plans that fail in reality.
  • Scalability remains limited when domains have many objects, because grounding action schemas can create millions of concrete actions.
  • Execution monitoring is essential: a plan built on a static model must be checked and repaired when the world changes during execution.
  • Optimality is expensive: satisficing planners find some valid plan quickly, while optimal planners may need orders of magnitude more time.

Practitioners therefore start with satisficing planning, validate plans with a tool such as VAL, and invest in domain model testing before deployment.

A non-technical view

Automated planning is how a computer works out the steps needed to reach a goal before it does anything. It is given three things: where things stand now, where they should end up, and a list of moves it may make, each with its own requirements and results.

Think of packing a moving van. A good mover thinks ahead: heavy boxes first, the sofa before the lamps, the door kept clear. A planner does the same kind of thinking for machines. The key idea is reasoning about consequences in advance, rather than reacting step by step or guessing from past examples.

A concrete example

A regional distribution center operates 40 mobile robots that move shelving units to packing stations. Each morning, the operations team feeds the planner a domain model with actions such as move, lift, drop and charge, plus the current robot positions, battery levels and about 600 open orders.

The temporal planner produces a schedule of several thousand timed actions within two minutes, avoiding aisle conflicts and sending robots to chargers before batteries fall below 20 percent. During the shift, an execution monitor compares sensor data with the expected state and triggers local replanning whenever a robot is blocked.

Compared with the earlier rule-based dispatcher, the team observed fewer idle robots and no battery-related stoppages. The outcome was higher throughput without adding hardware, because the planner reasoned about the whole fleet at once.