Abstract: The paper addresses the problem of computing goal orderings, which is one of the longstanding issues in AI planning. It makes two new contributions. First, it formally defines and discusses two different goal orderings, which are called the reasonable and the forced ordering. Both orderings are defined for simple STRIPS operators as well as for more complex ADL operators supporting negation and conditional effects. The complexity of these orderings is investigated and their practical relevance is discussed. Secondly, two different methods to compute reasonable goal orderings are developed. One of them is based on planning graphs, while the other investigates the set of actions directly. Finally, it is shown how the ordering relations, which have been derived for a given set of goals G, can be used to compute a so-called goal agenda that divides G into an ordered set of subgoals. Any planner can then, in principle, use the goal agenda to plan for increasing sets of subgoals. This can lead to an exponential complexity reduction, as the solution to a complex planning problem is found by solving easier subproblems. Since only a polynomial overhead is caused by the goal agenda computation, a potential exists to dramatically speed up planning algorithms as we demonstrate in the empirical evaluation, where we use this method in the IPP planner.
Abstract: This thesis introduces the theoretical foundations which are underlying the IPP planning system.
Abstract: The generation of the set of all ground actions for a given set of ADL operators, which are allowed to have conditional effects and preconditions that can be represented using arbitrary first-order formulas is a complex process which heavily influences the performance of any planner or pre-planning analysis method. The paper describes a sophisticated instantiation procedure that determines so-called inertia in a given problem representation and uses them to perform simplifications of formulas during the instantiation process. As a result, many inapplicable actions are detected and ruled out from the domain representation yielding a much smaller search space for the planner.
Abstract: This paper outlines the basic principles underlying reasoning about resources in IPP, which is a classical planner based on planning graphs originally introduced with the Graphplan system. The main idea is to deal with resources in a strictly action-centered way, i.e. one specifies how each action consumes or produces resources, but no explicit temporal model is used. This avoids the computational problems of solving general constraint satisfaction problems by using instead interval arithmetics and propagation of resource requirements over time steps in the planning graph.
Abstract: The paper introduces an approach to derive a total ordering between increasing sets of subgoals by defining a relation over atomic goals. The ordering is represented in a so-called goal agenda that is used by the planner to incrementally plan for the increasing sets of subgoals. This can lead to an exponential complexity reduction because the solution to a complex planning problem is found by solving easier subproblems. Since only a polynomial overhead is caused by the goal agenda computation, a potential exists to dramatically speed up planning algorithms as we demonstrate in the empirical evaluation.
Abstract: We describe an extension of Graphplan to a subset of ADL that allows conditional and universally quantified effects in operators in such a way that almost all interesting properties of the original Graphplan algorithm are preserved.
Abstract: It is traditional wisdom that one should start from the goals when generating a plan in order to focus the plan generation process on potentially relevant actions. The GRAPHPLAN system, however, which is the most efficient planning system nowadays, builds a ``planning graph'' in a forward-chaining manner. Although this strategy seems to work well, it may possibly lead to problems if the planning task description contains irrelevant information. Although some irrelevant information can be filtered out by GRAPHPLAN, most cases of irrelevance are not noticed. In this paper, we analyze the effects arising from ``irrelevant'' information to planning task descriptions for different types of planners. Based on that, we propose a family of heuristics that select relevant information by minimizing the number of initial facts that are used when approximating a plan by backchaining from the goals ignoring any conflicts. These heuristics, although not solution-preserving, turn out to be very useful for guiding the planning process, as shown by applying the heuristics to a large number of examples from the literature.
Abstract: In this paper we study a framework for encoding planning problems in logic programs with negation as failure. In contrast to other research work that focuses on the representional adequacy of nonmontonic logic programming as a language for describing theories of action and change, here we are concerned with more practical issues. Namely, we examine the effectiveness of an existing implementation of the stable models semantics called "Smodels" in solving a series of hard planning problems. We discuss representational issues and point out factors that can influence the performance of the method. It turns out that for careful and compact encodings, the performance of the method in a number of different domains, is comparable to that of planners like GRAPHPLAN and SATPLAN.
Abstract: Planning from second principles by reusing and modifying plans is one way to improve the efficiency of planning systems. In this paper, we study it in the general framework of deductive planning and develop a logical formalization of planning from second principles, which relies on a systematic decomposition of the planning process. Deductive inference processes with clearly defined semantics formalize each of the subtasks a second-principles planner has to address. Plan modification, which comprises matching and adaptation tasks is based on a deductive approach which yields provably correct modified plans. Reusable plans are retrieved from a dynamically created plan library using description logics as query languages to the library. Apart from sequential plans, this approach enables a planner to reuse and modify complex plans containing control structures like conditionals and loops.
Abstract: The ability of a planner to reuse parts of old plans is hypothesized to be a valuable tool for improving efficiency of planning by avoiding the repetition of the same planning effort. We test this hypothesis from an analytical and empirical point of view. A comparative worst-case complexity analysis of generation and reuse under different assumptions reveals that it is not possible to achieve a provable efficiency gain of reuse over generation. Further, assuming ``conservative'' plan modification, plan reuse can actually be strictly more difficult than plan generation. While these results do not imply that there won't be an efficiency gain in some situations, retrieval of a good plan may present a serious bottleneck for plan reuse systems, as we will show. Finally, we present the results of an empirical study of two different plan reuse systems, pointing out possible pitfalls one should be aware of when attempting to employ reuse methods.
Abstract: The reuse of plans is a valuable way of improving efficiency in planning systems because it avoids the repetition of planning effort. Several approaches to the modification and reuse of sequential plans in the framework of STRIPS-based planning have been developed, but no attempt of a deductive formalization of plan modification has been made. In this paper we present a general approach to flexible plan modification based on a deductive framework. The framework is independent of any particular planning formalism and makes no restrictive assumptions on the nature of plans. It enables a planner to modify complex plans containing control structures like conditionals and iterations.
Abstract: Case-based planning is considered as a valuable tool for improving efficiency in planning by reuse and modification of existing plans. In this paper, the results of an empirical study are discussed in which several factors influencing case-based planning are investigated. The results demonstrate relative efficiency gains or losses caused by different refitting strategies, different types of plans or typical properties of the application domain and identify possible pitfalls for case-based planning.
Abstract: In this paper we present a domain-independent approach to flexible plan reuse based on a deductive framework. A formalization of the whole reuse process is proposed including the modification, representation and retrieval of plans. Plan modification is based on a semantic approach which yields provably correct modified plans. The plan library is represented in a hybrid knowledge representation formalism linking the planning logic with a terminological logic and is dynamically created and maintained by the system requiring no user interaction. Comparing the performance of the deductive plan reuse system with performance measures reported from other systems it turns out that deductive approaches can compete very well with heuristic ones.
Abstract: The ability of a planner to modify a plan is considered as a valuable tool for improving efficiency of planning by avoiding the repetition of the same planning effort. From a computational complexity point of view, however, it is by no means obvious that modifying a plan is computationally as easy as planning from scratch if the modification has to follow the principle of ``conservatism,'' i.e., to reuse as much of the old plan as possible. Indeed, considering propositional STRIPS planning, it turns out that conservative plan modification is as hard as planning and can sometimes be harder than plan generation. Furthermore, this holds even if we consider modification problems where the old and the new goal specification are similar. We put these results into perspective and discuss the relationship to existing plan modification systems. Although sometimes claimed otherwise, these systems do not address the modification problem, but use a non-conservative form of conservative plan modification as a heuristic technique.
Abstract: We introduce a logic-based system which improves the performance of intelligent help systems by supplying them with plan generation and plan recognition components. Both components work in close mutual cooperation. There are two modes of cross-talk between them, one where plan recognition is done on the basis of abstract plans provided by the planner and the other where optimal plans are generated based on recognition results. The examples which are presented are taken from an operating system domain, namely from the Unix mail domain.
Abstract: We introduce a deductive planning system intended to supply intelligent help systems. It consists of a deductive planner and a plan reuse component, providing planning from first as well as planning from second principles. Both components rely on an interval-based temporal logic. The deductive formalisms realizing plan formation from formal specifications and the reuse of already existing plans are presented and demonstrated by examples taken from the domain of operating systems.
Abstract: In dieser Arbeit wird erstmals ein logik-basierter Ansatz für den Einsatz von Wiederverwendungstechniken im KI-Planen entwickelt, der unabhängig von bestimmten Planungsformalismen und Anwendungen ist. Die Modifikation von Plänen basiert auf deduktiven Inferenzverfahren, die es ermöglichen, Pläne beweisbar korrekt zu modifizieren. Zur Bestimmung von wiederverwendbaren Plänen aus einer Planbibliothek werden terminologische Logiken als Anfragesprachen an die Bibliothek verwendet. Eine Diskussion relevanter komplexitätstheoretischer und empirischer Resultate zeigt sinnvolle Einsatzfelder für Wiederverwendungstechniken in Planungssystemen auf.