AltAltp: Online Parallelization of Plans with Heuristic State Search
  Despite their near dominance, heuristic state search planners still lag
behind disjunctive planners in the generation of parallel plans in classical
planning. The reason is that directly searching for parallel solutions in state
space planners would require the planners to branch on all possible subsets of
parallel actions, thus increasing the branching factor exponentially. We
present a variant of our heuristic state search planner AltAlt, called AltAltp
which generates parallel plans by using greedy online parallelization of
partial plans. The greedy approach is significantly informed by the use of
novel distance heuristics that AltAltp derives from a graphplan-style planning
graph for the problem. While this approach is not guaranteed to provide optimal
parallel plans, empirical results show that AltAltp is capable of generating
good quality parallel plans at a fraction of the cost incurred by the
disjunctive planners.
