The Fast Downward Planning System
By Malte Helmert. 2006
2,109 citations recorded by the source corpus.
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. However, unlike other PDDL planning systems, Fast Downward does not use the propositional PDDL representation of a planning task directly. Instead, the input is first translated into an alternative representation called multivalued planning tasks, which makes many of the implicit constraints of a propositional planning task explicit. Exploiting this alternative representation, Fast Downward uses hierarchical decompositions of planning tasks for computing its heuristic function, called the causal graph heuristic, which is very different from traditional HSP-like heuristics based on ignoring negative interactions of operators. In this article, we give a full account of Fast Downward's approach to solving multivalued planning tasks. We extend our earlier discussion of the causal graph heuristic to tasks involving axioms and conditional effects and present some novel techniques for search control that are used within Fast Downward's best-first search algorithm: preferred operators transfer the idea of helpful actions from local search to global best-first search, deferred evaluation of heuristic functions mitigates the negative effect of large branching factors on search performance, and multiheuristic best-first search combines several heuristic evaluation functions within a single search algorithm in an orthogonal way. We also describe efficient data structures for fast state expansion (successor generators and axiom evaluators) and present a new non-heuristic search algorithm called focused iterative-broadening search, which utilizes the information encoded in causal graphs in a novel way. Fast Downward has proven remarkably successful: It won the "classical" (i. e., propositional, non-optimising) track of the 4th International Planning Competition at ICAPS 2004, following in the footsteps of planners such as FF and LPG. Our experiments show that it also performs very well on the benchmarks of the earlier planning competitions and provide some insights about the usefulness of the new search enhancements.
Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, LLM Agents & Tool Use, Optimization & Training
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Sergey Levine
- Pieter Abbeel
- Chelsea Finn
- Yoshua Bengio
- Dieter Fox
- Mohit Bansal
- Ruslan Salakhutdinov
- Yejin Choi
In Computer Vision and Pattern Recognition
- Luc Van Gool
- Jitendra Malik
- Li Fei-Fei
- Trevor Darrell
- Dacheng Tao
- Xiaogang Wang
- Bernt Schiele
- Cordelia Schmid
In LLM Agents & Tool Use
- Malte Helmert
- Dieter Fox
- Hector Geffner
- Jörg Hoffmann
- Subbarao Kambhampati
- Sarath Sreedharan
- Silvia Richter
- Marcel Steinmetz
In Optimization & Training
- Jörg Hoffmann
- Subbarao Kambhampati
- Sarath Sreedharan
- Tomas Lozano-Perez
- Leslie Pack Kaelbling
- Silvia Richter
- Marcel Steinmetz
- Matthias Westphal
Citations in the corpus
- ALFWorld: Aligning Text and Embodied Environments for Interactive Learning (2020, methodology): “Planner TextWorld Engine uses Fast Downward (Helmert, 2006), a domain-independent classical planning system to maintain and update the current state of the game.”
- Plan Explanations as Model Reconciliation: Moving Beyond Explanation as Soliloquy (2017, methodology): “Our explanation generation system (as previewed in the Fetch domain) integrates calls to Fast-Downward [ Helmert, 2006 ] for planning, VAL [ Howey et al. , 2004 ] for plan validation, and pyperplan [ Alkhazraji et al. , 2016 ] for parsing.”
- Combined task and motion planning through an extensible planner-independent interface layer (2014, methodology): “2011 version of FD [7] in seq-opt-lmcut mode, which makes it a cost-optimal planner.”
- A review of generalized planning (2019, background): “Nowadays Fast-Downward evaluates derived predicates with quantified variables implementing the marking algorithm [37].”
- The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks (2010, methodology): “In addition, both search algorithms use three types of search enhancements inherited from Fast Downward (Helmert, 2006; Richter & Helmert, 2009).”
- Concise finite-domain representations for PDDL planning tasks (2009, methodology): “The algorithm has been implemented as part of the Fast Downward planner [29] and used by a number of other planning algorithms [3,27,31,48,49].”
- Learning Generalized Reactive Policies using Deep Neural Networks (2017, neutral): “To see why this is correct, note that for any ( s, t ) ∈ [ − a, a ] × [ − a, a ] there is exactly one polynomial inside the summands that does not have either of the terms ( i + u y ) or ( j + u x ) appearing in its factorization.”
- Coming up With Good Excuses: What to do When no Plan Can be Found (2010, methodology): “In order to analyze the relations between fluent symbols, we apply the notion of causal graphs and domain transition graphs (Helmert 2006) to the abstract domain description.”
- Large Language Models as Commonsense Knowledge for Large-Scale Task Planning (2023, background): “In the early stage, many studies [1, 15, 14, 12] focused on task planning in a discrete state space with deterministic transitions.”
- Robot task planning and explanation in open and uncertain worlds (2015, methodology): “At the beginning of each planning process we create a plain PDDL planning task that can be used by Fast Downward [18] as follows:”
- Leveraging Pre-trained Large Language Models to Construct and Utilize World Models for Model-based Task Planning (2023, background): “In order to achieve the goal conditions specified in i , a planner, which can be either an LLM or an external planner [16, 12, 17], needs to come up with a sequence of high-level skills that the agent can execute.”
- Planning as Model Checking in Hybrid Domains (2014, background): “Hence, we represent discrete variables with a variant of their domain-transition graphs (Helmert 2006).”
- Robot task planning and explanation in open and uncertain worlds (2017, methodology): “With these concepts, we can now illustrate how the switching planner in our system works. the beginning of each planning process we create a plain PDDL planning task that can be used by Fast Downward [18] as follows:”
- Integrated Task and Motion Planning (2020, background): “Furthermore, the AI planning community has developed a repertoire of very effective, domain-independent search algorithms that exploit this type of action representation (16, 17, 18).”
- Towards Clause-Learning State Space Search: Learning to Recognize Dead-Ends (2016, positive): “Our implementation is in FD (Helmert 2006).”