Search

Automated planning is a prominent Artificial Intelligence (AI) challenge that has been extensively studied for decades, which has led to the development of powerful domain-independent planning syst...

In Automated Planning, generating macro-operators (macros) is a well-known reformulation approach that is used to speed-up the planning process. Nowadays, given the number of existing techniques, a...

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.

Over the last years, the planning community has formalised several models and approaches to multi-agent (MA) propositional planning. One of the main motivations in MA planning is that some or all a...

In Automated Planning, generating macro-operators (macros) is a well-known reformulation approach that is used to speed-up the planning process. Most of the macro generation techniques aim for using the same set of generated macros on every problem instance of a given domain. This limits the usefulness of macros in scenarios where the environment and thus the structure of instances is dynamic, such as in real-world applications. Moreover, despite the wide availability of parallel processing units, there is a lack of approaches that can take advantage of multiple parallel cores, while exploiting macros.

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

Case-based planning (CBP) 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. In this work, we address CBP in PDDL domains with real-valued fluents, action durations and timed-initial literals, which are essential to model real-world planning problems involving continuous resources and temporal constraints. We propose some new heuristic techniques for retrieving a plan from a library of existing plans that is promising for solving a new planning problem encountered by the CBP system, 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 proposed use of the numerical/temporal information...

Case-based planning (CBP) is an approach to automated planning that tries to save computational effort by reusing previously found solutions. In 2001, Spalazzi published a survey of work in CBP; here, we present an updated overview of systems that have contributed to the evolution of the field or addressed some issues related to planning by reuse in a novel way. The article presents relevant planners so that readers gain insight into the operation of these systems. This analysis will allow readers to understand the approaches both in the quality of the solutions and in the complexity of finding them.

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.

In classical domain-independent planning, derived predicates are predicates that the domain actions can only indirectly affect. Their truth in a state can be inferred by particular axioms, that enrich the typical operator description of a planning domain. As discussed in [3,6], derived predicates are practically useful to express in a concise and natural way some indirect action effects, such as updates on the transitive closure of a relation. Moreover, compiling them away by introducing artificial actions and facts in the formalization is infeasible because, in the worst case, we have an exponential blow up of either the problem description or the plan length [6]. This suggests that is worth investigating new planning methods supporting derived predicates, rather than using existing methods with “compiled” problems.

GPG is a planner based on planning graphs that combines local search and backtracking techniques for solving both plan-generation and plan-adaptation tasks. The space of the local search is formed by particular subgraphs of a planning graph representing partial plans. The operators for moving from one search state to the next one are graph modification operations corresponding to adding (deleting) actions to (from) a partial plan. GPG can use different types of heuristics based on a parametrized cost function, where the parameters weight different types of constraint violation that are present in the current subgraph. A drawback of this method is that the performance is sensitive to the static values assigned to these parameters.In this paper we propose a refined version of the local search heuristics of GPG using a cost function with dynamic parameters. In particular, the cost of the constraint violations are dynamically evaluated using Lagrange multipliers. As the experimental results show, the use of these multipliers gives two important improvements to our local search. First, the revised cost function is more informative and can discriminate more accurately the elements in the neighborhood. As a consequence, the new cost function can give better performances. Secondly, the performance of the search does not depend anymore on the values of the parameters that in the previous version need to be tuned by hand before the search.

Fast plan adaptation is important in many AI applications. From a theoretical point of view, in the worst case adapting an existing plan to solve a new problem is no more efficient than a complete regeneration of the plan. However, in practice plan adaptation can be much more efficient than plan generation, especially when the adapted plan can be obtained by performing a limited amount of changes to the original plan. In this paper, we investigate a domain-independent method for plan adaptation that modifies the original plan by replanning within limited temporal windows containing portions of the plan that need to be revised. Each window is associated with a particular replanning subproblem that contains some “heuristic goals” facilitating the plan adaptation, and that can be solved using different planning methods. An experimental analysis shows that, in practice, adapting a given plan for solving a new problem using our techniques can be much more efficient than replanning from scratch.