Randomized Motion Planning on Parallel and Distributed Architectures

Motion planning is a fundamental problem in a number of application areas, including robotics, automation, and virtual reality. This paper describes a parallel implementation of a motion planning algorithm particularly suited for complex systems characterized by many degrees of freedom. The implementation is based on the concurrent exploration of the search space by a randomized planner replicated on each node of the parallel architecture. All processing elements compete to obtain a solution over the entire search space in an OR-parallel fashion. Reported results refer to a low-cost cluster of PCs and an SGI Onyx2 parallel machine. The experiments emphasise the effectiveness of the approach for complex, high-dimensionality planning problems, We believe that the approach may be useful in other complex search problems, especially when the parallel architecture exhibits relatively high communication latency.