6.1 Complexity of Summarization

Consider a hierarchy with $n$ total plans, $b$ subplans for each non-primitive plan, and depth $d$, starting with zero at the root, as shown in Figure 18. The procedure for deriving summary conditions works by basically propagating the conditions from the primitives up the hierarchy to the most abstract plans. Because the conditions of any non-primitive plan depend only on those of its immediate subplans, deriving summary conditions can be done quickly if the number of subplans is not large. The derivation algorithm mainly involves checking for achieve, clobber, and undo interactions among subplans for all possible total orderings of the subplans (as described in Section 3.4). Checking for one of these relations for one summary condition of one subplan is $O(bs)$ for $b$ subplans, each with $s$ summary conditions (as discussed in Section 3.3). Since there are $O(bs)$ conditions that must be checked in the set of subplans, deriving the summary conditions of one plan from its subplans is $O(b^2s^2)$.

However, the maximum number of summary conditions for a subplan grows exponentially up the hierarchy since, in the worst case, no summary conditions merge during summarization. This happens when the conditions of each subplan are on completely different propositions/variables than those of any sibling subplan. In this case, a separate summary condition will be generated for each summary condition of each subplan. If the children share conditions on the same variable, this information is collapsed into a single summary condition in the parent plan.

As shown in the third column of the table in Figure 18, a plan at the lowest level $d$ has $s=c$ summary conditions derived from its $c$ pre-, in-, and postconditions. A plan at level $d-1$ derives $c$ summary conditions from its own conditions and $c$ from each of its $b$ subplans giving $c+bc$ summary conditions, or $s=O(bc)$. So, in this worst case $s=O(b^{d-i}c)$ for a plan at level $i$ in a hierarchy for which each plan has $c$ (non-summary) conditions. Thus, the complexity of summarizing a plan at level $i$ (with subplans at level $i+1$) is $O(b^2b^{2(d-(i+1))}c^2)=O(b^{2(d-i)}c^2)$. There are $b^i$ plans at level $i$ (second column in the figure), so the complexity of summarizing the set of plans at level $i$ is $O(b^ib^{2(d-i)}c^2)=O(b^{2d-i}c^2)$ as shown in the fourth column in the figure. Thus, the complexity of summarizing the entire hierarchy of plans would be $O(\sum_{i=0}^{d-1} b^i b^{2(d-i)}c^2)$. In this summation $i=0$ dominates, so the complexity can be simplified to $O(b^{2d}c^2)$. If there are $n=O(b^d)$ plans in the hierarchy, we can write this simply as $O(n^2c^2)$, which is the square of the size of the hierarchy.

In the best case where all conditions are on the same variable, each plan will have $c$ summary conditions. Thus, the complexity for summarizing the hierarchy will be $O(\sum_{i=0}^{d-1} b^i b^2c^2)$, which simplifies to $O(b^{d+1}c^2) = O(nbc^2)$. In any case, the summarization of conditions is tractable, and as we discussed in Section 3.5.2, the summarization of resources is also tractable.