The FF Planning System: Fast Plan Generation Through Heuristic Search

Abstract

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.

References in corpus (3)

• The Automatic Inference of State Invariants in TIM
• On Reasonable and Forced Goal Orderings and their Use in an Agenda-Driven Planning Algorithm
• Efficient Implementation of the Plan Graph in STAN

Cited by in corpus (10)

• Planning Through Stochastic Local Search and Temporal Action Graphs in LPG
• The 3rd International Planning Competition: Results and Analysis
• The Metric-FF Planning System: Translating "Ignoring Delete Lists" to Numeric State Variables
• VHPOP: Versatile Heuristic Partial Order Planner
• SAPA: A Multi-objective Metric Temporal Planner
• Planning Graph Heuristics for Belief Space Search
• A Critical Assessment of Benchmark Comparison in Planning
• The GRT Planning System: Backward Heuristic Construction in Forward State-Space Planning
• Cost Based Satisficing Search Considered Harmful
• Reasoning and Planning with Sensing Actions, Incomplete Information, and Static Causal Laws using Answer Set Programming