Even though the planner or coordinator can use the search techniques described in the Section 5.2 to prune the search space, just being able to find solutions at multiple levels of abstraction can reduce the computation as much as doubly exponentially. In this section, we give an example of this and then analyze the complexity of planning and scheduling to characterize this cost reduction and the conditions under which it occurs.
An agent that interleaves execution with planning/coordination often must limit the total computation and execution cost required to achieve its goals. The planning algorithm described in Section 5.1 is able to search for solutions at different levels of abstraction. For the manufacturing example, our implementation of a centralized coordinator uses this algorithm to find in 1.9 CPU seconds a solution at the top level of the agents' plans as shown in Figure 13b. If we define the cost of execution as the makespan (completion time) of the coordinated plan, the cost of this solution is 210 where the makespan of the production manager's plan is 90, the facilities manager's is 90, and the inventory manager's is 30. For the solution in Figure 13c, the coordinator required 667 CPU seconds, and the makespan of the coordinated plan is 170. Another solution is found at an intermediate level of abstraction, taking 69 CPU seconds and having a makespan of 180. So, with a little more effort, the algorithm expanded the hierarchy to an intermediate level where the cost of the solution was reduced by 30. Thus, overall cost can be reduced by coordinating at intermediate levels.
For this problem, coordinating at higher levels of abstraction is less costly because there are fewer plan steps. But, even though there are fewer plans at higher levels, those plans may have greater numbers of summary conditions to reason about because they are collected from the much greater set of plans below. Here we argue that even in the worst case where the number of summary conditions per plan increases exponentially up the hierarchy, finding solutions at abstract levels is expected to be exponentially cheaper than at lower levels. We first analyze the complexity of the summarization algorithm to help the reader understand how the summary conditions can collect in greater sets at higher levels.