Scalable Multicore Motion Planning Using Lock-Free Concurrency.
Scalable Multicore Motion Planning Using Lock-Free Concurrency.
复制标题
DOI：
10.1109/tro.2014.2331091
复制
发表时间：
2014-10
期刊：
影响因子：
--
通讯作者：
Alterovitz R
中科院分区：
文献类型：
--
作者：
Ichnowski J;Alterovitz R
我们提出了PRRT（并行RRT）和PRRT*（并行RRT*），基于采样的方法，为现代多核CPU设计的可行和最佳的运动规划。我们将RRT和RRT* 并行化，以便所有线程同时构建单个运动规划树。以这种方式的并行化要求数据结构（诸如最近邻搜索树和运动规划树）在多个线程之间安全地共享。而不是依赖于传统的锁，这可能会导致由于锁争用速度减慢，我们介绍了基于无锁并发使用原子操作的算法。我们通过使用基于分区的采样（缩小每个核心的工作数据集以提高缓存效率）和并行工作节省（减少PRRT* 中执行的重新布线步骤的数量）进一步提高可扩展性。由于PRRT和PRRT* 是基于CPU的，因此它们可以直接与现有库集成。我们证明，PRRT和PRRT* 规模以及核心数量的增加，在某些情况下表现出超线性加速，如阿尔法拼图和立方体的情况下，毕宿五Nao机器人执行双手任务的情况。
We present PRRT (Parallel RRT) and PRRT* (Parallel RRT*), sampling-based methods for feasible and optimal motion planning designed for modern multicore CPUs. We parallelize RRT and RRT* such that all threads concurrently build a single motion planning tree. Parallelization in this manner requires that data structures, such as the nearest neighbor search tree and the motion planning tree, are safely shared across multiple threads. Rather than rely on traditional locks which can result in slowdowns due to lock contention, we introduce algorithms based on lock-free concurrency using atomic operations. We further improve scalability by using partition-based sampling (which shrinks each core’s working data set to improve cache efficiency) and parallel work-saving (in reducing the number of rewiring steps performed in PRRT*). Because PRRT and PRRT* are CPU-based, they can be directly integrated with existing libraries. We demonstrate that PRRT and PRRT* scale well as core counts increase, in some cases exhibiting superlinear speedup, for scenarios such as the Alpha Puzzle and Cubicles scenarios and the Aldebaran Nao robot performing a 2-handed task.