Simple Algorithm
Artificial Intelligence · Hidden Layer · 22 min

Automated Planning

STRIPS, PDDL and searching over actions.

Give a planner a description of what actions do, a start and a goal, and it must invent the sequence itself. Deciding whether any plan exists is PSPACE-complete, yet modern planners routinely solve tasks with astronomically large state spaces. Their trick is to estimate distances by solving an easier problem: one in which nothing is ever deleted.

What you’ll learn

  • Define a STRIPS planning task and its state space, and compute successor states and regressed subgoals.
  • Derive the delete-relaxation heuristics hmax⁡h_{\max} and haddh_{\mathrm{add}}, and prove hmax⁡≤h+≤haddh_{\max}\le h^+\le h_{\mathrm{add}}.
  • Explain planning graphs, and encode bounded planning as propositional satisfiability.
  • Read a PDDL domain and problem, and relate them to the ground STRIPS task that a planner actually searches.

Planning tasks, precisely

The Input Layer described actions by preconditions and effects. To reason about automated planning we need the formal version. In STRIPS, a state is a set of facts read under the closed-world assumption: a fact not in the set is false.

Domains are written with action schemas, which planners ground by substituting objects for parameters. In the blocks world, Move(b,x,y)\mathit{Move}(b,x,y) has precondition {On(b,x),Clear(b),Clear(y)}\{\mathit{On}(b,x),\mathit{Clear}(b),\mathit{Clear}(y)\}, adds {On(b,y),Clear(x)}\{\mathit{On}(b,y),\mathit{Clear}(x)\} and deletes {On(b,x),Clear(y)}\{\mathit{On}(b,x),\mathit{Clear}(y)\}. A schema with kk parameters over nn objects has up to nkn^k ground instances, so ∣A∣|A| is polynomial for fixed arity, while the state space can have up to 2∣F∣2^{|F|} states.

Predict before you look

Three labeled blocks can be arranged on a table in stacks of any height and order. How many distinct states does this blocks world have?

Show the answer

13 states

One tower of three: 3!=63!=6 orders. A tower of two plus a single block: 3 choices for the single block times 2 orders, so 6. Three single blocks: 1. Total: 13. The count grows faster than exponentially: 73 states for 4 blocks, 501 for 5, and 58,941,091 for 10. Planning is search in spaces like these, which no planner enumerates.

Searching forward and backward

Progression searches forward from II: the successors of ss are the states s⟦a⟧s\llbracket a\rrbracket for the applicable actions aa, and any graph search, from breadth-first search to A*, applies. Regression searches backward from GG over subgoals, sets of facts that stand for all the states containing them. An action aa is relevant to a subgoal gg if it achieves part of it, add(a)∩g≠∅\mathrm{add}(a)\cap g\neq\varnothing, and consistent with it if it destroys none of it, del(a)∩g=∅\mathrm{del}(a)\cap g=\varnothing. The subgoal that must hold before aa is then:

regr(g,a)=(g∖add(a))∪pre(a)\mathrm{regr}(g,a)=\big(g\setminus\mathrm{add}(a)\big)\cup\mathrm{pre}(a)
Regression branches only on relevant actions, often far fewer than the applicable ones, but each subgoal stands for many states at once, which complicates duplicate detection and heuristics.
DerivationRegressing a blocks-world goal
  1. g={On(A,B), On(B,C)}pre(a)={On(A,T),Clear(A),Clear(B)},add(a)={On(A,B)},del(a)={On(A,T),Clear(B)}\begin{aligned}&g=\{\mathit{On}(A,B),\ \mathit{On}(B,C)\}\\&\mathrm{pre}(a)=\{\mathit{On}(A,T),\mathit{Clear}(A),\mathit{Clear}(B)\},\quad\mathrm{add}(a)=\{\mathit{On}(A,B)\},\quad\mathrm{del}(a)=\{\mathit{On}(A,T),\mathit{Clear}(B)\}\end{aligned}

    Goal: AA on BB on CC. Let aa move AA from the table TT onto BB:

  2. regr(g,a)={On(B,C)}∪{On(A,T), Clear(A), Clear(B)}\mathrm{regr}(g,a)=\{\mathit{On}(B,C)\}\cup\{\mathit{On}(A,T),\ \mathit{Clear}(A),\ \mathit{Clear}(B)\}

    aa is relevant (it adds On(A,B)\mathit{On}(A,B)) and consistent (it deletes nothing in gg), so:

  3. regr(g,b)={On(A,B), On(B,T), Clear(B), Clear(C)}\mathrm{regr}(g,b)=\{\mathit{On}(A,B),\ \mathit{On}(B,T),\ \mathit{Clear}(B),\ \mathit{Clear}(C)\}

    Regress gg instead through bb, which moves BB from the table onto CC. It is relevant, and consistent because gg does not mention Clear(C)\mathit{Clear}(C), yet the result is a subgoal that no reachable state satisfies: if AA is on BB, then BB is not clear.

  4. On(A,B)∧Clear(B)  holds in no reachable state\mathit{On}(A,B)\wedge\mathit{Clear}(B)\ \text{ holds in no reachable state}

    Regression planners prune such subgoals with state invariants (mutexes), sets of facts that never hold together. Discovering invariants automatically is a standard preprocessing step of modern planners.

