Ivan Serina

AAAI Conference 2026 Conference Paper

Learning Heuristic Functions with Graph Neural Networks for Numeric Planning

• Valerio Borelli
• Alfonso Gerevini
• Enrico Scala
• Ivan Serina

In this paper, we investigate the application of heuristics based on Graph Neural Networks (GNNs) to lifted numeric planning problems, an area that has been relatively unexplored. Building upon the GNN approach for learning general policies proposed by Ståhlberg, Bonet, and Geffner (2022b), we extend the architecture to make it sensitive to the numeric components inherent in the planning problems we address. We achieve this by observing that, although the state space of a numeric planning problem is infinite, the finite subgoal structure of the problem can be incorporated into the architecture, enabling the construction of a finite structure. Instead of learning general policies, we train our models to serve as heuristics within a best-first search algorithm. We explore various configurations of this architecture and demonstrate that the resulting heuristics are highly informative and, in certain domains, offer a better trade-off between guidance and computational cost compared to state-of-the-art heuristics.

ECAI Conference 2025 Conference Paper

Improving Resilient Planning Through Landmarks and Regressed State Formulas

• Alberto Rovetta
• Diego Aineto
• Alfonso Emilio Gerevini
• Enrico Scala
• Ivan Serina

In real-world scenarios, the successful execution of an agent’s planned actions is not always guaranteed, as actions may fail in unpredictable ways that are not explicitly modeled. To address this challenge, the concept of Resilient Planning and the RESPLAN framework were introduced focusing on the generation of k-resilient plans that enable an agent to reach its goals even in the presence of up to k execution failures. In this paper, we propose a new version of the RESPLAN planning algorithm based on two significant enhancements. The first incorporates landmarks into a pruning strategy, enabling the planner to avoid unnecessary explorations and yielding substantial performance gains, especially when no resilient plan exists. The second introduces a planning adaptation strategy exploiting regressed state formulas to support the search process during (re)planning, reducing the number of iterations required when a resilient plan does exist. We compare our methods against RESPLAN and other baselines, demonstrating substantial improvements across multiple domains.

AAMAS Conference 2025 Conference Paper

Towards Efficient Online Goal Recognition through Deep Learning

• Lorenzo Serina
• Mattia Chiari
• Alfonso Emilio Gerevini
• Luca Putelli
• Ivan Serina

Online goal recognition (OGR) is the task of understanding the intention of an agent as it executes a plan, recognizing its goal every time it performs a new action. This task is important in different contexts, such as applications of cyber-security and human-robot collaboration. An effective OGR system should (i) compute the correct goal of the agent as early as possible with respect to the agent’s performed actions, and (ii) perform fast, given that, while the OGR system infers the agent’s goal, the agent keeps executing the plan. In this paper, we propose a deep-learning approach to OGR based on Recurrent Neural Networks. The approach is implemented in a new system that learns to predict the goal of an agent acting in a given planning domain using a training dataset for the domain. We propose a method that exploits planning-related knowledge for designing a training dataset that is effective for the OGR and for improving the system performance. An experimental evaluation of our system on several benchmark domains shows that it performs generally better than the state-of-the-art in terms of accuracy and execution time, considering both the requirements (i) and (ii).

NeSy Conference 2024 Conference Paper

Enhancing GPT-Based Planning Policies by Model-Based Plan Validation

• Nicholas Rossetti
• Massimiliano Tummolo
• Alfonso Emilio Gerevini
• Matteo Olivato
• Luca Putelli
• Ivan Serina

Abstract Despite Large Language Models (LLMs) have revolutionised Natural Language Processing (NLP), their capability of performing logical reasoning and automated planning is still debated. In this context, the state of the art is PlanGPT, a GPT-2 model specifically trained for planning tasks. This recent approach provides GPT-based planning policies with remarkable performance, but it can generate invalid plans containing violated action preconditions or unsatisfied goals. To address this limitation, we propose an extension of PlanGPT that integrates a plan validator into the generation process. The validator is exploited to prune invalid plan prefixes during the GPT token generation, obtaining a more robust and powerful solution to planning via GPT. We empirically evaluate the effectiveness of our approach and demonstrate its potential in various planning domains.

AAMAS Conference 2024 Conference Paper

Fast and Slow Goal Recognition

• Mattia Chiari
• Alfonso Emilio Gerevini
• Andrea Loreggia
• Luca Putelli
• Ivan Serina

