Alessandro Saetti

AAAI Conference 2026 Conference Paper

Planning with Uncertain Action Models

• Francesco Percassi
• Alessandro Saetti
• Enrico Scala

Uncertainty over model knowledge is a core challenge in planning and has been addressed through various approaches tailored to different scenarios. In this paper, we focus on scenarios where the agent does not initially know the exact outcome of its actions but gains knowledge upon execution, i.e., each action reveals its actual effect, removing uncertainty about future occurrences. We refer to this formulation as Planning with Uncertain Models of Actions (PUMA). We show that PUMA can be compiled in polynomial time in both Fully Observable Non-Deterministic planning and, perhaps more unexpectedly, classical planning, providing a constructive proof that PUMA remains PSPACE-complete despite its apparent exponential uncertainty. Finally, we experimentally evaluate both compilations with benchmark domains that capture the key aspects of the problem. The results show the practical feasibility of our approach and reveal a complementary behavior between the two compilations.

AIJ Journal 2025 Journal Article

Lifted action models learning from partial traces

• Leonardo Lamanna
• Luciano Serafini
• Alessandro Saetti
• Alfonso Emilio Gerevini
• Paolo Traverso

For applying symbolic planning, there is the necessity of providing the specification of a symbolic action model, which is usually manually specified by a domain expert. However, such an encoding may be faulty due to either human errors or lack of domain knowledge. Therefore, learning the symbolic action model in an automated way has been widely adopted as an alternative to its manual specification. In this paper, we focus on the problem of learning action models offline, from an input set of partially observable plan traces. In particular, we propose an approach to: (i) augment the observability of a given plan trace by applying predefined logical rules; (ii) learn the preconditions and effects of each action in a plan trace from partial observations before and after the action execution. We formally prove that our approach learns action models with fundamental theoretical properties, not provided by other methods. We experimentally show that our approach outperforms a state-of-the-art method on a large set of existing benchmark domains. Furthermore, we compare the effectiveness of the learned action models for solving planning problems and show that the action models learned by our approach are much more effective w. r. t. a state-of-the-art method. 1

KER Journal 2025 Journal Article

Optimally stable plan repair

• Alessandro Saetti
• Enrico Scala

Abstract Plan repair is the problem of solving a given planning problem by using a solution plan of a similar problem. This paper presents the first approach where the repair has to be done optimally, that is, we aim at finding a minimum distance plan from an input plan; we do so by introducing a number of compilation schemes that convert a classical planning problem into another where optimal plans correspond to plans with the minimum distance from an input plan. We also address the problem of finding a minimum distance plan from a set of input plans, instead of just one plan. Our experiments using a number of planners show that such a simple approach can solve many problems optimally and more effectively than replanning from scratch for a large number of cases. Also, the approach proves competitive with ${\mathsf{LPG}\textrm{-}\mathsf{adapt}}$, a state-of-the-art approach for the plan repair problem.

SoCS Conference 2024 Conference Paper

Deployable Yet Effective Traffic Signal Optimisation via Automated Planning (Extended Abstract)

• Anas El Kouaiti
• Francesco Percassi
• Alessandro Saetti
• Thomas Leo McCluskey
• Mauro Vallati

The use of planning techniques in traffic signal optimisation has proven effective in managing unexpected traffic conditions as well as typical traffic patterns. However, significant challenges concerning the deployability of generated signal plans remain, as planning systems need to consider constraints and features of the actual real-world infrastructure on which they will be implemented. To address this challenge, we introduce a range of PDDL+ models embodying technological requirements as well as insights from domain experts. The proposed models have been extensively tested on historical data using a range of well-known search strategies and heuristics, as well as alternative encodings. Results demonstrate their competitiveness with the state of the art.

ICAPS Conference 2024 Conference Paper

PDDL+ Models for Deployable yet Effective Traffic Signal Optimisation

• Anas El Kouaiti
• Francesco Percassi
• Alessandro Saetti
• Thomas Leo McCluskey
• Mauro Vallati

The use of planning techniques in traffic signal optimisation has proven effective in managing unexpected traffic conditions as well as typical traffic patterns. However, significant challenges concerning the deployability of generated signal strategies remain, as existing approaches tend not to consider constraints and features of the actual real-world infrastructure on which they will be implemented. To address this challenge, we introduce a range of PDDL+ models embodying technological requirements as well as insights from domain experts. The proposed models have been extensively tested on historical data using a range of well-known search strategies and heuristics, as well as alternative encodings. Results demonstrate their competitiveness with the state of the art.

IJCAI Conference 2023 Conference Paper

