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 o f the longstanding issues in AI planning. It makes two new contributions. F irst, it formally defines and discusses two different goal orderings, which are called the reasonable and the forced ordering. Both orderings are defi ned for simple STRIPS operators as well as for more complex ADL operators s upporting negation and conditional effects. The complexity of these orderin gs is investigated and their practical relevance is discussed. Secondly, tw o 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 plan ner 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 subproble ms. Since only a polynomial overhead is caused by the goal agenda computati on, a potential exists to dramatically speed up planning algorithms as we d emonstrate in the empirical evaluation, where we use this method in the IPP planner.