The Complexity of Planning Problems With Simple Causal Graphs

Omer Giménez, Anders Jonsson

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.

Introduction

Automated planning involves finding a sequence of actions to transition a system from an initial state to a goal state. A key tool in analyzing the complexity of these problems is the causal graph, which represents dependencies between state variables. Traditionally, it was assumed that if a problem instance required an exponentially long plan, generating that plan must be computationally hard. This paper challenges that assumption by investigating the 3S class (acyclic causal graphs with binary variables) and other simple structures like chains ($C_n$) and polytrees.

Tractable Plan Generation: The MACRO-3S Algorithm

The primary contribution is the MACRO-3S algorithm, which demonstrates that plan generation can be efficient even when the resulting plan is exponentially long. The key is succinct representation. Instead of a flat list of actions, the algorithm outputs a hierarchy of macros—sequences that can contain both primitive actions and other macros.

Figure 1(b): Partitioning of variables in the causal graph for recursive macro construction.

The algorithm traverses the causal graph in topological order. For each variable, it constructs macros to change its value while ensuring that all ancestor variables are either preserved or restored to their required states. This recursive approach allows the algorithm to handle the $(3^n - 1)/2$ plan length bound of the 3S class in polynomial time relative to the number of variables $n$.

Hardness Results for Simple Structures

While the 3S class proves tractable for generation, slight increases in structural complexity lead to intractability. The authors provide two significant hardness results:

  1. Multi-valued Variables in Chains ($C_n$): Moving from binary to multi-valued variables in a simple chain causal graph makes the plan existence problem NP-hard. This indicates that the difficulty is not merely a function of plan length but is inherent in the search for the plan's structure.
  2. Binary Variables in Polytrees: For binary variables, if the causal graph is a polytree (a directed graph where the underlying undirected graph is a tree), the plan existence problem is NP-complete.
Table 5: Formal definition of operators and variable sets used in the complexity reductions.

These results are established through reductions from 3SAT and CNF-SAT, mapping boolean formulas into planning instances where a valid plan exists if and only if the formula is satisfiable. The sensitivity of planning complexity to small changes in variable domain size or graph topology is a core finding of this work.

Conclusion

This work redefines the boundaries of tractability in AI planning. It shows that plan length and computational complexity are decoupled; structured, repetitive solutions can be generated efficiently using macros. However, it also highlights the extreme sensitivity of planning complexity to structural parameters. Future research may explore other parameters, such as graph width, to identify further tractable subclasses.

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},
}
Figure