What is AI Planning?

AI Planning (Automated Planning) is the part of artificial intelligence that decides what to do. Given a description of a world, the actions available and a goal, a planner works out a sequence of actions that reaches the goal, without being told how.

The main concepts

Term	Meaning	Example
State	The world at one moment	The van is at the depot, with 40 litres of fuel
Action	Something that changes the state, if its preconditions hold	Drive from the depot to the market
Goal	The condition to reach	Every parcel is delivered
Plan	The actions that reach the goal	Load, drive, unload
Domain	A model of a kind of world, reusable across problems	Vans, parcels and roads
Problem	One situation in a domain	These vans, these parcels, today
Metric	What makes one plan better than another	Total cost, or finishing soonest

Models are usually written in PDDL, the standard language of the field.

Domain-independent planning

The defining idea is that the planner knows nothing about vans. One general solver reads a model and solves it, whatever the model describes. You change behaviour by changing the model, not by writing a new algorithm, and a planner can explain what it did, because every step of a plan follows from stated preconditions and effects.

Kinds of planning

Classical planning assumes a fully known world, instantaneous actions with certain outcomes, and states made of true and false facts.
Numeric planning adds quantities such as fuel, money and capacity, in conditions and effects.
Temporal planning adds actions that take time and can overlap, with deadlines and schedules.
Hybrid planning adds continuous change, such as a tank that fills while a pump runs, as in PDDL+.
Probabilistic and non-deterministic planning drop the assumption that actions have certain outcomes.
Hierarchical planning breaks tasks into subtasks using methods supplied by the modeller.

Autoplan covers classical, numeric and temporal planning. See what it supports.

How planners search

Most modern planners treat planning as search through states, and the difficulty is the size of that space: deciding whether a propositional STRIPS problem has a plan at all is PSPACE-complete. What makes this practical is the heuristic, an estimate of how far a state is from the goal, computed automatically from the model. Bonet and Geffner's work on planning as heuristic search, and the FF planner of Hoffmann and Nebel, showed that a good one can come from a simplified version of the problem, typically by ignoring what actions undo.

Other approaches include landmarks, facts every plan must achieve; local search on partial plans; novelty, which favours states that show something new; encoding the problem for a SAT or SMT solver; and model checking.

A satisficing planner aims for a good plan quickly, an optimal planner for a provably best one, and an anytime planner keeps improving its plan until time runs out.

Planning and scheduling

Scheduling decides when and with what to do a known set of tasks. Planning decides which tasks to do in the first place. Temporal planning does both at once, which matters when the choice of actions depends on time and resources.

Where it is used

Planning suits problems where the steps are not known in advance, the rules are clear, and the model changes more often than you would want to rewrite a solver.

Space

In 1999, the Remote Agent experiment gave an AI system control of the Deep Space 1 spacecraft, generating and executing plans on board. On Earth Observing One, the CASPER planner generated operations plans on board from goals set by onboard science analysis, re-planning observations of events such as volcanic eruptions and floods. On the ground, NASA's MAPGEN supported human planners in building daily plans for the Mars Exploration Rovers.

Manufacturing

Ruml and colleagues at PARC used on-line planning to control modular printers, sheet by sheet. They describe it as, to their knowledge, the first successful industrial application of embedded domain-independent temporal planning, driving several commercial prototypes.

Cyber security

Penetration testing can be modelled as planning: what an attacker could do next, and in which order. According to Hoffmann, classical planning variants of this idea have been used commercially since 2010, in Core Security's Core IMPACT tool, using a variant of Metric-FF.

Transport and traffic

Vallati and colleagues used PDDL+ to control the green phases of traffic lights so as to reduce congestion, in simulation on networks including Manchester city centre. The Airport domain of IPC 2004 models airport ground traffic, and its largest instances correspond to Munich airport.

Robotics

ROSPlan embeds task planning in the Robot Operating System, and was evaluated with autonomous underwater vehicles.

Energy

Piacentini and colleagues extended the POPF planner to control voltage in electricity networks, in research work that combines a temporal planner with a power-flow solver.

Games

The enemies in the game F.E.A.R. plan their actions with a system its developer, Jeff Orkin, says most closely resembles STRIPS.

Try the ideas yourself: the PDDL walkthrough takes you from an empty workspace to a validated plan.