computed based on the operational semantics of the planning actions. 6 In the case of a set of STRIPS actions, one simply adds all ADD effects to and deletes all DEL effects from a state description in order to obtain the resulting state, following the Result function in Definition 2. For STRIPS, the Result function coincides directly with the R function. In the case of a set of parallel ADL actions, one needs to consider all possible linearizations of the parallel action set and has to deal with the conditional effects separately. For each linearization, a different resulting state can be obtained, but each of them will satisfy the goals. To obtain the new initial state I 2 , one takes the intersection of the resulting states for each possible linearization of the actions in a parallel set. This means to compute n!

linearizations for a parallel action set of n actions in each time step. Since n is usually small (more than 5 or 6 ADL actions per time step are very rare), the practical costs for this computation are neglectible.

This way, given a solution to a subproblem ( O, I i, G i ), one calculates the new initial state Z i +1 and runs the planner on the subsequent planning problem ( O i Z i +1 i G i +1 ) until the planning problem ( O, I, , G, ) is solved.

The plan solving the original planning problem ( O, I, G ) is obtained by taking the sequence of subplans P 1 , P 2 , . . , P k .  One could argue that planning for increasing goal sets can lead to highly non-optimal plans. But IPP still uses the "no-ops first" strategy to achieve goals, which was originally introduced in the GRAPHPLAN system (Blum & Furst, 1997). Employing this strategy, the GRAPHPLAN algorithm, in short, first tries to achieve goals by simply keeping them true, if possible. Since all goals G 1 , G 2 , . . , G i are already stisfied in the initial state Z i +1, starting from which the planner tries to achieve G i +1, this strategy ensures that these goals are only destroyed and re-established if no solution can be found otherwise. The no-ops first strategy is merely a GRAPHPLAN feature, but any reasonable planning strategy should preserve goals that are already true in the initial state whenever possible.

The soundness of the agenda-driven planning algorithm is obvious because G k = G and we have a sequence of sound subplans yielding a state transition from the initial state I to a state satisfying G.

The completeness of the approach is less obvious and holds only if the planner cannot make wrong decisions before finally reaching the goals.  More precisely, the approach is complete on problems that do not contain deadlocks as they were introduced in Definition 14.

Theorem 8  Given a solvable planning problem (O,I,G), and a goal agenda G1, G2,...Gk with Gi ⊆ Gi+1 and Gk = G. Running any complete planner in the agenda-driven manner described above will yield a solution if the problem is deadlock-free.

Proof: Let us assume the planner does not find a solution in step i of the agenda-driven algorithm, i.e., no solution is found for the subproblem ( O, I, G, ).  As the planner is assumed to be complete on each subproblem, this implies unsolvability of ( O , I , G i ). If this problem is not solvable, then neither is the problem ( O, I, G) solvable, since G, E G holds. Therefore, the goals cannot be reached from Z i . Furthermore, Z i is a reachable state—it was reached by executing the partial solution plans P 1 , . . , P i -1 in the initial state. Consequently, I i must be a deadlock state in the sense of Definition 14, which is a contradiction.

6. See (Koehler et al., 1997) for the exact definition of R , which we do not want to repeat here