AI planning

AI planning, or automated planning, is the branch of symbolic AI that computes a sequence of actions, each described by explicit preconditions and effects, that transforms a given initial state into a state satisfying a goal. Because every action’s requirements and consequences are written down, a planner’s output can be checked step by step before anything is executed.

1. What an AI planning problem is

The simplest and best-studied setting is classical planning: one agent, a single known initial state, deterministic actions that take no time, and a goal that is a set of facts. States are sets of ground atoms such as On(C, A); an action is applicable when its preconditions hold, and applying it changes some atoms. Classical planning is a special case of state-space search in which the states and actions are not a black box but a logical description a planner can read. That difference is the whole point: because the planner can see why an action is useful (it adds a fact the goal needs) and what it breaks (the facts it deletes), it can compute heuristics, reason backwards from goals, and decompose problems, none of which a blind search can do. Extensions relax each assumption: temporal planning (durations, concurrency), numeric planning, planning under uncertainty and partial observability. This page covers the symbolic core; Russell and Norvig give a full textbook treatment [1], and Ghallab, Nau and Traverso a specialist one [2].

2. Planning as logic: the situation calculus and the frame problem

Situation calculus

Who and when. John McCarthy introduced the situation calculus in 1963, and McCarthy and Patrick Hayes developed it in 1969 in “Some Philosophical Problems from the Standpoint of Artificial Intelligence” [3]. In 1969 Cordell Green at SRI showed that a resolution theorem prover could construct plans: prove that a goal situation exists, and read the plan off the proof [4]. Ray Reiter’s 1991 solution to the frame problem produced the version used today [5].

How it works. A situation is a history of actions. $S_0$ is the initial situation and $\mathrm{do}(a,s)$ is the situation after doing action $a$ in $s$. Properties that change, fluents, take the situation as an extra argument: $\mathrm{On}(b,y,s)$. A precondition axiom says when an action is possible, and a successor-state axiom (Reiter) says exactly when a fluent is true after an action. For a blocks world with a single action $\mathrm{move}(b,y)$, “put block $b$ on $y$”, where the table is always clear:

In words: $b$ is on $y$ after action $a$ if $a$ put it there, or it was already there and $a$ did not move it somewhere else. Planning is then deduction: find a term $\sigma =\mathrm{do}(a_n,\dots \mathrm{do}(a_1,S_0\left)\right)$ such that every action is possible where it is done and the goal holds in $\sigma$. Used today mainly in knowledge representation research and in GOLOG, a logic programming language built on it. Limits: general first-order theorem proving is far too slow to be a practical planner, which is why STRIPS narrowed the language.

The frame problem, as it hits planning

McCarthy and Hayes named the frame problem in the same 1969 paper [3]. Effect axioms say what an action changes. Logic does not assume that everything else stays the same, so without further axioms a prover cannot conclude that moving block B leaves block C where it was. Writing a separate frame axiom for every pair of action and unaffected fluent works, but the number grows with the product of actions and fluents, and every new action requires revisiting them all. Reiter’s successor-state axioms (above) compress this into one axiom per fluent, under the assumption that the listed effects are the only ways a fluent can change. STRIPS took the procedural route: anything an action does not explicitly delete persists. That STRIPS assumption is why planners work in practice, and it is also a commitment: an effect missing from the action model is not a warning, it is silently assumed not to happen. The broader, philosophical frame problem, and the non-monotonic logics it produced, are covered on the non-monotonic reasoning page.

3. STRIPS and a worked blocks-world example

STRIPS

Who and when. Richard Fikes and Nils Nilsson at SRI International, 1971, as the planner for the Shakey mobile robot [6]. The name stands for Stanford Research Institute Problem Solver. Its planning algorithm, a means–ends search in the style of GPS, has long been superseded; its representation is the base of almost every planning language in use today, including PDDL.