Goal recognition is a crucial aspect of understanding the intentions and objectives of agents by observing some of their actions. The most prominent approaches to goal recognition can be divided into two main categories: (1) trustworthy systems, which exploit automated reasoning for computing plans compatible with the observed actions, and (2) swifter systems, which try to quickly infer goals, often overlooking complex cognitive processes, and have no formal guarantees of their results. This paper introduces a novel approach inspired by the dual process theory, which integrates these two techniques. A dual-process model is proposed, leveraging fast, experience-based recognition for immediate goal identification, and slow, deliberate analysis for deeper understanding. Machine learning techniques and classical planning techniques are employed to obtain this dual-process system. Experimental evaluations demonstrate the effectiveness of the approach, reducing the amount of resources required to compute a solution (e. g. , time to find a goal), while at the same time enhancing accuracy and robustness, especially in more complex scenarios.

ICAPS Conference 2024 Conference Paper

Learning General Policies for Planning through GPT Models

• Nicholas Rossetti
• Massimiliano Tummolo
• Alfonso Emilio Gerevini
• Luca Putelli
• Ivan Serina
• Mattia Chiari
• Matteo Olivato

Transformer-based architectures, such as T5, BERT and GPT, have demonstrated revolutionary capabilities in Natural Language Processing. Several studies showed that deep learning models using these architectures not only possess remarkable linguistic knowledge, but they also exhibit forms of factual knowledge, common sense, and even programming skills. However, the scientific community still debates about their reasoning capabilities, which have been recently tested in the context of automated AI planning; the literature presents mixed results, and the prevailing view is that current transformer-based models may not be adequate for planning. In this paper, we address this challenge differently. We introduce a GPT-based model customised for planning (PLANGPT) to learn a general policy for classical planning by training the model from scratch with a dataset of solved planning instances. Once PLANGPT has been trained for a domain, it can be used to generate a solution plan for an input problem instance in that domain. Our training procedure exploits automated planning knowledge to enhance the performance of the trained model. We build and evaluate our GPT model with several planning domains, and we compare its performance w. r. t. other recent deep learning techniques for generalised planning, demonstrating the effectiveness of the proposed approach.

ECAI Conference 2023 Conference Paper

Action-Failure Resilient Planning

• Diego Aineto
• Alessandro Gaudenzi
• Alfonso Emilio Gerevini
• Alberto Rovetta
• Enrico Scala
• Ivan Serina

In the real world, the execution of the actions planned for an agent is never guaranteed to succeed, as they can fail in a number of unexpected ways that are not explicitly captured in the planning model. Based on these observations, we introduce the task of finding plans for classical planning that are resilient to action execution failures. We refer to this problem as Resilient Planning and to its solutions as K-resilient plans; such plans guarantee that an agent will always be able to reach its goals (possibly by replanning alternative sequences of actions) as long as no more than K failures occur along the way. We also present RESPLAN, a new algorithm for Resilient Planning, and we compare its performance to methods based on compiling Resilient Planning to Fully-Observable-Non-Deterministic (FOND) planning.

ICAPS Conference 2023 Conference Paper

Falsification of Cyber-Physical Systems Using PDDL+ Planning

• Diego Aineto
• Enrico Scala
• Eva Onaindia
• Ivan Serina

This work explores the capabilities of current planning technologies to tackle the falsification of safety requirements for cyber-physical systems. Cyber-physical systems are systems where software and physical processes interact over time, and their requirements are commonly specified in temporal logic with time bounds. Roughly, falsification is the process of finding a trajectory of the cyber-physical system that violates the safety requirements, and it is a task typically tackled with black-box algorithms. We analyse the challenges posed by industry-driven falsification benchmarks taken from the ARCH-COMP competition, and propose a first attempt to deal with these problems through PDDL+ planning instead. Our experimental analysis on a selection of these problems provides empirical evidence on the feasibility and effectiveness of planning-based approaches, whilst also identifying the main areas of improvement.

ICAPS Conference 2023 Conference Paper

Goal Recognition as a Deep Learning Task: The GRNet Approach

• Mattia Chiari
• Alfonso Emilio Gerevini
• Francesco Percassi
• Luca Putelli
• Ivan Serina
• Matteo Olivato

Recognising the goal of an agent from a trace of observations is an important task with many applications. The state-of-the-art approach to goal recognition (GR) relies on the application of automated planning techniques. We study an alternative approach, called GRNet, where GR is formulated as a classification task addressed by machine learning. GRNet is primarily aimed at solving GR instances more accurately and more quickly by learning how to solve them in a given domain, which is specified by a set of propositions and a set of action names. The goal classification instances in the domain are solved by a Recurrent Neural Network (RNN). The only information required as input of the trained RNN is a trace of action labels, each one indicating just the name of an observed action. A run of the RNN processes a trace of observed actions to compute how likely it is that each domain proposition is part of the agent

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.

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.

