6.2 Complexity of Finding Abstract Solutions

In order to resolve conflicts (and potentially arrive at a solution)
at a particular level of expansion of the hierarchy, the coordination
algorithm checks for threats between the plans under particular
ordering constraints at that level. Checking for threats involves
finding clobber relations among the plans and their summary
conditions. The complexity of finding threats among plans each
with summary conditions is as shown in Section
4.1 for the algorithm. For a hierarchy expanded to level , there are
plans at the frontier of expansion, and each plan has
summary conditions. So, as shown in the fifth column
of the table in Figure 18, the worst case complexity of checking for
threats for one synchronization of a set of plans at level is
. Notice that drops out of the
formula, meaning that the complexity of checking a candidate solution
is *independent of the depth level*. In the best case where summary conditions fully merge, each plan has summary conditions, so the complexity of checking a candidate solution is , a factor of faster than the worst case.

However, the algorithm may check many synchronizations at a particular
level before finding a solution or exhausting the search space. In
fact this search complexity grows exponentially with the number of
plans.^{5} Thus, as shown in the last column of the table in Figure
18, the search space is
for plans at level and constant .^{6} Thus, the search space grows doubly
exponentially down the hierarchy based on the number of plan steps.

In our refinement coordination and planning algorithm, the conflict detection is a basic operation that is done for resolving conflicts. So, to also include the effect of the size of conditions (in addition to plan steps) on the complexity of the planning/coordination algorithm, we must multiply by the complexity to check threats. Thus, the complexity is when summary information does not merge at all and when summary information fully merges. The complexity of resolving conflicts at the primitive level is , so resolving conflicts at an abstract level speeds search doubly exponentially, a factor of even when summary information does not merge during summarization. Now, if it completely merges, the speedup is a factor of .

There are only plans in this analysis. In the case that there are plans, being able to prune branches at higher levels based on summary information will also greatly improve the search despite the overhead of deriving and using summary conditions. Pruning effectively reduces the branching factor since the branch is eliminated before investigating its details. Thus, the complexity based on the number of plan steps becomes when a fraction of branches can be pruned. Thus, pruning can also create an exponential reduction in search.