Learning to Act for Perceiving in Partially Unknown Environments

• Leonardo Lamanna
• Mohamadreza Faridghasemnia
• Alfonso Gerevini
• Alessandro Saetti
• Alessandro Saffiotti
• Luciano Serafini
• Paolo Traverso

Autonomous agents embedded in a physical environment need the ability to correctly perceive the state of the environment from sensory data. In partially observable environments, certain properties can be perceived only in specific situations and from certain viewpoints that can be reached by the agent by planning and executing actions. For instance, to understand whether a cup is full of coffee, an agent, equipped with a camera, needs to turn on the light and look at the cup from the top. When the proper situations to perceive the desired properties are unknown, an agent needs to learn them and plan to get in such situations. In this paper, we devise a general method to solve this problem by evaluating the confidence of a neural network online and by using symbolic planning. We experimentally evaluate the proposed approach on several synthetic datasets, and show the feasibility of our approach in a real-world scenario that involves noisy perceptions and noisy actions on a real robot.

JAIR Journal 2023 Journal Article

Maintenance of Plan Libraries for Case-Based Planning: Offline and Online Policies

• Alfonso Emilio Gerevini
• Alessandro Saetti
• Ivan Serina
• Andrea Loreggia
• Luca Putelli
• Anna Roubickova

Case-based planning is an approach to planning where previous planning experience provides guidance to solving new problems. Such a guidance can be extremely useful, or even necessary, when the new problem is very hard to solve, or the stored previous experience is highly valuable, because, e.g., it was provided or validated by human experts, and the system should try to reuse it as much as possible. To do so, a case-based planning system stores in a library previous planning experience in the form of already encountered problems and their solutions. The quality of such a plan library critically influences the performance of the planner, and therefore it needs to be carefully designed and created. For this reason, it is also important to update the library during the lifetime of the system, as the type of problems being addressed may evolve or differ from the ones the library was originally designed for. Moreover, like in general case-based reasoning, the library needs to be maintained at a manageable size, otherwise the computational cost of querying it grows excessively, making the entire approach ineffective. In this paper, we formally define the problem of maintaining a library of cases, discuss which criteria should drive the maintenance, study the computational complexity of the maintenance problem, and propose offline techniques to reduce an oversized library that optimize different criteria. Moreover, we introduce a complementary online approach that attempts to limit the growth of the library, and we consider the combination of offline and online techniques to ensure the best performance of the case-based planner. Finally, we experimentally show the practical effectiveness of the offline and online methods for reducing the library.

AAAI Conference 2023 Conference Paper

Planning for Learning Object Properties

• Leonardo Lamanna
• Luciano Serafini
• Mohamadreza Faridghasemnia
• Alessandro Saffiotti
• Alessandro Saetti
• Alfonso Gerevini
• Paolo Traverso

Autonomous agents embedded in a physical environment need the ability to recognize objects and their properties from sensory data. Such a perceptual ability is often implemented by supervised machine learning models, which are pre-trained using a set of labelled data. In real-world, open-ended deployments, however, it is unrealistic to assume to have a pre-trained model for all possible environments. Therefore, agents need to dynamically learn/adapt/extend their perceptual abilities online, in an autonomous way, by exploring and interacting with the environment where they operate. This paper describes a way to do so, by exploiting symbolic planning. Specifically, we formalize the problem of automatically training a neural network to recognize object properties as a symbolic planning problem (using PDDL). We use planning techniques to produce a strategy for automating the training dataset creation and the learning process. Finally, we provide an experimental evaluation in both a simulated and a real environment, which shows that the proposed approach is able to successfully learn how to recognize new object properties.

AIJ Journal 2023 Journal Article

Width-based search for multi agent privacy-preserving planning

• Alfonso E. Gerevini
• Nir Lipovetzky
• Francesco Percassi
• Alessandro Saetti
• Ivan Serina

In multi-agent planning, preserving the agents' privacy has become an increasingly popular research topic. For preserving the agents' privacy, agents jointly compute a plan that achieves mutual goals by keeping certain information private to the individual agents. Unfortunately, this can severely restrict the accuracy of the heuristic functions used while searching for solutions. It has been recently shown that, for centralized planning, blind search algorithms such as width-based search can solve instances of many existing domains in low polynomial time when they feature atomic goals. Moreover, the performance of goal-oriented search can be improved by combining it with width-based search. In this paper, we investigate the usage of width-based search in the context of (decentralised) collaborative multi-agent privacy-preserving planning, addressing the challenges related to the agents' privacy and performance. In particular, we show that width-based search is a very effective approach over several benchmark domains, even when the search is driven by heuristics that roughly estimate the distance from goal states, computed without using the private information of other involved agents. Moreover, we show that the use of width-based techniques can significantly reduce the number of messages transmitted among the agents, better preserving their privacy and improving their performance. An experimental study presented in the paper analyses the effectiveness of our techniques, and compares them with the state-of-the-art of collaborative multi-agent planning.

