Publications

Conference papers:

• Anas El Kouaiti, Francesco Percassi, Alessandro Saetti, Thomas Leo McCluskey, Mauro Vallati, PDDL+ Models for Deployable yet Effective Traffic Signal Optimisation. In “Proceedings of the Thirty-fourth International Conference on Automated Planning & Scheduling (ICAPS-24)”, Banff, Canada, 1–6 giugno, 2024.

  • • Abstract: 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. 

• Leonardo Lamanna, Luciano Serafini, Mohamadreza Faridghasemnia, Alessandro Saffiotti, Alessandro Saetti, Alfonso Gerevini, Paolo Traverso, Learning to Act for Perceiving in Partially Unknown Environments. In “Proceedings of the Thirty-second International Joint Conference on Artificial Intelligence (IJCAI-23)”, Macao, Cina, 19–25 agosto, 2023.

  • • Abstract: 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. 

• Leonardo Lamanna, Luciano Serafini, Mohamadreza Faridghasemnia, Alessandro Saffiotti, Alessandro Saetti, Alfonso Gerevini, Paolo Traverso, Planning for Learning Object Properties. In “Proceedings of the Thirty-seventh AAAI Conference on Artificial Intelligence (AAAI-23)”, Wash- ington, USA, 7–14 febbraio, 2023. AAAI Press.

  • • Abstract: 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. 

• Alfonso Gerevini, Nir Lipovetzky, Francesco Percassi, Alessandro Saetti, Ivan Serina, On the use of Width-based search for Multi Agent Privacy-preserving Planning. In “Proceedings of the 15th International Symposium on Combinatorial Search (SoCS-22)”, Vienna, Austria, 21–23 luglio, 2022. AAAI Press.

  • • Abstract: 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' privacy and performance. 

• Leonardo Lamanna, Luciano Serafini, Alessandro Saetti, Alfonso Gerevini, Paolo Traverso, Online Grounding of Symbolic Planning Domains in Unknown Environments, In “Proceedings of the Nineteenth International Conference on Knowledge Representation and Reasoning (KR- 22)”, Haifa, Israel, 31 luglio – 5 agosto, 2022.

  • • Abstract: 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 needed 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 the state of the art methods on object goal navigation based on reinforcement learning, showing better performances.

• Alessandro Saetti, Enrico Scala, Optimising the Stability in Plan Repair via Compilation. In “Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling (ICAPS-22)”, Singapore Online, 13–24 giugno, 2022. AAAI Press.

  • • Abstract: 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.

• Leonardo Lamanna, Alessandro Saetti, Luciano Serafini, Alfonso Gerevini, Paolo Traverso, Online Learning of Action Models for PDDL Planning, In “Proceedings of the Thirtieth Joint Conference on Artificial Intelligence (IJCAI-21)”, Montreal, Canada Online, 21–26 agosto, 2021.

  • • Abstract: 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.

• Leonardo Lamanna, Alfonso Gerevini, Alessandro Saetti, Luciano Serafini, Paolo Traverso, On-line Learning of Planning Domains from Sensor Data in PAL: Scaling up to Large State Spaces. In “Proceedings of the Thirty-fifth AAAI Conference on Artificial Intelligence (AAAI- 21)”, Vancouver, Canada Online, 2–9 febbraio, 2021. AAAI Press.

  • • Abstract: 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 state transition 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 the previous work.

• Alfonso Gerevini, Alessandro Saetti, An Interactive Tool for Plan Generation, Inspection, and Visualization. In “Knowledge Engineering Tools and Techniques for AI Planning”, capitolo 7, pp. 127–156, 2020, Springer.

  • • Abstract: In mixed-initiative planning systems, humans and AI planners work together for generating satisfactory solution plans or making easier solving hard planning problems, which otherwise would require much greater human planning efforts or much more computational resources. In this approach to plan generation, it is important to have effective plan visualization capabilities, as well to support the user with some interactive capabilities for the human intervention in the planning process. This paper presents an implemented interactive tool for the visualization, generation, and revision of plans. The tool provides an environment through which the user can interact with a state-of-the-art domain-independent planner, and obtain an effective visualization of a rich variety of information during planning, including the reasons why an action is being planned or why its execution in the current plan is expected to fail, the trend of the resource consumption in the plan, and the temporal scheduling of the planned actions. Moreover, the proposed tool supports some ways of human intervention during the planning process to guide the planner towards a solution plan, or to modify the plan under construction and the problem goals.

