Homepage LPG

Welcome to the homepage of

A fully-automated domain-independent planner for PDDL2.2 domains

Awarded at the 4th International Planning Competition (IPC4)
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)

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).

An abstract describing the most important new features of LPG-td can be found here, while some papers describing the LPG approach to planning can be found below. Some experimental results from the IPC4 and a comparison with the previous version of the planner using the IPC3 test domains:

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.

Download of LPG-td (executable code)

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 (1999-2008)

New: Alfonso Gerevini, Ugur Kuter, Dana S. Nau, Alessandro Saetti, Nathaniel Waisbrot, Combining Domain-Independent Planning and HTN Planning: The Duet Planner, Proceedings of the 18th European Conference on Artificial Intelligence (ECAI-08), IOS Press, Patras (Grecia), 2008.

New: Alfonso Gerevini, Alessandro Saetti, An Interactive Environment for Plan Visualization and Generation: InLPG, in 18th International Conference on Automated Planning & Scheduling (ICAPS-08), booklet of the ICAPS-08 system demo section, Sydney (Australia), 2008.

Alfonso Gerevini, Alessandro Saetti and Ivan Serina, " An Approach to Efficient Planning with Numerical Fluents and Multi-Criteria Plan Quality", Artificial Intelligence, volume 172(8-9), pp. 899-944, 2008.

Maria Fox, Alfonso Gerevini, Derek Long and Ivan Serina, "Plan Stability: Replanning versus Plan Repair", pp. 193-202, Proceedings of the 16th International Conference on Automated Planning and Scheduling (ICAPS-06), 2006.

Alfonso Gerevini, Alessandro Saetti, Ivan Serina, " An Approach to Temporal Planning and Scheduling in Domains with Predicatable Exogenous Events", Journal of Artificial Intelligence Research (JAIR), volume 25, pp. 187-231, 2006.

Alfonso Gerevini, Alessandro Saetti, Ivan Serina, Paolo Toninelli, " Fast Planning in Domains with Derived Predicates: An Approach Based on Rule-Action Graphs and Local Search ", in Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI-05), AAAI-Press, Pittsburgh, USA, 2005.

Alfonso Gerevini, Alessandro Saetti, Ivan Serina, " Integrating Planning and Temporal Reasoning for Domains with Durations and Time Windows", in Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI-05), IJCAI-Inc., Edinburgh, Scotland, UK, 2005.

Alfonso Gerevini, Alessandro Saetti, Ivan Serina, Paolo Toninelli, " Planning with Derived Predicates through Rule-Action Graphs and Relaxed-Plan Heuristics ", R.T. 2005-01-40, Università degli Studi di Brescia, Dipartimento di Elettronica per l Automazione. Brescia, Italy. 2005.

Alfonso Gerevini, Alessandro Saetti, Ivan Serina, "Planning with Numerical Expressions in LPG", in Proceedings of the 16th European Conference on Artificial Intelligence (ECAI-04), IOS-Press, Valencia, Spain, 2004.

Alfonso gerevini, Alessandro Saetti, Ivan Serina, "An Empirical Analysis of Some Heuristic Features for Local Search in LPG", in Proceedings of the 14th International Conference on Automated Planning and Scheduling (ICAPS-04), AAAI Press, Whistler, Canada, 2004.

Alfonso Gerevini, Alessandro Saetti, Ivan Serina, "Planning in PDDL2.2 Domains with LPG-TD" (short paper), in International Planning Competition, 14th Int. Conference on Automated Planning and Scheduling (ICAPS-04), abstract booklet of the competing planners, Whistler, Canada, 2004.

Alfonso Gerevini, Alessandro Saetti, Ivan Serina, "LPG-TD: a Fully Automated Planner for PDDL2.2 Domains" (short paper), in 14th Int. Conference on Automated Planning and Scheduling (ICAPS-04), booklet of the system demo section, Whistler, Canada, 2004.

Alfonso Gerevini, Alessandro Saetti, Ivan Serina "Planning through Stochastic Local Search and Temporal Action Graphs", Journal of Artificial Intelligence Research (JAIR), vol 20, pp. 239-290. This paper contains the description of some techniques implemented in the version of LPG that took part in the 3rd International Planning Competition.

Alfonso Gerevini, Alessandro Saetti, Ivan Serina "On Managing Temporal Information for Handling Durative Actions in LPG", in A. Cappelli, F. Turini (eds.), AI*IA 2003: Advances in Artificial Intelligence. LNAI 2829 , pages 91-104, Springer-Verlag, Pisa, Italy, 2003.

Alfonso Gerevini , Ivan Serina, Alessandro Saetti, Sergio Spinoni "Local Search Techniques for Temporal Planning in LPG", in Proceedings of the 13th International Conference on Automated Planning and Scheduling (ICAPS-03), AAAI Press, Trento, Italy, 2003.

Alfonso Gerevini and Ivan Serina, "Planning as Propositional CSP: from Walksat to Local Search for Action Graphs", in CONSTRAINTS Journal, vol 8, pp. 389-413, 2003.

Alfonso Gerevini and Ivan Serina, "LPG: a Planner based on Local Search for Planning Graphs", in Proceedings of the Sixth International Conference on Artificial Intelligence Planning and Scheduling (AIPS'02), AAAI Press, Toulouse, France, 2002.

Alfonso Gerevini and Ivan Serina "Lagrange Multipliers for Local Search on Planning Graphs", in Proceedings of the ECAI workshop on Local Search for Planning and Scheduling, A. Nareyek (Ed.), Lectures Notes in Artificial Intelligence 2148, Springer-Verlag, 2001.

Alfonso Gerevini and Ivan Serina, "Fast Plan Adaptation through Planning Graphs: Local and Systematic Search Techniques", in Proceedings of the 5th International Conference on Artificial Intelligence Planning Systems (AIPS-00), AAAI Press, Breckenridge, Colorado, USA, 2000.

Alfonso Gerevini and Ivan Serina "Fast Planning through Greedy Action Graphs", in Proceedings of Sixteenth National Conference of Artificial Intelligence (AAAI-99), AAAI-MIT Press, Orlando, Florida, USA, 1999.

LPG Team

Project leaders: Prof. Alfonso Gerevini and Dr. Ivan Serina
Current students working on LPG: Alessandro Saetti (Ph.D.).
Past undergraduate students involved in the project: Marco Lazzaroni, Stefano Orlandi, Valerio Lorini, Fabrizio Morbini, Sergio Spinoni, Alberto Bettini, Paolo Toninelli.

Alfonso Gerevini. September 31, 2005