The Complexity of Planning Problems With Simple Causal Graphs

Omer Giménez, Anders Jonsson

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:

  1. Plan existence: Does any valid sequence of actions move the system from an initial state to a goal state?
  2. 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-3S algorithm 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-3S produces 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

Abstract

We present three new complexity results for classes of planning problems with simple causal graphs. First, we describe a polynomial-time algorithm that uses macros to generate plans for the class 3S of planning problems with binary state variables and acyclic causal graphs. This implies that plan generation may be tractable even when a planning problem has an exponentially long minimal solution. We also prove that the problem of plan existence for planning problems with multi-valued variables and chain causal graphs is NP-hard. Finally, we show that plan existence for planning problems with binary state variables and polytree causal graphs is NP-complete.
BibTeX
@article{gimenez2008complexity,
  author = {Omer Giménez and Anders Jonsson},
  title = {{The Complexity of Planning Problems With Simple Causal Graphs}},
  journal = {J. Artif. Intell. Res.},
  year = {2008},
  url = {https://openreview.net/forum?id=BKnBcdNk7wn},
}

Loading related content...

Figure