Complexity analyses and experiments showing potential doubly-exponential speedups in refinement and local search planning/scheduling using summary information.

Our algorithms demonstrate that exploiting summary information to guide hierarchical planning and scheduling can achieve exponential speedups, and resolving interdependencies at abstract levels can improve the performance of plan coordination algorithms doubly exponentially. While others have shown that abstraction can exponentially reduce search space size [Korf, 1987, Knoblock, 1991] when subproblem independence properties hold, we show that our techniques lead to exponential improvements if any of these broader conditions hold for the problem:

• solutions can be found at abstract levels;
• the amount of summary information is less at higher levels than at lower levels; or
• choices of decompositions lead to varying numbers of plan threats.

When none of these conditions hold, we show that generating and using summary information provides no benefit and can increase computation and communication overhead. Thus, care must be taken when deciding to use summary information, though it has proven to be extremely worthwhile in the types of problem domains we have examined, an example of which we next describe.