Check your understanding

Pick(Box,R2)\mathit{Pick}(\mathit{Box},R_2) has precondition {RobotAt(R2),At(Box,R2),HandEmpty}\{\mathit{RobotAt}(R_2),\mathit{At}(\mathit{Box},R_2),\mathit{HandEmpty}\}, adds {Holding(Box)}\{\mathit{Holding}(\mathit{Box})\} and deletes {At(Box,R2),HandEmpty}\{\mathit{At}(\mathit{Box},R_2),\mathit{HandEmpty}\}. What is regr(g,Pick(Box,R2))\mathrm{regr}(g,\mathit{Pick}(\mathit{Box},R_2)) for g={Holding(Box),RobotAt(R2)}g=\{\mathit{Holding}(\mathit{Box}),\mathit{RobotAt}(R_2)\}?

  1. {Holding(Box),RobotAt(R2),At(Box,R2),HandEmpty}\{\mathit{Holding}(\mathit{Box}),\mathit{RobotAt}(R_2),\mathit{At}(\mathit{Box},R_2),\mathit{HandEmpty}\}
  2. {RobotAt(R2),At(Box,R2),HandEmpty}\{\mathit{RobotAt}(R_2),\mathit{At}(\mathit{Box},R_2),\mathit{HandEmpty}\}
  3. {At(Box,R2),HandEmpty}\{\mathit{At}(\mathit{Box},R_2),\mathit{HandEmpty}\}
  4. Undefined: the action is inconsistent with gg, because it deletes HandEmpty\mathit{HandEmpty}
Show the answer

B. {RobotAt(R2),At(Box,R2),HandEmpty}\{\mathit{RobotAt}(R_2),\mathit{At}(\mathit{Box},R_2),\mathit{HandEmpty}\}

Remove what the action achieves, Holding(Box)\mathit{Holding}(\mathit{Box}), and add its precondition: {RobotAt(R2)}∪{RobotAt(R2),At(Box,R2),HandEmpty}\{\mathit{RobotAt}(R_2)\}\cup\{\mathit{RobotAt}(R_2),\mathit{At}(\mathit{Box},R_2),\mathit{HandEmpty}\}. The action is consistent with gg because it deletes nothing in gg.

Heuristics from the delete relaxation

Delete lists are what make planning hard: achieving one goal can destroy another. The delete relaxation Π+\Pi^+ drops them. Facts then only accumulate, so a relaxed plan never has to re-achieve anything, and every real plan is also a relaxed plan. The cost h+(s)h^+(s) of an optimal relaxed plan from ss is therefore an admissible heuristic, h+≤h∗h^+\le h^*. Deciding whether a relaxed plan exists takes polynomial time, but computing h+h^+ is NP-hard (Bylander, 1994). Bonet & Geffner (2001) approximate it by pretending that subgoals are independent:

