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.
Scenario
1 core for 10ms
4 cores for 10ms
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.
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
Publications
- Jeffrey Ichnowski and Ron Alterovitz, "Motion Planning Templates: A Motion Planning Framework for Robots with Low-power CPUs," in Proc. IEEE International Conference on Robotics and Automation (ICRA), May 2019. (Download PDF) (Software)
- Jeffrey Ichnowski and Ron Alterovitz, "Concurrent Nearest-Neighbor Searching for Parallel Sampling-based Motion Planning in SO(3), SE(3), and Euclidean Topologies," in Algorithmic Foundations of Robotics (WAFR 2018), Dec. 2018, pp. 1-16. (Download PDF) (Software)
- Jeffrey Ichnowski and Ron Alterovitz, "Scalable Multicore Motion Planning Using Lock-Free Concurrency," IEEE Transactions on Robotics, vol. 30, no. 5, pp. 1123-1136, Oct. 2014. (Publisher) (Download PDF) (Software)
- Jeffrey Ichnowski, Jan F. Prins, and Ron Alterovitz, "Cache-Aware Asymptotically-Optimal Sampling-Based Motion Planning," in Proc. IEEE International Conference on Robotics and Automation (ICRA), May 2014, pp. 5804-5810. (Publisher) (Download PDF)
- Jeffrey Ichnowski and Ron Alterovitz, "Parallel Sampling-Based Motion Planning with Superlinear Speedup," in Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Oct. 2012, pp. 1206-1212. (Publisher) (Download PDF) (Software)
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.