SoCS Conference 2022 Conference Paper

On the Use of Width-Based Search for Multi Agent Privacy-Preserving Planning (Extended Abstract)

• Alfonso Emilio Gerevini
• Nir Lipovetzky
• Francesco Percassi
• Alessandro Saetti
• Ivan Serina

The aim of decentralised multi-agent (DMA) planning is to coordinate a set of agents to jointly achieve a goal while preserving their privacy. Blind search algorithms, such as width-based search, have recently proved to be very effective in the context of centralised automated planning, especially when combined with goal-oriented techniques. In this paper, we discuss a recent line of research in which the usage of width-based search has been extensively studied in the context of DMA planning, addressing the challenges related to the agents

KR Conference 2022 Conference Paper

Online Grounding of Symbolic Planning Domains in Unknown Environments

• Leonardo Lamanna
• Luciano Serafini
• Alessandro Saetti
• Alfonso Gerevini
• Paolo Traverso

If a robotic agent wants to exploit symbolic planning techniques to achieve some goal, it must be able to properly ground an abstract planning domain in the environment in which it operates. However, if the environment is initially unknown by the agent, the agent needs to explore it and discover the salient aspects of the environment necessary to reach its goals. Namely, the agent has to discover: (i) the objects present in the environment, (ii) the properties of these objects and their relations, and finally (iii) how abstract actions can be successfully executed. The paper proposes a framework that aims to accomplish the aforementioned perspective for an agent that perceives the environment partially and subjectively, through real value sensors (e. g. , GPS, and on-board camera) and can operate in the environment through low level actuators (e. g. , move forward of 20 cm). We evaluate the proposed architecture in photo-realistic simulated environments, where the sensors are RGB-D on-board camera, GPS and compass, and low level actions include movements, grasping/releasing objects, and manipulating objects. The agent is placed in an unknown environment and asked to find objects of a certain type, place an object on top of another, close or open an object of a certain type. We compare our approach with a state of the art method on object goal navigation based on reinforcement learning, showing better performances.

ICAPS Conference 2022 Conference Paper

Optimising the Stability in Plan Repair via Compilation

• Alessandro Saetti
• Enrico Scala

Plan repair is the problem of solving a given planning problem by using a solution plan of a similar problem. Plan repair problems can arise in execution contexts, that is, when an agent performing the plan has to deal with some unexpected contingency that makes the given plan invalid. Repairing a plan works often much better than replanning from scratch, and is crucial when plans have to be kept stable. There is no planning system until now that guarantees to find plans at the minimum distance from an input plan. This paper presents the first approach to such a problem; we indeed introduce a simple compilation scheme that converts a classical planning problem into another where optimal plans correspond to plans with the minimum distance from an input plan. Our experiments using a number of planners show that such a simple approach can solve the plan repair problem optimally and more effectively than replanning from scratch for a large number of cases. Last but not least, the approach proves competitive with LPG-ADAPT.

AAAI Conference 2021 Conference Paper

On-line Learning of Planning Domains from Sensor Data in PAL: Scaling up to Large State Spaces

• Leonardo Lamanna
• Alfonso Emilio Gerevini
• Alessandro Saetti
• Luciano Serafini
• Paolo Traverso

We propose an approach to learn an extensional representation of a discrete deterministic planning domain from observations in a continuous space navigated by the agent actions. This is achieved through the use of a perception function providing the likelihood of a real-value observation being in a given state of the planning domain after executing an action. The agent learns an extensional representation of the domain (the set of states, the transitions from states to states caused by actions) and the perception function on-line, while it acts for accomplishing its task. In order to provide a practical approach that can scale up to large state spaces, a “draft” intensional (PDDL-based) model of the planning domain is used to guide the exploration of the environment and learn the states and state transitions. The proposed approach uses a novel algorithm to (i) construct the extensional representation of the domain by interleaving symbolic planning in the PDDL intensional representation and search in the statetransition graph of the extensional representation; (ii) incrementally refine the intensional representation taking into account information about the actions that the agent cannot execute. An experimental analysis shows that the novel approach can scale up to large state spaces, thus overcoming the limits in scalability of current approaches.

IJCAI Conference 2021 Conference Paper

Online Learning of Action Models for PDDL Planning

