Abstract
Factored planning offers a "divide and conquer" strategy for complex AI planning problems, yet it has historically lacked a rigorous theoretical foundation. This paper addresses this gap by identifying the causal graph and its tree-width as the primary determinants of planning complexity. We introduce the Local Iterative Deepening (LID) algorithm, which decomposes problems into local factors and stitches them together via a Constraint Satisfaction Problem (CSP). Our analysis proves that this approach is exponentially more efficient than standard non-factored planning under specific structural conditions, providing a clear roadmap for when factoring is advantageous.
Introduction
In automated planning, an agent must determine a sequence of actions to transition from an initial state to a goal. As the number of variables increases—common in logistics or large-scale robotics—the search space grows exponentially. Factored planning attempts to mitigate this "state-space explosion" by decomposing the global problem into smaller, manageable sub-problems. However, two critical questions have remained largely unanswered: how to optimally decompose a domain and when factoring provides a genuine performance benefit over monolithic search.
The LID Framework and Causal Graphs
The authors propose a framework based on the SAS+ formalism, using multi-valued variables to represent the world state. Central to their approach is the Local Iterative Deepening (LID) algorithm. LID treats state variables (or clusters thereof) as individual factors and performs local searches based on "local depth" ($\delta$), which represents the number of times a variable changes its value.
The core of this decomposition is the causal graph. This directed graph captures the dependencies between variables, where an edge from one variable to another indicates that the former influences the transitions of the latter.
Compiling to SeqCSP
Once local plans are generated, they must be "stitched" together to ensure global consistency. The authors compile this coordination task into a Constraint Satisfaction Problem (CSP) called SeqCSP. The constraints in SeqCSP are derived directly from the edges of the causal graph, ensuring that the local transitions of one variable are compatible with the requirements of its neighbors in the graph.
By utilizing tree-decompositions of the causal graph, the authors also introduce LID-GF (Generalized Factoring). This method groups variables into larger factors to further minimize the complexity of the resulting CSP, particularly when the graph is not a simple tree.
Complexity and Key Insights
The paper establishes that the complexity of factored planning is governed by the tree-width ($w$) of the causal graph and the local depth ($\delta$). Specifically, the LID algorithm can solve a planning problem in $O(n(n\delta a)^{w\delta+\delta})$ time, where $n$ is the number of variables and $a$ is the maximum actions per variable.
Key theoretical takeaways include:
- Tree-width as a Litmus Test: Sparse causal graphs (low tree-width) are ideal for factoring. If your causal graph is dense, the coordination overhead of SeqCSP may outweigh the benefits of local search.
- Exponential Speedups: When the causal graph has a constant tree-width and plan lengths are relatively short, factored planning is shown to be exponentially faster than standard non-factored methods like Step-Optimal Planning (SOP).
- Refined Interaction Models: The authors prove their causal-graph-based approach is strictly more efficient than previous methods (like the "AE" approach) because the tree-width of the causal graph is always less than or equal to the tree-width of the interaction graphs used previously.
Conclusion
This work provides the first comprehensive theoretical "instruction manual" for factored planning. By linking planning complexity to the structural properties of the causal graph, it identifies the specific conditions under which "divide and conquer" strategies succeed. While the current focus is on worst-case complexity and local optimality, these results lay the groundwork for more efficient, structurally-aware planning algorithms in the future.
Summary updated