IJCAI Conference 2022 Conference Paper

Explaining the Behaviour of Hybrid Systems with PDDL+ Planning

• Diego Aineto
• Eva Onaindia
• Miquel Ramirez
• Enrico Scala
• Ivan Serina

The aim of this work is to explain the observed behaviour of a hybrid system (HS). The explanation problem is cast as finding a trajectory of the HS that matches some observations. By using the formalism of hybrid automata (HA), we characterize the explanations as the language of a network of HA that comprises one automaton for the HS and another one for the observations, thus restricting the behaviour of the HS exclusively to trajectories that explain the observations. We observe that this problem corresponds to a reachability problem in model-checking, but that state-of-the-art model checkers struggle to find concrete trajectories. To overcome this issue we provide a formal mapping from HA to PDDL+ and show how to use an off-the-shelf automated planner. An experimental analysis over domains with piece-wise constant, linear and nonlinear dynamics reveals that the proposed PDDL+ approach is much more efficient than solving directly the explanation problem with model-checking solvers.

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

ICAPS Conference 2020 Conference Paper

Generating and Exploiting Cost Predictions in Heuristic State-Space Planning

• Francesco Percassi
• Alfonso Emilio Gerevini
• Enrico Scala
• Ivan Serina
• Mauro Vallati

This paper proposes and investigates a novel way of combining machine learning and heuristic search to improve domain-independent planning. On the learning side, we use learning to predict the plan cost of a good solution for a given instance. On the planning side, we propose a bound-sensitive heuristic function that exploits such a prediction in a state-space planner. Our function combines the input prediction (derived inductively) with some pieces of information gathered during search (derived deductively). As the prediction can sometimes be grossly inaccurate, the function also provides means to recognise when the provided information is actually misguiding the search. Our experimental analysis demonstrates the usefulness of the proposed approach in a standard heuristic best-first search schema.

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.

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

A General Approach for Configuring PDDL Problem Models

• Mauro Vallati
• Ivan Serina

The development of a large number of domain-independentplanners is leading to the use of planning engines in a widerange of applications. This is despite the complexity issues inherent in plan generation, which are exacerbated by the separation of planner logic from domain knowledge. However, this separation supports the use of reformulation and configuration techniques, which transform the model representation in order to improve the planner's performance. In this paper, we investigate how the performance of domain-independent planners can be improved by problem model configuration. We introduce a fully automated method for this configuration task, that considers problem-specific aspects extracted by exploiting a problem- and domain-independent representation of the instance. Our extensive experimental analysis shows that this reformulation technique can have a significant impact on planners' performance.

AIIM Journal 2018 Journal Article

Automatic classification of radiological reports for clinical care

• Alfonso Emilio Gerevini
• Alberto Lavelli
• Alessandro Maffi
• Roberto Maroldi
• Anne-Lyse Minard
• Ivan Serina
• Guido Squassina

Radiological reporting generates a large amount of free-text clinical narratives, a potentially valuable source of information for improving clinical care and supporting research. The use of automatic techniques to analyze such reports is necessary to make their content effectively available to radiologists in an aggregated form. In this paper we focus on the classification of chest computed tomography reports according to a classification schema proposed for this task by radiologists of the Italian hospital ASST Spedali Civili di Brescia. The proposed system is built exploiting a training data set containing reports annotated by radiologists. Each report is classified according to the schema developed by radiologists and textual evidences are marked in the report. The annotations are then used to train different machine learning based classifiers. We present in this paper a method based on a cascade of classifiers which make use of a set of syntactic and semantic features. The resulting system is a novel hierarchical classification system for the given task, that we have experimentally evaluated.

SoCS Conference 2016 Conference Paper

Partial Delete Relaxation, Unchained: On Intractable Red-Black Planning and Its Applications

• Daniel Gnad 0001
• Marcel Steinmetz
• Mathäus Jany
• Jörg Hoffmann 0001
• Ivan Serina
• Alfonso Emilio Gerevini

Partial delete relaxation methods, like red-black planning, are extremely powerful, allowing in principle to force relaxed plans to behave like real plans in the limit. Alas, that power has so far been chained down by the computational overhead of the use as heuristic functions, necessitating to compute a relaxed plan on every search state. For red-black planning in particular, this has entailed an exclusive focus on tractable fragments. We herein unleash the power of red-black planning on two applications not necessitating such a restriction: (i) generating seed plans for plan repair, and (ii) proving planning task unsolvability. We introduce a method allowing to generate red-black plans for arbitrary inputs — intractable red-black planning — and we evaluate its use for (i) and (ii). With (i), our results show promise and outperform standard baselines in several domains. With (ii), we obtain substantial, in some domains dramatic, improvements over the state of the art.

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

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.

