The FF Planning System: Fast Plan Generation Through Heuristic Search
This paper describes and evaluates the FF planning system, which relies on forward state space search using a heuristic that estimates goal distances by ignoring delete lists. Unlike HSP, FF does not assume facts to be independent. FF introduces a novel search strategy that combines hill-climbing with systematic search and employs pruning techniques to enhance efficiency. FF was the most successful automatic planner at the AIPS-2000 planning competition. The paper reviews the competition results, provides data for other benchmark domains, and investigates the reasons for FF's runtime performance compared to HSP.
FF's system architecture includes a base heuristic technique, a search algorithm, and pruning methods. The base heuristic technique, relaxed GRAPHPLAN, is derived from GRAPHPLAN applied to relaxed planning tasks. The search algorithm, enforced hill-climbing, combines local and systematic search. Pruning techniques include "helpful actions" and "added goal deletion," which are derived from the base heuristic method and used to prune the search space.
FF's performance is evaluated on a range of planning benchmark domains, demonstrating its ability to generate solutions quickly. The paper also discusses the limitations of FF and compares it with HSP, highlighting the effectiveness of the new algorithmic techniques in FF.The FF Planning System: Fast Plan Generation Through Heuristic Search
This paper describes and evaluates the FF planning system, which relies on forward state space search using a heuristic that estimates goal distances by ignoring delete lists. Unlike HSP, FF does not assume facts to be independent. FF introduces a novel search strategy that combines hill-climbing with systematic search and employs pruning techniques to enhance efficiency. FF was the most successful automatic planner at the AIPS-2000 planning competition. The paper reviews the competition results, provides data for other benchmark domains, and investigates the reasons for FF's runtime performance compared to HSP.
FF's system architecture includes a base heuristic technique, a search algorithm, and pruning methods. The base heuristic technique, relaxed GRAPHPLAN, is derived from GRAPHPLAN applied to relaxed planning tasks. The search algorithm, enforced hill-climbing, combines local and systematic search. Pruning techniques include "helpful actions" and "added goal deletion," which are derived from the base heuristic method and used to prune the search space.
FF's performance is evaluated on a range of planning benchmark domains, demonstrating its ability to generate solutions quickly. The paper also discusses the limitations of FF and compares it with HSP, highlighting the effectiveness of the new algorithmic techniques in FF.