# LPG - Local Search in Planning Graphs

## Alfonso Gerevini and Ivan Serina and Team

LPG 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, such as the "heuristic
search cost" and the "heuristic 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.