The FF planning system: Fast plan generation through heuristic search

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 sea rch, using a heuristic that estimates goal distances by ignoring delete lis ts. Unlike HSP's heuristic, our method does not assume facts to be independ ent. 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 successfu l 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.