Technical Report No. 217 - Abstract

Malte Helmert
The Fast Downward Planning System

Fast Downward is a classical planning system based on heuristic search. It can deal with general deterministic planning problems encoded in the propositional fragment of PDDL2.2, including advanced features like ADL conditions and effects and derived predicates (axioms). Like other well-known planners such as HSP and FF, Fast Downward is a progression planner, searching the space of world states of a planning task in the forward direction. Unlike most other heuristic planners, whose state evaluations are based on ignoring negative interactions of operators, Fast Downward uses hierarchical decompositions of planning tasks for computing its heuristic function, which we call the causal graph heuristic. This approach has proven remarkably successful: Fast Downward won the "classical" (i.e., propositional, non-optimizing) track of the 4th International Planning Competition at ICAPS 2004, following in the footsteps of planners such as FF and LPG. This article provides a detailed overview of Fast Downward's architecture and the underlying algorithms. The technical part explains the three phases of the planner: During translation, the propositional input task is transformed into a representation with multi-valued state variables more amenable to hierarchical decomposition. During knowledge compilation, the crucial information of the translated planning task is compiled into a number of efficient data structures. Finally, during search, the causal graph heuristic is used in a best-first search framework to compute a solution plan. Some building blocks of the Fast Downward planning system have been presented in previous work. We extend these techniques originally tailored to STRIPS tasks to the full generality of propositional PDDL and present some genuinely new algorithms for fast operator instantiation (Horn exploration), search control preferred operators, multi-heuristic best-first search), and a new alternative search algorithm which uses the information encoded in the causal graph and domain transition graphs in a novel way (focused iterative-widening search). Our experimental data shows the merits of these techniques for the standard benchmark suite, comparing various configurations of Fast Downward to one another and to other efficient planning systems.