7.1 Coordinated Planning Experiments

In this section, we describe experiments that evaluate the use of summary information in coordinating a group of evacuation transports that must together retrieve evacuees from a number of locations with constraints on the routes. In comparing the EMTF and CFTF search techniques described in Section 5.2 against conventional HTN approaches, the experiments show that reasoning about summary information finds optimally coordinated plans much more quickly than prior HTN techniques.

We compare different techniques for ordering the expansion of subplans of both $and$ and $or$ plans to direct the decomposition of plan hierarchies in the search for optimal solutions. These expansion techniques are the $expand$ (for $and$ subplans) and $select$ (for $or$ subplans) operators of the algorithm described in Section 5.1.

We compare EMTF's expansion of $and$ plans to the ExCon heuristic and to a random selection heuristic. The ExCon heuristic [Tsuneto, Hendler, Nau, 1998] first selects plans that can achieve an external precondition, or if there are no such plans, it selects one that threatens the external precondition. In the case that there are neither achieving or threatening plans, it chooses randomly. Note that EMTF will additionally choose to expand plans with only threatened external preconditions but has no preference as to whether the plan achieves, threatens, or is threatened. For the expansion of $or$ plans, we compare CFTF to a depth-first (DFS) and a random heuristic.

We also compare the combination of CFTF and EMTF to an FAF (``fewest alternatives first'') heuristic and to the combination of DFS and ExCon. The FAF heuristic does not employ summary information but rather chooses to expand $and$ and select $or$ plans that have the fewest subplans [Currie, Tate, 1991,Tsuneto, Hendler, Nau, 1997]. Since no summary information is used, threats are only resolved at primitive levels. While it has been shown that the FAF heuristic can be effectively used by an HTN planner [Tsuneto, Hendler, Nau, 1997], the combination of DFS and ExCon has been shown to make great improvements over FAF in a domain with more task interactions [Tsuneto, Hendler, Nau, 1998]. We show in one such domain that the CFTF and EMTF heuristics can together outperform combinations of FAF, DFS, and ExCon.

The problems were generated for an evacuation domain where transports are responsible for visiting certain locations along restricted routes to pick up evacuees and bring them back to safety points. Transports are allowed to be at the same location at the same time, but the coordinator must ensure that transports avoid collisions along the single lane routes. In addition, in order to avoid the risk of oncoming danger (from a typhoon or enemy attack), the transports must accomplish their goals as quickly as possible.

Figure 20: Evacuation problem

Suppose there are two transports, $t1$ and $t2$, located at safety points $s0$ and $s3$ respectively, and they must visit the locations 0, 1, and 2 and 2, 3, and 4 respectively and bring evacuees back to safe locations as shown in Figure 20. Because of overlap in the locations they must visit, the coordinator must synchronize their actions in order to avoid collision. The coordinator's goal network includes two unordered tasks, one for each transport to $evacuate$ the locations for which it is responsible. As shown in Figure 21, the high-level task for $t1$ ($evacuate$) decomposes into a primitive action of moving to location 0 on the ring and an abstract plan to traverse the ring ($make\ rounds$). $t1$ can travel in one direction around the ring without switching directions, or it can switch directions once. $t1$ can then either go clockwise or counterclockwise and, if switching, can switch directions at any location ($first\ route$) and travel to the farthest location it needs to visit from where it switched ($second\ route$). Once it has visited all the locations, it continues around until it reaches the first safety point in its path ($go\ back$ and $goto\ safe\ loc$). The $no\ move$ plan is for the case where $t1$ is already at location 0. The task for $t2$ can be refined similarly.

Figure 21: The plan hierarchy for transport $t1$

Suppose the coordinator gathers summary information for the plan hierarchy and attempts to resolve conflicts. Looking just at the summary information one level from the top, the coordinator can determine that if $t1$ finishes evacuating before $t2$ even begins, then there will be no conflicts since the external conditions of $t1$'s $evacuate$ plan are that none of the routes are being traversed. This solution has a makespan (total completion time) of 16 steps. The optimal solution is a plan of duration seven where $t1$ moves clockwise until it reaches location $s3$, and $t2$ starts out clockwise, switches directions at location 4, and then winds up at $s0$. For this solution $t1$ waits at location 2 for one time step to avoid a collision on the route from location 2 to location 3.

