Source-linked AI summary
The FF Planning System: Fast Plan Generation Through Heuristic Search
J. Hoffmann, B. Nebel
TL;DR
The paper addresses why FF performs so well despite its close relationship to HSP. It presents a planning approach that exploits fact interactions and reports that FF outperforms existing technology on most available benchmark domains.
Problem
The paper examines why FF performs so well in the competition despite being closely related to HSP.
Method
FF exploits interactions among planning facts to draw conclusions about the search space.
Results
FF outperforms all existing technology on the majority of currently available benchmark domains.
Takeaways & Limitations
The paper presents FF as a domain-independent planning approach with broad benchmark performance advantages.
Takeaways & Limitations
Some evaluated domains are ones where IPP and PropPlan probably generate optimal plans.
Abstract
from arXiv · showhide
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.
GRT Mips STAN
On large Logistics instances, FF and Mips behave similarly to the better planners, while System-R performs significantly worse. FF combines fast search with near-STAN plan lengths by finding shallow improvements and pruning most successors.
- Planner performance: The better planners behave quite similarly, with FF and Mips tending to be the strongest performers, whereas System-R performs significantly worse.Runtime is shown on a logarithmic scale, so the comparison does not represent linear time differences.
- Solution quality: STAN finds the shortest plans on most instances, while FF’s plans remain within 7% to 115% of STAN’s lengths.FF’s average plan length is 105% of STAN’s.
- Runtime explanation: FF’s good runtime behavior is attributed mainly to shallow enforced-hill-climbing improvements and the helpful-actions heuristic’s pruning of the search space.In Logistics, the maximal distance d between locations is constant at 1, and FF’s heuristic usually finds optimal or near-optimal relaxed solutions.
- Search behavior: Breadth-first search usually finds the next state with a better evaluation at depth 1, rarely needing to search beyond depth 3 independently of task size.These shallow improvements motivate enforced hill-climbing’s search strategy.
- Search pruning: Only between 40% and 50% of each state’s successors were considered helpful in the experiments, and larger tasks tended to have fewer helpful successors.The helpful-actions heuristic therefore prunes large fractions of the search space.
FF IPP BLACKBOX
On hard random SAT instances, FF solves only the small instances and two larger ones, while IPP and BLACKBOX scale better, with BLACKBOX tending to be fastest. Across planning benchmarks, FF’s strongest performance gains come from its distance estimates, search strategy, and helpful-actions pruning, though their effects depend on domain and configuration.
- Random SAT performance: FF solves only small hard random SAT instances and two larger ones, whereas IPP and BLACKBOX scale better, with BLACKBOX tending to be fastest.The paper attributes BLACKBOX’s advantage on these instances to its use of SAT technology.
- Sources of performance: FF’s performance advantages are primarily associated with its goal-distance estimates, search strategy, and pruning techniques.The runtime analysis indicates that helpful actions and enforced hill-climbing are especially important sources of performance.
- Heuristic estimates: FF distance estimates generally outperform HSP estimates, improving performance reliably but often by only a small factor and with effects scattered across domains and configurations.The paper reports that performance improves in up to 10 domains, with only 5 cases where it worsens, and that interactions among techniques explain much of the variation.
- Search strategy and pruning: Enforced hill-climbing improves performance significantly in 16 of 20 domains when helpful actions are enabled, but its adequacy depends strongly on the domain.Without helpful actions, enforced hill-climbing is degraded almost as often as it is improved, while with them it is degraded only in Fridge.
- Solution quality: FF’s techniques are more useful for reducing runtime than solution length, although enforced hill-climbing and helpful-actions pruning can produce shorter plans in many cases.The paper reports only one case in which enabling helpful actions degrades solution length, with especially significant shortening under hill-climbing.
- Overall assessment: FF outperforms existing technology on most available benchmark domains, but is not particularly well suited to random SAT instances and works best on suitable sequential STRIPS and ADL tasks.The paper credits FF’s performance mainly to its novel local search strategy and helpful-actions pruning.