**>> General Information **

Metric-FF is a domain independent planning system developed by Joerg
Hoffmann. The system is an extension of the FF
planner to (ADL combined with) numerical state variables, more
precisely to PDDL 2.1 level 2, yet more precisely to the subset of
PDDL 2.1 level 2 described below with the algorithmic principles. The
system is implemented in C. It has participated in the numerical
domains of the
3rd
International Planning Competition, demonstrating very competitive
performance. See the web page providing
gnuplots of the respective runtime and solution length data. On
this page, I summarize the main algorithmic principles underlying the
system, provide the source code used in the competition, and give
pointers to relevant publications.

**>> Algorithmic Principles **

As said, Metric-FF deals with PDDL 2.1 level 2, combined with
ADL. Apart from the well-known ADL features, this allows for a finite
number of * numerical state variables * (functions into the
rational numbers, applied to tuples of the objects present in the task
at hand). At any point in a (pre-, effect-, or goal-) condition
formula where a logical atom is allowed, we now also allow for a *
numerical constraint *, i.e., for a comparison ("<", "<=", "=",
">=", or ">") between two expressions over the rational numbers and
the numerical variables, using the operators "+", "-", "*" and "/". At
any point where a logical effect is allowed, we now also allow for a
* numerical effect *, which affects the value of a numerical
variable (left hand side) by a numerical expression (right hand side),
according to one of the operators ":=", "+=", or "-=" (the original
language also allows for the assignment operators "*=" and "/="; we do
not deal with these here).

Naturally, Metric-FF inherits the main ideas used in FF, see there
. Search still is a variation of hill-climbing in the space of all
reachable states, and heuristic evaluation still is done by means of
solving a relaxed task in each single search state, using a
Graphplan-style algorithm (i.e., to solve the * relaxed *
tasks). The resulting relaxed plans still inform the search by ways of
a goal distance estimation --- the number of steps in the relaxed plan
--- as well as by ways of an estimation which actions are most useful,
resp. * helpful * --- roughly, those actions that are contained
in the relaxed plan. The key difference is the definition of the *
relaxation*. In the STRIPS / ADL setting, the task is relaxed by
ignoring all delete lists, i.e., by ignoring all effects that worsen
the current situation. Trying to non-trivially extend this concept to
the numerical setting, the question is, * which numerical effects
worsen the situation? * There is no immediately apparent
answer. Any numerical effect might be good to achieve one numerical
constraint, but at the same time violate another. The reason for this
is that the numerical constraints are not * monotonic*: while one
constraint (e.g. * x > 2 *) might prefer higher values of a
variable * x *, another constraint (e.g. * x < 2 *) might
prefer lower values. As is opposed to that, the conditions in the
purely logical case all prefer "higher" values of the propositional
variables: negative conditions are compiled away as a pre-process, and
thus it is always preferable to have more propositional facts
true. The observation exploited in Metric-FF is that the same
methodology can be applied in the numerical setting, at least in a
subset of the language. The task is pre-processed such that all
numerical constraints are monotonic, i.e., for any constraint *
con*, if * con * is true in a state * S * then * con
* is true in any state * S' * where, for all variables *
x*, * x(S') >= x(S)*. The relaxation is then simply to *
ignore all effects that decrease the value of the affected
variable*, and the relaxed task can be solved in Graphplan-style in
a manner reminiscent of
Metric-IPP. To achieve the monotonicity property, one needs, in
the numerical constraints and effects, expressions that are monotonic
in all variables. In the current implementation, we restrict ourselves
to * linear expressions * which obviously have this property. For
more technical details, try to make sense of the source code supplied
below, or better yet, have a look at the ECAI paper or the JAIR
submission.

Note that the above description, as well as the ECAI paper, address
(only) the algorithms used in the version of Metric-FF that is called
* FF.speed * in the official competition data. This uses relaxed
plan length as the goal distance estimate in enforced hill-climbing
(FF's original search algorithm, see
there), enhanced by (the obvious extension of) helpful actions
pruning. One can also configure the system to favor minimization of a
given cost function. This configuration is what is called *
FF.quality * in the data. Configured thus, the system does a
standard weighted A* search where the cost of the relaxed plan
(explained below) is taken as an estimate of the remaining cost. The
weight parameters of the search can be given in the command line (in
the competition, we used a factor of 1 for the path cost and a factor
of 5 for the heuristic remaining cost). The cost function can be a
linear expression over numerical state variables, as long as this can
be translated to action costs that do not depend on the state of
execution --- i.e. the cost function is accepted if each action only
increases the cost by a constant, like the amount of fuel or time
used. The cost of a relaxed plan is then simply the sum of the costs
of the actions contained in it.

**>> Source Code Available**

Here is the source code for Metric-FF as used in the competition. This is distributed under the GNU General Public License. Please let us know if you download the code, and if you find it useful for whatever purposes you are pursueing.

NEW!! I made a version 2.0 of Metric-FF that treats additive cost minimization in a much better way, using A*-epsilon to combine the usual relaxed plan goal-distance estimation with relaxed plan remaining-cost estimation. As a gimmick, this version also handles a simple form of derived predicates where those predicates are not allowed to occur negated in preconditions/axiom conditions/goals.

Even newer I now made a version 2.1 of Metric-FF which is like 2.0 except it adds the possiblity to specify an upper bound on plan cost. (If that is done, states are pruned based on g + hmax.)

**ATTENTION!** Those of you who have been in contact with FF before
may be aware that for many years there has been trouble with the
parser, that had been written in 1997 and did no longer comply with
up-to-date bison/flex versions. I would like to extend **a big fat
thank-you to Andrew Coles of Strathclyde University, who took the time
to look into this and fix it.**
The link
above gives the new patched version of Metric-FF. Andrew has
tested this with flex 2.5.34 and 2.5.35, as well as bison 2.3 and
2.4.1.

**>> Relevant Papers**

- For the background, there is a detailed JAIR article on the FF
system as it was used in the 2nd international planning competition
(FF-v2.2).
B. Nebel,

**The FF Planning System: Fast Plan Generation Through Heuristic Search**, in: Journal of Artificial Intelligence Research, Volume 14, 2001, Pages 253 - 302. ( gzip'ed postscript file) (bib entry) - A conference paper on the main heuristic algorithm used in
Metric-FF is published at ECAI-2002.
Extending FF to Numerical State Variables, in:

*Proceedings of the 15th European Conference on Artificial Intelligence*, Lyon, France, July 2002. (gzip'ed postscript file) (bib entry) - There's also a long journal article, discussing in a lot of
detail the Metric-FF approach, and describing the system as used in
the 3rd International Planning Competition.
The Metric-FF Planning System: Translating ``Ignoring Delete Lists'' to Numeric State Variables, in: Journal of Artificial Intelligence Research, special issue on the 3rd International Planning Competition ( gzip'ed postscript file) (bib entry)