Publications

Conference papers:

• 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.5x10¹⁷ 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.