A plan $a_1,\dots ,a_n$ is valid if each action is applicable in turn and $G\subseteq \gamma (\dots \gamma (I,a_1)\dots ,a_n)$. Checking a given plan takes time linear in its length. Finding one is hard: Tom Bylander proved in 1994 that deciding whether a propositional STRIPS problem has any plan is PSPACE-complete [7].

Worked example: the blocks world. Three blocks on a table. Actions are written as schemas with variables, instantiated by substituting block names:

(A third schema, moving a block from one block to another, is not needed here.) The initial state has C on A, and A and B on the table; the goal is a tower with A on B on C:

After step 3, $G\subseteq s_3$: the plan is valid, and every step of the check is visible. Note what the delete lists do: step 2 deletes Clear(C), so no later action may put anything else on C unless something re-adds it. Note also what they do not do: nothing says that step 2 leaves On(C, …) or the colour of A unchanged. The STRIPS assumption covers it.

Used today as the core of PDDL and therefore of nearly every classical planner. Limits: no durations, no numbers, no uncertainty, no conditional effects in the original form; extensions such as ADL and later PDDL versions add them.

4. Partial-order planning and the Sussman anomaly

The Sussman anomaly

The example above is the Sussman anomaly, identified by Gerald Sussman in his doctoral work in the early 1970s [8]. Early planners were linear: they split a conjunctive goal into subgoals and solved them one after another. Here that fails in both orders. Achieve On(A,B) first (move C off A, put A on B) and you must take A down again to put B on C. Achieve On(B,C) first (put B on C) and the stack C-and-B now sits on A, so A cannot be moved without undoing it. The only short plan interleaves the subgoals: a step toward the first, the whole second, then the rest of the first.

Partial-order planning

Who and when. Earl Sacerdoti’s NOAH (1975) was the first planner to represent plans as partially ordered networks of actions [9]; Austin Tate’s NONLIN (1976–77) combined partial ordering with hierarchical decomposition [10]. David Chapman’s TWEAK (1987) gave the approach a formal footing [11], and SNLP (McAllester and Rosenblitt, 1991) and UCPOP (Penberthy and Weld, 1992) became the standard textbook algorithms [12].

How it works. Instead of searching through world states, a partial-order planner searches through plans. A plan is a set of steps, a set of ordering constraints $a_i\prec a_j$, a set of causal links $a_p\stackrel{q}{\to }{a}_c$ (“step $a_p$ achieves $q$ for step $a_c$”) and a list of open preconditions. The planner repeatedly picks an open precondition and supports it, with an existing step or a new one. A step $a_t$ that deletes $q$ and could fall between $a_p$ and $a_c$ is a threat, resolved by ordering it before the producer (demotion) or after the consumer (promotion):

On the Sussman anomaly: to support the goal On(A,B) add step MoveFromTable(A,B); for On(B,C) add MoveFromTable(B,C). The first deletes Clear(B), which the second needs, so order MoveFromTable(B,C) first. Clear(A) is still open, so add MoveToTable(C,A); it needs Clear(C), which MoveFromTable(B,C) deletes, so order MoveToTable(C,A) before it. The ordering is now total and is exactly the interleaved plan of Figure 1, found without ever trying a wrong order: this is least commitment. Legacy and limits: partial-order planning dominated research in the early 1990s and remains the clearest account of why a plan works (causal links are an explanation). It lost on speed once Graphplan and heuristic state-space planners appeared, because good heuristics are hard to compute over partial plans. Its ideas survive in temporal and hierarchical planners.

5. HTN planning

Hierarchical task network (HTN) planning

Who and when. Sacerdoti’s ABSTRIPS (1974) planned first in an abstraction hierarchy that ignored less critical preconditions [13], and NOAH and NONLIN decomposed tasks hierarchically. Kutluhan Erol, James Hendler and Dana Nau gave HTN planning a formal semantics and complexity analysis in 1994, showing it is strictly more expressive than STRIPS and undecidable in general [14]. SHOP2 (Nau and colleagues, 2003) is the best-known modern HTN planner [15].