AIJ Journal 2012 Journal Article

Generating diverse plans to handle unknown and partially known user preferences

• Tuan Anh Nguyen
• Minh Do
• Alfonso Emilio Gerevini
• Ivan Serina
• Biplav Srivastava
• Subbarao Kambhampati

Current work in planning with preferences assumes that user preferences are completely specified, and aims to search for a single solution plan to satisfy these. In many real world planning scenarios, however, the user may provide no knowledge or at best partial knowledge of her preferences with respect to a desired plan. In such situations, rather than presenting a single plan as the solution, the planner must instead provide a set of plans containing one or more plans that are similar to the one that the user really prefers. In this paper, we first propose the usage of different measures to capture the quality of such plan sets. These are domain-independent distance measures based on plan elements (such as actions, states, or causal links) if no knowledge of the user preferences is given, or the Integrated Convex Preference (ICP) measure in case incomplete knowledge of such preferences is provided. We then investigate various heuristic approaches to generate sets of plans in accordance with these measures, and present empirical results that demonstrate the promise of our methods.

ICAPS Conference 2012 Conference Paper

Using AI Planning to Enhance E-Learning Processes

• Antonio Garrido 0002
• Lluvia Morales
• Ivan Serina

This work describes an approach that automatically extracts standard metadata information from e-learning contents, combines it with the student preferences/goals and creates PDDL planning domains+problems. These PDDL problems can be solved by current planners, although we motivate the use and benefits of case-based planning techniques, to obtain fully tailored learning routes that significantly enhance the learning process. During the execution of a given route, a monitoring phase is used to detect discrepancies, i. e. flaws that prevent the student from continuing with the original plan. In such a situation, an adaptation mechanism becomes necessary to fix the flaws, while also trying to minimise the differences between the original and the new route. We have integrated this approach on top of Moodle and experimented with 100 benchmark problems to evaluate the quality, scalability and viability of the system.

AIJ Journal 2010 Journal Article

Kernel functions for case-based planning

• Ivan Serina

Case-based planning can take advantage of former problem-solving experiences by storing in a plan library previously generated plans that can be reused to solve similar planning problems in the future. Although comparative worst-case complexity analyses of plan generation and reuse techniques reveal that it is not possible to achieve provable efficiency gain of reuse over generation, we show that the case-based planning approach can be an effective alternative to plan generation when similar reuse candidates can be chosen. In this paper we describe an innovative case-based planning system, called OAKplan, which can efficiently retrieve planning cases from plan libraries containing more than ten thousand cases, choose heuristically a suitable candidate and adapt it to provide a good quality solution plan which is similar to the one retrieved from the case library. Given a planning problem we encode it as a compact graph structure, that we call Planning Encoding Graph, which gives us a detailed description of the topology of the planning problem. By using this graph representation, we examine an approximate retrieval procedure based on kernel functions that effectively match planning instances, achieving extremely good performance in standard benchmark domains. The experimental results point out the effect of the case base size and the importance of accurate matching functions for global system performance. Overall, we show that OAKplan is competitive with state-of-the-art plan generation systems in terms of number of problems solved, CPU time, plan difference values and plan quality when cases similar to the current planning problem are available in the plan library.

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.

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.

IJCAI Conference 2007 Conference Paper

• Biplav Srivastava
• Subbarao Kambhampati
• Tuan A. Nguyen
• Minh Binh Do
• Alfonso Gerevini
• Ivan Serina

In many planning situations, a planner is required to return a diverse set of plans satisfying the same goals which will be used by the external systems collectively. We take a domain-independent approach to solving this problem. We propose different domain independent distance functions among plans that can provide meaningful insights about the diversity in the plan set. We then describe how two representative state-of-the-art domain independent planning approaches -- one based on compilation to CSP, and the other based on heuristic local search -- can be adapted to produce diverse plans. We present empirical evidence demonstrating the effectiveness of our approaches.

ICAPS Conference 2006 Conference Paper

Plan Stability: Replanning versus Plan Repair

• Maria Fox 0001
• Alfonso Emilio Gerevini
• Derek Long
• Ivan Serina

