The Role of Macros in Tractable Planning over Causal Graphs

Anders JonssonIJCAI 2007 · OpenReview

Abstract

The complexity of existing planners is bounded by the length of the resulting plan, a fact that limits planning to domains with relatively short solutions. We present a novel planning algorithm that uses the causal graph of a domain to decompose it into subproblems and stores subproblem plans in memory as macros. In many domains, the resulting plan can be expressed using relatively few macros, making it possible to generate exponential length plans in polynomial time. We show that our algorithm is complete, and that there exist special cases for which it is optimal and polynomial. Experimental results demonstrate the potential of using macros to solve planning domains with long solution plans.

Introduction

In automated planning, computational complexity is traditionally tied to the length of the solution plan. Standard search-based planners struggle with "deep" problems where the required sequence of actions grows exponentially with the number of variables. This paper addresses this "plan length barrier" by focusing on domains characterized by unary operators and acyclic causal graphs. While determining plan existence in such domains is polynomial, generating the actual plan remains challenging due to the potential for astronomical plan lengths.

Methodology: The MACROPLANNER Algorithm

The proposed algorithm, MACROPLANNER, leverages a "divide and conquer" strategy driven by the domain's causal structure. The process begins with Causal Graph Analysis, where state variables and their dependencies are mapped. A critical step is the transitive reduction of this graph, which simplifies the hierarchy by removing redundant dependency edges.

Transitive reduction of a causal graph simplifies the dependency hierarchy.

Following this, the algorithm performs a Bottom-Up Decomposition based on a topological sort of the variables. Instead of re-solving recurring sub-tasks, MACROPLANNER employs Dynamic Programming to store partial plans as reusable macros. When navigating the state space of a subproblem via Dijkstra’s algorithm, the planner retrieves these pre-computed macros to satisfy conditions on parent variables. This approach allows the representation of exponential-length plans using a polynomial number of macros.

Experimental Evaluation

The algorithm was tested on benchmarks requiring exceptionally long plans, most notably the Tower of Hanoi (ToH) and a modified GRIPPER domain.

In the Tower of Hanoi, a solution for $n$ discs requires $2^n - 1$ moves. While a standard planner would fail to solve large instances within a reasonable timeframe, MACROPLANNER solved the 60-disc version in just 701 milliseconds. Despite the resulting plan containing over $10^{18}$ steps, the algorithm represented this sequence using only 177 macros.

Performance results for the Tower of Hanoi domain showing exponential plan length handled in polynomial time.

Similarly, in the GRIPPER domain—where a robot must transport 1,000 balls through a maze of nearly 1,000 rooms—the algorithm generated plans in approximately 2.9 seconds. It achieved this by recognizing that the navigation macro through the maze could be generated once and reused for every ball.

Discussion and Limitations

MACROPLANNER demonstrates that plan compression via macros can make previously intractable problems solvable. However, the current approach is limited to domains with unary operators and acyclic causal graphs. Future work aims to extend these techniques to non-unary operators and domains with circular dependencies, potentially by using approximation methods to break cycles in the causal graph. Additionally, refining macro generation to prune unused sub-plans could further optimize memory usage.

Summary updated

Abstract

The complexity of existing planners is bounded by the length of the resulting plan, a fact that limits planning to domains with relatively short solutions. We present a novel planning algorithm that uses the causal graph of a domain to decompose it into subproblems and stores subproblem plans in memory as macros. In many domains, the resulting plan can be expressed using relatively few macros, making it possible to generate exponential length plans in polynomial time. We show that our algorithm is complete, and that there exist special cases for which it is optimal and polynomial. Experimental results demonstrate the potential of using macros to solve planning domains with long solution plans.
BibTeX
@inproceedings{jonsson2007role,
  author = {Anders Jonsson},
  title = {{The Role of Macros in Tractable Planning over Causal Graphs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
  url = {https://openreview.net/forum?id=HkVOqmzd-B},
}
Figure