Probabilistic Roadmap Methods are Embarrassingly Parallel

In this paper we report on our experience in parallelizing probabilistic roadmap motion planning methods (PRMs). We show that significant, scalable speed-ups can be obtained with relatively little effort on the part of the developer. Our experience is not limited to PRMs. In particular, we outline general techniques for parallelizing types of computations commonly performed in motion planning algorithms, and identify potential difficulties that might be faced in other efforts to parallelize sequential motion planning methods.

Authors

• Nancy M. Amato
• Lucia K. Dale

Keywords

• Motion planning
• Robot kinematics
• Robotics and automation
• Virtual reality
• Concurrent computing
• Computer science
• Application software
• Design automation
• Engineering profession
• Animation
• Embarrassingly Parallel
• Meth-ods
• Parallelization
• Path Planning
• Planning Methods
• Data Structure
• Urban Planning
• Multiple Phases
• Hash Function
• Problem Size
• Probabilistic Method
• Node Connectivity
• Parallel Method
• Sequential Algorithm
• Serialized
• Collision Detection
• Parallel Algorithm
• Parallel Implementation
• Parallel Connection
• Multiple Processors
• Real-time Solution
• Robot Configuration
• Global Structure Of Data