The ultimate objective in planning is to construct plans for execution. However, when a plan is executed in a real environment it can encounter differences between the expected and actual context of execution. These differences can manifest as divergences between the expected and observed states of the world, or as a change in the goals to be achieved by the plan. In both cases, the old plan must be replaced with a new one. In replacing the plan an important consideration is plan stability. We compare two alternative strategies for achieving the {em stable} repair of a plan: one is simply to replan from scratch and the other is to adapt the existing plan to the new context. We present arguments to support the claim that plan stability is a valuable property. We then propose an implementation, based on LPG, of a plan repair strategy that adapts a plan to its new context. We demonstrate empirically that our plan repair strategy achieves more stability than replanning and can produce repaired plans more efficiently than replanning.

AAAI Conference 2005 Conference Paper

Fast Planning in Domains with Derived Predicates: An Approach Based on Rule-Action Graphs and Local Search

• Alfonso Gerevini
• Ivan Serina

The ability to express “derived predicates” in the formalization of a planning domain is both practically and theoretically important. In this paper, we propose an approach to planning with derived predicates where the search space consists of “Rule-Action Graphs”, particular graphs of actions and rules representing derived predicates. We present some techniques for representing rules and reasoning with them, which are integrated into a method for planning through local search and rule-action graphs. We also propose some new heuristics for guiding the search, and some experimental results illustrating the performance of our approach. Our proposed techniques are implemented in a planner that took part in the fourth International Planning Competition showing 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.

ICAPS Conference 2002 Conference Paper

LPG: A Planner Based on Local Search for Planning Graphs with Action Costs

• Alfonso Emilio Gerevini
• Ivan Serina

We present LPG, a fast planner using local search for solving planning graphs. LPG can use various heuristics based on a parametrized objective function. These parameters weight different types of inconsistencies in the partial plan represented by the current search state, and are dynamically evaluated during search using Lagrange multipliers. LPG’s basic heuristic was inspired by Walksat, which in Kautz and Selman’s Blackbox can be used to solve the SAT-encoding of a planning graph. An advantage of LPG is that its heuristics exploit the structure of the planning graph, while Blackbox relies on general heuristics for SAT-problems, and requires the translation of the planning graph into propositional clauses. Another major difference is that LPG can handle action costs to produce good quality plans. This is achieved by an "anytime" process minimizing an objective function based on the number of inconsistencies in the partial plan and on its overall cost. The objective function can also take into account the number of parallel steps and the overall plan duration. Experimental results illustrate the efficiency of our approach showing, in particular, that for a set of well-known benchmark domains LPG is significantly faster than existing Graphplan-style planners.

ICAPS Conference 2000 Conference Paper

Fast Plan Adaptation through Planning Graphs: Local and Systematic Search Techniques

• Alfonso Emilio Gerevini
• Ivan Serina

Fast plan adaptation is important in many AIapplications. Froma theoretical point of view, in the worst case adapting an existing plan to solve a new problemis no more efficient than a complete regeneration of the plan. However, in practice plan adaptation can be muchmoreefficient than plan generation, especially whenthe adapted plan can be obtained by performinga limited amountof changes to the original plan. In this paper we propose a domain-independent method for plan adaptation that combines t~ techniques. The first technique modifies the original plan by replanning within limited temporal window-scontalning portions of the plan that need to be revised. Each windowis associated with a particular replanning subproblemthat is solved using systematic search for Planning Graphs. The second technique modifies the original plan using local search for Action Graphs, which are particular subgraphs of a planning graph. This technique can be used either for solving a plan adaptation task or as a preprocessing for reducing the numberof inconsistencies in the input plan. Experimental results showthat in practice adapting a plan using our techniquescan be very efficient.

AAAI Conference 1999 Conference Paper

Fast Planning through Greedy Action Graphs

• Alfonso Gerevini
• Ivan Serina
• Univeritá di Brescia

Domain-independentplanning is a notoriously hard search problem. Several systematic search techniques have been proposed in the context of various formalisms. However, despite their theoretical completeness, in practice these algorithms are incompletebecause for many problemsthe search space is too large to be (evenpartially) explored. In this paper we propose a newsearch method in the context of Blumand Furst’s planning graph approach, whichis based on local search. Local search techniques are incomplete, but in practice they can efficiently solve problemsthat are unsolvablefor current systematic search methods. Weintroduce three heuristics to guide the local search (Walkplan, Tabuplan and T-Walkplan), and we propose two methods for combininglocal andsystematic search. Our techniques are implementedin a system called GPG, which can be used for both plan-generation and plan-adaptation tasks. Experimentalresults show that GPG can efficiently solve problemsthat are very hard for current planners based on planning graphs.