Welcome to the Homepage of

FAST-FORWARD

Now provided under the GNU General Public License

Awarded for Outstanding Performance at the 2nd International Planning Competition

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

Also Featuring

METRIC-FF

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

Now also Featuring

CONFORMANT-FF

and

CONTINGENT-FF

Not-so-Top Performers in the Conformant Track of the 5th International Planning Competition ;-)

-- well actually they were not so bad; and Hector^2 (Palacios & Geffner) "beat me with my own planner", using a compiler+classical-FF approach...

Finally, aufgrund der grossen Nachfrage, also Featuring

FF-X

which didn't perform in any competition (I'm aware of), but which I finally got bored of sending around by email. The link above is the .tgz'ed source code. In case you wonder what "FF-X" actually is -- it's the version handling PDDL 2.1 derived predicates, aka "axioms".

Check out my results on the patterns of structure (common to most of the benchmarks) that enable FF's performance
Check out my results on the fully-automatic recognition of these patterns of structure
The FF domain collection provides problem generators for 20 benchmark domains

>> General Information

Fast-Forward, abbreviated FF, is a domain independent planning system developed by Joerg. FF can handle classical STRIPS- as well as full scale ADL- planning tasks, to be specified in PDDL (for the version that can handle numerical state variables on top of that, check out the other page). The system is implemented in C. It has competed in the fully automated track of the 2nd International Planning Competition. As a result of the competition, FF was granted ``Group A distinguished performance Planning System'', and it also won the Schindler Award for the best performing planning system in the Miconic 10 Elevator domain, ADL track. The system (slightly de-bugged) also participated in the 3rd International Planning Competition where it excelled in the STRIPS domains (but didn't get an award because of the broader language coverage of other competitive systems). Check out our web page providing gnuplots of the runtime and solution length data in the STRIPS (and Numerical) domains used in the competition. On the page at hand we make available the source code used in the 3rd International Planning Competition, and some older source code for an easier readable STRIPS version. We also give pointers to publications relevant for the system, and provide some interesting information on what makes the system so efficient across many benchmark domains.

>> Basic Principles

FF is a forward chaining heuristic state space planner. The main heuristic principle was originally developed by Blai Bonet and Hector Geffner for the HSP system: to obtain a heuristic estimate, relax the task P at hand into a simpler task P+ by ignoring the delete lists of all operators. While HSP employs a technique that gives a rough estimate for the solution length of P+ , FF extracts an explicit solution to P+ , by using a GRAPHPLAN-style algorithm. The number of actions in the relaxed solutions is used as a goal distance estimate. These estimates control a novel local search strategy, enforced hill-climbing: this is a hill-climbing procedure that, in each intermediate state, uses breadth first search to find a strictly better, possibly indirect, successor. As a second important heuristic information, the relaxed plans can be used to prune the search space: usually, the actions that are really useful in a state are contained in the relaxed plan, so one can restrict the successors of any state to those produced by members of the respective relaxed solution. FF employs a slightly more elaborated form of this heuristic, which we call helpful actions pruning. The simple architecture described so far already solves most of the available benchmarks extremely efficiently. Problematic cases are when there are dead ends --- states from which the goals get unreachable --- or goal orderings. In the presence of the latter phenomenon, like in the Blocksworld, the local search sometimes proceeds too greedily, and gets trapped. To overcome this, we have integrated the Goal Agenda algorithm (first proposed by Jana Koehler), as well as a simple goal ordering technique of our own, based on the relaxed solutions. In order to deal with dead end states, which can cause the search to fail entirely, we have chosen a simple safety-net solution: if local search fails, then we skip everything done so far and switch to a complete best-first algorithm that simply expands all search nodes by increasing order of goal distance evaluation.

>> Source Code Available

FF is publicly available under the GNU General Public License. For the source code of Metric-FF, see the other web page. FF-v2.3 is here. This is the ADL version, enhanced with our own goal orderings pruning technique, and with the ordering informations provided by the Goal Agenda, adapted from Jana Koehler's work. It is identical to version FF-v2.2 as used in the 2nd International Planning Competition, modulo removal of a few minor bugs in the pre-processing phase.

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 FF-v2.3. Andrew has tested this with flex 2.5.34 and 2.5.35, as well as bison 2.3 and 2.4.1. The changes needed were, after all, quite simple. Here's Andrew's description:

  • In lex-fct_pddl.l replace "#define fct_pddlwrap() 1" with "int fct_pddlwrap() { return 1; };"
  • In lex-ops_pddl.l replace "#define ops_pddlwrap() 1" with "int ops_pddlwrap() { return 1; };"

Robert Goldman has kindly contributed a patched version of FF-v2.3 in which the parser allows newlines within typed lists.

Finally, Martin Suda has contributed a patched version of FF-v2.3 whose parser is supposed to be able to parse larger inputs. I haven't tested this but wanted to let you have it anyway.

>> Relevant Papers

>> Local Search Topology in Planning Benchmarks

One of the most exciting questions opened up by the performance of FF is, why does this work so good in so many domains? It is ovbious that the success of a heuristic algorithm, especially of a local search algorithm, depends on the quality of the heuristic function it uses, i.e., on the local search topology of the underlying search space under evaluation with that heuristic function. So the question comes down to, what are the characteristic topological properties of the search spaces in those domains where FF works well? We investigated 20 of the most commonly used benchmark domains. Our first research effort was to observe, empirically, the topology of example instances. We looked at a collection of random examples whose state spaces were small enough to be built entirely. For an idealized version of FF's heuristic function (optimal relaxed distances, usually notated h+), we made the following three crucial observations: there were no unrecognized dead end states (states from which there is a relaxed plan but no real plan) in the examples of 16 of the domains; there were no local minima at all in 14 of the domains; in 8 domains, there seemed to be a constant upper bound on the maximal exit distance (roughly, the maximal distance to a better state on flat regions). The topological properties of FF's actual heuristic function (an approximation of the optimal relaxed distances) were similar. With all three properties, FF's search algorithm evaluates polynomially many states before finding the goal.

The empirical work having provided us with the relevant distinctions between planning domains, the next step was to verify the observations in general. A theoretical investigation proved that, for optimal relaxed distances h+, with a single exception all the observations in our small examples do in fact carry over to the respective entire domains. Through the process of proving, the investigation also provided a picture of the common patterns of structure in the investigated domains that cause the high heuristic quality of relaxed distances, and thereby the performance of planners like FF. The patterns of structure are, very coarsely, that: 1. the available actions are invertible or need not be inverted (--> no dead ends); 2. any action that is good for solving the real task is also good for solving the relaxed task (together with 1. --> no local minima); 3. some actions have delete effects that are irrelevant upon application, the other actions need to be applied at most a constant number of times in a row (together with 1. and 2. --> constant upper bound on the maximal exit distance).

A final empirical working step confirmed that the proved heuristic quality of optimal relaxed distances largely carries over to FF's approximation of these distances. In particular, it follows that FF is "largely" polynomial in those eight of the investigated 20 domains where all three of the aforementioned patterns of structure occur (amongst others, this is true in the Logistics domain).

The first two investigations are published as conference papers. The first empirical work is published at IJCAI'01:

Local Search Topology in Planning Benchmarks: An Empirical Analysis, in: Proceedings of the 17th International Joint Conference on Artificial Intelligence, Seattle, Washington, USA, August 2001. (gzip'ed postscript file) (bib entry)

The paper about the theoretical analysis is published at AIPS'02:

Local Search Topology in Planning Benchmarks: A Theoretical Analysis, in: Proceedings of the 6th International Conference on Artificial Intelligence Planning and Scheduling, Toulouse, France, April 2002. (gzip'ed postscript file) (bib entry)

An extended and revised version of the AIPS'02 paper, including results for 10 new domains (the IPC-3 and IPC-4 benchmarks), as well as a revised definition of the main distinctions between planning domains, involving several new results for the 20 ``old'' domains, is published in JAIR:

J. Hoffmann, Where Ignoring Delete Lists Works: Local Search Topology in Planning Benchmarks, Journal of Artificial Intelligence Research, Volume 24, 2005, pages 685 - 758. (gzip'ed postscript file)

The JAIR paper contains overview proof sketches. A long (138 pages) TR provides the full details of the investigation:

Where Ignoring Delete Lists Works: Local Search Topology in Planning Benchmarks, Technical Report No. 185, Institut für Informatik, March 2003. (gzip'ed postscript file)

>> TorchLight

This is a recent tool I've developed. It allows to analyze search space topology without actually running any search. What I mean with this is that TorchLight can, fully automatically, draw conclusions on the local search topology under h+ (cf. above), without even starting to generate any search states. The key to this is a connection between that topology and properties of the Causal Graph as well as the Domain Transition Graphs, as have been made popular several years after I performed the work described above. In a nutshell, the basic property is: If the Causal Graph is acyclic, and all variable transitions are invertible, then there are no local minima under h+.

The basic result can be extended by a more local analysis, looking at certain sub-graphs of the Causal Graph rather than at the full one, and allowing certain special cases of non-invertible transitions. With these extensions, the criterion allows to also derive a bound on the exit distance under h+, and it applies to 4 standard benchmark domains. While this is only a small fraction of benchmarks, TorchLight also features a simple sampling method, looking at a small number (default: 10) of randomly generated states, applying a per-state version of the criterion to each, and returning the fraction of sample states where the criterion said "yes". This "success rate" gives a measure of the "hardness" -- more precisely, of the quality of h+ as a heuristic -- for arbitrary planning tasks. My experiments have shown that this measure correlates strongly with planner performance (for FF and LAMA).

TorchLight's source code is publicly available under the GNU GPL license: TorchLight.zip.

Papers on TorchLight have been published at JAIR'11 and ICAPS'11 (in this order :-)

J. Hoffmann, Analyzing Search Topology Without Running Any Search: On the Connection Between Causal Graphs and h+, Journal of Artificial Intelligence Research, Volume 41, 2011, pages 155-229. (PDF file)

J. Hoffmann, Where Ignoring Delete Lists Works, Part II: Causal Graphs, in Proceedings of the 21st International Conference on Automated Planning and Scheduling (ICAPS'11), Freiburg, Germany, June 2011. Nominated for the best paper award. (pdf file)

There's also an easy-to-read ICAPS'11 demo paper with example runs, and you can have a look at my talk slides or at the ICAPS'11 demo poster.

Site Meter