Concurrent Nearest-Neighbor Searching for Parallel Sampling-Based Motion Planning in SO(3), SE(3), and Euclidean Spaces
Concurrent Nearest-Neighbor Searching for Parallel Sampling-Based Motion Planning in SO(3), SE(3), and Euclidean Spaces
复制标题
SO(3)、SE(3) 和欧几里德空间中基于并行采样的运动规划的并发最近邻搜索
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
R. Alterovitz
中科院分区：
文献类型：
--
作者：
Jeffrey Ichnowski;R. Alterovitz
本文提出了一种快速精确最近邻搜索数据结构和方法，设计用于在现代多核处理器上的高并发并行操作下操作。基于kd树，该方法是快速的，支持度量空间常见的机器人运动规划，并支持最近的，k-最近的，基于半径的查询。但与传统的方法使用kd树，我们的方法支持并发下的并发查询和插入，支持无等待查询，并提供渐进减少随机并发插入的预期等待时间。我们提供的并发下的正确性证明，我们证明了所提出的方法的性能在一个并行化的渐近最优采样为基础的运动规划。
This paper presents a fast exact nearest neighbor searching data structure and method that is designed to operate under highly-concurrent parallel operation on modern multi-core processors. Based on a kd-tree, the proposed method is fast, supports metric spaces common to robot motion planning, and supports nearest, k-nearest, and radius-based queries. But unlike traditional approaches using kd-trees, our approach supports simultaneous queries and insertions under concurrency, supports wait-free queries, and provides asymptotically diminishing expected wait-times for random concurrent inserts. We provide proofs of correctness under concurrency, and we demonstrate the proposed method’s performance in a parallelized asymptotically-optimal sampling-based motion planner.