next up previous
Next: 7.3 Communication Overhead Up: 7.2 Scheduling Experiments Previous: 7.2.1 Problem Domains

7.2.2 Empirical Results for Mars Rovers

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.

Figure 29: Plots for the a) no channel, b) mixed, and c) channel only domains

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 $or$ 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.

Figure 30: Performance using the CFTF heuristic

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: Performance of EMTF vs. level-decomposition heuristics

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 $or$ decomposition choices have varying numbers of conflicts.

next up previous
Next: 7.3 Communication Overhead Up: 7.2 Scheduling Experiments Previous: 7.2.1 Problem Domains
Bradley Clement 2006-12-29