An Operator Distribution Method for Parallel Planning

D. Vrakas, I. Refanidis, I. Vlahavas, “An Operator Distribution Method for Parallel Planning”, Proc. AAAI-2000 Workshop on Parallel and Distributed Search for Reasoning, pp. 17-21, 2000.

Proc. AAAI-2000 Workshop on Parallel and Distributed Search for Reasoning, pp. 17-21, 2000.

This paper presents the Operator Distribution Method for Parallel Planning (ODMP), a parallelization method especially suitable for heuristic planners. ODMP distributes the process of finding and applying the ground applicable actions to a given state, to the set of the available processors. The operator schemas of the domain are distributed to the available processors in a dynamic manner. In order to utilize a larger number of processors and to achieve better load balancing, the set of the domain’s operators is initially expanded by considering all the possible instantiations of their first argument. The proposed method, ODMP, is an effective parallelization method for heuristic planners, but it can also be applied to planners that embody other search strategies as well. We implemented ODMP in a best first planner that uses a domain specific heuristic for logistics problems and tested its efficiency on a variety of problems, adopted from the AIPS-98 planning competition.