Consider a seemingly simple problem: a robot must rearrange blocks on a table into a specific configuration. Each action—picking up a block, placing it elsewhere—follows precise rules. Given unlimited time, any configuration is reachable. But here's the computational reality that haunts artificial intelligence: determining whether a plan exists, and finding one if it does, can require resources that dwarf the age of the universe.

This isn't hyperbole or theoretical hand-wringing. The complexity of planning sits at the heart of why artificial general intelligence remains elusive. Planning is PSPACE-complete—a classification that places it among the hardest problems computers can verify in polynomial space. Understanding what this means, and why it matters, reveals fundamental limits on machine reasoning while illuminating the ingenious techniques that make real-world planning possible despite these barriers.

The story of planning complexity is ultimately a story about the structure of problems themselves. Some planning domains hide exponential difficulty behind innocent-looking specifications. Others, despite surface complexity, harbor tractable cores that efficient algorithms can exploit. The difference lies not in our cleverness as algorithm designers, but in the mathematical properties of the domains we're trying to solve.

The STRIPS formalism, introduced at Stanford Research Institute in 1971, remains the foundation of classical planning. A STRIPS problem consists of an initial state, a goal condition, and a set of operators—each specifying preconditions and effects. The planning question asks: does a sequence of operators exist that transforms the initial state into one satisfying the goal?

In 1979, Chapman proved that STRIPS planning is undecidable in the general case. Subsequent work by Bylander in 1994 established the precise complexity for propositional STRIPS: PSPACE-complete. This means planning is as hard as any problem solvable with polynomial space, regardless of time. More practically, it means worst-case plan lengths can be exponential in the problem description size.

What does PSPACE-completeness actually mean for practitioners? Consider that NP-complete problems—already considered intractable—sit strictly below PSPACE unless P equals NP. Planning hardness exceeds even the satisfiability problems that challenge industrial constraint solvers. The state space of a planning problem can be doubly exponential: exponentially many states, each requiring exponential description.

The proof technique reveals why planning is hard. Bylander showed that STRIPS planning can simulate the behavior of polynomial-space Turing machines. Any computation requiring polynomial space—including verifying complex logical formulas and solving quantified Boolean formulas—reduces to a planning problem. Planning inherits the difficulty of all these problems simultaneously.

This hardness isn't an artifact of pathological encodings. Even heavily restricted variants remain intractable. Planning with only positive preconditions and effects is NP-complete. Adding delete effects immediately escalates to PSPACE-completeness. The transition from constructive to destructive actions fundamentally transforms computational difficulty. This insight shapes every practical planning system: managing the interaction between adding and removing facts is where complexity hides.

Takeaway

Worst-case complexity classifications describe what's possible when adversarial structure is present—they don't predict typical performance, but they warn us where dragons live.

PSPACE-completeness is a worst-case result. The critical question for practical systems becomes: what structural properties make planning easy? Decades of research have identified numerous tractable fragments—restricted problem classes where polynomial-time algorithms exist.

The most fundamental tractability condition involves acyclicity in causal structure. When state variables can be ordered such that each variable's changes depend only on earlier variables, planning reduces to a sequence of independent subproblems. Kautz and Selman's work on causal graphs formalized this intuition: polynomial planning is possible when the causal graph has bounded treewidth.

Delete-free planning—where operators only add facts, never remove them—drops from PSPACE to NP. This relaxation underlies many practical heuristics: solving the delete-free version of a problem provides admissible estimates for the original. The computational gap between NP and PSPACE represents not just theoretical interest but practical opportunity.

Unary operators—those affecting at most one state variable—enable polynomial planning algorithms. This captures domains like logistics where moving an object changes only that object's location. More generally, bounded effect size combined with bounded causal graph width guarantees tractability. These conditions describe why real-world domains often admit efficient solutions despite worst-case hardness.

The theory of tractable planning extends to temporal and numeric extensions. Restricted temporal planning with fixed durations and simple concurrency requirements admits polynomial algorithms. Numeric planning with monotonic resource consumption often decomposes into tractable subproblems. Identifying which structural features your domain possesses—and encoding problems to preserve them—separates successful planning applications from computational catastrophes.

Takeaway

Tractability emerges from structure, not size. The key question isn't 'how big is my problem?' but 'what dependencies exist between my state variables?'

Classical planning systems achieve remarkable performance on problems that theoretical analysis declares hopeless. The Fast Downward planner, using landmark heuristics and other advances, solves problems with millions of reachable states in seconds. This practical success against theoretical impossibility demands explanation.

Landmark heuristics exploit necessary subgoal structure. A landmark is a fact that must be true at some point in every valid plan. Identifying landmarks is computationally cheap—often achievable by analyzing the delete-relaxation of a problem—while providing powerful pruning information. If achieving fact A requires achieving fact B first, and the current state lacks B, we have a lower bound on remaining plan length.

The landmark-cut heuristic extends this idea by computing minimum hitting sets of landmark orderings. When multiple ordering constraints compete for satisfaction, the planner must traverse bottlenecks that force specific action sequences. Detecting these bottlenecks transforms exponential search spaces into navigable channels. Empirically, landmark-based planners often examine only a tiny fraction of reachable states.

Partial-order planning represents an orthogonal approach: instead of searching through state sequences, search through partially-ordered sets of actions with causal links. This representation naturally exploits plan structure—irrelevant actions remain unordered, reducing commitment and backtracking. Modern partial-order planners like VHPOP combine this flexibility with heuristic guidance from forward-search innovations.

The synthesis of these techniques in contemporary planners demonstrates a fundamental principle: worst-case complexity describes adversarial instances, not typical problems. Real domains have structure—repeated subgoals, natural decompositions, redundant paths to goals—that heuristics can exploit. The art of planning lies in designing representations and algorithms that recognize and leverage this structure automatically.

Takeaway

Practical tractability often exists within theoretically intractable problem classes—the goal is building algorithms that find and exploit the structure that makes real instances easy.

Planning complexity theory delivers both sobering limits and practical guidance. PSPACE-completeness tells us that no algorithm will solve all planning problems efficiently—adversarial instances will always defeat us. But this same theory identifies escape routes: structural restrictions that guarantee tractability and heuristic approaches that succeed on typical instances.

The implications extend beyond planning to AI reasoning generally. Intelligence is not raw computational power but the ability to recognize and exploit structure. Human planners succeed not by exhaustive search but by decomposing problems, identifying subgoals, and focusing attention on critical bottlenecks. Computational planning research formalizes and extends these strategies.

For practitioners, the lesson is clear: understand your domain's structure before choosing algorithms. Analyze causal dependencies, identify natural decompositions, and select representations that preserve tractable features. Worst-case complexity is real, but so is the remarkable tractability of well-structured problems.