# FF

## Joerg Hoffmann

Two versions of FF competed in the competition. The first version was just
FF-v2.2, the version used in the previous competition, modulo removal of
minor bugs in the pre-processing phase. The second version was Metric-FF,
which can handle numerical constraints and effects on linear functions
over numerical state variables.

Metric-FF can be configured to either
favor fast runtime behavior, or good quality solutions. In the former
configuration, the search technique is (like in FF-v2.2) enforced
hill-climbing, using relaxed plan length as a goal distance estimate, as
well as a straightforward adaption of helpful actions pruning. In the
latter configuration, the search strategy is a standard weighted A*
algorithm using relaxed plan cost as an estimate of the remaining cost. In
both cases, relaxed plans are constructed in a manner that naturally
extends the techniques used in the STRIPS/ADL case. In a pre-processing
step, the numerical constraints and effects are transformed such that they
are all * positively monotone *: a constraint is positively monotone
if, when it holds in a state S, it also holds in any state S' where the
values of all numerical variables are at least as high as in S'; an effect
is positively monotone if its value is, with S and S' as above, at
least as high in S' as it is in S.

With these monotonicity properties, one
can relax a task by ignoring all delete lists * and * all numerical
effects that decrease the value of the affected variable. The relaxed task
can then be solved, * combining its logical and numerical aspects *, in
Graphplan-style parallelizing what FF's heuristic function does in the
STRIPS/ADL case. The resulting heuristic function inherits the properties
of FF's original function, for example if there is no relaxed plan to a
state then that state is proved to be a dead end. The
approach is (yet) restricted to linear functions (after replacing static
variables with their numerical values) in order to enable its
naturality: for the algorithms to make sense in the way they do, one needs
functions that are monotone in all arguments.