Abstract: The scalability of recent planning algorithms allows developers to automate planning tasks, which so far have been reserved to humans. However in real-world applications, synthesizing a plan is just the beginning of a complex life-cycle management process. Plans must be organized in large collections, where they can be grouped along different purposes and are amenable to the search, inspection, evaluation, and modification by human experts or automated reasoning systems. Eventually, plans will outlast their utility and be replaced. We present our solution to plan life cycle management for an autonomic computing application. We focus in particular on the automatic synthesis of plan metadata for plans containing conditional and parallel actions, well-structured loops, and non-deterministic choices. The plans are of unknown origin, i.e., their underlying action model, which could provide us with pre- and postconditions, is not available. New analysis techniques are presented that uniformly generate metadata for plans, thus allowing a system to embed plans into context and organize them in meaningfully structured plan repositories.
Abstract: Not widely known by the AI community, elevator control has become a major field of application for AI technologies. Techniques such as neural networks, genetic algorithms, fuzzy rules, and, recently, multi-agent systems and AI planning have been adopted by leading elevator companies not only to improve the transportation capacity of conventional elevator systems, but also to revolutionize the way in which elevators interact with and serve passengers. In this article, we begin with an overview of AI techniques adopted by this industry and explain the motivations behind the continuous interest in AI. We review and summarize publications that are not easily accessible from the common AI sources. In the second part, we present in more detail a recent development project to apply AI planning and multi-agent systems to elevator control problems.
Abstract: Offering an individually tailored service to passengers while maintaining a high transportation capacity of an elevator group is an upcoming challenge in the elevator business, which cannot be met by software methods traditionally used in this industry. AI planning offers a novel solution to these control problems: (1) by synthesizing the optimal control for any situation occurring in a building based on fast search algorithms, (2) by implementing a domain model, which allows to easily add new features to the control software. By embedding the planner into a multi-agent system, real-time interleaved planning and execution is implemented and results in a high-performing, self-adaptive, and modular control software.
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: The synthesis of elevator control commands is a difficult problem when new service requirements such as VIP service, access restrictions, nonstop travel etc. have to be individually tailored to each passenger. AI planning technology offers a very elegant and flexible solution because the possible actions of a control system can be made explicit and their preconditions and effects can be specified using expressive representation formalisms. Based on the specification, a planner can flexibly synthesize the required control and changes in the specification do not require any reimplementation of the control software. In this paper, we describe the application and investigate how currently available domain-independent planning formalisms can cope with it.
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: Let us consider the following problem: Given a (probably huge) set of sets S and a query set q, is there some set s in S such that s is a subset of q? This problem occurs in at least four application areas: the matching of a large number (usually several 100,000s) of production rules, the processing of queries in data bases supporting set-valued attributes, the identification of inconsistent subgoals during artificial intelligence planning and the detection of potential periodic chains in labeled tableau systems for modal logics. In this paper, we introduce a data structure and algorithm that allow a compact representation of such a huge set of sets and an efficient answering of subset and superset queries. The algorithm has been used successfully in the IPP system and enabled this planner to win the ADL track of the first planning competition.
Abstract: The paper proves the destination control problem for elevators to be NP-hard and investigates two possible algorithmic approaches towards a solution, one based on constraint satisfaction, another one based on heuristic search.
Abstract: We introduce mathematical programming and atomic decomposition as the basic modal (T-Box) inference techniques for a large class of modal and description logics. The class of description logics suitable for the proposed methods is strong on the arithmetical side. In particular there may be complex arithmetical conditions on sets of accessible worlds (role fillers). The atomic decomposition technique can deal with set constructors for modal parameters (role terms) and parameter (role) hierarchies specified in full propositional logic. Besides the standard modal operators, a number of other constructors can be added in a relatively straightforward way. Examples are graded modalities (qualified number restrictions) and also generalized quantifiers like `most', `n%', `more' and `many'.
Abstract: We investigate how to augment a given logical system, for example an arithmetical equation solver, with a Boolean component. The atomic decomposition technique proposed in this paper reduces reasoning about the Boolean component in the combined system to reasoning in the pure basic system only. A typical instance of this scheme is a linear programming system which is to be augmented with reasoning about cardinalities of sets, or other functions mapping sets to integers. The sets and their set-theoretic relationships are axiomatized with propositional logic. Atomic decomposition then reduces reasoning about numerical attributes of these sets to arithmetic equation solving.
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 introduce a new technique that translates cardinality information about finite sets into simple arithmetic terms and thereby enables a system to reason about such set cardinalities by solving arithmetic equation problems. The atomic decomposition technique separates a collection of sets into mutually disjoint smallest components (``atoms'') such that the cardinality of the sets are just the sum of the cardinalities of their atoms. With this idea it is possible to have languages combining arithmetic formulae with set terms, and to translate the formulae of this combined logic into pure arithmetical formulae. As a particular application we show how this technique yields new inference procedures for concept languages with so called number restriction operators.
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: We describe reasoning methods for the interval-based modal temporal logic LLP which employs the modal operators sometimes, always, next, and chop. We propose a constraint deduction approach and compare it with a sequent calculus, developed as the basic machinery for the deductive planning system PHI which uses LLP as underlying formalism.
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: A key problem in case-based reasoning is the representation, organization and maintenance of case libraries. While current approaches rely on heuristic and psychologically inspired formalisms, terminological logics have emerged as a powerful representation formalism with clearly defined formal semantics. This paper demonstrates how the indexing of case libraries can be grounded on terminological logics by using them as a kind of query language to the case library. Indices of cases are represented as concepts in a terminological logic. They are automatically constructed from the symbolic representation of cases with the help of a well-defined abstraction process. The retrieval of cases from the library is grounded on concept classification.
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.