Causal Graph Tractability Boundaries in Classical Planning

89 concepts39 papers1 proposal

Automated planning is notoriously difficult. In its general form, determining whether a sequence of actions can transition a system from an initial state to a goal state is PSPACE-complete. The root of this complexity is the state-space explosion: if a system is described by $n$ variables, the number of possible states grows exponentially.

To find "islands of tractability" within this combinatorial wilderness, researchers look to the causal graph. A causal graph maps the structural dependencies of a planning problem. Each node represents a state variable, and a directed edge from variable $A$ to variable $B$ indicates that an action modifying $B$ either depends on the value of $A$ as a precondition or changes $A$ simultaneously.

By analyzing the topology of these graphs and the properties of the variables within them, researchers have mapped out precise boundaries where planning transitions from computationally impossible to efficiently solvable. The core insight of this field is that when these structural properties are sufficiently constrained, complex sequential planning problems can be compiled into static, localized problems—such as tree-structured Constraint Satisfaction Problems (CSPs)—or compressed into a polynomial set of hierarchical macros.

The Geometry of Dependency

The simplest way to simplify a planning problem is to break it into independent pieces. If the causal graph can be decomposed into isolated or loosely coupled components, we can solve sub-goals individually and coordinate the results.

As demonstrated by Ronen I. Brafman et al. in Factored Planning: How, When, and When Not, the structural metric that governs this decomposability is the tree-width of the causal graph. When the tree-width is low and local sub-plans are relatively short, factored planning strategies achieve exponential speedups over traditional methods.

However, topology alone does not guarantee efficiency. For a long time, it was assumed that simply ensuring the causal graph was acyclic (meaning information flows in only one direction) would make planning easy. This assumption was shattered by Anders Jonsson et al. in When Acyclicity Is Not Enough: Limitations of the Causal Graph, which proved that plan existence remains PSPACE-complete even under strictly acyclic constraints. To achieve true tractability, we must look closer at the variables themselves.

The Domain Size Trap

Why does acyclicity fail to guarantee tractability? The answer lies in the domain size of the state variables—the number of distinct values a variable can hold.

Consider a simple "fork" topology, where a single root variable influences multiple independent leaf variables. If the root variable is binary (can only take 2 values), the problem is tractable. But as Michael Katz et al. showed in Structural Patterns Beyond Forks: Extending the Complexity Boundaries of Classical Planning, the moment the root variable becomes ternary (3 values), optimal planning instantly becomes NP-complete. This sudden shift occurs because a ternary root variable has enough internal state capacity to encode the Shortest Common Superstring problem, allowing the leaf variables to become subtly entangled.

A similar phenomenon occurs in "chains," where variable $A$ influences $B$, which influences $C$, and so on. Omer Giménez demonstrated in Planning over Chain Causal Graphs for Variables with Domains of Size 5 Is NP-Hard that once variables in a chain can take on five or more values, the problem becomes NP-hard.

[Binary Domain]  ---> Tractable (Simple state transitions)
[Ternary/Domain 5] ---> NP-Hard (Variables can act as memory buffers/state machines)

The intuition here is that variables with larger domains can act as local memory buffers or state machines. They can pass complex, coordinated signals down a chain or across a fork, destroying the independence required for efficient problem decomposition.

Compiling Planning to Constraint Satisfaction

When we do restrict both the topology and the domain size, a powerful mechanism emerges: the ability to compile a dynamic planning problem into a static Constraint Satisfaction Problem (CSP).

In A Refined Understanding of Cost-optimal Planning with Polytree Causal Graphs, Christer Bäckström et al. analyzed polytrees—directed graphs whose underlying undirected structure is a tree. They proved that if a causal graph is a polytree with both bounded domain size and bounded graph depth, cost-optimal planning can be solved in polynomial time.

Why does this combination work?

  1. Bounded Depth and Domain Size limit transitions: Because the domain size is small and the depth (the distance from the source nodes) is fixed, there is a strict mathematical limit on the maximum number of times any single variable can change its state in an optimal plan. A variable cannot flip back and forth indefinitely without its ancestors changing, and its ancestors have limited states.
  2. Unrolling into a Tree-CSP: Because the total number of state transitions for every variable is bounded by a constant, we no longer have to search through an infinite timeline of actions. Instead, we can "unroll" the planning problem into a finite, tree-structured network of choices.

Each node in this compiled tree represents the sequence of values a variable takes, and the edges represent the local preconditions required by actions. Because tree-structured CSPs are famously solvable in polynomial time using local consistency algorithms (like arc consistency or dynamic programming), the global planning problem can be solved entirely through efficient, localized operations. Remarkably, this tractability holds true regardless of the graph's in-degree—meaning a variable can have an unlimited number of parents without causing intractability, so long as the hierarchy remains shallow.

Bypassing the Plan Length Barrier with Macros

There is one final catch. Even if a planning problem has an acyclic causal graph and is structurally tractable, the length of the shortest valid plan can still be exponentially long relative to the size of the problem description (a classic example being the Tower of Hanoi). How can an algorithm run in polynomial time if it has to output an exponential number of actions?

The solution is to change how we represent the plan. In The Complexity of Planning Problems With Simple Causal Graphs, Omer Giménez et al. demonstrated that we can generate valid solutions in polynomial time by representing them succinctly as a system of macros—reusable, hierarchical sub-plans.

Because the causal graph dictates a strict one-way flow of dependencies, an algorithm can recursively compute the necessary sub-plans for child variables conditioned on the state transitions of their parents. As Anders Jonsson et al. detailed in their work on The Role of Macros in Tractable Planning, this allows a planner to compress an exponential sequence of steps into a polynomial-sized grammar of macros. The planner solves the problem efficiently not by writing out every step, but by discovering the structural recipe of the solution.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 38 papers
  2. Version 1 · 2026-10-04 · 31 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_planning_to_csp_reduction_de7ce92c,
  title = {planning-to-CSP reduction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/planning-to-csp-reduction/rdr_de7ce92c53dd4b59b5e32c40b50aeeb9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 2, frozen text):

@misc{lacuna_planning_to_csp_reduction_de7ce92c_v2,
  title = {planning-to-CSP reduction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/planning-to-csp-reduction/rdr_de7ce92c53dd4b59b5e32c40b50aeeb9/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake