using some domain control knowledge based on the generation **of rules for each specific**
planning domain. The Graphplan algorithm tries to maximize **its parallelism by satisfying** most of the subgoals at each time step, if the search fails then it backtracks and reduces the set of parallel actions being considered one level before. AltAltp **does the opposite, it**
tries to guess initial parallel nodes given the heuristics, **and iteratively adds more actions**
to these nodes as possible with the Pushup **procedure later during search.**
More recently, there has been some work on generalizing forward state search to handle action concurrency in metric temporal domains. Of particular relevance to this work are the Temporal TLPlan (Bacchus & Ady, 2001) and SAPA (Do & Kambhampati, 2001).

Both these planners are designed specifically for handling metric temporal domains, and use similar search strategies. The main difference between them **being that Temporal TLPlan** depends on hand-coded search control knowledge to guide its search, while SAPA (like AltAltp) uses heuristics derived from (temporal) planning graphs. **As such, both these**
planners can be co-opted to produce parallel plans in classical domains. Both these planners do a forward chaining search, and like AltAltp**, both of them achieve concurrency**
incrementally, without projecting sets of actions, in the following way. Normal forward search planners start with the initial state S0, corresponding to time t0**, consider all actions**
that apply to S0, and choose one, say a1 apply it to S0, getting S1**. They simultaneously**
progress the "system clock" from t0 to t1**. In order to allow for concurrency, the planners**
by Bacchus and Ady (2001), and Do and Kambhampati (2001) essentially decouple the
"action application" and "clock progression." At every point in the search, there is a nondeterministic choice - between progressing the clock, or applying (additional) actions at the current time point. From the point of view of these planners, AltAltp**can be seen as providing heuristic guidance for this non-deterministic choice (modulo the difference that** AltAltp does regression search). The results of empirical comparisons between AltAltp **and SAPA,**
which show that AltAltp **outperforms SAPA, suggest that the heuristic strategies employed** in AltAltp**including the incremental fattening, and the pushup procedure, can be gainfully**
adapted to these planners to increase the concurrency in the **solution plans. Finally, HSP*,**
and TP4, its extension to temporal domains, are both heuristic state search planners using regression that are capable of producing parallel plans (Haslum & Geffner, 2000). TP4 can be seen as the regression version of the approach used in SAPA **and temporal TLPlan. Our** experiments however demonstrate that neither of these planners scales well in comparison to AltAltp.

The Pushup **procedure can be seen as a plan compression procedure. As such, it is similar**
to other plan compression procedures such as "double-back optimization" (Crawford, 1996).

One difference is that double-back is used in the context of a local search, while Pushup is used in the context of a systematic search. Double-back could be also applied to any finished plan or schedule, but as any other post-processing approach its outcome would depend highly on the plan given as input.

## 6. Concluding Remarks

Motivated by the acknowledged inability of heuristic search planners to generate parallel plans, we have developed and presented an approach to generate parallel plans in the context of AltAlt**, a heuristic state space planner. This is a challenging problem because of**