The FF Planning System: Fast Plan Generation Through Heuristic Search
By Jörg Hoffmann, Bernhard Nebel. 2011
2,435 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, LLM Agents & Tool Use
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
- Percy Liang
- Pieter Abbeel
- Luke S. Zettlemoyer
- Mohit Bansal
- Jianfeng Gao
- Yoshua Bengio
- Chelsea Finn
In Computer Vision and Pattern Recognition
- Luc Van Gool
- Trevor Darrell
- Li Fei-Fei
- Jitendra Malik
- Dacheng Tao
- Cordelia Schmid
- Kristen Grauman
- Xiaogang Wang
In LLM Agents & Tool Use
- Malte Helmert
- Dieter Fox
- Subbarao Kambhampati
- Sarath Sreedharan
- Silvia Richter
- Marcel Steinmetz
- Matthias Westphal
- Hector Geffner
Citations in the corpus
- ALFRED: A Benchmark for Interpreting Grounded Instructions for Everyday Tasks (2019, methodology): “These demonstrations are generated by a planner [23] using metadata not available to the agent at inference time.”
- Plan explicability and predictability for robot task planning (2015, background): “Here, we consider the FastForward (FF) planner with enforced hill climbing [14] (see Alg 1).”
- FF: The Fast-Forward Planning System (2001, background): “We remark that, in many of the domains with improved runtime performance, FF's estimates improve runtime across all our problem instancess reliably, but only by a small amount Hoomann & Nebel 2001.”
- 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).”
- Practical solution techniques for first-order MDPs (2009, background): “, 2007) (2006 version) is a deterministic replanner based on FF (Hoffmann and Nebel, 2001).”
- Robust planning with incomplete domain models (2017, methodology): “Comparing with baseline approaches: We also compare PISA with an approach in which the relaxed plans are extracted in the similar way used in the FF planner (Hoffmann and Nebel, 2001).”
- NovelGridworlds: A Benchmark Environment for Detecting and Adapting to Novelties in Open Worlds (2021, methodology): “MetricFF [4] planner is used to find a plan to solve the task.”
- The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks (2010, methodology): “In LAMA, Fast Downward’s causal graph heuristic is replaced with a variant of the FF heuristic (Hoffmann & Nebel, 2001) and heuristic estimates derived from landmarks.”
- Approximate Policy Iteration with a Policy Language Bias (2003, background): “2) Each learned policy is a domain-specific planner that is fast and empirically compares well to the state-of-the-art domain-independent pla ner FF [13].”
- Concise finite-domain representations for PDDL planning tasks (2009, methodology): “This is not necessarily problematic – for example, a planning algorithm based on forward search, such as Hoffmann and Nebel’s FF [33], will never encounter any of the infeasible states, so there is no obvious advantage to the finite-domain representation.”
- Learning High-Level Planning from Text (2012, methodology): “for this evaluation, we employ the Metric-FF planner (Hoffmann and Nebel, 2001),4 as well as a textunaware variant of our model.”
- Forward-Chaining Partial-Order Planning (2010, background): “A side-effect of the use of a relaxed plan heuristic is the opportunity to extract helpful actions (Hoffmann and Nebel 2001).”
- Fast Detection of Unsolvable Planning Instances Using Local Consistency (2013, methodology): “New and efficient planners have entered the scene, for instance, FAST FORWARD (Hoffmann and Nebel 2001), FAST DOWNWARD (Helmert 2006b), LAMA (Richter and Westphal 2010), and planners based on compilation into SAT instances (Rintanen, Heljanko, and Niemelä 2006).”
- Towards Clause-Learning State Space Search: Learning to Recognize Dead-Ends (2016, methodology): “We break ties (i. e. order children in the DFS) using h FF (Hoffmann and Nebel 2001)), which helps a bit mainly on solvable instances.”
- Robot task planning using semantic maps (2008, methodology): “In order to test the use of semantics for improving task planning in large and/or complex scenarios we have performed a number of simulated experiments, using the Metric-FF planner [51] for generating both the semantic-level and the ground-level plans (recall section 5).”
- Landmarks, Critical Paths and Abstractions: What's the Difference Anyway? (2009, methodology): “, h [6], h [1], h [1], h [6], h [11], h [9] 2.”
- Approximate Policy Iteration with a Policy Language Bias: Solving Relational Markov Decision Processes (2011, methodology): “In Fern, Yoon, and Givan (2003), we showed that by bootstrapping API with the domain-independent heuristic of the planner FF (Hoffmann & Nebel, 2001), API was able to uncover good policies for the blocks world, simplified logistics world (no planes), and stochastic variants.”
- IkeaBot: An autonomous multi-robot coordinated furniture assembly system (2013, methodology): “At present, there is no At present, the planner converts ABPL into PDDL and executes the Fast-Forward solver.”
- The 3rd International Planning Competition: Results and Analysis (2003, background): “B.1.1 FF ff has been an extremely successful and influential planner since 2000 ( Homann & Nebel, 2000 ).”