Dipartimento di Ingegneria dell'Informazione
+39-030-3715521 
+39-030-380014 
saetti(AT)ing.unibs.it
Alessandro Saetti is assistant professor (ricercatore) in Information Processing Systems at the Dept. of Information Engineering of the University of Brescia, Italy. He has been working at the University of Brescia since 2002: from 2002 to 2005 was a Ph.D. student, from 2006 to 2008 a Postdoctoral Researcher and since 2008 he has been assistant professor.
He was a program committee member or served as a reviewer of many international workshops, conferences and journals. He co-organized the classical track of IPC-5 (The Fifth International Planning Competition), and AI*IA 2010 (The 11th Symposium of the Italian Association for the Artificial Intelligence); he was also co-chair of PlanSig 2010 (The 28th Workshop of the UK Planning and Scheduling Special Interest Group) and 1st AI*IA Doctoral Consortium; currently, he is a PC-member of RCRA-13 (The 20th RCRA International Workshop on Experimental Evaluation of Algorithms for solving problems with combinatorial explosion), SOCS-13 (The Sixth International Symposium on Combinatorial Search), ICAPS-13 (The 23rd International Conference on Automated Planning and Scheduling), AAAI-13 (The 27th National Conference on Artificial Intelligence), and IJCAI-13 (The 23rd International Joint Conference on Artificial Intelligence).
He is author or co-author of about 40 reviewed papers in various fields of Artificial Intelligence, which have been published in international journals (including "Artificial Intelligence" and "Journal of Artificial Intelligence Research") and conferences (including CP, ECAI, IJCAI, ICAPS, AAAI).
Most of his scientific work concerns the following aspects: design and analysis of languages for knowledge representation and automated reasoning, computational complexity analysis, development of efficient algorithmic techniques and data structures, implementation of innovative software systems and experimental analysis of the proposed algorithmic techniques. The software systems that he developed, LPG, LPG-td, PbP.s and PbP2.q have been awarderd at several editions of the Internation Planning Competition (IPC), which is an important scientific event organized in the context of the International Conference on Planning and Scheduling (ICAPS).
His research interests focus on temporal reasoning, constraint-based reasoning, anytime planning, machine learning for planning, mixed-initiative planning, plan execution, monitoring and repair, planning with resources and time constraints and HTN-planning.
Abstract: 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 propose some techniques for representing such rules and reasoning with them, which are integrated into a framework for planning through local search and rule-action graphs. We also present some heuristics for guiding the search of a rule-action graph representing a valid plan.
Finally, we analyze our approach through an extensive experimental study aimed at evaluating the importance of some specific techniques for the performance of the approach. The results of our experiments also show that our planner performs quite well compared to other state-of-the-art planners handling derived predicates.
Abstract: Computing the minimal representation of a given set of constraints (a CSP) over the Point Algebra (PA) is a fundamental temporal reasoning problem. The main property of a minimal CSP over PA is that the strongest entailed relation between any pair of variables in the CSP can be derived in constant time. We study some new methods for solving this problem which exploit and extend two prominent graph-based representations of a CSP over PA: the timegraph and the series-parallel (SP) metagraph. Essentially, these are graphs partitioned into sets of chains and series-parallel subgraphs, respectively, on which the search is supported by a metagraph data structure. The proposed approach is based on computing the metagraph closure for these representations, which can be accomplished by some methods studied in the paper. In comparison with the known techniques based on enforcing path consistency, under certain conditions about the structure of the input CSP and the size of the generated metagraph, the proposed metagraph closure approach has better worst-case time and space complexity. Moreover, for every sparse CSP over the convex PA, the time complexity is reduced to O(n2) from O(n3), where n is the number of variables involved in the CSP. An extensive experimental analysis presented in the paper compares the proposed techniques and other known algorithms. These experimental results identify the best performing methods and show that, in practice, for CSPs exhibiting chain or SP-graph structure and randomly generated (both sparse and dense) CSPs, the metagraph closure approach is significantly faster than the approach based on enforcing path consistency.
Abstract: Planning through local search and action graphs is a powerful approach to fully-automated planning which is implemented in the well-known LPG planner. The approach is based on a stochastic local search procedure exploring a space of partial plans and several heuristic features with different possible options. In this paper, we experimentally analyze the most important of them, with the goal of understanding and evaluating their impact on the performance of LPG, and of identifying default settings that work well on a large class of problems. In particular, we analyze several heuristic techniques for (a) evaluating the search neighborhood, (b) defining/restricting the search neighborhood, (c) selecting the next plan flaw to handle, (d) setting the "noise" parameter randomizing the search, and (e) computing reachability information that can be exploited by the heuristic functions used to evaluate the neighborhood elements. Some of these techniques were introduced in previous work on LPG, while others are new. Additional experimental results indicate that the current version of LPG using the identified best heuristic techniques as the default settings is competitive with the winner of the last (2008) International Planning Competition.
Abstract: The international planning competition (IPC) is an important driver for planning research. The general goals of the IPC include pushing the state of the art in planning technology by posing new scientific challenges, encouraging direct comparison of planning systems and techniques, developing and improving a common planning domain definition language, and designing new planning domains and problems for the research community. This paper focuses on the deterministic part of the fifth international planning competition (IPC5), presenting the language and benchmark domains that we developed for the competition, as well as a detailed experimental evaluation of the deterministic planners that entered IPC5, which helps to understand the state of the art in the field. We introduce an extension of PDDL, called PDDL3, allowing the user to express strong and soft constraints about the structure of the desired plans, as well as strong and soft problem goals. We discuss the expressive power of the new language focusing on the restricted version that was used in IPC5, for which we give some basic results about its compilability into PDDL2. Moreover, we study the relative performance of the IPC5 planners in terms of solved problems, CPU time, and plan quality; we analyse their behaviour with respect to the winners of the previous competition; and we evaluate them in terms of their capability of dealing with soft goals and constraints, and of finding good quality plans in general. Overall, the results indicate significant progress in the field, but they also reveal that some important issues remain open and require further research, such as dealing with strong constraints and computing high quality plans in metric-time domains and domains involving soft goals or constraints.
Abstract: 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.
Abstract: The treatment of exogenous events in planning is practically important in many real-world domains where the preconditions of certain plan actions are affected by such events. In this paper we focus on planning in temporal domains with exogenous events that happen at known times, imposing the constraint that certain actions in the plan must be executed during some predefined time windows. When actions have durations, handling such temporal constraints adds an extra difficulty to planning. We propose an approach to planning in these domains which integrates constraint-based temporal reasoning into a graph-based planning framework using local search. Our techniques are implemented in a planner that took part in the 4th International Planning Competition (IPC-4). A statistical analysis of the results of IPC-4 demonstrates the effectiveness of our approach in terms of both CPU-time and plan quality. Additional experiments show the good performance of the temporal reasoning techniques integrated into our planner.
Abstract: We present some techniques for planning in domains specified with the recent standard language PDDL2.1, supporting durative actions and numerical quantities. These techniques are implemented in LPG, a domain-independent planner that took part in the 3rd International Planning Competition (IPC). LPG is an incremental, any time system producing multi-criteria quality plans. The core of the system is based on a stochastic local search method and on a graph-based representation called "Temporal Action Graphs" (TA-graphs). This paper focuses on temporal planning, introducing TA-graphs and proposing some techniques to guide the search in LPG using this representation. The experimental results of the 3rd IPC, as well as further results presented in this paper, show that our techniques can be very effective. Often LPG outperforms all other fully-automated planners of the 3rd IPC in terms of speed to derive a solution, or quality of the solutions that can be produced.
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.
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.
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.
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.
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.
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).
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.
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.
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.
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.
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.
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.
Abstract: Reasoning about complex information in automated planning is important for representing real-world problems. Unlike classical planning paradigm where strong assumptions are assumed, in real-world domains actions take time and consume resources; the execution of certain actions can occur only during some predefined time windows imposing scheduling constraints, and can indirectly affect high level properties of world states; moreover, the quality of plans generally takes consumption of resources and makespan into account. This thesis proposes some domain-independent techniques based on graphs and local search for automated planning in complex domains. Specifically, the work has three main contributions. Firstly, we propose a rule-based inference system for efficient reasoning about derived predicates during planning; secondly, we describe a new plan representation for reasoning about quantitative information, and some new heuristics for guiding the planning process towards good quality plans; finally, we propose a new approach to planning with temporal features, integrating constraint-based temporal reasoning into a graph-based planning framework. The techniques described in this thesis are implemented in a new planner called LPG-td. LPG-td took part in the 2004 planning competition showing good performance especially in problems formalized by using recent languages enabling the representation of temporal and quantitative information. A large experimental evaluation shows that our approach works well in practice.