How it works. The goal is not a set of facts but a task to perform. Primitive tasks are ordinary actions. Compound tasks are refined by methods: each method says how to carry out the task, under which preconditions, as a network of subtasks. Planning means decomposing the top task until only primitive, executable actions remain, while checking preconditions as you go. A travel domain:

The methods encode expert know-how about how things are done, which prunes the search enormously: the planner never considers flying across town. Used today wherever standard operating procedures exist: SHOP2 has been used to compose web services [16], and HTN planners are used in military and emergency operations planning, manufacturing, and to control characters in video games. Limits: the planner can only find plans the methods allow. If the methods are incomplete, a feasible plan can be missed; the domain author, not the planner, carries much of the intelligence.

6. Graphplan and SATPlan

Graphplan

Who and when. Avrim Blum and Merrick Furst, IJCAI 1995; journal version 1997 [17]. It was much faster than the partial-order planners of its day on the standard benchmarks and changed the direction of the field.

How it works. Graphplan builds a planning graph of alternating layers: fact layer 0 is the initial state; action layer $i$ contains every action whose preconditions appear in fact layer $i$ (plus “no-op” actions that carry each fact forward); fact layer $i+1$ contains all their effects. It also records mutual exclusions: two actions are mutex if one deletes a precondition or effect of the other, or their preconditions are mutex; two facts are mutex if every way of achieving them together uses mutex actions. The graph grows in polynomial time. When all goal facts appear in a layer with no pair mutex, Graphplan searches backwards from them for a mutex-free set of actions at each layer; if it fails, it extends the graph and tries again. The first plan found is optimal in the number of parallel time steps. Legacy: the planning graph turned out to be even more valuable as a source of heuristics: the layer at which a goal first appears is an admissible estimate of how many steps it needs, and FF’s heuristic is computed from a relaxed planning graph.

SATPlan (planning as satisfiability)

Who and when. Henry Kautz and Bart Selman proposed planning as satisfiability in 1992 and showed its practical strength in 1996 with “Pushing the Envelope” [18].

How it works. Fix a horizon $T$. Create a Boolean variable $f_t$ for each fact at each time $0\le t\le T$ and $a_t$ for each action at each step. Encode the problem as clauses, then hand them to a SAT solver:

The formula is satisfiable exactly when a plan of at most $T$ steps exists, and a satisfying assignment is the plan (read off the true action variables). Try $T=0,1,2,\dots$ until it succeeds. The explanatory frame axioms are the frame problem solved in propositional logic: a fact may change only if some action that changes it occurred. Why it matters: SATPlan let planning benefit directly from every advance in SAT solving, and the same encoding idea underlies bounded model checking in hardware verification. Limits: the formula grows with the horizon, so long plans are expensive, and optimising action costs does not fit plain SAT.

7. PDDL and the International Planning Competition

PDDL (Planning Domain Definition Language)

Who and when. Drew McDermott and colleagues released PDDL in 1998, mainly to make the first International Planning Competition possible [19]. PDDL2.1 (Fox and Long, 2003) added numeric fluents and durative actions for temporal planning [20]; PDDL2.2, PDDL3.0 and PDDL3.1 followed for later competitions.

How it works. A PDDL domain file declares predicates and action schemas; a problem file lists objects, the initial state and the goal. Any planner that reads PDDL can then solve any domain written in it. The MoveFromTable schema above, in PDDL:

(:action move-from-table
  :parameters (?b ?y)
  :precondition (and (on-table ?b) (clear ?b) (clear ?y))
  :effect (and (on ?b ?y)
               (not (on-table ?b)) (not (clear ?y))))

The add list becomes positive effects and the delete list becomes negated effects: STRIPS, in Lisp-like syntax. Used today as the standard input language of research and many industrial planners, and increasingly as the target when language models are asked to formalise a planning problem so that a classical planner can solve it and a validator can check it. Limits: writing a correct domain model is itself hard, and PDDL cannot express everything a real application needs without extensions.

The International Planning Competition (IPC)

