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 $n$ plans each with $s$ summary conditions is $O(n^2s^2)$ as shown in Section 4.1 for the $MightSomeWay$ algorithm. For a hierarchy expanded to level $i$, there are $n=O(b^i)$ plans at the frontier of expansion, and each plan has $s=O(b^{d-i}c)$ 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 $i$ is $O(b^{2i}(b^{d-i}c)^2)=O(b^{2d}c^2)$. Notice that $i$ 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 $s=c$ summary conditions, so the complexity of checking a candidate solution is $O(b^{2i}c^2)$, a factor of $O(b^{2(d-i)})$faster than the worst case.

Figure 18: Complexity of threat identification and resolution at abstract levels

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.⁵ Thus, as shown in the last column of the table in Figure 18, the search space is $O(k^{b^i})$ for $b^i$ plans at level $i$ and constant $k$.⁶ 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 $O(k^{b^i} b^{2d}c^2)$ when summary information does not merge at all and $O(k^{b^i} b^{2i}c^2)$ when summary information fully merges. The complexity of resolving conflicts at the primitive level is $O(k^{b^d} b^{2d}c^2)$, so resolving conflicts at an abstract level speeds search doubly exponentially, a factor of $O(k^{b^d-b^i})$ even when summary information does not merge during summarization. Now, if it completely merges, the speedup is a factor of $O(k^{b^d-b^i} b^{2(d-i)})$.

There are only $and$ plans in this analysis. In the case that there are $or$ 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 $O(k^{(b-p)^d})$ when a fraction of $p/b$ branches can be pruned. Thus, pruning can also create an exponential reduction in search.