Although researchers have studied planning since the early days of AI, recent developments have revolutionized the field. Furthermore, work on propositional planning is closely related to the algorithms used in the autonomous controller for the National Aeronautics and Space Administration (NASA) Deep Space One spacecraft, launched in October 1998. As a result, our understanding of interleaved planning and execution has advanced as well as the speed with which we can solve classical planning problems. The goal of this survey is to explain these recent advances and suggest new directions for research. Because this article requires minimal AI background (for example, simple logic and basic search algorithms), it's suitable for a wide audience, but my treatment is not exhaustive because I don't have the space to discuss every active topic of planning research.

In 1998, the international planning community was invited to take part in the first planning competition, hosted by the Artificial Intelligence Planning Systems Conference, to provide a new impetus for empirical evaluation and direct comparison of automatic domain-independent planning systems. This article describes the systems that competed in the event, examines the results, and considers some of the implications for the future of the field. Competitors were invited to come and compete on a collection of domains and associated problems, sight unseen, using whatever planning technology they wanted. (Anderson and Weld 1998). Another important problem was anticipating the demands of the competition domains.

The way work load is shared between these stages depends on the particular approach in use. The reader unfamiliar with Petri nets needs only know the following: They are made of places, transitions, and tokens. A place can be seen as a token holder. When it contains one or more tokens, it is said to be marked. Transitions allow tokens to circulate from place to place.

This planning graph structure is then fed to a heuristic extractor module that is capable of extracting a variety of effective and admissible heuristics, based on our recent theory (Nguyen and Kambhampati 2000). This heuristic, along with the problem specification, and the set of ground actions in the final action level of the planning graph structure are fed to a regression state search planner. To guide a regression search in the state space, a heuristic function needs to evaluate the cost of some set S of subgoals, comprising a regression state from the initial state, in terms of the number of actions required to achieve S from the initial state. This heuristic approximates the cost of a set S as the length of a "relaxed plan" for supporting S, ignoring all the mutex relations, plus the penalty for ignoring these negative interac-88 AI MAGAZINE Yochan is the planning group directed by Subbarao Kambhampati at Arizona State University.

I comment on the PDDL 2.1 language and its use in the planning competition, focusing on the choices made for accommodating time and concurrency. I also discuss some methodological issues that have to do with the move toward more expressive planning languages and the balance needed in planning research between semantics and computation.

We describe and evaluate the algorithmic techniques that are used in the FF planning system. Like the HSP system, FF relies on forward state space search, using a heuristic that estimates goal distances by ignoring delete lists. Unlike HSP's heuristic, our method does not assume facts to be independent. We introduce a novel search strategy that combines hill-climbing with systematic search, and we show how other powerful heuristic information can be extracted and used to prune the search space. FF was the most successful automatic planner at the recent AIPS-2000 planning competition. We review the results of the competition, give data for other benchmark domains, and investigate the reasons for the runtime performance of FF compared to HSP.

This paper reviews the connections between Graphplan's planning-graph and the dynamic constraint satisfaction problem and motivates the need for adapting CSP search techniques to the Graphplan algorithm. It then describes how explanation based learning, dependency directed backtracking, dynamic variable ordering, forward checking, sticky values and random-restart search strategies can be adapted to Graphplan. Empirical results are provided to demonstrate that these augmentations improve Graphplan's performance significantly (up to 1000x speedups) on several benchmark problems. Special attention is paid to the explanation-based learning and dependency directed backtracking techniques as they are empirically found to be most useful in improving the performance of Graphplan.

STAN is a Graphplan-based planner, so-called because it uses a variety of STate ANalysis techniques to enhance its performance. STAN competed in the AIPS-98 planning competition where it compared well with the other competitors in terms of speed, finding solutions fastest to many of the problems posed. Although the domain analysis techniques STAN exploits are an important factor in its overall performance, we believe that the speed at which STAN solved the competition problems is largely due to the implementation of its plan graph. The implementation is based on two insights: that many of the graph construction operations can be implemented as bit-level logical operations on bit vectors, and that the graph should not be explicitly constructed beyond the fix point. This paper describes the implementation of STAN's plan graph and provides experimental results which demonstrate the circumstances under which advantages can be obtained from using this implementation.

The Graphplan algorithm for generating optimal make-span plans containing parallel sets of actions remains one of the most effective ways to generate such plans. However, despite enhancements on a range of fronts, the approach is currently dominated in terms of speed, by state space planners that employ distance-based heuristics to quickly generate serial plans. We report on a family of strategies that employ available memory to construct a search trace so as to learn from various aspects of Graphplan's iterative search episodes in order to expedite search in subsequent episodes. The planning approaches can be partitioned into two classes according to the type and extent of search experience captured in the trace. The planners using the more aggressive tracing method are able to avoid much of Graphplan's redundant search effort, while planners in the second class trade off this aspect in favor of a much higher degree of freedom than Graphplan in traversing the space of'states' generated during regression search on the planning graph. The tactic favored by the second approach, exploiting the search trace to transform the depth-first, IDA* nature of Graphplan's search into an iterative state space view, is shown to be the more powerful. We demonstrate that distance-based, state space heuristics can be adapted to informed traversal of the search trace used by the second class of planners and develop an augmentation targeted specifically at planning graph search. Guided by such a heuristic, the step-optimal version of the planner in this class clearly dominates even a highly enhanced version of Graphplan. By adopting beam search on the search trace we then show that virtually optimal parallel plans can be generated at speeds quite competitive with a modern heuristic state space planner.

In 1998, the international planning community was invited to take part in the first planning competition, hosted by the Artificial Intelligence Planning Systems Conference, to provide a new impetus for empirical evaluation and direct comparison of automatic domain-independent planning systems. This article describes the systems that competed in the event, examines the results, and considers some of the implications for the future of the field.