We are not able to provide an explanation for this phenomenon, but the division into subproblems causes a much larger search space for the planner although the same solution plans result. RIFO cannot improve on the situation because it selects all actions as relevant.

The tower of hanoi domain is the only one we found where IPP's performance is deteriorated by GAM. We do currently not see a way of how one can tell in advance whether IPP will gain an advantage from using GAM or not. The overhead caused by the goal analysis itself is very small, but an "inadequate" split of the goals into subgoal sets can lead to more search, see also Section 6.

However in this case, the phenomenon seems to be specific to IPP. We simulated the information that is provided by GAM in UCPOP and obtained a quite different picture.

The fifth column in Figure 13 shows the runtime of UCPOP using ZLIFO (Pollack, Joslin, & Paolucci, 1997) and the ibf control strategy with the number of explored partial plans in parentheses. UCPOP can only solve the problem for 2 and 3 discs. In the last column of the figure, we show the runtime and number of explored partial plans, which result when UCPOP is run on the subproblems that result from the agenda. These are exactly the same subproblems whi IPP has to solve, but the performance of UCPOP improves ssignificantly. Instead of taking 8 s and exploring 2291 partial plans, UCPOP only takes 0.18+0.06+0.01=0.25 s and explores only 48+13+6=67 plans. Unfortunately, any problems or subproblems with more than 3 discs remain beyond the performance of UCPOP. The performance improvement is independent of the search strategies used by UCPOP. For example, if ibf control is used without ZLIFO, the number of explored partial plans is reduced from 78606 down to 2209 in the case of the problem with 3 discs. Runtime improves from 65 seconds down to 2 seconds. Similarly, when using bf control without ZLIFO the nmmmmer of explored partial plans reduces from 1554 down to 873.

Knoblock (1994) also reports an improvement in performance for the Prodigy planner
(Fink & Veloso, 1994) when it is using the abstraction hierarchy generated for this domain by the ALPINE module, which provides in essence the same information as the goal agenda. 9

## 6. Summary And Comparison To Related Work

Many related approaches have been developed to provide a planner with the ability to decompose a planning problem by giving it any kind of goal ordering information. Subsequently, we discuss the most important of them and review our own work in the light of these approaches Our method introduces a preprocessing approach, which derives a total ordering for subsets of goals by performing a static, heuristic analysis of the planning problem at hand.

The approach works for domains described with STRIPS or ADL operators and is based on polynomial-time algorithms. The purpose of this method is to provide a planner with search control, i.e., we opt at deriving a goal achievement order and then successively call the planner on the totally ordered subsets of goals.

The method preserves the soundness of the planning system, but the completeness only in the case that the planning domain does not contain deadlocks.  We argue that