Discussion

McDermott (2000) finds the absence of POCL planners at the first planning competition in 1998 striking, as such planners had been dominating planning research just a few years earlier. ``It seems doubtful that the arguments in [POCL planners'] favor were all wrong, and it would be interesting to see partial-order planners compete in future competitions'', McDermott writes. After two competitions without POCL planners, we believe that VHPOP's performance at IPC3 demonstrates that POCL planning--at least with ground actions--can be competitive with CSP-based and heuristic state space planning. VHPOP also shows that temporal POCL planning can be made practical by using the same heuristic techniques that have been developed for classical planning. The idea of using the POCL paradigm for temporal planning is not new and goes back at least to Vere's DEVISER (Vere, 1983), but we are the first to demonstrate the effectiveness of temporal POCL planning on a larger set of benchmark problems.

We hope that the success of VHPOP at IPC3 will inspire a renewed interest in plan space planning, and we have made the source code for VHPOP, written in C++, available to the research community in an online appendix so that others can build on our effort.⁷

While VHPOP performed well above our expectations at IPC3, we see several ways in which we can further improve the planner. Speed, as mentioned in Section 5, is the principal weakness of VHPOP. The code for the reachability analysis is not satisfactory, as it currently generates ground action instances before performing any reachability analysis. This often leads to many ground action instances being generated that do not have preconditions with finite heuristic cost (according to the additive heuristic). We believe that VHPOP could profit from code for reachability analysis in well-established planning systems such as FF. We could also improve speed by better scheduling different flaw selection strategies. We would like to see statistical studies, similar to that of Howe et al. (1999), linking domain and problem features to the performance of various flaw selection strategies.

We have so far only considered using different flaw selection strategies. However, running multiple instances of VHPOP using different plan selection heuristics could be equally interesting. We have, for example, noticed that using the additive heuristic without accounting for reuse helps us solve two more problems in the Satellite domain. It would also be interesting to have the FF heuristic implemented in VHPOP and see how well it performs in a plan space planner, possibly using local search techniques instead of A^*. It is not likely, however, that the results on local search topology for the FF heuristic in state space (Hoffmann, 2001) carry over to plan space. While many of the benchmark planning domains contain actions whose effects can be undone by other actions, the plan operators causing transitions in the search space of a plan space planner are different from the actions defined for a planning domain, and the effects of a plan space operator are generally irreversible. We would likely need to add transformational plan operators that can undo linking and ordering decisions. Incidentally, VHPOP started out as a project for adding transformational plan operators to UCPOP, but we got side-tracked by the need for better search control, and our research on transformational POCL planning was suspended. With the recent improvements in search control for POCL planners, it may be worthwhile to once again consider adding transformational plan operators.

In addition to considering different search control heuristics, we could also have instances of VHPOP working with lifted actions instead of ground actions. Recent improvements to the code have significantly reduced the overhead for maintaining binding constraints, making planning with lifted actions look considerably more favorable than was reported in earlier work (Younes & Simmons, 2002). Planning with lifted actions could be beneficial for problems with a high branching factor in the search space due to a large number of objects.

We would also like to see support for numeric effects and preconditions in future versions of VHPOP. This would make VHPOP fully compatible with PDDL2.1. We have also mentioned the need for plan ranking heuristics better tailored for temporal planning, so that VHPOP's performance in terms of plan execution time for domains with durative actions can approach the performance of the best temporal planners at IPC3.