h(p;s)={0p∈smin⁡a: p∈add(a)[c(a)+h(pre(a);s)]otherwisehadd(P;s)=∑p∈Ph(p;s),hmax⁡(P;s)=max⁡p∈Ph(p;s)h(p;s)=\begin{cases}0&p\in s\\ \min\limits_{a:\,p\in\mathrm{add}(a)}\big[c(a)+h(\mathrm{pre}(a);s)\big]&\text{otherwise}\end{cases}\qquad h_{\mathrm{add}}(P;s)=\sum_{p\in P}h(p;s),\quad h_{\max}(P;s)=\max_{p\in P}h(p;s)
A Bellman–Ford-style fixpoint over facts computes either version in polynomial time, and the heuristic value of a state is h(G;s)h(G;s). hmax⁡h_{\max} charges a set of facts for its most expensive member, haddh_{\mathrm{add}} for all of them.
DerivationBoth heuristics on a delivery task
  1. h(RobotAt(A))=h(PkgAt(B))=0h(\mathit{RobotAt}(A))=h(\mathit{PkgAt}(B))=0

    A robot at AA, a package at BB, a corridor AA–BB–CC, and the goal of having the package at CC. The actions Go\mathit{Go}, Pick\mathit{Pick} and Drop\mathit{Drop} cost 1 each. Facts that are true now cost 0:

  2. h(RobotAt(B))=1+0=1,h(RobotAt(C))=1+1=2h(\mathit{RobotAt}(B))=1+0=1,\qquad h(\mathit{RobotAt}(C))=1+1=2

    Moving: Go(A,B)\mathit{Go}(A,B) needs RobotAt(A)\mathit{RobotAt}(A), and Go(B,C)\mathit{Go}(B,C) needs RobotAt(B)\mathit{RobotAt}(B):

  3. hadd(Holding)=1+(1+0)=2,hmax⁡(Holding)=1+max⁡(1,0)=2h_{\mathrm{add}}(\mathit{Holding})=1+(1+0)=2,\qquad h_{\max}(\mathit{Holding})=1+\max(1,0)=2

    Picking up at BB needs RobotAt(B)\mathit{RobotAt}(B) and PkgAt(B)\mathit{PkgAt}(B); the two versions agree here:

  4. hadd(PkgAt(C))=1+(2+2)=5,hmax⁡(PkgAt(C))=1+max⁡(2,2)=3h_{\mathrm{add}}(\mathit{PkgAt}(C))=1+(2+2)=5,\qquad h_{\max}(\mathit{PkgAt}(C))=1+\max(2,2)=3

    Dropping at CC needs RobotAt(C)\mathit{RobotAt}(C) and Holding\mathit{Holding}:

  5. hmax⁡=3 ≤ h+=4 ≤ hadd=5h_{\max}=3\ \le\ h^+=4\ \le\ h_{\mathrm{add}}=5

    The optimal plan Go(A,B),Pick,Go(B,C),Drop\mathit{Go}(A,B),\mathit{Pick},\mathit{Go}(B,C),\mathit{Drop} costs 4=h+=h∗4=h^+=h^*. hmax⁡h_{\max} underestimates; haddh_{\mathrm{add}} overestimates, because it pays for the move A→BA\to B twice, once inside Holding\mathit{Holding} and once inside RobotAt(C)\mathit{RobotAt}(C):

FF (Hoffmann & Nebel, 2001) extracts an explicit relaxed plan backward from the goals and counts each action once, so the shared move above is paid for only once; the plan's cost is the heuristic hFFh_{\mathrm{FF}}. FF also treats the relaxed plan's first actions as helpful actions to try first. Combined with a greedy local search (enforced hill-climbing), this made FF the most successful fully automatic planner at the AIPS-2000 competition. Like haddh_{\mathrm{add}}, hFFh_{\mathrm{FF}} is not admissible: planners that use it trade optimality for speed.

Planning graphs and planning as satisfiability

Graphplan (Blum & Furst, 1997) builds a planning graph: alternating layers of facts P0=I,P1,P2,…P_0=I,P_1,P_2,\dots and actions A0,A1,…A_0,A_1,\dots, where AiA_i holds the actions whose preconditions appear in PiP_i, and Pi+1P_{i+1} adds their effects (no-op actions carry facts forward). It also records mutexes. Two actions are mutex if one deletes a precondition or an add effect of the other, or if their preconditions are mutex; two facts are mutex if every pair of their achievers is.

Facts and actions only accumulate from layer to layer and mutexes only disappear, so the graph levels off after polynomially many layers, each of polynomial size. If the goals are not all present and pairwise non-mutex at layer kk, no plan with kk parallel steps exists, which makes the first layer where they are an admissible estimate. Graphplan searches backward for a plan from that layer, and extends the graph when the search fails.

SATPlan (Kautz & Selman, 1992, 1996) turns "is there a plan with TT steps?" into a propositional satisfiability problem, with a variable ptp^t for each fact at each time t≤Tt\le T and a variable ata^t for each action at each step t<Tt<T:

ClausesMeaning
p0p^0 for p∈Ip\in I; ¬p0\neg p^0 for p∉Ip\notin I; gTg^T for g∈Gg\in Ginitial state and goal
at⇒pta^t\Rightarrow p^t for p∈pre(a)p\in\mathrm{pre}(a)preconditions
at⇒pt+1a^t\Rightarrow p^{t+1} for p∈add(a)p\in\mathrm{add}(a); at⇒¬pt+1a^t\Rightarrow\neg p^{t+1} for p∈del(a)p\in\mathrm{del}(a)effects
¬pt∧pt+1⇒⋁a: p∈add(a)at\neg p^t\wedge p^{t+1}\Rightarrow\bigvee_{a:\,p\in\mathrm{add}(a)}a^t, and dually for deletesexplanatory frame axioms: facts change only for a reason
¬at∨¬bt\neg a^t\vee\neg b^t for interfering actions a,ba,bno conflicting actions in parallel
Satisfying assignments are plans: read off the true action variables. The planner tries T=0,1,2,…T=0,1,2,\dots until a formula is satisfiable; modern encodings that allow more parallel actions per step keep TT, and the formulas, small.

PDDL, and where to go deeper

PDDL (McDermott et al., 1998), created for the first International Planning Competition, separates a domain (types, predicates and action schemas) from a problem (objects, initial state and goal). Later versions added numeric fluents and durative actions (PDDL2.1, 2003), derived predicates and timed initial literals (PDDL2.2, 2004), preferences and trajectory constraints (PDDL3, for the 2006 competition), and continuous processes and events (PDDL+, 2006). Here is this lesson's delivery task:

text
(define (domain delivery)
  (:requirements :strips :typing)
  (:types room box)
  (:predicates (robot-at ?r - room) (at ?b - box ?r - room)
               (connected ?x ?y - room) (holding ?b - box) (hand-empty))
  (:action go
    :parameters (?x ?y - room)
    :precondition (and (robot-at ?x) (connected ?x ?y))
    :effect (and (robot-at ?y) (not (robot-at ?x))))
  (:action pick
    :parameters (?b - box ?r - room)
    :precondition (and (robot-at ?r) (at ?b ?r) (hand-empty))
    :effect (and (holding ?b) (not (at ?b ?r)) (not (hand-empty))))
  (:action drop
    :parameters (?b - box ?r - room)
    :precondition (and (robot-at ?r) (holding ?b))
    :effect (and (at ?b ?r) (hand-empty) (not (holding ?b)))))

(define (problem deliver-1) (:domain delivery)
  (:objects A B C - room  pkg - box)
  (:init (robot-at A) (at pkg B) (hand-empty)
         (connected A B) (connected B A) (connected B C) (connected C B))
  (:goal (at pkg C)))

Planners first ground the schemas. The action go has 3×3=93\times3=9 groundings, but only the 4 whose static precondition connected holds in the initial state survive: static facts never change, so they are evaluated once, during grounding. Any domain-independent planner, Fast Downward for instance, reads exactly these two definitions.

Key takeaways

  • A STRIPS task is ⟨F,A,I,G⟩\langle F,A,I,G\rangle, with states as sets of facts and s⟦a⟧=(s∖del(a))∪add(a)s\llbracket a\rrbracket=(s\setminus\mathrm{del}(a))\cup\mathrm{add}(a). State spaces explode: 59 million states for just 10 blocks.
  • Planners search forward (progression) or backward over subgoals (regression, (g∖add(a))∪pre(a)(g\setminus\mathrm{add}(a))\cup\mathrm{pre}(a)), guided by heuristics; plan existence is PSPACE-complete.
  • The delete relaxation gives h+h^+, admissible but NP-hard. hmax⁡≤h+≤haddh_{\max}\le h^+\le h_{\mathrm{add}}, and FF's relaxed-plan heuristic powers fast but suboptimal search.
  • Planning graphs (Graphplan) and SAT encodings (SATPlan) attack bounded planning through mutex reasoning and satisfiability; explanatory frame axioms stop facts from changing without a cause.
  • PDDL separates domain from problem, and planners ground its schemas into a STRIPS-like task before searching.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

An action has a fact pp in both its add list and its delete list. Under the semantics s⟦a⟧=(s∖del(a))∪add(a)s\llbracket a\rrbracket=(s\setminus\mathrm{del}(a))\cup\mathrm{add}(a), what holds after applying it?

  1. pp is false
  2. pp keeps its value from ss
  3. pp is true
  4. The result is undefined
Show the answer

C. pp is true

Deletes are applied first and adds second, so the add wins: p∈s⟦a⟧p\in s\llbracket a\rrbracket whatever ss was. PDDL uses the same convention.

Question 2

Why is STRIPS plan existence in PSPACE, even though it is not known to be in NP?

  1. Because the number of ground actions is exponential
  2. Because checking whether a given plan works is PSPACE-hard
  3. Because the state space is infinite
  4. Shortest plans can be exponentially long, so a plan cannot serve as a short certificate, but a search can keep just the current state and a step counter
Show the answer

D. Shortest plans can be exponentially long, so a plan cannot serve as a short certificate, but a search can keep just the current state and a step counter

A nondeterministic search guesses one action at a time, storing only the current state (∣F∣|F| bits) and a counter up to 2∣F∣2^{|F|}: polynomial space. Savitch's theorem removes the nondeterminism. The Deep Layer proves the problem PSPACE-complete.

Question 3

Which of these heuristics is admissible on every STRIPS task?

  1. haddh_{\mathrm{add}}
  2. hmax⁡h_{\max}
  3. hFFh_{\mathrm{FF}}
  4. 3⋅hmax⁡3\cdot h_{\max}
Show the answer

B. hmax⁡h_{\max}

hmax⁡≤h+≤h∗h_{\max}\le h^+\le h^*. The other three can overestimate.

Question 4

In the delivery example, hadd=5h_{\mathrm{add}}=5 while the optimal plan costs 4. Why does haddh_{\mathrm{add}} overestimate?

  1. It adds up the costs of Holding\mathit{Holding} and RobotAt(C)\mathit{RobotAt}(C) independently, so the shared move A→BA\to B is counted twice
  2. It ignores delete effects
  3. It takes a maximum over preconditions
  4. Unit action costs make sums inexact
Show the answer

A. It adds up the costs of Holding\mathit{Holding} and RobotAt(C)\mathit{RobotAt}(C) independently, so the shared move A→BA\to B is counted twice

Both subgoals need the robot at BB, and haddh_{\mathrm{add}} charges for getting there in each sum. FF's relaxed-plan extraction counts each action once and gets 4 here.

Question 5

In a SATPlan encoding, which clauses stop facts from becoming true for no reason?

  1. The precondition clauses
  2. The action mutex clauses
  3. The explanatory frame axioms
  4. The goal clauses
Show the answer

C. The explanatory frame axioms

¬pt∧pt+1⇒⋁a: p∈add(a)at\neg p^t\wedge p^{t+1}\Rightarrow\bigvee_{a:\,p\in\mathrm{add}(a)}a^t says that a fact can become true only if some action that adds it is executed. Without these axioms, a solver can satisfy the goal by "miracles".

Go deeper

Further reading

  • S. Russell & P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed. (Pearson, 2020), chapter 11.
  • M. Ghallab, D. Nau & P. Traverso, Automated Planning: Theory and Practice (Morgan Kaufmann, 2004).
  • B. Bonet & H. Geffner, "Planning as heuristic search," Artificial Intelligence 129(1–2) (2001), 5–33.
  • J. Hoffmann & B. Nebel, "The FF planning system: fast plan generation through heuristic search," Journal of Artificial Intelligence Research 14 (2001), 253–302.