A New Method for Parallel Planning via Heuristic Search

Due to the need of solving the problem of exponential branching factor, parallel planning through heuristic state space search is a challenging problem. A new method based on heuristic state search is introduced. The method generates parallel plan by parallelism of one action (center action) and other independent actions applicable in one state, thereby, avoids the problem mentioned above. Furthermore, the method considers the negative interaction between actions and uses two time-step partial plan that adds more goals to be substitute of one action during the process of choosing the center action. PPFF (parallel planning FF) is designed based on FF (Fast-forward) planning system and the method introduced above. Primary analysis indicates that the running time of PPFF is faster than existing parallel planning systems.