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 facts can need 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 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 is NP-hard and hard to approximate.
- State the guarantees of , planning graphs and SAT encodings, including the NP-completeness of planning with a polynomial horizon.
Plan existence is PSPACE-complete
Membership. If a plan exists, a plan without repeated states exists, hence one shorter than . A nondeterministic procedure guesses applicable actions one at a time, storing only the current state ( bits) and a binary step counter ( bits), and accepts when the goal holds. For the bounded version the counter stops at . Savitch's theorem removes the nondeterminism:
Hardness. Let be a deterministic Turing machine that decides a PSPACE-complete language in space . For an input , introduce facts for the tape contents, the head position and the control state:
For each transition and each position , one action rewrites the configuration (when a fact is both added and deleted, the add wins). The initial state encodes the start configuration on , and the goal is :
In every reachable state exactly one action is applicable, the one that simulates 's next step, so plans correspond to runs. The task has facts and actions, so this is a polynomial reduction:
Plans can also be exponentially long. Take facts and for , and for each an action with precondition that adds and deletes . It increments a binary counter whose lowest 0 is bit . On the way from all zeros to the goal of all ones, exactly one action is applicable at every step.
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 , 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 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
| Setting | Plan existence | Source |
|---|---|---|
| Propositional STRIPS (literal preconditions and effects) | PSPACE-complete | Bylander (1994) |
| At most 2 preconditions and 2 effects per action | still PSPACE-complete | Bylander (1994) |
| Positive preconditions, 1 effect per action | polynomial | Bylander (1994) |
| No delete effects, positive preconditions (the delete relaxation) | polynomial; with a length bound, that is, computing , NP-complete | Bylander (1994) |
| Lifted STRIPS: schemas given as input, no function symbols | EXPSPACE-complete | Erol, Nau & Subrahmanian (1995) |
| With function symbols (infinitely many terms) | undecidable | Erol, Nau & Subrahmanian (1995) |
| Blocks world (a fixed domain) | always solvable; finding an optimal plan is NP-hard | Gupta & Nau (1992) |
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 and stabilize within rounds, and the relaxed task is solvable if and only if . This is propositional Horn reasoning: each action becomes the Horn clauses for , and with counters it runs in linear time (Dowling & Gallier, 1984).
Take a set cover instance: a universe and sets . Build a delete-free task with one fact per element, nothing true initially, every element a goal, and one action per set:
Without deletes and preconditions, order is irrelevant: a set of actions is a relaxed plan exactly when its sets cover , and its cost is the number of sets:
The reduction is polynomial and preserves the objective exactly. So the NP-hardness of set cover (Karp, 1972) and its inapproximability within unless P = NP (Dinur & Steurer, 2014) transfer to , with .
Practical heuristics therefore approximate or bound it, as with . The family (Haslum & Geffner, 2000) strengthens by estimating the cost of achieving each set of at most facts jointly, regressing a set through any action that adds part of it and deletes none of it:
Which statement about the heuristics is true?
- can overestimate, because it sums over pairs of facts
- , every is admissible, and for fixed it takes polynomial time, tracking sets
- always equals
- can be computed in time polynomial in
Show the answer
B. , every is admissible, and for fixed it takes polynomial time, tracking sets
never sums: it takes a maximum over subsets of size , each costed by a regression lower bound, so it never overestimates. The price of a larger is the 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 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 is set cover in disguise: NP-hard and inapproximable within .
- generalizes with admissible estimates, polynomial for fixed . 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.
Which argument shows that PlanSAT is in PSPACE?
- Every solvable task has a plan of polynomial length
- The planning graph has polynomial size
- Guess actions one at a time, storing only the current state and a step counter up to ; NPSPACE = PSPACE by Savitch's theorem
- 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 ; NPSPACE = PSPACE by Savitch's theorem
The procedure never stores the plan, only the current state and a counter of bits, so it runs in nondeterministic polynomial space, and Savitch's theorem makes it deterministic.
Bounded plan existence, with the bound written in unary, is…
- PSPACE-complete
- NP-complete
- solvable in polynomial time
- 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 in binary, it is PSPACE-complete again.
Why does plan existence jump from PSPACE to EXPSPACE when action schemas, rather than ground actions, are part of the input?
- Because predicates of unbounded arity have exponentially many ground atoms, so a single state can need exponential space
- Because grounding takes exponential time
- Because schemas can contain function symbols
- 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 objects, a predicate of arity has ground atoms, and 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).
In the reduction from set cover to delete-free planning, what does an optimal relaxed plan correspond to?
- A shortest path in the state space
- A maximum matching
- A minimum vertex cover of the causal graph
- 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 inherits the NP-hardness of set cover and its 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).