Parallelizing State Space Plans Online

1 Introduction

Parallel plans allow concurrent execution of multiple actions at each time step. While disjunctive planners such as Graph­ plan [Blum and Furst, 1997], SATPLAN [Kautz and Sel­ man, 1996] and GP-CSP [Do and Kambhampati, 2000] seem to have no trouble generating such parallel plans, planners that search in the space of states are overwhelmed by this task [Haslum and Geffner, 2000]. The problem for state space planners is the exponential branching factor of the search space. One approach to solve this problem is to post­ process the sequential plans generated by the state space plan­ ners. This could easily be done-using approaches such as those explored by Backstrom [Backstrom, 1998], but they are limited to transforming the sequential plan given as in­ put. An alternative that we introduce in this article, in­ volves incremental online parallelization. Specifically, our planner AltAJtp [Sanchez and Kambhampati, 2003], which is a variant of the AltAlt planner [Sanchez et a!., 2000; Nguyen et a!., 2000], attempts to parallelize a heuristically selected search branch with other independent actions, and then tries to rearrange the evolving parallel plan using a plan­ compression algorithm.

We will provide a brief background on AltAlt planning system on Section 2. Section 3 describes the generation of parallel plans in AltAJtP. Section 4 presents some empiri­ cal evaluation of AltAJtP. Finally, Section 5 summarizes our contributions.

2 AltAlt Background

The AltAlt planning system is based on a combination of Graphplan [Blum and Furst, 1997] and heuristic state space search [Haslum and Geffner, 2000] technology. The prob­ lem specification and the action template description are first fed to a Graphplan-style planner, which constructs a planning graph for that problem in polynomial time. This planning graph structure is then fed to a heuristic extractor module that is capable of extracting a variety of effective heuristics [Nguyen eta!., 2000]. These heuristics, along with the prob­ lem specification, and the set of ground actions in the final action level of the planning graph are then fed to a regression state-search planner.

3 Plan Compression Algorithm

AltAJtpconsiders at each step during search only those (pair­ wise parallel) actions that individually regress to states with lower heuristic estimates than their parent node to parallelize (fatten) a search branch. This greedy nature of the fatten­ ing procedure while useful in avoiding the addition of irrele­ vant actions to the plan, may also sometimes preclude actions that are ultimately relevant. When this happens, the parallel length of the solution plan is likely to be worsened, as more steps may be needed to support the preconditions of such ac­ tions. In order to offset this negative effect of greediness, AltAJtp re-arranges the partial plan to promote such actions higher up the search branch using a plan-compression algo­ rithm (See Figure 1 ). Specifically, before expanding a given nodeS, AltAJtp checks to see if any ofthe actions in As lead­ ing to S from its parent node, can be pushed up to higher lev­ els in the search branch. The push-up procedure is called each time before a node gets expanded, and it will try to compress the current partial plan. For each of the actions a E A~ we find the highest ancestor node Bx of S in the search branch to which the action can be applied (i.e., it gives some literal in Sx without deleting any other literals in Sx, and it is pairwise independent of all the actions currently leading out of S x)· Once Bx is found, a is then removed from the set of actions leading to S and introduced into the set of actions leading out of Sx (to its child in the current search branch). Next, the states in the search branch below Sx are adjusted to re­ flect this change. The adjustment involves recomputing the regressions of all the search nodes below Sx. At first glance, this might seem like a transformation of questionable utility since the preconditions of a (and their regressions) just be­ come part ofthe descendants of Sx, and this does not nec­ essarily reduce the length of the plan. We however expect a l~ngth reduction because actions supporting the preconditions of a will get "pushed up" eventually during later expansions.

4 Empirical Evaluation

We compare our online parallelization approach to post­ processing, we have implemented Backstrom's 'Minimal De­ ordering Algorithm" from [Backstrom, 1998], and used it to post-process the sequential plans produced by AltAlt. We can see on Figure 2 some empirical results on the Zeno do­ main [Long and Fox, 2002].

As expected, the original AltA It has the longest plans since it allows only one action per time step. The plot shows that post-processing techniques do help in reducing the makespan of the plans generated by AltAlt. However, we also no­ tice that AltAJtp outputs plans with better makespan than either AltAlt or AltAlt followed by post-processing. This shows that online parallelization is a better approach than post-processing sequential plans. AltAJtP also does not result in any additional run-time overhead with respect to AltAlt. Further experiments reported in [Sanchez and Kambhampati, 2003] show that our approach is competitive or outperforms other state of the art approaches in generating parallel plans.

5 Conclusions

We have introduced an approach to generate parallel plans in the context of state space search. Our approach tries to avoid the branching factor blow up by greedy and online par­ allelization of the evolving partial plans. A plan compression procedure is used to offset the ill effects of the greedy search. Our empirical results show that our approach seems to return better quality plans than post-processing the sequential plans.

ZenoTravel AIPS-02

In future, we plan to adapt the AltAJtP approach to met­ ric temporal domains, where the need of concurrency is more pressing. It is in these scenarios where more powerful heuris­ tics based on resource usage can be further investigated to improve the parallelism of state space planners.