Prof. Alessandro Saetti
Dipartimento di Ingegneria dell'Informazione
Facoltà di Ingegneria, Università degli Studi di Brescia
Via Branze 38, I-25123 Brescia, Italy.
Alessandro Saetti, Automated Planning in Complex Domains: Algorithms and Systems Based on Graphs and Local Search, Ph.D. Thesis, Università degli Studi di Brescia, DEA, Brescia, Italia, 2006. (PDF file)
Abstract: Reasoning about complex information in automated planning is important for representing real-world problems. Unlike classical planning paradigm where strong assumptions are assumed, in real-world domains actions take time and consume resources; the execution of certain actions can occur only during some predefined time windows imposing scheduling constraints, and can indirectly affect high level properties of world states; moreover, the quality of plans generally takes consumption of resources and makespan into account. This thesis proposes some domain-independent techniques based on graphs and local search for automated planning in complex domains. Specifically, the work has three main contributions. Firstly, we propose a rule-based inference system for efficient reasoning about derived predicates during planning; secondly, we describe a new plan representation for reasoning about quantitative information, and some new heuristics for guiding the planning process towards good quality plans; finally, we propose a new approach to planning with temporal features, integrating constraint-based temporal reasoning into a graph-based planning framework. The techniques described in this thesis are implemented in a new planner called LPG-td. LPG-td took part in the 2004 planning competition showing good performance especially in problems formalized by using recent languages enabling the representation of temporal and quantitative information. A large experimental evaluation shows that our approach works well in practice.
Alessandro Saetti, Sergio Spinoni, Algorithms Based on Local Search for Fully-Automated Planning, Master Thesis, Università degli Studi di Brescia, DEA, Brescia, Italia, 2002.