Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

Classical Planning & Its Complexity

Why planning is PSPACE-complete, and heuristics that help.

A STRIPS task can simulate any Turing machine that runs in polynomial space, and a task with only 2n2n facts can need 2n−12^n-1 steps to solve. This lesson proves that plan existence is PSPACE-complete, maps exactly where the hardness comes from, and shows why the ideal delete-relaxation heuristic h+h^+ is NP-hard even to approximate.

What you’ll learn

  • Prove that propositional STRIPS plan existence is PSPACE-complete, and construct tasks whose shortest plans are exponentially long.
  • Locate the sources of hardness with Bylander's syntactic restrictions and with the lifted (EXPSPACE-complete) and function-symbol (undecidable) cases.
  • Prove that delete-free plan existence reduces to Horn reachability, while computing h+h^+ is NP-hard and hard to approximate.
  • State the guarantees of hmh^m, planning graphs and SAT encodings, including the NP-completeness of planning with a polynomial horizon.

Plan existence is PSPACE-complete

DerivationProof
  1. PlanSAT∈NPSPACE=PSPACE\text{PlanSAT}\in\mathsf{NPSPACE}=\mathsf{PSPACE}

    Membership. If a plan exists, a plan without repeated states exists, hence one shorter than 2∣F∣2^{|F|}. A nondeterministic procedure guesses applicable actions one at a time, storing only the current state (∣F∣|F| bits) and a binary step counter (∣F∣|F| bits), and accepts when the goal holds. For the bounded version the counter stops at min⁡(k,2∣F∣)\min(k,2^{|F|}). Savitch's theorem removes the nondeterminism:

  2. F={Cell(i,σ)}i≤p(n), σ∈Σ ∪ {Head(i)}i≤p(n) ∪ {State(q)}q∈QF=\{\mathit{Cell}(i,\sigma)\}_{i\le p(n),\,\sigma\in\Sigma}\ \cup\ \{\mathit{Head}(i)\}_{i\le p(n)}\ \cup\ \{\mathit{State}(q)\}_{q\in Q}

    Hardness. Let MM be a deterministic Turing machine that decides a PSPACE-complete language in space p(n)p(n). For an input ww, introduce facts for the tape contents, the head position and the control state:

  3. pre={State(q), Head(i), Cell(i,σ)}add={State(q′), Head(i+d), Cell(i,σ′)}del={State(q), Head(i), Cell(i,σ)}\begin{aligned}\mathrm{pre}&=\{\mathit{State}(q),\ \mathit{Head}(i),\ \mathit{Cell}(i,\sigma)\}\\ \mathrm{add}&=\{\mathit{State}(q'),\ \mathit{Head}(i+d),\ \mathit{Cell}(i,\sigma')\}\\ \mathrm{del}&=\{\mathit{State}(q),\ \mathit{Head}(i),\ \mathit{Cell}(i,\sigma)\}\end{aligned}

    For each transition δ(q,σ)=(q′,σ′,d)\delta(q,\sigma)=(q',\sigma',d) and each position ii, one action rewrites the configuration (when a fact is both added and deleted, the add wins). The initial state encodes the start configuration on ww, and the goal is {State(qacc)}\{\mathit{State}(q_{\mathrm{acc}})\}:

  4. M accepts w  ⟺  ΠM,w has a planM\text{ accepts }w\iff\Pi_{M,w}\text{ has a plan}

    In every reachable state exactly one action is applicable, the one that simulates MM's next step, so plans correspond to runs. The task has O(p(n) ∣Σ∣+∣Q∣)\order{p(n)\,|\Sigma|+|Q|} facts and O(p(n) ∣δ∣)\order{p(n)\,|\delta|} actions, so this is a polynomial reduction:

Plans can also be exponentially long. Take facts zeroi\mathit{zero}_i and onei\mathit{one}_i for i=1,…,ni=1,\dots,n, and for each ii an action inci\mathit{inc}_i with precondition {zeroi,one1,…,onei−1}\{\mathit{zero}_i,\mathit{one}_1,\dots,\mathit{one}_{i-1}\} that adds {onei,zero1,…,zeroi−1}\{\mathit{one}_i,\mathit{zero}_1,\dots,\mathit{zero}_{i-1}\} and deletes {zeroi,one1,…,onei−1}\{\mathit{zero}_i,\mathit{one}_1,\dots,\mathit{one}_{i-1}\}. It increments a binary counter whose lowest 0 is bit ii. On the way from all zeros to the goal of all ones, exactly one action is applicable at every step.

Predict before you look

How many actions does the shortest (indeed the only) plan of the 6-bit counter task have?

Show the answer

63 actions

The counter must pass through every value from 0 to 26−1=632^6-1=63, one increment at a time: 63 actions, from a task with only 12 facts and 6 actions. With 60 bits the plan would have about 1.15×10181.15\times10^{18} steps. So a plan cannot always serve as a polynomial-size certificate, although it is PSPACE-completeness, not plan length alone, that makes membership in NP unlikely.

Where the hardness lives