The IPC began in 1998, alongside PDDL, and has been held regularly since, now usually alongside the ICAPS conference. PDDL1.2 was the official language of the 1998 and 2000 competitions, PDDL2.1 of 2002, PDDL2.2 of 2004 and PDDL3.0 of 2006 [19]. Shared benchmark domains (logistics, rovers, satellites, blocks) and head-to-head comparison drove much of the progress described next.

8. Heuristic search planners: HSP, FF, Fast Downward

Heuristic search planning

Who and when. Blai Bonet and Héctor Geffner’s HSP showed that plain forward state-space search with an automatically derived heuristic was competitive [21]. Jörg Hoffmann and Bernhard Nebel’s FF (2001) refined the idea [22], and Malte Helmert’s Fast Downward (2006) became a common platform on which many modern classical planners are built [23].

How it works. The key trick is the delete relaxation: pretend that actions have no delete lists. The relaxed problem is easy (facts only accumulate), and its solution cost estimates the real one. For a state $s$, define the cost of reaching an atom $p$ recursively:

$h_{\max }$ never overestimates, so it is admissible and A* with it returns optimal plans; replacing both maxima with sums gives $h_{\mathrm{add}}$, which is more informative but can overestimate. FF’s heuristic counts the actions in a relaxed plan extracted from a planning graph. In the blocks example, from $s_0$ with unit costs, $h_{\max }=2$ (On(A,B) needs Clear(A) first) while the true cost is 3: an underestimate, as promised. The heuristic is computed from the action schemas alone; no one writes it by hand.

Fast Downward and LAMA

Fast Downward translates PDDL into a multi-valued state representation and provides a library of search algorithms and heuristics; it is open source under the GPL. LAMA (Richter and Westphal, 2010), built on Fast Downward, combines the FF heuristic with landmarks, facts that every plan must make true at some point [24]. Planners of this family, plus abstraction heuristics (pattern databases) and later learned heuristics, are the state of the art for classical planning. Limits: in the worst case all of them still face PSPACE-completeness; relaxation heuristics can be badly misleading in domains where deletes are the whole difficulty, such as puzzles with scarce resources.

9. Where AI planning is used

• Space. NASA’s Remote Agent flew on Deep Space 1 in 1999, with an onboard planner-scheduler that generated command sequences from goals [25]. The Hubble Space Telescope’s long-term observation scheduling uses the Spike system.
• Logistics, manufacturing and operations. Scheduling production lines, sequencing maintenance, and planning military and emergency operations, often with HTN or temporal planners.
• Software. Web-service and workflow composition (SHOP2, above).
• Robotics. Task-level planning in PDDL on top of motion planning, the lineage of Shakey and STRIPS.
• Games. Goal-oriented and hierarchical planners choose the actions of non-player characters in commercial video games.
• Language-model systems. A model can propose a plan or translate a request into PDDL; a symbolic planner or plan validator then finds or checks the plan exactly. This is covered on the neuro-symbolic AI page.

10. Timeline

11. Limits

• Computational hardness. Plan existence for propositional STRIPS is PSPACE-complete, and general HTN planning is undecidable. Planners succeed because real domains have structure, not because the problem is easy.
• The model is the bottleneck. A planner is exactly as right as its action descriptions. Writing complete, correct preconditions and effects is the knowledge-acquisition problem of expert systems in another form, and the STRIPS assumption means an omitted side effect is not flagged, it is assumed absent.
• The world is not classical. Actions fail, take time, have uncertain outcomes and happen alongside other agents. Execution monitoring and replanning, or probabilistic planning, are needed outside the classical setting.
• The frame, qualification and ramification problems. What does not change, what could stop an action working, and which indirect effects follow are never fully captured by a finite model.

12. AI planning and fail-safe models

A fail-safe model is an AI model built so that failure drives it toward a controlled, safe state rather than a confident error. Planning contributes a precise version of that idea: a plan written against a STRIPS or PDDL model can be validated mechanically. Each precondition is checked against the state it must hold in, as in the table in §3, and a plan that fails a check is rejected with the step and the missing fact named. Whoever proposed the plan, a search procedure, a human or a language model, the check is the same. That is the division of authority we care about: a model may propose; only the floor admits a fact, and here, only the validator admits a plan.

