Most modern PCs and mobile devices have between 2 and 32 processing cores, and that number is increasing. We have developed 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. These methods explicitly leverage parallel, multi-core architectures to introduce substantial speedups in motion planning.
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 have demonstrated fast performance and superlinear speedups in multiple scenarios, including using an Aldebaran Nao small humanoid robot performing 2-handed manipulation tasks using 10 degrees of freedom.
This research is made possible by support from the National Science Foundation (NSF) under awards IIS-1117127, IIS-1149965, CNS-1305286, and CCF-1533844. Any opinions, findings, and conclusions or recommendations expressed on this web site do not necessarily reflect the views of NSF.