Parallel sampling-based motion planning with superlinear speedup

We present PRRT (Parallel RRT) and PRRT* (Parallel RRT*), sampling-based methods for feasible and optimal motion planning that are tailored to execute on modern multi-core CPUs. Our algorithmic improvements enable PRRT and PRRT* to achieve a superlinear speedup: when p processor cores are used instead of 1 processor core, computation time is sped up by a factor greater than p. To achieve this superlinear speedup, our algorithms utilize three key features: (1) lock-free parallelism using atomic operations to eliminate slowdowns caused by lock overhead and contention, (2) partition-based sampling to reduce the size of each processor core's working data set to improve cache efficiency, and (3) parallel backtracking to reduce the number of rewiring steps performed in PRRT*. Our parallel algorithms retain the ability to integrate with existing CPU-based libraries and algorithms. We demonstrate fast performance and superlinear speedups in two scenarios: (1) a holonomic disc-shaped robot moving in a planar environment and (2) an Aldebaran Nao small humanoid robot performing a 2-handed manipulation task using 10 DOF.

Authors

• Jeffrey Ichnowski
• Ron Alterovitz

Keywords

• Multicore processing
• Instruction sets
• Data structures
• Planning
• Robots
• Partitioning algorithms
• Image edge detection
• Path Planning
• Parallel Motion
• Sampling-based Motion
• Super-linear Speedup
• Computation Time
• Core Processes
• Linearizable
• Core Work
• Small Robot
• Rapidly-exploring Random Tree
• Right-hand
• Data Structure
• Parallelization
• Configuration Space
• Short Path
• Nearest Neighbor Search
• Voronoi Diagram
• Collision Detection
• Multiple Cores
• Non-overlapping Regions
• Sequential Execution
• Cost Path
• Robot Configuration
• Multiple Threads
• L2 Cache