TL;DR
This paper challenges the long-held belief that automated planning problems with exponentially long solutions are inherently intractable for plan generation. By representing plans compactly as hierarchical macros, the authors present a polynomial-time plan generation algorithm for the well-known class 3S. In addition, they resolve open complexity gaps by proving that plan existence is NP-hard for chain-structured causal graphs with multi-valued variables ($\mathcal{C}_n$) and NP-complete for binary polytree causal graphs.
What Problem Does This Paper Address?
In automated planning, researchers distinguish between two computational questions:
- Plan existence: Does any valid sequence of actions move the system from an initial state to a goal state?
- Plan generation: Can we actually construct such an action sequence?
Historically, the class 3S (binary variables, acyclic causal graphs where variables are static, reversible, or "splitting") was seen as a canonical counterexample showing that plan existence is easy ($\mathbf{P}$), but plan generation is inherently intractable because the shortest valid plans can be exponentially long ($2^{n-1}$ steps).
The authors investigate whether this intractability is intrinsic or simply an artifact of insisting that plans be written out step-by-step. They also revisit two other classes where exponential plan length was used as an argument for hardness—directed chain causal graphs ($\mathcal{C}_n$) and polytree causal graphs—to determine whether their hardness is fundamental (i.e., whether deciding if a plan even exists is NP-hard).
Methods
- Hierarchical Macro Generation (
Macro-3S): Instead of expanding an exponentially long sequence of primitive operators, the authors generate unary macros—sequences composed of operators and sub-macros that change a single variable and reset side effects. - The algorithm traverses variables in topological order, building macros via
GenerateMacro. - For splitting variables, the problem is divided recursively into variables that depend on value 0 ($V^v_0$), value 1 ($V^v_1$), or neither ($V^v_*$), generating the final plan recursively via
GeneratePlan. - Random-Access Plan Evaluation: The authors provide dynamic programming and recursive search procedures to compute total plan length and extract the $i$-th primitive action of an unexpanded macro plan in polynomial time without flattening it into memory.
- Complexity Reductions:
- $\mathcal{C}_n$ NP-hardness: A reduction from CNF-SAT where multi-valued state variables along a chain commit to truth assignments and propagate clause satisfaction "messages" down to the goal.
- Polytree NP-completeness: A reduction from 3SAT to binary polytrees where satisfying clause assignments enable a counter variable $v_1$ to alternate values, which in turn unlocks a chain of auxiliary variables required by the goal.
Datasets
Not discussed in the paper. This is a purely theoretical computer science paper establishing formal computational complexity bounds; no empirical datasets or experimental benchmarks were evaluated.
Key Insights and Ideas
- Long plans $\neq$ hard problems: Exponential plan length does not imply that planning is intractable. If a solution exhibits regular, nested subproblems, it can be encoded concisely as a macro grammar in polynomial time.
- You don’t need to expand macros to use them: An agent executing a plan only needs to know the next action to apply. The authors show that the $i$-th action of a macro-encoded plan can be retrieved in $O(|V|^2)$ time, and the plan length can be computed in $O(|V|^2)$ time.
- Genuine intractability in simple graphs:
- For chain causal graphs ($\mathcal{C}_n$), multi-valued domains allow the problem to encode SAT clauses, making plan existence NP-hard regardless of output representation.
- For polytree causal graphs with binary variables, unbounded indegree allows encoding 3SAT satisfaction checks, showing that plan existence is NP-complete. This tightly complements previous algorithms that required bounded indegree or bounded depth.
Key Results
- Polynomial Plan Generation for 3S: The
Macro-3Salgorithm outputs a valid macro-plan in $O(|A||V|^2)$ time, where $|A|$ is the number of operators and $|V|$ is the number of state variables. - Plan Length Bounds:
- A plan generated by the algorithm on $n$ variables with graph depth $d$ has length at most $\frac{1}{2} \left[\left(1 + \frac{2n}{d + 1}\right)^{d+1} - 1\right]$.
- The worst-case bound across all 3S instances is $(3^n - 1)/2$, which is shown to be tight. If depth $d$ is bounded by a constant, plan length is polynomial: $O(n^{d+1})$.
- NP-Hardness of $\mathcal{C}_n$: Plan existence for multi-valued chain causal graphs is NP-hard.
- NP-Completeness of Binary Polytrees: Plan existence for planning problems with binary variables and polytree causal graphs is NP-complete.
- CP-Nets Corollary: Testing dominance in polytree CP-nets with binary variables and partially specified conditional preference tables (CPTs) is NP-complete.
Limitations and Future Work
- Suboptimal Plans: While
Macro-3Sproduces a valid macro plan in polynomial time, the resulting plan is generally suboptimal (finding the optimal or bounded plan in 3S remains NP-hard). - Execution Overhead: If a system must ground out and write down every single physical action upfront, the output remains exponential in worst-case scenarios.
- Domain Size in Chains: The reduction for $\mathcal{C}_n$ uses domains whose size grows with the number of clauses. The authors leave open whether $\mathcal{C}_n$ remains tractable if the variable domain size is bounded by a constant greater than 2.
Summary updated