AIPS'00 Planning Competition: The Fifth International Conference on Artificial Intelligence Planning and Scheduling Systems

Article excerpt

* The planning competition has become a regular part of the biennial Artificial Intelligence Planning and Scheduling (AIPS) conferences. AIPS'98 featured the very first competition, and for AIPS'00, we built on this foundation to run the second competition. The 2000 competition featured a much larger group of participants and a wide variety of different approaches to planning. Some of these approaches were refinements of known techniques, and others were quite different from anything that had been tried before. Besides the dramatic increase in participation, the 2000 competition demonstrated that planning technology has taken a giant leap forward in performance since 1998. The 2000 competition featured planning systems that were orders of magnitude faster than the planners of just two years prior. This article presents an overview of the competition and reviews the main results.

The Fifth International Conference on Artificial Intelligence Planning and Scheduling (AIPS'00) was held in April 2000. AlPS is a biennial event, and in 1998, it featured its first planning competition, organized by Drew McDermott.1 The competition proved to be a successful and interesting addition to the conference, and it was decided to make the competition a regular feature of AIPS. I was asked to organize the competition for the 2000 conference, and in this article, I describe the results of this competition.

First, I briefly describe the manner in which the competition was structured along with a discussion of some of the various trade-offs involved in its structure. This discussion will be of greatest interest to those in other areas who might be considering developing similar competitions. Second, I present a description of the problem domains used in the competition. Finally, I summarize the results of the competition. Besides the summary presented here, all the raw data generated during the competition are available online. The hope is that these data can be further analyzed by researchers to provide additional insights into planner performance.

The Competitors

Fifteen different teams participated in the 2000 competition. The participants are listed in table 1. The systems themselves were quite diverse in design, and as explained later, they fell into two different tracks: (1) fully automated planners and (2) hand-tailored planners that could take as input additional domainspecific information. More information about many of these systems appears in the subsequent articles. Here, I provide a short summary of the approaches used.2

Heuristically guided forward-chaining planners: Plans are searched for by chaining forward from the initial state, guided by domain-independent heuristic estimates of the distance to the goal. Systems using this approach include FF; GRT; HsP2; and, to some extent, STAN.

Binary decision diagram (BDD)-based planners: These planners utilize BDDs, a representation originally developed in the verification literature, to compactly represent a set of states in the search space. Systems using this technique include MIPS, PROPPLAN, and BDDPLAN.

Regression-progression planners: SYSTEM R uses a formally correct version of the original regression-progression algorithm of STRIPS.

GRAPHPLAN-based planners: IPP and, to some extent, STAN base their planners on GRAPHPLAN.3

SAT-based planners: BLACKBOX operates by converting a planning problem to a satisfiability problem and then applies sAT-solver technology.

Petri net planners: TOKENPLAN uses a novel approach that uses colored Petri nets.

Hierarchical task network (HTN) planners: SHOP is an HTN planner that uses a novel left-to-right plan-elaboration scheme.

Plan rewriting: PBR takes the output of a simple, low-quality planner and rewrites the plan to produce a better plan.

Temporal logic search control: TALPLANNER uses the TLPLAN approach to planning,4 where additional domain-specific control is specified using a temporal logic. …