Temporal Fast Downward
Temporal Fast Downward (TFD) extends Fast Downward to temporal and numeric planning, searching through time-stamped states with an adapted heuristic. It was runner-up at IPC 2008 and at IPC 2014.
- Authors
- Patrick Eyerich, Robert Mattmüller, Gabriele Röger; developers also include Christian Dornhege
- Institution
- University of Freiburg
- Kind of planning
- Temporal and numeric
- Source
- tfd.informatik.uni-freiburg.de (GPL)
How it works
TFD performs, in its paper's words, "a heuristic search in the space of time-stamped states". It has two kinds of step: insert a durative action at the current time, or advance the clock. Its heuristic is the context-enhanced additive heuristic of Helmert and Geffner, extended to numeric fluents, and it aims for plans with a low makespan.
What it handles
Durative actions with numeric fluents, along with ADL features and derived predicates. It handles some forms of required concurrency, and no continuous effects. In our benchmarks it solved no problem of the classical tracks. See the feature comparison.
In the competitions
- Runner-up in the temporal satisficing track of IPC 2008, with SGPlan 6 the winner.
- Runner-up in the temporal track of IPC 2014, in a version by Patrick Eyerich, Thomas Keller, Johannes Aldinger and Christian Dornhege, with YAHSP3-MT the winner.
Results in our benchmarks
| Track | Problems | TFD | Autoplan |
|---|---|---|---|
| IPC 1998–2018 classical | 2,742 | 0 | 2,450 |
| IPC 2023 classical | 140 | 0 | 109 |
| IPC 2002 temporal | 436 | 157 | 338 |
| IPC 2004 temporal | 976 | 97 | 715 |
| IPC 2006 temporal | 450 | 140 | 308 |
| IPC 2008 temporal | 390 | 323 | 348 |
| IPC 2011 temporal | 240 | 140 | 218 |
| IPC 2014 temporal | 200 | 83 | 181 |
| IPC 2018 temporal | 90 | 44 | 86 |
TFD 0.4: problems solved with a plan the VAL validator accepts, within 60 seconds and 4 GB of memory on one core. These are our own runs, not competition results, and a planner written for other goals or for a different kind of problem can score low here while being the right tool for its purpose. How we measured.
Paper
- Patrick Eyerich, Robert Mattmüller, Gabriele Röger. Using the Context-Enhanced Additive Heuristic for Temporal and Numeric Planning. ICAPS 2009, 130-137.