Parallel Planning via the Distribution of Operators

Dimitris Vrakas, Ioannis Refanidis & Ioannis Vlahavas (2001) Parallel planning via the distribution of operators, Journal of Experimental & Theoretical Artificial Intelligence, 13:3, 211-226, DOI: 10.1080/09528130110063074

This paper describes ODMP (Operator Distribution Method for Parallel Planning), a parallelization method for efficient heuristic planning. The method innovates in that it parallelizes the application of the available operators to the current state and the evaluation of the successor states using the heuristic function. In order to achieve better load balancing and a lift in the scalability of the algorithm, the operator set is initially enlarged, by grounding the first argument of each operator. Additional load balancing is achieved through the reordering of the operator set, based on the expected amount of imposed work. ODMP is effective for heuristic planners, but it can be applied to planners that embody other search strategies as well. It has been applied to GRT, a domain–independent heuristic planner, and CL, a heuristic planner for simple Logistics problems, and has been thoroughly tested on a set of Logistics problems adopted from the AIPS-98 planning competition, giving quite promising results.