Welcome to the Homepage of

METRIC-FF

Top Performer in the Numeric Track of the 3rd International Planning Competition

>> 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.

Vidminas Mikucionis made a cross-platform port of Metric-FF v1.0 and v2.1, that runs on windows. You can find this code here: Metric-FF windows versions.

>> Relevant Papers

Site Meter