• Leonardo Lamanna
• Alessandro Saetti
• Luciano Serafini
• Alfonso Gerevini
• Paolo Traverso

The automated learning of action models is widely recognised as a key and compelling challenge to address the difficulties of the manual specification of planning domains. Most state-of-the-art methods perform this learning offline from an input set of plan traces generated by the execution of (successful) plans. However, how to generate informative plan traces for learning action models is still an open issue. Moreover, plan traces might not be available for a new environment. In this paper, we propose an algorithm for learning action models online, incrementally during the execution of plans. Such plans are generated to achieve goals that the algorithm decides online in order to obtain informative plan traces and reach states from which useful information can be learned. We show some fundamental theoretical properties of the algorithm, and we experimentally evaluate the online learning of the action models over a large set of IPC domains.

ICAPS Conference 2020 Conference Paper

Bounded Suboptimal Path Planning with Compressed Path Databases

• Shizhe Zhao
• Mattia Chiari
• Adi Botea
• Alfonso Emilio Gerevini
• Daniel Harabor
• Alessandro Saetti
• Peter J. Stuckey

Compressed Path Databases (CPDs) are a state-of-the-art method for path planning. They record, for each start position, an optimal first move to reach any target position. Computing an optimal path with CPDs is extremely fast and requires no state-space search. The main disadvantages are overhead related: building a CPD usually involves an all-pairs precomputation, and storing the result often incurs prohibitive space overheads. Previous research has focused on reducing the size of CPDs and/or improving their online performance. In this paper we consider a new type of CPD, which can also dramatically reduce preprocessing times. Our idea involves computing first-move data for only selected target nodes; chosen in such a way as to guarantee that the cost of any extracted path is within a fixed bound of the optimal solution. Empirical results demonstrate that our new bounded suboptimal CPDs improve preprocessing times by orders of magnitude. They further reduce storage costs, and compute paths more quickly – all in exchange for only a small amount of suboptimality.

ICAPS Conference 2020 Conference Paper

Search-Guidance Mechanisms for Numeric Planning Through Subgoaling Relaxation

• Enrico Scala
• Alessandro Saetti
• Ivan Serina
• Alfonso Emilio Gerevini

Recently, a new decomposition based relaxation has been proposed for numeric planning problems. Roughly, this relaxation is grounded on the identification of regression-based necessary conditions for the satisfaction of sets of numeric subgoals. So far, it has been used to define novel heuristics that are able to provide great guidance in problems exhibiting a pronounced numeric structure. This paper investigates how to further exploit this relaxation; it does so by introducing the notion of the multi-repetition relaxed plan. The multi-repetition plan annotates actions with the number of times such actions need to be executed. We use this structure for different purposes: extraction of a concrete relaxed plan based heuristic, definition of subgoaling based helpful actions, and definition of what we call up-to-jumping actions. Up-to-jumping actions allow us to deeply leverage from the metric structure of the problem and devise an informed search strategy that can collapse several decision steps. We experimentally analyze a forward state space planner equipped with these novel mechanisms across several planning benchmarks, showing the benefit of the ideas presented in the paper.

ICAPS Conference 2019 Conference Paper

Best-First Width Search for Multi Agent Privacy-Preserving Planning

• Alfonso Emilio Gerevini
• Nir Lipovetzky
• Francesco Percassi
• Alessandro Saetti
• Ivan Serina

In multi-agent planning, preserving the agents’ privacy has become an increasingly popular research topic. For preserving the agents’ privacy, agents jointly compute a plan that achieves mutual goals by keeping certain information private to the individual agents. Unfortunately, this can severely restrict the accuracy of the heuristic functions used while searching for solutions. It has been recently shown that, for centralized planning, the performance of goal oriented search can be improved by combining goal oriented search and width-based search. The combination of these techniques has been called best-first width search. In this paper, we investigate the usage of best-first width search in the context of (decentralised) multi-agent privacy-preserving planning, addressing the challenges related to the agents’ privacy and performance. In particular, we show that best-first width search is a very effective approach over several benchmark domains, even when the search is driven by heuristics that roughly estimate the distance from goal states, computed without using the private information of other agents. An experimental study analyses the effectiveness of our techniques and compares them with the state-of-the-art.

ICAPS Conference 2019 Conference Paper

Cutting the Size of Compressed Path Databases with Wildcards and Redundant Symbols

• Mattia Chiari
• Shizhe Zhao
• Adi Botea
• Alfonso Emilio Gerevini
• Daniel Harabor
• Alessandro Saetti
• Matteo Salvetti
• Peter J. Stuckey

