Automated planning is a cornerstone of AI, yet it remains one of the most computationally demanding tasks. While basic planning is NP-complete, more realistic scenarios—incorporating uncertainty, soft goals, or optimization—often escalate to $\Sigma^P_2$-complete or even PSPACE-complete. This paper, presented at IJCAI 2015, explores the boundary between these "impossible" planning problems and those that can be solved efficiently using modern SAT solvers.
By applying the lens of parameterized complexity, the authors identify specific structural conditions that allow high-complexity planning problems to be reduced to SAT. They provide a comprehensive "complexity map" for planning problems sitting beyond NP, characterizing which variants can be efficiently reduced based on structural parameters like the degree of uncertainty or plan length.
Defining the Planning Landscape
To understand the boundary of tractability, the authors analyze several flavors of planning. A primary example is planning under uncertainty, where the initial state is not fully known.
In this variant, the goal is to find a plan that works for all possible ways of completing the initial state. Standard SAT solvers are designed for NP problems, but these "harder-than-NP" problems require an efficient way to translate (reduce) the problem into a SAT instance. The authors ask: Under what structural conditions is such a reduction actually possible? Instead of looking only at the total input size, they use "parameters"—specific properties like the number of unknown variables—to see if they can "trap" the high complexity.
The Parameterized Approach
The researchers utilize Parameterized Complexity Theory to analyze how specific parts of a problem contribute to its overall difficulty. Their methodology involves:
- FPT-Reductions: Defining reductions that run in polynomial time relative to the input size, but may be exponential relative to a small, fixed parameter ($k$).
- Class Characterization: Proving that various planning flavors (uncertainty, soft goals, essential actions) are "complete" for specific parameterized classes like
para-NP,para-DP, and $FPT^{NP[f(k)]}$. - Machine Characterization: Developing a novel characterization of the class $\exists^*\forall^k\text{-W[P]}$ using restricted Alternating Turing Machines (ATMs).
A Map of Intractability
The core contribution of the paper is the establishment of a hierarchy that maps planning variants to their corresponding complexity classes. This map identifies the "SAT-Feasibility" threshold: problems in classes like para-NP and para-DP are considered "SAT-friendly."
As shown in the hierarchy above, the authors distinguish between parameters that help and those that do not. For instance, if a planning problem with uncertainty has a small number of unknown variables, it can be "materialized" into a single SAT formula. However, if the same problem is parameterized by plan length ($k$) rather than the amount of uncertainty, it lands in the class $\exists^k\forall^*$, where a standard SAT reduction is likely impossible.
Key Results
The paper establishes several critical bounds for planning variants:
PLANNING[UNCERTAINTY]: (Parameter: # of unknown variables + domain size). Proved para-NP-complete, meaning it can be solved with a single call to a SAT solver if the parameter is small.PLANNING[ESSENTIAL ACTION]: (Determining if a specific action is required for all valid plans). Proved para-DP-complete, requiring at most two SAT calls.PLANNING[SOFT GOAL]-PARITY: (Maximizing satisfied goals). Proved $FPT^{NP[f(k)]}$-complete, solvable using a logarithmic number of SAT calls via binary search.PLANNING[BOUNDED DEVIATION]: (Uncertainty where only $d$ variables differ from a "base" state). Proved $\exists^*\forall^k\text{-W[P]}$-complete, placing it in a much higher, non-SAT-reducible zone of the hierarchy.
Conclusion and Future Work
While this work provides a theoretical roadmap for SAT reductions, the authors note that a reduction that is "efficient" in theory might still produce SAT instances too large for practical use. Future work involves extending this complexity mapping to other fields of AI, such as Knowledge Representation, and identifying more "natural" problems that fit into the more complex classes like the $\text{W[P]}$ variants to better understand the landscape of intractability.
Summary updated