with aggressive Pushup**. The plots in Figure 18(c) and Figure 18(d) show the results of the**
same experiments in the Satellite domain. We see that the situation is quite similar in this domain. We can conclude then that the Pushup **procedure, used to offset the greediness of**
the algorithm, achieves its purpose.

Utility of basing heuristics on Parallel Planning Graphs: We can see in Figure 19(a) that using parallel planning graph as the basis for **deriving heuristic estimates**
in AltAltp**is a winning idea. The serial planning graph overestimates the heuristic values**
in terms of steps, producing somewhat longer parallel solutions. The fact that the version using serial planning graph runs out of time in many problems **also demonstrates that the** running times are also improved by the use of parallel planning graphs.

Comparison to AltAlt: **One final concern would be how much of an extra computational**
hit is taken by the AltAltp **algorithm in serial domains (e.g. Blocks-World from Bacchus,** 2001). We expect it to be negligible and to confirm our intuitions, we ran AltAltp **on a set**
of problems from the sequential Blocks-World domain. We see from the plot 19(b) that the time performance between AltAlt and AltAltp **are equivalent for almost all of the problems.**

## 5. Related Work

The idea of partial exploration of parallelizable sets of actions is not new (Kabanza, 1997; Godefroid & Kabanza, 1991; Do & Kambhampati, 2001). It has been studied in the area of concurrent and reactive planning, where one of the main goals is to approximate optimal parallelism. However, most of the research there has been focused on forward chaining planners (Kabanza, 1997), where the state of the world is completely known. It has been implied that backward-search methods are not suitable for this kind of analysis (Godefroid & Kabanza, 1991) because the search nodes correspond to partial states. We have shown that backward-search methods can also be used to approximate **parallel plans in the context** of classical planning.

Optimization of plans according to different criteria (e.g. **execution time, quality, etc)**
has also been done as a post-processing step. The post-processing computation of a given plan to maximize its parallelism has been discussed by Backstrom (1998). Reordering and de-ordering techniques are used to maximize the parallelism **of the plan. In de-ordering** techniques ordering relations can only be removed, not added. In reordering, arbitrary modifications to the plan are allowed. In the general case this problem is NP-Hard and it is difficult to approximate (Backstrom, 1998). Furthermore, as discussed in Section 1 and 4, post-processing techniques are just concerned with modifying the order between the existing actions of a given plan. Our approach not only considers modifying such orderings but also inserting new actions online which can minimize the **possible number of parallel**
steps of the overall problem.

We have already discussed Graphplan based planners (Long & Fox, 1999; Kautz &
Selman, 1999), which return optimal plans based on the number of time steps. Graphplan uses IDA* to include the greatest number of parallel actions **at each time step of the** search. However, this iterative procedure is very time consuming and it does not provide any guarantee on the number of actions in its final plans. There have been a few attempts to minimize the number of actions in these planners (Huang, Selman, & Kautz, 1999) by