Selected Papers on AI Planning (1992 - 2002)
J. Koehler, D. Ottiger:
An AI-based Approach to Destination Control in Elevators, AI Magazine, 23(3): pages 59-78, Fall 2002.
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.
J. Koehler, J. Hoffmann: On Reasonable and
Forced Goal Orderings and their Use in an Agenda-Driven Planning
Algorithm, Journal of Artificial Intelligence Research, 12/2000,
pages 339-386
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.
J. Koehler, K. Schuster: Elevator Control as a Planning Problem, AIPS-00, pages 331-338
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.
J. Koehler, J. Hoffmann: Handling of Inertia in a Planning System,
ECAI-2000 Workshop on New Trends in Planning, Scheduling and Design
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.
J. Koehler: Planning under Resource Constraints, ECAI-98, pages 489-493
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.
J. Koehler: Solving Complex
Planning Tasks Through Extraction of Subproblems, Copyright AAAI Press, AIPS-98, pages 62-69
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.
J. Koehler,
B. Nebel,
J. Hoffmann,
Y. Dimopoulos:
Extending Planning Graphs to an ADL Subset,
ECP-97, pages 273-285
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.
B. Nebel,
Y. Dimopoulos, J. Koehler:
Ignoring Irrelevant Facts and Operators in Plan Generation,
ECP-97, pages 338-350
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.
Y. Dimopoulos,
B. Nebel,
J. Koehler:
Encoding planning problems in non-monotonic logic
programs,
ECP-97, pages 169-181
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.
J. Koehler:
Planning from Second Principles. Artificial Intelligence, Volume 87, pages 148-187, 1996
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.
B. Nebel,
J. Koehler:
Plan Reuse versus Plan Generation: A theoretical
and empirical Analysis
Artificial Intelligence, Volume 76, pages 427-454, 1995.
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.
J. Koehler:
Correct Modification of Complex Plans.
ECAI-94, pages 605-609. (extended version)
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.
J. Koehler:
Avoiding Pitfalls in Case-based Planning.
AIPS-94, pages 104-109.
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.
J. Koehler:
Flexible Plan Reuse in a Formal Framework.
EWSP-93, pages 171-184.
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.
B. Nebel,
J. Koehler:
Plan Modification versus Plan Generation:
A Complexity-Theoretic Perspective.
IJCAI-93, pages 1436-1441.
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.
M. Bauer,
S. Biundo,
D. Dengler,
J. Koehler,
G. Merziger:
PHI - A Logic-Based Tool for Intelligent Help Systems.
IJCAI-93, pages 460-466.
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.
S. Biundo,
D. Dengler,
J. Koehler:
Deductive Planning and Plan Reuse in a Command Language
Environment.
ECAI-92, pages 628-632.
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.
J. Koehler: Reuse of Plans in Deductive Planning Systems.
(In German). Phd Thesis 1994. Available as book from infix publishers, series DISKI , number 65.
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.
Jana Koehler, 10/15/2006