\documentclass[11pt,twoside]{article}
\usepackage{jair}
\usepackage{theapa}
%\usepackage{times}
%\usepackage{a4wide}
\usepackage[pdftex]{graphicx}
\newcommand{\pddl}{\mbox{\sc pddl2.1}}
\newcommand{\lang}{\mbox{\sc pddl2.1}}
\newcommand{\strips}{\mbox{\sc strips}}
\newcommand{\complex}{\mbox{\sc complex}}
\newcommand{\numeric}{\mbox{\sc numeric}}
\newcommand{\simpletime}{\mbox{\sc simpletime}}
\newcommand{\hardnumeric}{\mbox{\sc hardnumeric}}
\newcommand{\lpg}{\mbox{\sc lpg}}
\newcommand{\ff}{\mbox{\sc ff}}
\newcommand{\shop}{\mbox{\sc shop}}
\newcommand{\htn}{\mbox{\sc htn}}
\newcommand{\htns}{\mbox{{\sc htn}s}}
\newcommand{\tp}{\mbox{\sc tp}}
\newcommand{\ttime}{\mbox{\sc time}}
\newcommand{\sapa}{\mbox{\sc sapa}}
\newcommand{\mips}{\mbox{\sc mips}}
\newcommand{\tlplan}{\mbox{\sc tlplan}}
\newcommand{\talplanner}{\mbox{\sc talplanner}}
\newcommand{\simplanner}{\mbox{\sc simplanner}}
\newcommand{\stella}{\mbox{\sc stella}}
\newcommand{\semsyn}{\mbox{\sc semsyn}}
\newcommand{\vhpop}{\mbox{\sc vhpop}}
\newcommand{\adl}{\mbox{\sc adl}}
\newcommand{\zeno}{\mbox{\sc zeno}}
\newcommand{\code}[1]{\mbox{\small {\tt{#1}}}}
\newcommand{\comp}{\mbox{$3^{rd}$ {\sc ipc}}}

\jairheading{20}{2003}{1-59}{3/03}{12/03}
\ShortHeadings{The 3rd International Planning Competition}
{Long \& Fox}
%\firstpageno{25}

\title{The 3rd International Planning Competition: Results and Analysis}
\author{\name Derek Long \email derek.long@cis.strath.ac.uk\\
\name Maria Fox \email maria.fox@cis.strath.ac.uk\\
\addr Department of Computer and Information Sciences\\University of Strathclyde, Glasgow, UK}

\begin{document}
\maketitle

\begin{abstract}
This paper reports the outcome of the third in the series of biennial international planning competitions, held in association with the International Conference on AI Planning and Scheduling (AIPS) in 2002. In addition to describing the domains, the planners and the objectives of the competition, the paper includes analysis of the results. The results are analysed from several perspectives, in order to address the questions of comparative performance between planners, comparative difficulty of domains, the degree of agreement between planners about the relative difficulty of individual problem instances and the question of how well planners scale relative to one another over increasingly difficult problems. The paper addresses these questions through statistical analysis of the raw results of the competition, in order to determine which results can be considered to be adequately supported by the data. The paper concludes with a discussion of some challenges for the future of the competition series.
\end{abstract}

\section{Introduction}

Beginning in 1998 the international planning community has held a biennial event to support the direct comparison of planning systems on a changing collection of benchmark planning problems. The benefits of this series of events have been significant: over five years, planning systems have been developed that are capable of solving large and complex problems, using richly expressive domain models and meeting advanced demands on the structure and quality of solutions. The competition series has inspired many advances in the planning research community as well as an increasingly empirical methodology and a growing interest in the application of planners to real problems. 

In this paper we describe the structure, objectives and outcomes of the third competition, which took place in Toulouse in 2002. The competition was colocated with the AI Planning and Scheduling (AIPS) conference. At that conference a brief report was presented of some of the results achieved by the participating planners. We begin by presenting an overview of the main results as presented at the conference, showing the number of problems attempted and solved by each planner and identifying the competition prize-winners. As in previous years the competition resulted in the collection of a large data set comprising data points for several different domains. A certain comparative understanding can be obtained by examining the data for the individual domains, but conclusions drawn on this basis cannot be generalised across domains. One of the goals of this paper is to try to reveal some insights that cross the boundaries of the domains and allow some general questions to be answered. These include: which planners reveal the most consistent, stable performance across domains? What benefit is obtained by exploiting hand-coded control knowledge? Is there any general agreement over what makes a planning problem hard? Are particular planning approaches best suited to particular kinds of problem domains? 

The accepted scientific methodology for addressing such questions is to frame precise hypotheses {\em prior} to the collection of the data sets in order to control for any extraneous variables that might distort the reality with respect to these questions. To date this has not been the practice of the planning community with respect to the competitions. In the third competition we proceeded, as in previous years, by collecting data prior to detailed consideration of the specific questions we wished to answer. The community has not yet agreed that the primary role of the competition is to provide a carefully crafted platform for the scientific investigation of planners: indeed, its main roles so far have been to motivate researchers in the field, to identify new research goals and thereby push forward the research horizons, and to publicise progress to the wider community. However, because competitions have winners there is a natural tendancy to draw conclusions from the competition data sets about the state of the art. If these conclusions are not scientifically supported they can be misleading and even erroneous. Therefore there is an argument for trying to combine the two objectives, although admittedly there is a tension between them that might make it difficult to combine them successfully.

Because of the way in which the planning competitions are currently conducted, the analyses we describe in this paper are post hoc. We conducted all of our analyses on the data collected during the competition period: we did not run any further experiments after the competition because the participants felt that it was important that the data they submitted during the competition should comprise the evidence on which they were judged. We have identified a number of analyses which we think provide interesting information to the planning community and, in the following sections, we explore each theme in as rigorous a way as possible within the constraints of the data we have at our disposal. It has been difficult to work with a fixed data set that was collected without precise experimental questions in mind, and we were unable to test many of the hypotheses that occurred to us during our analyses because the data was inappropriate or incomplete. However, despite the limitations of the data set we believe we have been able to pose and answer some important questions about the comparative performances revealed in the competition. We phrase the objectives of our analyses in terms of null and alternative hyptheses because this is the standard approach when applying statistical tests. Our approach was partly inspired by the earlier work of Howe and Dahlman~\citeyear{howe}. Their work raised the standard to which evaluation of planners should be done and compels the planning community to decide whether future planning competitions should be conducted in a way that supports the goals of scientific investigation of progress in the field.

The rest of this paper is organised as follows. We begin by discussing the context~--- the competition series itself and the general form of the third competition, including the domains, the competitors and the specific challenges raised. We then briefly summarise the results of the competition before embarking on a detailed post hoc analysis of the competition results. This analysis investigates the relative performances of the planners, the relative difficulties of the problem sets used and the relative scaling behaviours of the competitors across domains and levels. We provide an appendix in which we present summaries of the competing planners and details of the domains used.



\section{The International Planning Competition Series}

The first event was held in conjunction with the fourth international Artificial Intelligence Planning and Scheduling conference (AIPS'98). It was organised by Drew McDermott, together with a committee of senior members of the research community~\cite{drewaimag}. The event took some time to organise, with evolving agreement on the form of the event, the kinds of planning systems that should be compared, the basis of comparison and so on. The final event became a direct comparison of 5 \strips-based planners, with two of the planners also attempting an extended \adl-based language~\cite{drewaimag,aimag98}. The systems included three Graphplan-based systems, one forward heuristic search system and one planning-as-satisfiability {\sc sat}solver planner. A very important outcome of the first competition was the adoption of {\sc pddl}~\cite{pddl} as a common representation language for planning.

Although the opportunity was offered for competitors to hand-code control knowledge for their planners, in fact all of the planners were fully-automated and ran on the problem instances without any priming. The entire event was staged at the conference over a period of some four days, involving intensive sessions of generating and checking solutions and attempting to evaluate the results. One idea that was tried, but that turned out to be problematic in practice, was to score the planners' performances using a function that attempted to take into account the time taken to generate a plan, the length of the plan and the relative performance of all of the competitors on the problems. For example, a planner that produced a plan faster than all of its competitors would be rewarded based on how much faster it was than the average for the problem. This attempt to score planners using a one-dimensional measure proved difficult, with counter-intuitive results in certain cases. In the end it was abandoned in favour of two dimensions: length of plan and time taken to produce it. This decision indicates that, even for only five systems and a relatively small set of problems, it is impossible to make unequivocal decisions about which system is best. Nevertheless, the community can (and did) learn much from the data that is gathered, offering a variety of interpretations of the data, but ultimately being inspired to improve on it in every way possible.

In the second competition, chaired by Fahiem Bacchus, 17 planners competed. The increase in participation and the ambitions for larger scale testing required that the event be spread over a much longer period. In fact, testing was spread over a couple of months, with only one final test being carried out at the conference site (AIPS'00 in Breckenridge). In the second competition there was a more formal split between systems, with a small number using hand-coded control knowledge and others being fully-automated. There was also a split between \strips\ and \adl\ capable systems. The larger number of competitors included a wider range of approaches: as well as Graphplan-based systems, forward heuristic search and a {\sc sat}solver, there were several planners based on model-checking approaches using {\sc bdd}s, and one using planning-by-rewriting. Again, it proved difficult to compare planners unequivocally, but several important observations could be made: the advantages of hand-coded control rules in most domains could be seen clearly (as would be expected), although there remained an important question about the difficulty of generating and writing the rules. Of the fully-automated planners, the forward heuristic search approach proved to be particularly successful, dominating performance in most domains. Pure Graphplan-based planning seemed to have reached its zenith between the first two competitions and no longer appeared competitive.

The third competition (and most recent at the time of writing) was held in association with AIPS'02 at Toulouse. Fourteen planners participated. The primary objective of the competition was to help to push forward research into temporal and resource-intensive planning. Extensions were made to {\sc pddl} to support the modelling of temporal and numeric domain features. These resulted in the {\sc pddl2.1} language~\cite{foxl}. The extensive changes to \pddl\ and the ambitious objectives of the competition help to account for the fact that fewer people participated in 2002 than in 2000. Once again, the real testing and gathering of data took place over the two months prior to the conference. Although initial results were presented at the conference, no detailed analysis took place at the conference itself. The rest of this paper examines the objectives of the third competition, the results and some future challenges for the series.

\section{Overview: The Third International Planning Competition}

As organisers of the Third International Planning Competition we chose to address several new challenges that we believe are important to the ambitions of the planning community: the management of problems with metric constraints on numerically valued variables, temporal planning (including managing concurrency and scheduling of activities) and the construction of plans subject to specified optimisation criteria other than a simple count of the numbers of steps.

Setting these goals has obvious implications for the potential competitors in terms of extended expressive power and additional problem-solving required to manage the extensions. In order to control the extent to which competitors would be required to handle all of these extensions successfully, we constructed variants, or {\em levels}, of all of the domains used in the competition. For most of the domains we included a \strips\ level, a \numeric\ level (using \strips\ and metric variables only), a \simpletime\ level in which actions have duration but there are no other metric values in the domain and a full temporal level, \ttime, using durative actions with durations determined by the context of their usage (so duration depends on the parameter values and not only on the action name). The \simpletime\ and \ttime\ levels did not involve numeric resources other than time. To address this combination we introduced some additional domain variants, as we discuss below. Each of the four levels corresponds to a particular degree of expressive power of \lang, and there are different challenges posed by the versions of each domain at each level.

A secondary goal was to assess the relative effort of generating and encoding control rules for planners. Unfortunately, we failed to find any way to usefully quantify this effort. We discuss this question further in the following sections.


\subsection{Problem Domains}

The problem domains selected for the competitions have been, or have become, benchmark domains used by much of the community for empirical evaluation. The domains that have been used have often been chosen to probe some specific detail of performance. This has sometimes meant that the domains are not representative of general features of planning and are inappropriate for use in more widespread testing. A description of the domains used in all of the competitions so far can be found in Appendix~\ref{app-probs}. 

In the third competition, eight families of domains were used, broadly divided into transportation domains (Depots, DriverLog and ZenoTravel), applications-inspired domains (Rovers and Satellite) and a small collection of others (Settlers, FreeCell and UM-Translog-2). 

We briefly summarise the collection here and describe them in more detail in Appendix~\ref{app-probs}.
\begin{itemize}
\item {\bf Depots} This domain combines the transportation style problem of Logistics with the well-known Blocks domain. The Logistics domain exhibits a high degree of parallelism, since separate vehicles can be utilised concurrently. In contrast, the Blocks domain is characterised by significant goal interaction. Our intention in doing this was to discover whether the successes of planners in each of these domains separately could be brought together when the problems were combined.
\item {\bf DriverLog} This problem involves transportation, but with the twist that the vehicles must be supplied with a driver before they can move.
\item {\bf Zeno-travel} Another transportation problem, inspired by a domain used in testing the \zeno\ planner developed by Pemberthy and Weld~\citeyear{zeno}, in which people must embark onto planes, fly between locations and then debark, with planes consuming fuel at different rates according to speed of travel. 
\item {\bf Satellite} This domain was inspired by the problem of scheduling satellite observations. The problems involve satellites collecting and storing data using different instruments to observe a selection of targets. 
\item {\bf Rovers} This domain was motivated by the 2003 Mars Exploration Rover (MER) missions and the planned 2009 Mars Science Laboratory (MSL) mission. The objective is to use a collection of mobile rovers to traverse between waypoints on the planet, carrying out a variety of data-collection missions and transmitting data back to a lander. The problem includes constraints on the visibility of the lander from various locations and on the ability of individual rovers to traverse between particular pairs of waypoints.
\item {\bf Settlers} This domain revolves around the management of resources, measured using metric valued variables. Products must be manufactured from raw materials and used in the manufacture or transportation of further materials. New raw materials can be generated by mining or gathering. The objective is to construct a variety of structures at various specified locations. 
\item {\bf UM-Translog-2} This domain is a \lang\ encoding of a new variant of the UM-Translog~\cite{umtranslog} domain. This was generated for us by Dan Wu of the University of Maryland. This is essentially a transportation domain, but one that is significantly more complex than previous transportation benchmarks. In fact, this domain was introduced late in the competition and very little data was collected. It is therefore not discussed further in this paper.
\end{itemize}

We also reused the Freecell domain from the second competition. This domain presented a serious challenge to participants in 2000 and we were interested to see whether planning technology had surpassed this challenge in the intervening two years. Although the domain produced some interesting data we did not attempt to precisely measure the extent to which the 2002 performance surpassed that of 2000.

Each domain (other than Settlers, Freecell and UM-Translog-2) was presented to the competitors for at least the four different levels previously identified: {\sc strips}, \numeric\, \simpletime\ and \ttime. The problems presented at each of these levels comprised distinct {\em tracks} and the competitors were able to choose in which tracks they wished to compete. In addition to the four main tracks we also included two additional tracks, intended to explore particular ideas. These tracks did not necessitate the use of additional expressive power but simply allowed existing expressiveness to be combined to produce interesting planning challenges. For example, the \hardnumeric\ track consisted of problems from the Satellite domain that had very few logical goals. Plans were evaluated by a metric based on amount of data recorded rather than by determining whether a specified logical goal had been achieved. The challenge was for planners to respond to the plan metric and include actions that would acquire data. The \complex\ track consisted of problems that combined temporal and numeric features. The challenge was to reason about resource consumption in parallel with managing temporal constraints. In total, we defveloped 26 domains, with 20 problem instances in each domain (a few, unintentially, ended up with 16 or 22 instances). In most domains there were an additional 20 instances of large problems intended for the hand-coded planners. In total there were nearly 1000 problem instances to be solved, of which about half were intended primarily for the fully-automated planners.

\subsection{The Competitors}

The population of competing planning systems has changed over the three competitions. Few systems have competed more than once and no system has appeared in all three competitions. In part, this is a reflection of the speed of development of planning systems, revealing the extent to which the technology of 1998 has been surpassed by that of 2002. It is also a reflection of the growing interest in the series, which has encouraged more competitors to come forward, and of the work involved in taking part which has discouraged previous competitors from repeating their effort. Entering the competition involves more than generating interesting and efficient approaches to solving the planning problem: it demands the ability to construct a system that can respond robustly and reliably when confronted with previously unseen challenges, including domains that were not amongst those used in development of the system. It must be sufficiently well-engineered that its performance is not dominated by poor programming rather than by the real algorithmic effort of solving the problem (careless choice of a data structure can undermine the opportunity to show off a clever new planning algorithm). For systems that use hand-coded rules to guide the planning system there is an additional demand: the time required to read and understand domains sufficiently to construct sensible control knowledge and to then encode and test the knowledge to achieve good performance. The time-table for the testing was relatively compressed (the entire problem suite was generated and delivered to the competitors over a two month period and testing was carried out remotely on a single machine), so those using hand-coded controls were forced to find time to analyse the domains, hypothesise and test rules in intense sessions.

Details of the competing systems can be found in Appendix~\ref{app-planners}. To summarise, many of the fully-automated planners use relaxed plan heuristics to guide a heuristic search. {\sc lpg}~\cite{lpg} uses local search to improve candidate plan structures formed in a Graphplan-style plan graph. Several planners (\mips, \ff\ and \sapa) also extend the use of relaxed plan heuristics to include numeric features. \vhpop\ is a partial-order planner, demonstrating that partial-order planning can be competitive with the more recently fashionable heuristic forward state-space search planners. For various reasons, several planners generated only small collections of results, which are disregarded in the analysis. 

A few competitors used more than one version of their planner, or more than one parameter setting. We did not attempt to enforce the use of unique versions, but left it to competitors to ensure that we were informed where variations were used. Multiple versions of \ff, \mips\ and \lpg\ were used. \ff\ submitted almost all data for a version optimised for speed performance. A small subset of data was submitted for a version optimised for quality, showing that there are alternative criteria by which performance can be evaluated. In all of the analyses we report we have used the data generated by \ff\ optimised for speed exclusively. \mips\ also offered data in two variants, using slightly different parameter settings. In our analyses we use data for one variant (\mips) exclusively, except in the case of the Satellite {\sc hardnumeric} problems in which we used the data from the other variant (\mips.plain). \lpg\ submitted data in three versions: one based on earliest plan produced, one based on best plan produced over a longer time span and a third which represented a compromise between speed and quality. In fact, since all of the results for the version optimised for quality were generated within a few minutes at most, we chose to use this data exclusively in the analyses that follow. This should be borne in mind when reviewing the results for comparative speed performance of the planners. The performance of \lpg\ relies on certain parameter settings. In most cases, the parameters used for \lpg\ were automatically set, but in a few cases some parameters were set by hand. In their paper, appearing in this issue, Gerevini, Saetti and Serena~\citeyear{lpg} give new results of an experiment testing their planner with all parameters set automatically. In general they observe no significant difference in the performance of \lpg\ with respect to the data provided for the competition.

The three hand-coded planners that competed represent two alternative approaches to planning: forward state-space search using control rules to prune bad choices and promote good choices, and hierarchical task network (\htn) planning. 

\input{solved}
\input{extrabit}
\input{ResultsPaper/empirical}
\input{judgements}



\input{scalingstuff}



\input{respapconclusions}

\section*{Acknowledgements}

We would like to thank all the competitors in the 3rd International Planning Competition for contributing their time and enthusiasm to the event we report and for providing the data that has made this paper possible. We would also like to thank Adele Howe who has contributed invaluable advice, comments and huge support and made it possible for this paper to go far further than we could have hoped. We would like to thank David Smith for undertaking the unenviable task of coordinating and editing this special issue of the Journal of Artificial Intelligence Research and doing so with immense patience, good humour and generous support. Finally, we would like to thank Martha Pollack who first proposed the idea of publishing the assembled work in a special issue of the Journal of Artifical Intelligence Research. Her whole-hearted commitment to the project has been vital to its successful conclusion.

\include{appendix}
\include{appendix2}

\bibliographystyle{theapa}
\bibliography{pddlplusdoc}



\end{document}
