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. nle 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 emphasize 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.