We compare ASPEN using aggregation with and without summarization for
three variations of the rectangular field domain. When using summary information, ASPEN
also uses the EMTF and CFTF decomposition heuristics. One domain
excludes the communications channel resource (*no channel*); one
excludes the path capacity restrictions (*channel only*); and the
other excludes neither (*mixed*). Since all of
the movement tasks reserve the channel resource, greater improvement
in performance is expected when using summary information according to
the complexity analyses in Section 6.3. This is
because constraints on the channel resource collapse in the summary
information derived at higher levels such that any task in a hierarchy
only has one constraint on the resource. When ASPEN does not use
summary information, the hierarchies must be fully expanded,
and the number of constraints on the channel resource is equivalent to
the number of leaf movement tasks.

However, tasks within a rover's hierarchy rarely place constraints on
the other path variables more than once, so the *no channel*
domain corresponds to the worst case where summarization collapses no
constraints. Here the complexity of moving an abstract task is the
same without summary information for the fully
expanded hierarchy as it is with summary information
for a partially expanded hierarchy.

Figure 29 (top) exhibits two distributions of
problems for the *no channel* domain. In most of the cases
(points above the x=y diagonal), ASPEN with summary information finds a
solution quickly at some level of abstraction. However, in many
cases, summary information performs notably worse (points below the x=y diagonal). We discovered that for these problems finding a solution
requires the planner to dig deeply into the rovers' hierarchies, and
once it decomposes the hierarchies to the level of the solution, the
difference in the additional time to find a solution between the two
approaches is negligible (unless the use of summary information found
a solution at a slightly higher level of abstraction more quickly).
Thus, the time spent reasoning about summary information at higher
levels incurred unnecessary overhead.

But this is the worst case in the analysis in Section 6.3 where we showed that summary information had no advantage even if it found abstract solutions. So, why did summary information perform better when abstract solutions were found? It was not because of the CFTF heuristic since branch choices result in small differences in numbers of conflicts. It actually results from the stochastic nature of ASPEN's iterative repair. Although moving the most abstract tasks using aggregation without summary information would have enabled ASPEN to find solutions more quickly for fully expanded hierarchies, ASPEN must sometimes move lower level tasks independently of their parents and siblings in order to resolve conflicts at lower levels. The problem is that ASPEN has no heuristic to tell it at what level it needs to move activities, and it sometimes chooses to move activities at detailed levels unnecessarily. This search at lower levels is where the search space explodes. Using summary information to search at higher levels below lower levels of abstraction better protects ASPEN from unnecessary search.

Figure 29 (middle) shows significant improvement for
summary information in the *mixed* domain compared to the
*no channel* domain. Adding the channel resource rarely affects
the use of summary information because the collapse in summary
constraints incurs insignificant additional complexity. However,
the channel resource makes the scheduling task noticeably more
difficult for ASPEN when not using summary information. In the
*channel only* domain (Figure 29 bottom),
summary information finds solutions at the abstract level almost
immediately, but the problems are still complicated when ASPEN does
not use summary information. These results support the complexity
analysis in
Section 6.3
that argues that summary information exponentially improves
performance when tasks within the same hierarchy have constraints over
the same resource and when solutions are found at some level of
abstraction.

Because summary information is generated offline, the domain modeler knows up front whether or not constraints are significantly collapsed. Thus, an obvious approach to avoiding cases where reasoning about summary information causes unnecessary overhead is to fully expand at the start of scheduling the hierarchies of tasks where summary information does not collapse. Because the complexity of moving a task hierarchy is the same in this case whether fully expanded or not, ASPEN does not waste time by duplicating its efforts at each level of expansion before reaching the level at which it finds a solution. Evaluating this approach is a subject of future work.

Earlier we mentioned that the CFTF heuristic is not effective for the rectangular field problems. This is because the choice among different paths to a science location usually does not make a significant difference in the number of conflicts encountered--if the rovers cross paths, all path choices usually still lead to conflict. For the set of corridor problems, path choices always lead down a different corridor to get to the target location, so there is usually a path that avoids a conflict and a path that causes one depending on the path choices of the other rovers. When ASPEN uses the CFTF heuristic, the performance dominates that of when it chooses decompositions randomly for all but two problems (Figure 30). This reflects experiments for the coordination algorithm in Section 7 that show that CFTF is crucial for reducing the search time required to find solutions.

In order to evaluate the EMTF heuristic for iterative repair planning,
we compared it to a simple alternative. This alternative strategy
(that we refer to as *level decomposition*) is to interleave
repair with decomposition as separate steps. Step 1) The planner
repairs the current schedule until the number of conflicts cannot be
reduced. Step 2) It decomposes all abstract tasks one level down and
returns to Step 1. By only spending enough time at a particular level
of expansion that appears effective, the planner attempts to find the
highest decomposition level where solutions exist without wasting time
at any level. The time spent searching for a solution at any level of
expansion is controlled by the rate at which abstract tasks are
decomposed. The EMTF heuristic is implemented as a repair method
to give priority to detailing plans that are involved in more conflicts.

Figure 31 shows the performance of EMTF vs. level
decomposition for different rates of decomposition for three problems
from the set with varied performance. The plotted points are averages over ten runs
for each problem. Depending on the choice of rate of decomposition
(the probability that a task will decompose when a conflict is
encountered), performance varies significantly. However, the best
decomposition rate can vary from problem to problem making it
potentially difficult for the domain expert to choose. For example,
for problem A in the figure, all tested decomposition rates for EMTF
outperformed the use of level decomposition. At the same time, for
problem C using either decomposition technique did not make a
significant difference while for problem B choosing the rate for EMTF
made a big difference in whether to use EMTF or level decomposition.
Although these examples show varied performance, results for most
other problems showed that a decomposition rate of around 15%
was most successful. This suggests that a domain modeler may be able
to choose a generally successful decomposition rate by running
performance experiments for a set of example problems.^{8}

We have demonstrated many of the results of the complexity analyses in Section 6. Scheduling with summary information gains speedups (over aggregation) by resolving conflicts at appropriate levels of abstraction. When summary information collapses, the scheduler gains exponential speedups. In addition, the CFTF heuristic enables exponential speedups when decomposition choices have varying numbers of conflicts.