# On Reasonable And Forced Goal Orderings And Their Use In An  Agenda-Driven  Planning  Algorithm

Jana Koehler JANA_KOEHLER@CH. SCHINDLER.COM
Schindler Lifts, Ltd R & D Technology Management 6031 Ebikon, Switzerland

## Jörg Hoffmann

HOFFMANN@INFORMATIK.UNI-FREIBURG.DE
Institute for Computer Science Albert Ludwigs University George s-Köhler-Allee, Geb. 52 79110 Freiburg, Germany

## 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.

## 1. Introduction

How to effectively plan for interdependent subgoals has been in the focus of AI planning research for a very long time. Starting with the early work on ABSTRIPS (Sacerdoti, 1974) or on conjunctive-goal planning problems (Chapman, 1987), quite a number of approaches have been presented and the complexity of the problems has been studied. But until today, planners have made only some progress in solving bigger planning instances and scalability of classical planning systems is still a problem.

In this paper, we focus on the following problem: Given a set of conjunctive goals, can we define and detect an ordering relation over subsets from the original goal set? To arrive at such an ordering relation over subsets, we first focus on the atomic facts contained in the goal set. We formally define two closely related ordering relations over such atomic goals,