Path planning on gridmaps is a common problem in AI and a popular topic in application areas such as computer games. Compressed Path Databases (CPDs) represent a state-of-theart approach to the problem, in terms of the speed of computing full optimal paths and also individual optimal moves. Despite significant improvements in recent years, the memory required to store a CPD can still be a bottleneck for large game maps. In this work we present a new compression approach that can reduce the size of CPDs. Our approach uses an extended notion of wildcards and a novel concept called a redundant symbol. We implement our ideas on top of a state-of-the-art CPD system and, in a range of experiments, we demonstrate a substantial reduction in the size of CPDs.

SoCS Conference 2019 Conference Paper

Novelty Messages Filtering for Multi Agent Privacy-Preserving Plannin

• Alfonso Emilio Gerevini
• Nir Lipovetzky
• Nico Peli
• Francesco Percassi
• Alessandro Saetti
• Ivan Serina

In multi-agent planning, agents jointly compute a plan that achieves mutual goals, keeping certain information private to the individual agents. Agents

ICAPS Conference 2018 Conference Paper

Two-Oracle Optimal Path Planning on Grid Maps

• Matteo Salvetti
• Adi Botea
• Alfonso Emilio Gerevini
• Daniel Harabor
• Alessandro Saetti

Path planning on grid maps has progressed significantly in recent years, partly due to the Grid-based Path Planning Competition GPPC. In this work we present an optimal approach which combines features from two modern path planning systems, SRC and JPS+, both of which were among the strongest entrants at the 2014 edition of the competition. Given a current state s and a target state t, SRC is used as an oracle to provide an optimal move from s towards t. Once a direction is available we invoke a second JPS-based oracle to tell us for how many steps that move can be repeated, with no need to query the oracles between these steps. Experiments on a range of grid maps demonstrate a strong improvement from our combined approach. Against SRC, which remains an optimal solver with state-of-the-art speed, the performance improvement of our new system ranges from comparable to more than one order of magnitude faster.

ICAPS Conference 2017 Conference Paper

Compressed Path Databases with Ordered Wildcard Substitutions

• Matteo Salvetti
• Adi Botea
• Alessandro Saetti
• Alfonso Emilio Gerevini

Compressed path databases (CPDs) are a state-of-the-art approach to path planning, a core AI problem. In the Grid-based Path Planning Competition, the CPD-based SRC path planning system was the fastest competitor with respect to both computing full optimal paths and computing the first moves of an optimal path. However, on large maps, CPDs can require a significant amount of memory, which can be a serious practical bottleneck. We present an approach that significantly reduces the size of a CPD. Our approach replaces part of the data encoded in a CPD with wildcards ("don’t care" symbols), maintaining the ability to compute optimal paths for all pairs of nodes of an undirected graph. We show that using wildcards in a way that maximizes the memory savings is NP-hard. We consider heuristics that achieve a good performance in practice. We implement our ideas on top of SRC and provide a detailed empirical analysis. Average memory savings can reach a factor of 2. Our first-k-moves lag (i. e. , the time before knowing the first k optimal forward moves) increases, but it can be kept within competitive values. The speed of computing full optimal paths improves slightly.

SoCS Conference 2017 Conference Paper

On Realizing Planning Programs in Domains with Dead-End States

• Federico Falcone
• Alfonso Emilio Gerevini
• Alessandro Saetti

Agent planning programs are finite-state programs, possibly containing loops, whose atomic instructions consist of a guard, a maintenance goal, and an achievement goal, which act as precondition-invariance-postcondition assertions in program specification. The execution of such programs requires generating plans that meet the goals specified in the atomic instructions, while respecting the program control flow. Recently, De Giacomo et al. (2016) presented a technique, based on iteratively solving classical planning problems with action costs, for realizing planning programs in deterministic domains. Such a technique works generally well for domains with no or very few dead-end states. In this paper, we propose an enhancement of this technique to handle deterministic domains that have potentially many dead-end states, and we study the effectiveness of our technique through an experimental analysis.

AIJ Journal 2016 Journal Article

Agent planning programs

• Giuseppe De Giacomo
• Alfonso Emilio Gerevini
• Fabio Patrizi
• Alessandro Saetti
• Sebastian Sardina

