# Planning Through Stochastic Local Search And Temporal Action Graphs In Lpg

Alfonso Gerevini GEREVINIQING UNIBS IT

## Alessandro Saetti

SA ET T I Q I N G . U N I B S . IT
Ivan Serina SERINA QING. UNIBS. IT
Dipartimento di Elettronica per l'Automazione, Universita degli Studi di Brescia Via Branze 38, I-25123 Brescia, Italy

## Abstract

We present some techniques for planning in domains specified with the recent standard language PDDL 2.1, supporting "durative actions" and numerical quantities. These techniques are implemented in LPG , a domain-independent planner that took part in the 3rd International Planning Competition (IPC). LPG is an incremental, any time system producing multi-criteria quality plans. The core of the system is based on a stochastic local search method and on a graph-based representation called "Temporal Action Graphs" (TA-
graphs). This paper focuses on temporal planning, introducing TA-graphs and proposing some techniques to guide the search in LPG using this representation. The experimental results of the 3rd IPC, as well as further results presented in this paper, show that our techniques can be very effective. Often LPG outperforms all other fully-automated planners of the 3rd IPC in terms of speed to derive a solution, or quality of the solutions that can be produced.

## 1. Introduction

Modeling temporal and numerical information in automated planning is important for representing real-world domains, where actions take time, and consume resources, and the quality of the solutions should take these aspects into account. In the '80s and early '90s some expressive, but inefficient, planning systems handling time were developed (e.g., Vere, 1983; Tsang, 1986; Allen, 1991; Penberthy & Weld, 1994).  More recently, a number of alternative interesting approaches to temporal planning has been proposed (e.g., Smith &
Weld, 1999; Do & Kambhampati, 2001; Haslum & Geffner, 2001; Dimopoulos & Gerevini, 202).  Some of these planners can compute plans with optimal makespan, but in practice most of them scale up poorly.

Local search is emerging as a powerful method to address fully-automated planning, though in principle this approach does not guarantee generation of optimal plans. In particular, two planners that successfully participated in the recent 3rd International Planning Competition (IPC) are based on local search: FF (Hoffmann & Nebel, 2001) and LPG.

In earlier work on LPG (Gerevini & Serina, 1999, 2002) we proposed a first version of our system using several techniques for local search in the space of action graphs (A-graphs), particular subgraphs of the planning graph representation (Blum & Furst, 1997).

This version of the planner handled only STRIPS domains, possibly extended with simple costs associated with the actions. In this paper, which is a revised and extended version of a recent work (Gerevini, Serina, Saetti, & Spinoni, 2003), we present some major improvements