SettingPlan existenceSource
Propositional STRIPS (literal preconditions and effects)PSPACE-completeBylander (1994)
At most 2 preconditions and 2 effects per actionstill PSPACE-completeBylander (1994)
Positive preconditions, 1 effect per actionpolynomialBylander (1994)
No delete effects, positive preconditions (the delete relaxation)polynomial; with a length bound, that is, computing h+h^+, NP-completeBylander (1994)
Lifted STRIPS: schemas given as input, no function symbolsEXPSPACE-completeErol, Nau & Subrahmanian (1995)
With function symbols (infinitely many terms)undecidableErol, Nau & Subrahmanian (1995)
Blocks world (a fixed domain)always solvable; finding an optimal plan is NP-hardGupta & Nau (1992)
Hardness survives severe syntactic limits and vanishes without deletes. Lifting adds an exponential because predicates of unbounded arity have exponentially many ground atoms, so even writing down a state can take exponential space.

Domain-level analyses tell a similar story. Helmert (2003) classified the standard competition domains: in many of them, finding some plan takes polynomial time, while finding an optimal one is NP-hard. PSPACE-completeness is a worst-case statement. Benchmark domains have structure, and exploiting that structure is what heuristics do.

The delete relaxation, exactly

Without deletes, reachability is monotone: the sets R0=sR_0=s and Rj+1=Rj∪⋃{add(a):pre(a)⊆Rj}R_{j+1}=R_j\cup\bigcup\{\mathrm{add}(a):\mathrm{pre}(a)\subseteq R_j\} stabilize within ∣F∣|F| rounds, and the relaxed task is solvable if and only if G⊆R∞G\subseteq R_\infty. This is propositional Horn reasoning: each action becomes the Horn clauses ⋀pre(a)⇒p\bigwedge\mathrm{pre}(a)\Rightarrow p for p∈add(a)p\in\mathrm{add}(a), and with counters it runs in linear time (Dowling & Gallier, 1984).

DerivationProof: set cover in disguise
  1. F=G=U,I=∅,aj: pre=∅, add=Sj, c(aj)=1F=G=U,\qquad I=\varnothing,\qquad a_j:\ \mathrm{pre}=\varnothing,\ \mathrm{add}=S_j,\ c(a_j)=1

    Take a set cover instance: a universe UU and sets S1,…,Sm⊆US_1,\dots,S_m\subseteq U. Build a delete-free task with one fact per element, nothing true initially, every element a goal, and one action per set:

  2. h+(I)=min⁡{∣J∣: ⋃j∈JSj=U}h^+(I)=\min\Big\{|J|:\ \bigcup_{j\in J}S_j=U\Big\}

    Without deletes and preconditions, order is irrelevant: a set of actions is a relaxed plan exactly when its sets cover UU, and its cost is the number of sets:

  3. SetCover≤ph+⟹h+ is NP-hard and (1−ε)ln⁡∣G∣-inapproximable\text{SetCover}\le_p h^+\quad\Longrightarrow\quad h^+\text{ is NP-hard and }(1-\varepsilon)\ln|G|\text{-inapproximable}

    The reduction is polynomial and preserves the objective exactly. So the NP-hardness of set cover (Karp, 1972) and its inapproximability within (1−ε)ln⁡∣U∣(1-\varepsilon)\ln|U| unless P = NP (Dinur & Steurer, 2014) transfer to h+h^+, with ∣U∣=∣G∣|U|=|G|.

Practical heuristics therefore approximate h+h^+ or bound it, as with hmax⁡≤h+≤haddh_{\max}\le h^+\le h_{\mathrm{add}}. The hmh^m family (Haslum & Geffner, 2000) strengthens hmax⁡h_{\max} by estimating the cost of achieving each set of at most mm facts jointly, regressing a set PP through any action that adds part of it and deletes none of it:

hm(P)={0P⊆smin⁡a: add(a)∩P≠∅, del(a)∩P=∅[c(a)+hm((P∖add(a))∪pre(a))]∣P∣≤mmax⁡P′⊆P, ∣P′∣=mhm(P′)∣P∣>mh^m(P)=\begin{cases}0&P\subseteq s\\ \min\limits_{a:\ \mathrm{add}(a)\cap P\neq\varnothing,\ \mathrm{del}(a)\cap P=\varnothing}\big[c(a)+h^m\big((P\setminus\mathrm{add}(a))\cup\mathrm{pre}(a)\big)\big]&|P|\le m\\ \max\limits_{P'\subseteq P,\ |P'|=m}h^m(P')&|P|>m\end{cases}
h1=hmax⁡h^1=h_{\max}. Each hmh^m is admissible and computable in time polynomial in ∣F∣|F| and ∣A∣|A| for fixed mm (there are O(∣F∣m)\order{|F|^m} sets to track); hm+1h^{m+1} dominates hmh^m, and hm=h∗h^m=h^* once m≥∣F∣m\ge|F|. Graphplan's mutex reasoning is closely related to h2h^2.
Check your understanding

Which statement about the hmh^m heuristics is true?

  1. h2h^2 can overestimate, because it sums over pairs of facts
  2. h1=hmax⁡h^1=h_{\max}, every hmh^m is admissible, and for fixed mm it takes polynomial time, tracking O(∣F∣m)\order{|F|^m} sets
  3. h2h^2 always equals h+h^+
  4. hmh^m can be computed in time polynomial in mm
Show the answer

B. h1=hmax⁡h^1=h_{\max}, every hmh^m is admissible, and for fixed mm it takes polynomial time, tracking O(∣F∣m)\order{|F|^m} sets

hmh^m never sums: it takes a maximum over subsets of size mm, each costed by a regression lower bound, so it never overestimates. The price of a larger mm is the O(∣F∣m)\order{|F|^m} table.

Planning graphs and SAT, as theorems

SAT encodings differ in how much parallelism a step allows. Under ∀-step semantics, actions taken in parallel must be executable in every order, as in Graphplan; under ∃-step semantics, one valid order suffices (Rintanen, Heljanko & Niemelä, 2006). More parallelism means shorter horizons and smaller formulas. Kautz and Selman (1996) showed that SAT encodings solved by local search could beat the specialized planners of the day on hard instances, and their later BLACKBOX system compiled planning graphs into SAT. SAT-based planners such as Rintanen's Madagascar remain competitive on some benchmark families, and they inherit every advance in SAT solving.

Key takeaways

  • PlanSAT is PSPACE-complete (Bylander, 1994): nondeterministic search with a counter shows membership, a Turing-machine simulation shows hardness, and shortest plans can have 2n−12^n-1 steps.
  • Hardness survives tight syntactic limits (2 preconditions, 2 effects) and disappears without deletes; lifted STRIPS is EXPSPACE-complete, and function symbols make planning undecidable.
  • Delete-free reachability is Horn inference, decidable in linear time, but h+h^+ is set cover in disguise: NP-hard and inapproximable within (1−ε)ln⁡∣G∣(1-\varepsilon)\ln|G|.
  • hmh^m generalizes hmax⁡=h1h_{\max}=h^1 with admissible estimates, polynomial for fixed mm. With a unary horizon planning is NP-complete, the license for SAT encodings, whose parallel semantics keep horizons short.

Check yourself

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

Question 1

Which argument shows that PlanSAT is in PSPACE?

  1. Every solvable task has a plan of polynomial length
  2. The planning graph has polynomial size
  3. Guess actions one at a time, storing only the current state and a step counter up to 2∣F∣2^{|F|}; NPSPACE = PSPACE by Savitch's theorem
  4. Reachable states are polynomially many
Show the answer

C. Guess actions one at a time, storing only the current state and a step counter up to 2∣F∣2^{|F|}; NPSPACE = PSPACE by Savitch's theorem

The procedure never stores the plan, only the current state and a counter of ∣F∣|F| bits, so it runs in nondeterministic polynomial space, and Savitch's theorem makes it deterministic.

Question 2

Bounded plan existence, with the bound kk written in unary, is…

  1. PSPACE-complete
  2. NP-complete
  3. solvable in polynomial time
  4. undecidable
Show the answer

B. NP-complete

A unary bound makes the plan a certificate of polynomial size, checkable by simulation, so the problem is in NP; and set cover reduces to it, even without deletes. With kk in binary, it is PSPACE-complete again.

Question 3

Why does plan existence jump from PSPACE to EXPSPACE when action schemas, rather than ground actions, are part of the input?

  1. Because predicates of unbounded arity have exponentially many ground atoms, so a single state can need exponential space
  2. Because grounding takes exponential time
  3. Because schemas can contain function symbols
  4. Because lifted search cannot detect duplicate states
Show the answer

A. Because predicates of unbounded arity have exponentially many ground atoms, so a single state can need exponential space

With nn objects, a predicate of arity kk has nkn^k ground atoms, and kk is part of the input, so states are exponentially large. Searching such a state space takes exponential space, and the problem is EXPSPACE-complete (Erol, Nau & Subrahmanian, 1995).

Question 4

In the reduction from set cover to delete-free planning, what does an optimal relaxed plan correspond to?

  1. A shortest path in the state space
  2. A maximum matching
  3. A minimum vertex cover of the causal graph
  4. A minimum set cover
Show the answer

D. A minimum set cover

Each action adds the elements of one set and has no preconditions, so a relaxed plan is a family of sets covering the universe, and its cost is the number of sets. Hence h+h^+ inherits the NP-hardness of set cover and its (1−ε)ln⁡n(1-\varepsilon)\ln n inapproximability.

Further reading

  • T. Bylander, "The computational complexity of propositional STRIPS planning," Artificial Intelligence 69(1–2) (1994), 165–204.
  • K. Erol, D. S. Nau & V. S. Subrahmanian, "Complexity, decidability and undecidability results for domain-independent planning," Artificial Intelligence 76(1–2) (1995), 75–88.
  • A. L. Blum & M. L. Furst, "Fast planning through planning graph analysis," Artificial Intelligence 90(1–2) (1997), 281–300.
  • H. Kautz & B. Selman, "Pushing the envelope: planning, propositional logic, and stochastic search," Proceedings of AAAI (1996).
  • M. Ghallab, D. Nau & P. Traverso, Automated Planning: Theory and Practice (Morgan Kaufmann, 2004).