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.

Authors

• Anders Jonsson

Keywords

No keywords are indexed for this paper.