This work proposes a novel high-level paradigm, agent planning programs, for modeling agents behavior, which suitably mixes automated planning with agent-oriented programming. Agent planning programs are finite-state programs, possibly containing loops, whose atomic instructions consist of a guard, a maintenance goal, and an achievement goal, which act as precondition-invariance-postcondition assertions in program specification. Such programs are to be executed in possibly nondeterministic planning domains and their execution requires generating plans that meet the goals specified in the atomic instructions, while respecting the program control flow. In this paper, we define the problem of automatically synthesizing the required plans to execute an agent planning program, propose a solution technique based on model checking of two-player game structures, and use it to characterize the worst-case computational complexity of the problem as EXPTIME-complete. Then, we consider the case of deterministic domains and propose a different technique to solve agent planning programs, which is based on iteratively solving classical planning problems and on exploiting goal preferences and plan adaptation methods. Finally, we study the effectiveness of this approach for deterministic domains through an experimental analysis on well-known planning domains.

ICAPS Conference 2015 Conference Paper

Identifying and Exploiting Features for Effective Plan Retrieval in Case-Based Planning

• Mauro Vallati
• Ivan Serina
• Alessandro Saetti
• Alfonso Emilio Gerevini

Case-Based planning can fruitfully exploit knowledge gained by solving a large number of problems, storing the corresponding solutions in a plan library and reusing them for solving similar planning problems in the future. Case-based planning is extremely effective when similar reuse candidates can be efficiently chosen. In this paper, we study an innovative technique based on planning problem features for efficiently retrieving solved planning problems (and relative plans) from large plan libraries. Since existing planning features are not always able to effectively distinguish between problems within the same planning domain, we introduce anew class of features. Our experimental analysis shows that the proposed features-based retrieval approach can significantly improve the performance of a state-of-the-art case-based planning system.

ECAI Conference 2014 Conference Paper

A Privacy-preserving Model for the Multi-agent Propositional Planning Problem

• Andrea Bonisoli
• Alfonso Emilio Gerevini
• Alessandro Saetti
• Ivan Serina

SoCS Conference 2013 Conference Paper

Automatic Generation of Efficient Domain-Optimized Planners from Generic Parametrized Planners

• Mauro Vallati
• Chris Fawcett
• Alfonso Emilio Gerevini
• Holger H. Hoos
• Alessandro Saetti

When designing state-of-the-art, domain-independent planning systems, many decisions have to be made with respect to the domain analysis or compilation performed during preprocessing, the heuristic functions used during search, and other features of the search algorithm. These design decisions can have a large impact on the performance of the resulting planner. By providing many alternatives for these choices and exposing them as parameters, planning systems can in principle be configured to work well on different domains. However, planners are typically used in default configurations that have been chosen because of their good average performance over a set of benchmark domains, with limited experimentation over the potentially huge range of possible configurations. In this work, we propose a general framework for automatically configuring a parameterized planner, and show that substantial performance gains can be achieved. We apply the framework to the well-known LPG planner, which in the context of this work was expanded to 62 parameters and over 6. 5 x 10^17 possible configurations. By using this highly parameterized planning system in combination with the state-of-the-art automatic algorithm configuration procedure ParamILS, excellent performance on a broad range of well-known benchmark domains was achieved, as also witnessed by the results of the learning track of the 7th International Planning Competition.

ECAI Conference 2012 Conference Paper

Case-based Planning for Problems with Real-valued Fluents: Kernel Functions for Effective Plan Retrieval

• Alfonso Emilio Gerevini
• Alessandro Saetti
• Ivan Serina

Case-based planning (CBP) re-uses existing plans as a starting point to solve new planning problems. In this work, we address CBP for planning in PDDL domains with real-valued fluents, that are essential to model real-world problems involving continuous resources. Specifically, we propose some new heuristic techniques for retrieving a plan from a library of existing plans that is promising for a new given planning problem, i. e. , that can be efficiently adapted to solve the new problem. The effectiveness of these techniques, which derive much of their power from the use of the numerical information in the planning problem specification and in the library plans, is then evaluated by an experimental analysis.

ICAPS Conference 2011 Conference Paper

An Effective Approach to Realizing Planning Programs

• Alfonso Emilio Gerevini
• Fabio Patrizi
• Alessandro Saetti

Planning programs are loose, high-level, declarative representations of the behavior of agents acting in a domain and following a path of goals to achieve. Such programs are specified through transition systems that can include cycles and decisions to make at certain points. We investigate a new effective approach for solving the problem of realizing a planning program, i. e. , informally, for finding and combining a collection of plans that guarantee the planning program executability. We focus on deterministic domains and propose a general algorithm that solves the problem exploiting a planning technique handling goal constraints and preferences. A preliminary experimental analysis indicates that our approach dramatically outperforms the existing method based on formal verification and synthesis techniques.

AIJ Journal 2011 Journal Article

Computing the minimal relations in point-based qualitative temporal reasoning through metagraph closure

