On Reasonable and Forced Goal Orderings and their Use in an
  Agenda-Driven Planning Algorithm
  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.