Figure 22: Comparing EMTF to random expansion in searching for optimal solutions

We generated problems with four, six, eight, and twelve locations; with two, three and four transports; and with no, some, and complete overlap in the locations the transports visit. Performance was measured as the number of search states expanded to find the optimal solution or (if the compared heuristics did not both find the optimal solution) as the number of states each expanded to find solutions of highest common quality within memory and time bounds. We chose this instead of CPU time as the measure of performance in order to avoid fairness issues with respect to implementation details of the various approaches.

Figure 23: Comparing EMTF to ExCon in searching for optimal solutions

The scatter plot in Figure 22 shows the relative performance of the combination of CFTF and EMTF (CFTF-EMTF) and the combination of CFTF and random $and$ expansion (CFTF-Rand). We chose scatterplots to compare results because they capture the results more simply than trying to plot against three dimensions of problem size/complexity. Note that for all scatter plots, the axes are scaled logarithmically. Points above the diagonal line mean that EMTF (x-axis) is performing better than Rand (y-axis) because fewer search states were required to find the optimal solution. While performance is similar for most problems, there are a few cases where CFTF-EMTF outperformed CFTF-Rand by an order of magnitude or more. Figure 23 exhibits a similar effect for CFTF-EMTF and CFTF-ExCon. Note that runs were terminated after the expansion of 3,500 search states. Data points at 3,500 (the ones forming a horizontal line at the top) indicate that no solution was found within memory and time constraints. While performance is similar for most problems, there are four points along the top where CFTF-ExCon finds no solution. Thus, although EMTF does not greatly improve performance for many problems, it rarely performs much worse, and almost always avoids getting stuck in fruitless areas of the search space compared to the ExCon and the random heuristic. This is to be expected since EMTF focuses on resolving conflicts among the most problematic plans first and avoids spending a lot of time reasoning about the details of less problematic plans.

Figure 24: Comparing CFTF and DFS in searching for optimal solutions

The combination of CFTF with EMTF, pruning inconsistent abstract plan spaces, and branch-and-bound pruning of more costly abstract plan spaces (all described in Section 5.2) much more dramatically outperforms techniques that do not reason at abstract levels. Figure 24 shows DFS-Rand expanding between one and three orders of magnitude more states than CFTF-Rand. Runs were terminated after the expansion of 25,000 search states. Data points at 25,000 (forming the horizontal line at the top) indicate that no solution was found within memory and time constraints. By avoiding search spaces with greater numbers conflicts, CFTF finds optimal or near-optimal solutions much more quickly. In Figures 25 and 26, CFTF-EMTF outperforms FAF-FAF (FAF for both selecting $and$ and $or$ plans) and DFS-ExCon by one to two orders of magnitude for most problems. These last two comparisons especially emphasize the importance of abstract reasoning for finding optimal solutions. Within a maximum of 3,500 expanded search states (the lowest cutoff point in the experiments), CFTF-EMTF and CFTF-Rand found optimal solutions for 13 of the 24 problems. CFTF-ExCon and FAF-FAF found 12; and DFS-ExCon and DFS-Rand only found three.

Figure 25: Comparing the use of summary information to the FAF heuristic

Figure 26: Comparing the use of summary information to the algorithm using external conditions

A surprising result is that FAF-FAF performs much better than DFS-ExCon for the evacuation problems contrary to the results given by tsuneto:98 that show DFS-ExCon dominating for problems with more goal interactions. We believe that this result was not reproduced here because those experiments involved hierarchies with no $or$ plans. The experiments show that the selection of $or$ subplans more greatly affects performance than the order of $and$ subplans to expand. So, we believe DFS-ExCon performed worse than FAF-FAF not because FAF is better at choosing $and$ subplans than ExCon but because FAF is stronger at selecting $or$ subplans than DFS.

However, the main point of this section is that each of the heuristic combinations that use summary information to find solutions and prune the search space at abstract levels (CFTF-EMTF, CFTF-ExCon, and CFTF-Rand) greatly outperform all of those that do not (FAF-FAF, DFS-ExCon, and DFS-Rand) when searching for optimal solutions.