LPG-td
LPG, Local search for Planning Graphs, improves a plan by local search instead of building it step by step. LPG-td is the version for PDDL 2.2, and "td" stands for timed initial literals and derived predicates.
- Authors
- Alfonso Gerevini, Alessandro Saetti, Ivan Serina
- Institution
- University of Brescia
- Kind of planning
- Classical, numeric, temporal
- Source
- lpg.unibs.it. LPG-td is distributed as an executable, after registration
How it works
LPG works on partial plans held in a graph structure, which its JAIR paper calls Temporal Action Graphs. A stochastic local search repairs flaws in the graph, with noise and restarts to escape local minima. It is an anytime planner: once it has a plan it keeps looking for better ones. LPG-td adds constraint-based temporal reasoning for events known in advance.
What it handles
Numeric fluents, durative actions, derived predicates and timed initial literals. It does not handle continuous effects, or problems that need actions to overlap. See the feature comparison.
In the competitions
- The IPC 2002 organisers awarded LPG a prize as "the best performer of the fully-automated planners".
- LPG-td, by Alfonso Gerevini, Alessandro Saetti, Ivan Serina and Paolo Toninelli, took second prize in the satisficing metric temporal track of IPC 2004.
Results in our benchmarks
| Track | Problems | LPG-td | Autoplan |
|---|---|---|---|
| IPC 1998–2018 classical | 2,742 | 1,297 | 2,450 |
| IPC 2023 classical | 140 | 20 | 109 |
| IPC 2023 numeric | 400 | 152 | 383 |
| IPC 2026 numeric | 320 | 61 | 270 |
| IPC 2002 temporal | 436 | 324 | 338 |
| IPC 2004 temporal | 976 | 445 | 715 |
| IPC 2006 temporal | 450 | 192 | 308 |
| IPC 2008 temporal | 390 | 264 | 348 |
| IPC 2011 temporal | 240 | 126 | 218 |
| IPC 2014 temporal | 200 | 119 | 181 |
| IPC 2018 temporal | 90 | 63 | 86 |
LPG-td 1.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.
Papers
- Alfonso Gerevini, Alessandro Saetti, Ivan Serina. Planning through Stochastic Local Search and Temporal Action Graphs in LPG. Journal of Artificial Intelligence Research 20, 239-290, 2003.
- Alfonso Gerevini, Alessandro Saetti, Ivan Serina. An Approach to Temporal Planning and Scheduling in Domains with Predictable Exogenous Events. Journal of Artificial Intelligence Research 25, 187-231, 2006.