• Alfonso E. Gerevini
• Alessandro Saetti

Computing the minimal representation of a given set of constraints (a CSP) over the Point Algebra (PA) is a fundamental temporal reasoning problem. The main property of a minimal CSP over PA is that the strongest entailed relation between any pair of variables in the CSP can be derived in constant time. We study some new methods for solving this problem which exploit and extend two prominent graph-based representations of a CSP over PA: the timegraph and the series-parallel (SP) metagraph. Essentially, these are graphs partitioned into sets of chains and series-parallel subgraphs, respectively, on which the search is supported by a metagraph data structure. The proposed approach is based on computing the metagraph closure for these representations, which can be accomplished by some methods studied in the paper. In comparison with the known techniques based on enforcing path consistency, under certain conditions about the structure of the input CSP and the size of the generated metagraph, the proposed metagraph closure approach has better worst-case time and space complexity. Moreover, for every sparse CSP over the convex PA, the time complexity is reduced to O ( n 2 ) from O ( n 3 ), where n is the number of variables involved in the CSP. An extensive experimental analysis presented in the paper compares the proposed techniques and other known algorithms. These experimental results identify the best performing methods and show that, in practice, for CSPs exhibiting chain or SP-graph structure and randomly generated (both sparse and dense) CSPs, the metagraph closure approach is significantly faster than the approach based on enforcing path consistency.

ICAPS Conference 2010 Conference Paper

Temporal Planning with Problems Requiring Concurrency through Action Graphs and Local Search

• Alfonso Emilio Gerevini
• Alessandro Saetti
• Ivan Serina

We present an extension of the planning framework based on action graphs and local search to deal with PDDL2. 1 temporal problems requiring concurrency, while previously the approach could only solve problems admitting a sequential solution. The paper introduces a revised plan representation supporting concurrency and some new search techniques using it, which are implemented in a new version of the LPG planner. An experimental analysis indicates that the proposed approach is suitable to temporal planning with requiring concurrency and is competitive with state-of-the-art planners.

ICAPS Conference 2009 Conference Paper

An Automatically Configurable Portfolio-based Planner with Macro-actions: PbP

• Alfonso Emilio Gerevini
• Alessandro Saetti
• Mauro Vallati

While several powerful domain-independent planners have recently been developed, no one of these clearly outperforms all the others in every known benchmark domain. We present PbP, a multi-planner which automatically configures a portfolio of planners by (1) computing some sets of macro-actions for every planner in the portfolio, (2) selecting a promising combination of planners in the portfolio and relative useful macro-actions, and (3) defining some running time slots for their round-robin scheduling during planning. The configuration relies on some knowledge about the performance of the planners in the portfolio and relative macro-actions which is automatically generated from a training problem set. PbP entered the learning track of IPC-2008 and was the overall winner of this competition track. An experimental study confirms the effectiveness of PbP, and shows that the learned configuration knowledge is useful for PbP.

AIJ Journal 2009 Journal Article

Deterministic planning in the fifth international planning competition: PDDL3 and experimental evaluation of the planners

• Alfonso E. Gerevini
• Patrik Haslum
• Derek Long
• Alessandro Saetti
• Yannis Dimopoulos

The international planning competition (IPC) is an important driver for planning research. The general goals of the IPC include pushing the state of the art in planning technology by posing new scientific challenges, encouraging direct comparison of planning systems and techniques, developing and improving a common planning domain definition language, and designing new planning domains and problems for the research community. This paper focuses on the deterministic part of the fifth international planning competition (IPC5), presenting the language and benchmark domains that we developed for the competition, as well as a detailed experimental evaluation of the deterministic planners that entered IPC5, which helps to understand the state of the art in the field. We present an extension of pddl, called pddl3, allowing the user to express strong and soft constraints about the structure of the desired plans, as well as strong and soft problem goals. We discuss the expressive power of the new language focusing on the restricted version that was used in IPC5, for which we give some basic results about its compilability into pddl2. Moreover, we study the relative performance of the IPC5 planners in terms of solved problems, CPU time, and plan quality; we analyse their behaviour with respect to the winners of the previous competition; and we evaluate them in terms of their capability of dealing with soft goals and constraints, and of finding good quality plans in general. Overall, the results indicate significant progress in the field, but they also reveal that some important issues remain open and require further research, such as dealing with strong constraints and computing high quality plans in metric-time domains and domains involving soft goals or constraints.

AIJ Journal 2008 Journal Article

An approach to efficient planning with numerical fluents and multi-criteria plan quality

• Alfonso E. Gerevini
• Alessandro Saetti
• Ivan Serina