• Enrico Scala, Alessandro Saetti, Ivan Serina, Alfonso Gerevini, Search-Guidance Mechanisms for Numeric Planning through Subgoaling Relaxation. In “Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling (ICAPS-20)”, Nancy, Francia Online, 14–19 giugno, 2020. AAAI Press.

  • • Abstract: 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.

• Shizhe Zhao, Mattia Chiari, Adi Botea, Alfonso Gerevini, Daniel Harabor, Alessandro Saetti, Peter. J. Stuckey, Bounded Suboptimal Path Planning with Compressed Path Databases. In “Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling (ICAPS-20)”, Nancy, Francia Online, 14–19 giugno, 2020. AAAI Press.

  • • Abstract: 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.

• Alfonso Gerevini, Nir Lipovetzky, Nico Peli, Francesco Percassi, Alessandro Saetti, Ivan Serina, Novelty Messages Filtering for Multi Agent Privacy-preserving Planning, Proceedings of the Twelfth Annual Symposium on Combinatorial Search (SOCS-19), Napa, California (USA), 16–17 luglio, 2019. AAAI Press.

  • • Abstract: In multi-agent planning, agents jointly compute a plan that achieves mutual goals, keeping certain information private to the individual agents. Agents’ coordination is achieved through the transmission of messages. These messages can be a source of privacy leakage as they can permit a malicious agent to collect information about other agents’ actions and search states. In this paper, we investigate the usage of novelty techniques 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 the use of novelty based techniques can significantly reduce the number of messages transmitted among agents, better preserving their privacy and improving their performance. An experimental study analyses the effectiveness of our techniques and compares them with the state-of-the-art. Finally, we evaluate the robustness of our approach, considering different delays in the transmission of messages as they would occur in overloaded networks, due for example to massive attacks or critical situations.

• Alfonso Gerevini, Nir Lipovetzky, Francesco Percassi, Alessandro Saetti, Ivan Serina, Best-First Width Search for Multi Agent Privacy-preserving Planning, Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling (ICAPS-19), Berkeley, California (USA), 11–15 luglio, 2019. AAAI Press.

  • • Abstract: 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.

• Mattia Chiari, Shizhe Zhao, Adi Botea, Alfonso Gerevini, Daniel Harabor, Alessandro Saetti, Matteo Salvetti, Peter J. Stuckey, Cutting the Size of Compressed Path Databases With Wildcards and Redundant Symbols, Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling (ICAPS-19), Berkeley, California (USA), 11–15 luglio, 2019. AAAI Press.

  • • Abstract: 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-the-art 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.

• Gabriele Bazzotti, Alfonso Gerevini, Nir Lipovetzky, Francesco Percassi, Alessandro Saetti, Ivan Serina, Iterative Width Search for Multi Agent Privacy-Preserving Planning, Proceedings of the Seventeenth International Conference of the Italian Association for Artificial Intelligence (AI*IA-18), Trento, Italy, 20–23 novembre, 2018. Springer.

  • • Abstract: In multi-agent planning, preserving the agents’ privacy has become an increasingly popular research topic. In multi-agent privacy-preserving planning, agents jointly compute a plan that achieves mutual goals by keeping certain information private to the individual agents. Unfortunately, preserving the privacy of such information can severely restrict the accuracy of the heuristic functions used while searching for solutions. Recently, it has been shown that centralized planning based on Width-based search is a very effective approach over several benchmark domains, even when the search is driven by uninformed heuristics. In this paper, we investigate the usage of Width-based search in the context of (decentralised) multi-agent privacy-preserving planning, addressing the challenges related to the agents’ privacy and performance. An experimental study analyses the effectiveness of our techniques and compares them with the state-of-the-art.

• Matteo Salvetti, Adi Botea, Alfonso Gerevini, Daniel Harabor, Alessandro Saetti, Two-Oracle Optimal Path Planning on Grid Maps, Proceedings of the Twenty-Eigth International Conference on Automated Planning and Scheduling (ICAPS-18), Delft (Olanda), 24–29 giugno 2018. AAAI Press.

  • • Abstract: 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 SRC between the 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.

• Matteo Salvetti, Adi Botea, Alessandro Saetti, Alfonso Gerevini, Compressed Path Databases with Ordered Wildcard Substitutions, Proceedings of the Twenty-Seventh International Conference on Automated Planning and Scheduling (ICAPS-17), Pittsburgh (USA), 18–23 giugno 2017. AAAI Press.

  • • Abstract: 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.

• Federico Falcone, Alfonso Gerevini, Alessandro Saetti, On Realizing Planning Programs in Domains with Dead-end States, Proceedings of the Tenth Annual Symposium on Combinatorial Search (SOCS-17), Pittsburgh (USA), 16–17 giugno 2017. AAAI Press.

  • • Abstract: 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.

