In the early 1990s, the field of Automated Planning faced a significant theoretical challenge: while it was widely accepted that planning was "hard," there was no unified understanding of which specific features contributed to its computational difficulty. In their seminal 1992 paper, "On the Complexity of Domain-Independent Planning," Kutluhan Erol, Dana S. Nau, and V. S. Subrahmanian established a definitive taxonomy for the complexity of STRIPS-style planning.
Defining the Planning Problem
The authors focused on domain-independent planning, where the goal is to find a sequence of actions to transform an initial state into a target state. They specifically analyzed two primary decision problems:
- Plan Existence: Determining if any valid plan exists to reach the goal.
- Plan Length: Determining if a plan exists with a length of at most $k$.
To provide a comprehensive analysis, the paper examines these problems across various language restrictions, such as the inclusion of delete lists, negated preconditions, and the arity of predicates.
Complexity Analysis Framework
The research utilizes formal complexity theory, mapping different planning configurations to classes like PSPACE, EXPSPACE, and NEXPTIME. A central distinction is made between Propositional Planning, where predicates are 0-ary atoms (simple boolean flags), and Datalog Planning, where predicates can include constants and variables (but no function symbols, ensuring decidability).
A significant technical finding was that negated preconditions do not fundamentally increase complexity if delete lists are permitted; they can be "compiled away" into positive preconditions in polynomial time.
The Role of Domain Examples
While the paper is primarily theoretical, it uses the classic Blocks World domain to ground its analysis. Blocks World serves as a perfect vehicle to demonstrate how different formalizations of the same physical task—stacking blocks—can lead to vastly different computational profiles depending on the allowed operators and predicates.
Key Insights into Planning Hardness
The authors identified several critical drivers of planning complexity:
- The "One Level Up" Rule: Generally, moving from propositional logic to Datalog (adding variables) shifts the problem exactly one level higher in the complexity hierarchy. For instance, a PSPACE-complete propositional problem often becomes EXPSPACE-complete in Datalog.
- The Plan Length Anomaly: Counter-intuitively, finding a plan of a specific length can be "easier" than finding any plan. In Datalog planning with delete lists, Plan Length is NEXPTIME-complete, while Plan Existence is EXPSPACE-complete. This occurs because a binary-encoded $k$ constrains the search space to exponential lengths, whereas a general plan might require doubly exponential steps.
- The Impact of Delete Lists: The ability to delete facts (non-monotonicity) is a primary driver of difficulty. Removing delete lists makes planning monotonic and significantly reduces complexity, as actions never need to be "undone."
- Fixed vs. Variable Operators: Complexity is lower when the set of actions is fixed beforehand rather than provided as part of the problem input.
A Roadmap of Complexity Results
The paper’s most enduring contribution is its comprehensive summary table, which has become a standard reference for AI researchers. It clearly delineates how specific constraints—like the absence of delete lists or the use of 0-ary predicates—impact the tractability of the planning task.
| Restrictions | PLAN EXISTENCE Complexity |
|---|---|
| General Datalog | EXPSPACE-complete |
| Datalog (No Delete Lists) | NEXPTIME-complete |
| General Propositional | PSPACE-complete |
| Propositional (No Delete Lists) | NP-complete |
| Propositional (Positive, Context-free) | Polynomial (P) |
Conclusion and Future Directions
The study concludes that general domain-independent planning is exceptionally difficult, often exceeding the complexity of other common AI tasks like constraint satisfaction. The authors noted that adding function symbols would render the problem undecidable.
Given these hardness results, the paper suggests that future efforts should focus on identifying tractable sub-problems, developing efficient plan-merging techniques, and exploring heuristic approaches that perform well in practice despite theoretical worst-case complexities. This work remains a cornerstone of planning theory, providing the essential "complexity roadmap" for the field.
Summary updated