Abstract: Fast Downward had won the classical track of the 4th International Planning Competition at ICAPS 2004, our work extended the Fast Downward planning system to a parallel setting, and implemented a parallel planning system called Parallel Downward. Several techniques were proposed in this paper. Firstly, four definitions related to parallel plan were given. Secondly, we proposed a method to decide mutual exclusive actions in multi-valued planning tasks, ineluding definitions, the necessary and sufficient condition and the deciding algorithm. Thirdly, we designed an efficient generation of successor states with low cost of generating all the legal sets of actions. Finally,we proposed an effective search control policy of parallel planning to enhance the quality of this valid plan. In addition, we proposed the pruning policy to restrain state space of parallel planning exploding exponentially. We tested Parallel Downward on planning benchmarks used in the International Planning Competitions. The experimental results show that Parallel Downward is excellent in both planning efficiency and planning quality. Parallel Downward is superior in scalability compared with Sapa parallel planning system.

Key words: Parallel planning, Multi-valued planning task, Planning as heuristic search in state space, Causal graph heuristic