
## 8.2 Sapa In The 2002 International Planning Competition

We entered an implementation of Sapa, using several of the techniques discussed in this paper, in the recent International Planning Competition. The specific techniques used in the competition version of Sapa are infinite look-ahead termination of cost propagation (Section 3.3), resource adjustment
(Section 5.2), and greedy post-processing (Section 6). In the competition, we focused solely on the metric/temporal domains.

The sophisticated support for multi-objective search provided by Sapa was not fully exploited in the competition, since action cost is not part of the standard PDDL2.1 language used in the competition.14 The competition did evaluate the quality of solution plans both in terms of number of actions and in terms of the overall makespan. Given this state of affairs, we assumed unit cost for all actions, and ran Sapa with α = 1, thus making the search sensitive only to the action costs. Infinitelookahead was used for cost propagation. This strategy biased Sapa to produce low cost plans (in terms of number of actions). Although the search was not sensitive to makespan optimization, the greedy post processing of p.c. plans to o.c. plans improved the makespan of the solutions enough to make Sapa one of the best planners in terms of the overall quality of solutions produced.15 The competition results were collected and distributed by the IPC3's organizers and can be found at the competition website (Fox & Long, 2002). Detailed descriptions of domains used in the competition are also available at the same place. The temporal planning domains in the competition came in two sets, one containing two domains, Satellite and Rovers (adapted from NASA
domains), and the other containing three domains: Depots, *DriverLogistics* and *Zeno Travel*. In the planning competition, each domain had multiple versions–depending on whether or not the actions had durations and whether actions use continuous resources. Sapa participated in the highest levels of PDDL2.1 (in terms of the complexity of temporal and metric constraints) for the five domains listed above.

Figures 17 and 18 show that five planners (Sapa, LPG, MIPS, TP4, and TPSYS) submitted results for the *timed* setting and only three (Sapa, MIPS, and TP4) were able to handle the *complex* setting of the Satellite domain. In the *timed* setting, action durations depend on the setting of instruments aboard a particular satellite and the direction it needs to turn to. The *"complex"* setting is further complicated by the fact that each satellite has a different capacity limitation so that it can only store a certain amount of image data. Goals involve taking images of different planets and stars located at different coordinate directions. To achieve the goals, the satellite equipped with the right set of instruments should turn to the right direction, calibrate and take the image.

For the *timed* setting of this Satellite domain, Figure 17 shows that among the five planners, Sapa, LPG and MIPS were able to solve 19 of 20 problems while TP4 and TPSYS were able to solve 2 and 3 problems respectively. For quality comparison, LPG with the *quality* setting was able to return solutions with the best quality, Sapa was slightly better than LPG with the *speed* setting and was much better than MIPS. LPG with the *speed* setting is generally the fastest, followed by MIPS and then Sapa and LPG with the *quality* setting. For the *complex* setting, Figure 18 shows that, among the three planners, Sapa was able to solve the most problems (16), and generated plans of higher quality than MIPS. TP4 produced the highest quality solutions, but was able to solve only