Fast Motion Planning Using Parallelization on Multi-core CPUs

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.

Parallel motion planning scenario.


Parallel motion planning on 1 core.

1 core for 10ms

Parallel motion planning on 4 cores.

4 cores for 10ms

Parallel motion planning on 32 cores.

32 cores for 10ms

With PRRT*, more CPU cores results in higher quality solutions in the same wall clock time.

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.

Nao robot places an effervescent antacid in a glass of water. Nao robot places an effervescent antacid in a glass of water. Nao robot places an effervescent antacid in a glass of water. Nao robot places an effervescent antacid in a glass of water.

The Aldebaran Nao robot carries an effervescent antacid in one hand and places it over a glass of water held in the other hand, all while avoiding the bottles on the table and not spilling the water. We observed superlinear speedup using PRRT* for this task.

Source Code


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.