Search

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. [ABSTRACT FROM AUTHOR]

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 FROM AUTHOR]

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 FROM AUTHOR]

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 FROM AUTHOR]

In this paper we propose myPTutor , a general and effective approach which uses AI planning techniques to create fully tailored learning routes, as sequences of Learning Objects (LOs) that fit the pedagogical and students’ requirements. myPTutor has a potential applicability to support e-learning personalization by producing, and automatically solving, a planning model from (and to) e-learning standards in a vast number of real scenarios, from small to medium/large e-learning communities. Our experiments demonstrate that we can solve scenarios with large courses and a high number of students. Therefore, it is perfectly valid for schools, high schools and universities, especially if they already use Moodle , on top of which we have implemented myPTutor . It is also of practical significance for repairing unexpected discrepancies (while the students are executing their learning routes) by using a Case-Based Planning adaptation process that reduces the differences between the original and the new route, thus enhancing the learning process. [ABSTRACT FROM AUTHOR]

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. [Copyright &y& Elsevier]

In multi-agent planning, preserving the agents' privacy has become an increasingly popular research topic. For preserving the agents' privacy, agents jointly compute a plan that achieves mutual goals by keeping certain information private to the individual agents. Unfortunately, this can severely restrict the accuracy of the heuristic functions used while searching for solutions. It has been recently shown that, for centralized planning, blind search algorithms such as width-based search can solve instances of many existing domains in low polynomial time when they feature atomic goals. Moreover, the performance of goal-oriented search can be improved by combining it with width-based search. In this paper, we investigate the usage of width-based search in the context of (decentralised) collaborative multi-agent privacy-preserving planning, addressing the challenges related to the agents' privacy and performance. In particular, we show that width-based search is a very effective approach over several benchmark domains, even when the search is driven by heuristics that roughly estimate the distance from goal states, computed without using the private information of other involved agents. Moreover, we show that the use of width-based techniques can significantly reduce the number of messages transmitted among the agents, better preserving their privacy and improving their performance. An experimental study presented in the paper analyses the effectiveness of our techniques, and compares them with the state-of-the-art of collaborative multi-agent planning. [ABSTRACT FROM AUTHOR]

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