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.