(AIJ bib entry, Fundam. Inform. Journal bib entry)
Top performer at IPC4 in domains involving "Timed Initial Literals"
Top performer at IPC4 in plan quality (satisficing planning track)
Awarded best fully-automated planner at the 3rd International Planning Competition (IPC3)
new: ICAPS 2019 Influential Paper Award for the Paper "LPG: A Planner Based on Local Search for Planning Graphs with Action Costs".
The LPG-td version (June 2004)
LPG-td is a new version of LPG that extends and improves version 1.2 (see below), and that took part in the 4th International Planning Competition, 2004. LPG-td is an extension of LPG to handle the new features of the standard planning domain description languages PDDL2.2: "Timed initial literals" and "derived predicates". Timed initial literals are a simply way to express facts that become true or false at certain known time points, and they correspond to deterministic unconditional exogenous events, which are practically important for modeling planning domains. Derived predicates are predicates that are not affected by any of the actions available to the planner. Their truth values are determined by a set of implicative domain rules. More details on the new features of PDDL and links to related material are available from the official web site of IPC4.
At IPC4 we submitted three versions of LPG-td, but only the first two were evaluated due to time constraints in producing and evaluating all data:
- LPG-td.speed
finds as quickly as possible
a plan and then stops;
- LPG-td.quality finds a plan
and then
spends a certain amount of CPU-time (automatically decided)
trying to
improve it;
- LPG-td.bestquality
incrementally finds the best plan
that the planner can derive within an user-specified
CPU-time limit (30
min
for IPC4).
- Results of an experimental analysis showing the top performance of LPG-td in terms of plan quality can be found here.
- Results of an experimental analysis comparing the performance of LPG-td and the previous version of the planner (LPG-IPC3) can be found here.
- Results of an
experimental
analysis showing the top performance of LPG-td in the IPC4 domains involving
timed
initial literals are
available
in "An
Approach to Temporal Planning and Scheduling in Domains
with
Predicatable Exogenous Events", Journal of
Artificial
Intelligence Research (JAIR), volume 25, pp.
187-231.
The 1.2 version of LPG
(September 2003)
Download
of
LPG 1.2 (executable
and
source code)
Short description of LPG 1.2 (see also
available papers below)
LPG
(Local search for Planning Graphs) is a
planner
based on local search and planning graphs that handles PDDL2.1
domains
involving numerical quantities and durations. The system can
solve both
plan generation and plan adaptation problems. The basic
search
scheme
of LPG was inspired by Walksat, an efficient procedure to
solve
SAT-problems.
The search space of LPG consists of "action graphs",
particular
subgraphs
of the planning graph representing partial plans. The search
steps are
certain graph modifications transforming an action graph into
another
one.
LPG exploits a compact representation of the planning graph to
define
the
search neighborhood and to evaluate its elements using a
parametrized
function,
where the parameters weight different types of inconsistencies
in the
current
partial plan, and are dynamically evaluated during search
using
discrete
Lagrange multipliers.
The evaluation function uses some
heuristics
to estimate the "search cost" and the "execution cost" of
achieving a
(possibly numeric) precondition. Action durations and
numerical
quantities
(e.g., fuel consumption) are represented in the actions
graphs, and are
modeled in the evaluation function. In temporal domains,
actions are
ordered
using a "precedence graph" that is maintained during search,
and that
takes
into account the mutex relations of the planning graph.
The system can produce good quality plans
in
terms of one or more criteria. This is achieved by an anytime
process
producing
a sequence of plans, each of which is an improvement of the
previous
ones
in terms of its quality. LPG is integrated with a best-first
algorithm
similar to the one used by FF. The system can automatically
switch to
best-first
search after a certain number of search steps and "restarts"
have been
performed. Finally, LPG can be used as a preprocessor to
produce a
quasi-solution
that is then repaired by ADJ, a plan-analysis technique for
fast
plan-adaptation.
Experimental Results (3rd IPC test problems)
Color Plots and data showing the performance of LPG for all test problems of the planning competition. Notice that these are new results, improving the official results of the competition. Overall, the number of problems attempted in the new tests by our planner was 468 (over a total of 508 problems), and the success ratio was 94.4% (the problems attempted by LPG in the competition were 428 and the success ratio 87%), which by far the highest success ratio among the fully-automated planners of the competition
Performance
of LPG in Satellite HardNumeric:
Speed,
Quality
This domain was not addressed in the 3rd
IPC
because the current version of the system did not handle
maximization
of
plan metrics expressions. LPG is compared with FF and MIPS.
(Note that
we consider valid plans only those that are not empty). LPG
solves more
problems than the other planners and produces plans which have
a much
better
quality.
Performance of LPG's RelaxedPlan heuristics with and without counting "threats" in the relaxed plans. Details on these heuristics and this experiment are given in the JAIR paper: Color Plots.
Main papers related to LPG (from 1999)