Dealing with numerical information is practically important in many real-world planning domains where the executability of an action can depend on certain numerical conditions, and the action effects can consume or renew some critical continuous resources, which in pddl can be represented by numerical fluents. When a planning problem involves numerical fluents, the quality of the solutions can be expressed by an objective function that can take different plan quality criteria into account. We propose an incremental approach to automated planning with numerical fluents and multi-criteria objective functions for pddl numerical planning problems. The techniques in this paper significantly extend the framework of planning with action graphs and local search implemented in the lpg planner. We define the numerical action graph (NA-graph) representation for numerical plans and we propose some new local search techniques using this representation, including a heuristic search neighborhood for NA-graphs, a heuristic evaluation function based on relaxed numerical plans, and an incremental method for plan quality optimization based on particular search restarts. Moreover, we analyze our approach through an extensive experimental study aimed at evaluating the importance of some specific techniques for the performance of the approach, and at analyzing its effectiveness in terms of fast computation of a valid plan and quality of the best plan that can be generated within a given CPU-time limit. Overall, the results show that our planner performs quite well compared to other state-of-the-art planners handling numerical fluents.

ECAI Conference 2008 Conference Paper

Combining Domain-Independent Planning and HTN Planning: The Duet Planner

• Alfonso Emilio Gerevini
• Ugur Kuter
• Dana S. Nau
• Alessandro Saetti
• Nathaniel Waisbrot

Despite the recent advances in planning for classical domains, the question of how to use domain knowledge in planning is yet to be completely and clearly answered. Some of the existing planners use domain-independent search heuristics, and some others depend on intensively-engineered domain-specific knowledge to guide the planning process. In this paper, we describe an approach to combine ideas from both of the above schools of thought. We present Duet, our planning system that incorporates the ability of using hierarchical domain knowledge in the form of Hierarchical Task Networks (HTNs) as in SHOP2 [14] and using domain-independent local search techniques as in LPG [8]. In our experiments, Duet was able to solve much larger problems than LPG could solve, with only minimal domain knowledge encoded in HTNs (much less domain knowledge than SHOP2 needed to solve those problems by itself).

IJCAI Conference 2005 Conference Paper

Integrating Planning and Temporal Reasoning for Domains with Durations and Time Windows

• Alfonso Gerevini
• Alessandro Saetti
• Ivan

The treatment of exogenous events in planning is practically important in many domains. In this paper we focus on planning with exogenous events that happen at known times, and affect the plan actions by imposing that the execution of certain plan actions must be during some time windows. When actions have durations, handling such constraints adds an extra difficulty to planning, which we address by integrating temporal reasoning into planning. We propose a new approach to planning in domains with durations and time windows, combining graph-based planning and disjunctive constraint-based temporal reasoning. Our techniques are implemented in a planner that took part in the 4th International Planning Competition showing very good performance in many benchmark problems.

ICAPS Conference 2004 Conference Paper

An Empirical Analysis of Some Heuristic Features for Local Search in LPG

• Alfonso Emilio Gerevini
• Alessandro Saetti
• Ivan Serina

LPGis a planner that performed very well in the last International planning competition (2002). The system is based on a stochastic local search procedure, and it incorporates several heuristic features. In this paper we experimentally analyze the most important of them with the goal of understanding and evaluating their impact on the performance of the planner. In particular, we examine three heuristic functions for evaluating the search neighborhood and some settings of the "noise" parameter, that randomizes the next search step for escaping from local minima. Moreover, we present and analyze additional heuristic techniques for restricting the search neighborhood and for selecting the next inconsistency to handle. The experimental results show that the use of such techniques significantly improves the performance of the planner.

ECAI Conference 2004 Conference Paper

Planning with Numerical Expressions in LPG

• Alfonso Emilio Gerevini
• Alessandro Saetti
• Ivan Serina

ICAPS Conference 2003 Conference Paper

Local Search Techniques for Temporal Planning in LPG

• Alfonso Emilio Gerevini
• Ivan Serina
• Alessandro Saetti
• Sergio Spinoni

We present some techniques for planning in temporal domains specified with the recent standard languange PDDL2. 1. These techniques are implemented in LPG, a fully-automated system that took part in the third International Planning Competition (Toulouse, 2002) showing excellent performance. The planner is based on a stochastic local search method and on a graph-based representation called "Temporal Action Graphs" (TA-graphs). In this paper we present some new heuristics to guide the search in LPG using this representation. An experimental analysis of the performance of LPG on a large set of test problems used in the competition shows that our techniques can be very effective, and that often our planner outperforms all other fully-automated temporal planners that took part in the contest.