• • Mauro Vallati, Ivan Serina, Alessandro Saetti, Alfonso Gerevini, Identifying and Exploiting Features for Effective Plan Retrieval in Case-Based Planning, Proceedings of the Twenty-Fifth International Conference on Automated Planning and Scheduling (ICAPS-15), Jerusalem (Israel), 2015. (PDF file)

    • • Abstract: 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 - real number summarising potentially important property of the instance - 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 a new 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.

  • Andrea Bonisoli, Alfonso Gerevini, Alessandro Saetti, Ivan Serina, A Privacy-preserving Model for the Multi-agent Propositional Planning Problem, Proceedings of the Twenty-First European Conference on Artificial Intelligence (ECAI-14), Prague (Czech Republic), 2014. (PDF file)

    • • Abstract: Over the last years, the planning community has formalized several models and approaches to multi-agent (MA) planning. One of the main motivations in MA planning is that some or all agents have private knowledge that cannot be communicated to other agents during the planning process and the plan execution. In this paper, we propose a model that preserves the privacy of the involved agents, and discuss how the MA-A* search algorithm can be adapted to implement our model.

  • Alfonso Gerevini, Anna Roubickova, Alessandro Saetti, Ivan Serina, Offline and Online Plan Library Maintenance in Case-based Planning, Proceedings of the Thirteenth Conference of the Italian Association for Artificial Intelligence (AIIA-13), Turin (Italy), 2013. (PDF file)

    • • Abstract: One of the ways to address the high computational complexity of planning is reusing previously found solutions whenever they are applicable to the new problem with limited adaptation. To do so, a reuse planning system needs to store found solutions in a library of plans, also called a case base. The quality of such a library critically influences the performance of the planner, and therefore it needs to be carefully designed and created. For this reason, it may be 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 case base was originally designed for. In our ongoing research, we address the problem of maintaining the library of plans in a recent case-based planner called OAKplan. After having developed offline techniques to reduce an oversized library, we introduce here 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. The different investigated approaches and techniques are then experimentally evaluated and compared.

  • Mauro Vallati, Chris Fawcett, Alfonso Gerevini, Holger H. Hoos, Alessandro Saetti, Automatic Generation of Efficient Domain-Optimized Planners from Generic Parametrized Planners, Proceedings of the Sixth Annual Symposium on Combinatorial Search (SOCS-13), Leavenworth (WA), 2013. (PDF file)

    • • Abstract: 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.5x1017 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.

  • Alfonso Gerevini, Anna Roubickova, Alessandro Saetti, Ivan Serina, On the Plan-library Maintenance Problem in a Case-based Planner, Proceedings of the 21st International Conference on Case-Based Reasoning (ICCBR-13), Saratoga Springs (NY), 2013. (PDF file)

    • • Abstract: Case-based planning is an approach to planning where previous planning experience stored in a case base provides guidance to solving new problems. Such a guidance can be extremely useful when the new problem is very hard to solve, or the stored previous experience is highly valuable (because, e.g., it was provided and/or validated by human experts) and the system should try to reuse it as much as possible. However, as known in general case-based reasoning, the case base needs to be maintained at a manageable size, in order to avoid that the computational cost of querying it excessively grows, making the entire approach ineffective. We formally define the problem of case base maintenance for planning, discuss which criteria should drive a successful policy to maintain the case base, introduce some policies optimizing different criteria, and experimentally analyze their behavior by evaluating their effectiveness and performance.

  • Alfonso Gerevini, Alessandro Saetti, Ivan Serina, Case-based Planning for Problems with Real-valued Fluents: Kernel Functions for Effective Plan Retrieval, Proceedings of the 20th European Conference on Artificial Intelligence (ECAI-12), Montpellier (France), 2012. (PDF file)

    • • Abstract: 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.

  • Alfonso Gerevini, Alessandro Saetti, Fabio Patrizi, An Effective Approach to Realizing Planning Programs, Proceedings of the Twenty-First International Conference on Automated Planning and Scheduling (ICAPS-11), Freiburg (Germany), 2011. (PDF file)

    • • Abstract: 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.

  • Alfonso Gerevini, Alessandro Saetti, Ivan Serina, Temporal Planning with Problems Requiring Concurrency through Action Graphs and Local Search, Proceedings of the Twentieth International Conference on Automated Planning and Scheduling (ICAPS-10), Toronto (Canada), 2010. (PDF file)

    • • Abstract: 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.

  • Alfonso Gerevini, Alessandro Saetti, Mauro Vallati, An Automatically Configurable Portfolio-based Planner with Macro-actions: PbP, Proceedings of the Nineteenth International Conference on Automated Planning and Scheduling (ICAPS-09), Thessaloniki (Greece), 2009. (PDF file)

    • • Abstract: 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 (i) computing some sets of macro-actions for every planner in the portfolio, (ii) selecting a promising combination of planners in the portfolio and relative useful macro-actions, and (iii) 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.

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

    • • Abstract: 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 and using domain-independent local search techniques as in LPG. 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).

  • Alfonso Gerevini, Alessandro Saetti Efficient Computation of Minimal Point Algebra Constraints by Metagraph Closure, Proceedings of the 13th International Conference on Principles and Practice of Constraint Programming (CP-07), pp. 301-316, Providence (USA), 2007. (PDF file)

    • • Abstract: Computing the minimal network (or minimal CSP) representation of a given set of constraints over the Point Algebra (PA) is a fundamental reasoning problem. In this paper we propose a new approach to solving this task which exploits the timegraph representation of a CSP over PA. A timegraph is a graph partitioned into a set of chains on which the search is supported by a metagraph data structure. We introduce a new algorithm that, by making a particular closure of the metagraph, extends the timegraph with information that supports the derivation of the strongest implied constraint between any pair of point variables in constant time. The extended timegraph can be used as a representation of the minimal CSP. We also compare our method and known techniques for computing minimal CSPs over PA. For CSPs that are sparse or exhibit chain structure, our approach has a better worst-case time complexity. Moreover, an experimental analysis indicates that the performance improvements of our approach are practically very significant. This is the case especially for CSPs with a chain structure, but also for randomly generated (both sparse and dense) CSPs.

  • Alfonso Gerevini, Alessandro Saetti, Ivan Serina, Paolo Toninelli, Fast Planning in Domains with Derived Predicates: An Approach Based on Rule-Action Graphs and Local Search, Proceedings of the 20th National Conference on Artificial Intelligence (AAAI-05), pp. 1157-1162, Pittsburgh (USA), 2005. (PDF file)

    • • Abstract: The ability to express "derived predicates" in the formalization of a planning domain is both practically and theoretically important. We propose an approach to planning with derived predicates where the search space consists of particular graphs of actions and rules, called rule-action graphs, representing partial plans. We present some techniques for managing domain rules in the context of a local search process for rule-action graphs, and new heuristics for guiding the search. The proposed approach and techniques are implemented in a new version of the LPG planner, which took part in the fourth International Planning Competition showing good performance in many benchmark problems.

  • Alfonso Gerevini, Alessandro Saetti, Ivan Serina, Integrating Planning and Temporal Reasoning for Domains with Durations and Time Windows, Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI-05), pp. 1226-1235, Edinburgh (UK), 2005. (PDF file)

    • • Abstract: 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 add an extra difficulty to planning, which can be obtained by integrating temporal reasoning into planning. We propose a new approach to planning in domains with durations and time windows, which combines 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. 

  • Alfonso Gerevini, Alessandro Saetti, Ivan Serina, Planning with Numerical Expressions in LPG Proceedings of the 16th European Conference on Artificial Intelligence (ECAI-04), pp. 667-671, Valencia (Spain), 2004. (PDF file)

    • • Abstract: We present some techniques for handling planning problems with numerical expressions that can be specified using the standard planning language PDDL. These techniques are implemented in LPG, a fully-automated planner based on local search that was awarded at the third international planning competition (2002). First, we present a plan representation for handling numerical expressions called Numerical Action Graph (NA-graph). Then, we propose some extensions of LPG to guide a search process where the search states are NA-graphs. Finally, we give some experimental results showing that our techniques are very effective in terms of CPU-time or plan quality, and that they significantly improve the previous version of the planner.

  • Alfonso Gerevini, Alessandro Saetti, Ivan Serina, An Empirical Analysis of Some Heuristic Features for Local Search in LPG , Proceedings of the 14th International Conference on Automated Planning and Scheduling (ICAPS-04), pp. 171-180, Vancouver (Canada), 2004. (PDF file)

    • • Abstract: LPG is 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.

  • Alfonso Gerevini, Ivan Serina, Alessandro Saetti, Sergio Spinoni, Local Search for Temporal Planning in LPG, Proceedings of the 13th International Conference on Automated Planning & Scheduling (ICAPS-03), pp. 62-71, Trento (Italy), 2003. (PDF file)

    • • Abstract: We present some techniques for planning in temporal domains specified with the recent standard language 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.