The honest limit is the one from §11: validation is relative to the model. A plan can pass every check and still fail in a world the model does not describe, so a fail-safe design has to treat “not provable from the model” as a reason to stop, not to guess. Peel, by Perslis Research, applies this discipline to knowledge: there is no neural network in the loop that decides, knowledge is typed, sourced cards, and learning is readable counts. To our knowledge it is the first fail-safe model; the exact claim and the closest earlier work are on What is a fail-safe model? Peel is a research prototype. See also What is symbolic AI?, the history of symbolic AI and the guide to all symbolic AI techniques.

13. Questions

What is AI planning?

AI planning, or automated planning, is the part of artificial intelligence that computes a sequence of actions to reach a goal. Each action is described by explicit preconditions and effects, so a planner can reason about which actions help, which ones interfere, and whether a proposed plan is valid before it is executed.

What is STRIPS planning?

STRIPS is a planner and action representation created by Richard Fikes and Nils Nilsson at SRI in 1971 for the Shakey robot. Each action has a list of preconditions, an add list of facts it makes true and a delete list of facts it makes false. Almost every modern planning language, including PDDL, is built on this representation.

What is the difference between STRIPS and PDDL?

STRIPS is the underlying model of actions with preconditions, add lists and delete lists. PDDL, the Planning Domain Definition Language introduced in 1998, is a standard file format that expresses STRIPS-style domains and problems and extends them with types, conditional effects, numbers, durations and preferences. PDDL made planners interchangeable and enabled the International Planning Competition.

What is HTN planning?

Hierarchical task network planning starts from tasks to perform rather than facts to achieve. Methods describe how each compound task can be broken into subtasks, and the planner decomposes tasks until only executable actions remain. HTN planners such as SHOP2 are fast in practice because the methods encode expert knowledge about how things are done.

What is partial-order planning?

A partial-order planner builds a plan whose steps are only partly ordered, adding an ordering constraint only when one step would otherwise undo a condition another step needs. This least-commitment approach solves problems such as the Sussman anomaly, where achieving one goal completely before starting the next leads to wasted or undone work.

What is the Sussman anomaly?

The Sussman anomaly is a three-block planning problem identified by Gerald Sussman: block C is on A, B is on the table, and the goal is A on B on C. A planner that solves the two goals one after the other must undo one of them, whichever order it picks, so the shortest plan requires interleaving the goals.

How is AI planning different from search?

Planning is a kind of search, but the states and actions are described in logic rather than hidden inside a black-box successor function. Because a planner can read the preconditions and effects, it can derive heuristics automatically, reason backwards from goals, and decompose problems, which blind or hand-tuned search cannot do.

Is automated planning still used today?

Yes. Descendants of STRIPS written in PDDL, HTN planners and heuristic planners built on Fast Downward are used in space missions, logistics, manufacturing, robotics, video games and software automation. Planners are also paired with language models, which propose or formalise a plan while the symbolic planner finds or checks it exactly.

14. References

