which we call reasonable and forced ordering, and study their complexity. It turns out that both are very hard to decide.

Consequently, we introduce two efficient methods that can both be used to approximate rea so nable goal orderings.  The definitions are first given for simple STRIPS domains, where the desired theoretical properties can be easily proven.  Afterwards, we extend our definitions to ADL operators (Pednault, 1989) handling conditional effects and negative preconditions, and discuss why we do not further invest any effort in trying to find forced orderings.

We show how a set of ordering relations between atomic goals can be used to divide the goal set into disjunct subsets, and how these subsets can be ordered with respect to each other.  The resulting sequence of subsets comprises the so-called goal agenda, which can then be used to control an agenda-driven planning algorithm.

The method, called Goal Agenda Manager, is implemented in the context of the IPP
planning system, where we show its potential of exponentially reducing computation times on certain planning domains.

The paper is organized as follows: Section 2 introduces and motivates reasonable and forced goal orderings. Starting with simple STRIPS operators, they are formally defined, and their complexity is investigated. In Section 3, we present two methods, which compute an approximation of the reasonable ordering and discuss both orderings from a more practical point of view. The section concludes with an extension of our definitions to ADL
operators having conditional effects. Section 4 shows how a planning system can benefit from ordering information by computing a goal agenda that guides the planner. We define how subsets of goals can be ordered with respect to each other and discuss how a goal agenda can affect the theoretical properties, in particular the completeness of a planning algorithm. Section 5 contains the empirical evaluation of our work, showing results that we obtained using the goal agenda in IPP. In Section 6 we summarize our approach in the light of related work. The paper concludes with an outlook on possible future research directions in Section 7.

## 2. Ordering Relations Between Atomic Goals

For a start, we only investigate simple STRIPS domains just allowing sets of atoms to describe states, the preconditions, and the add and delete lists of operators.

Definition 1 (State) The set of all ground atoms is denoted with P. A state s E 2 P is a subset of ground atoms. Note that all states are assumed to be complete , i.e., we always know for an atom p whether p E s or p & s holds. We also assume that all operator schemata are ground, i.e., we only talk about actions.

Definition 2 (Strips Action) A STRIPS action o has the usual form

$$p r\,e(o)\ \longrightarrow\ \ A D D\ \ a d d(o)\ \ D E L\ \ d e l(o)$$

where pre(o) are the preconditions of o, add(o) is the Add list of o and del(o) is the Delete list of the action, each being a set of ground atoms.  We also assume that del(o) Nadd(o) = 0.

The result of applying a STRIPS action to a state is defined as usual: