Introduction
In automated planning, the objective is to find a sequence of actions that transitions a system from an initial state to a goal state. While generally PSPACE-complete or undecidable, researchers seek "tractable fragments"—specific problem structures that allow for optimal solutions in polynomial time. This paper identifies a new such fragment: planning problems where the causal graph is a polytree (a graph that is a tree when edge directions are ignored) with bounded domain sizes and diameters.
Methodology: The POLYTREE Algorithm
The authors introduce a "defoliation" algorithm termed POLYTREE, which simplifies complex planning tasks through a novel technique called variable isomorphism.
- Variable Isomorphism: The algorithm identifies "isomorphic" leaf variables in the causal graph—those that behave identically regarding transitions, costs, and parent interactions.
- Compression and Merging: These identical variables are merged into a single representative, reducing dimensionality without altering the optimal solution's cost.
- Product Operation and Recursion: The algorithm collapses branches by taking the "product" of leaves and their parents. This process repeats, "shaving" the polytree until a minimal, manageable problem remains.
- Final Optimization: Once reduced to a few variables, Dijkstra’s algorithm is employed to find the optimal path.
The Complexity Landscape
The primary theoretical contribution is the classification of planning complexity based on two parameters: domain size ($k$) and graph diameter ($d$). The paper proves that finding a cost-optimal plan (COPG) is in P (polynomial time) when both $k$ and $d$ are fixed constants.
As shown in the table above, the problem becomes NP-hard if either the domain size or the diameter is allowed to grow freely. This result fills a significant gap in planning theory, establishing the precise boundaries of tractability for polytree-structured problems.
Key Insights and Theoretical Implications
- Isomorphism as Compression: The formalization of variable isomorphism suggests that many planning problems contain redundant structures that can be compressed to significantly reduce state space.
- The Bottleneck of Diameter: The research highlights that diameter (the longest path in the undirected graph) is a critical constraint. Even simple path graphs become NP-hard if the diameter is unrestricted.
- Bounded Change: A key proof (Theorem 3) demonstrates that in these restricted classes, each variable only changes its value a constant number of times in an optimal plan, keeping the search space polynomial.
Limitations and Future Outlook
While theoretically polynomial, the algorithm's exponents are currently high, making it more of a "proof of concept" than a practical tool for immediate deployment. Future work may focus on:
- Indegree Constraints: Restricting the number of variables influencing a single node could potentially reduce complexity to $O(||\Pi||^4)$.
- Structural Expansion: Extending isomorphism definitions to more complex sub-structures beyond simple leaves could lead to more powerful reduction techniques.
- Heuristic Insights: These findings may explain the empirical success of "merge-and-shrink" heuristics, which likely exploit similar structural redundancies.
Summary updated