1. S. Russell, P. Norvig. Artificial Intelligence: A Modern Approach, 4th ed. Pearson, 2020.
2. M. Ghallab, D. Nau, P. Traverso. Automated Planning: Theory and Practice. Morgan Kaufmann, 2004.
3. J. McCarthy, P. J. Hayes. Some Philosophical Problems from the Standpoint of Artificial Intelligence. Machine Intelligence 4, Edinburgh University Press, 1969.
4. C. Green. Application of Theorem Proving to Problem Solving. Proceedings of IJCAI-69, 1969; also SRI technical report, 1969.
5. R. Reiter. The Frame Problem in the Situation Calculus: A Simple Solution (Sometimes) and a Completeness Result for Goal Regression. In V. Lifschitz (ed.), Artificial Intelligence and Mathematical Theory of Computation. Academic Press, 1991.
6. R. E. Fikes, N. J. Nilsson. STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving. Artificial Intelligence 2(3–4):189–208, 1971. doi:10.1016/0004-3702(71)90010-5
7. T. Bylander. The Computational Complexity of Propositional STRIPS Planning. Artificial Intelligence 69(1–2):165–204, 1994. doi:10.1016/0004-3702(94)90081-7
8. G. J. Sussman. A Computer Model of Skill Acquisition. American Elsevier, 1975.
9. E. D. Sacerdoti. The Nonlinear Nature of Plans. Proceedings of IJCAI-75, 1975; and A Structure for Plans and Behavior, Elsevier, 1977.
10. A. Tate. Generating Project Networks. Proceedings of IJCAI-77, pp. 888–893, 1977.
11. D. Chapman. Planning for Conjunctive Goals. Artificial Intelligence 32(3):333–377, 1987. doi:10.1016/0004-3702(87)90092-0
12. D. McAllester, D. Rosenblitt. Systematic Nonlinear Planning. Proceedings of AAAI-91, 1991; J. S. Penberthy, D. S. Weld. UCPOP: A Sound, Complete, Partial Order Planner for ADL. Proceedings of KR-92, 1992.
13. E. D. Sacerdoti. Planning in a Hierarchy of Abstraction Spaces. Artificial Intelligence 5(2):115–135, 1974. doi:10.1016/0004-3702(74)90026-5
14. K. Erol, J. Hendler, D. S. Nau. HTN Planning: Complexity and Expressivity. Proceedings of AAAI-94, 1994.
15. D. S. Nau, T.-C. Au, O. Ilghami, U. Kuter, J. W. Murdock, D. Wu, F. Yaman. SHOP2: An HTN Planning System. Journal of Artificial Intelligence Research 20:379–404, 2003. doi:10.1613/jair.1141
16. E. Sirin, B. Parsia, D. Wu, J. Hendler, D. Nau. HTN Planning for Web Service Composition Using SHOP2. Journal of Web Semantics 1(4), 2004. doi:10.1016/j.websem.2004.06.005
17. A. L. Blum, M. L. Furst. Fast Planning Through Planning Graph Analysis. Artificial Intelligence 90(1–2):281–300, 1997 (conference version IJCAI-95). doi:10.1016/S0004-3702(96)00047-1
18. H. Kautz, B. Selman. Planning as Satisfiability. Proceedings of ECAI-92, pp. 359–363, 1992; Pushing the Envelope: Planning, Propositional Logic, and Stochastic Search. Proceedings of AAAI-96, pp. 1194–1201, 1996.
19. D. McDermott et al. PDDL: The Planning Domain Definition Language. Technical Report CVC TR-98-003 / DCS TR-1165, Yale Center for Computational Vision and Control, 1998.
20. M. Fox, D. Long. PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains. Journal of Artificial Intelligence Research 20:61–124, 2003. doi:10.1613/jair.1129
21. B. Bonet, H. Geffner. Planning as Heuristic Search. Artificial Intelligence 129(1–2):5–33, 2001. doi:10.1016/S0004-3702(01)00108-4
22. J. Hoffmann, B. Nebel. The FF Planning System: Fast Plan Generation Through Heuristic Search. Journal of Artificial Intelligence Research 14:253–302, 2001. doi:10.1613/jair.855
23. M. Helmert. The Fast Downward Planning System. Journal of Artificial Intelligence Research 26:191–246, 2006. doi:10.1613/jair.1705
24. S. Richter, M. Westphal. The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks. Journal of Artificial Intelligence Research 39:127–177, 2010. doi:10.1613/jair.2972
25. N. Muscettola, P. P. Nayak, B. Pell, B. C. Williams. Remote Agent: To Boldly Go Where No AI System Has Gone Before. Artificial Intelligence 103(1–2):5–47, 1998. doi:10.1016/S0004-3702(98)00068-X