改进采样运动规划中最近邻搜索，提升狭窄通道通过效率
Edge Nearest Neighbor in Sampling-Based Motion Planning
- 在树边集合上定义邻域，用层次数据结构加速最近邻查找
- 实验表明新方法路径生成更快，尤其在狭窄通道场景下效率提升显著
- 适合研究机器人路径规划、需要高效探索的算法开发者
基于采样的运动规划算法依赖于邻域查找和最近邻查询。采用不同的距离度量或邻域定义会带来具有独特理论与实证特性的算法。在文献\cite{l-pa-06}中，LaValle提出了针对快速扩展随机树（RRT）算法\cite{l-rrtnt-98}的邻域查找方法，该方法在树的所有边构成的曲面上寻找采样点的最近邻，并使用层次化数据结构实现。本文实现了该邻域查找器，并从理论和实验两方面证明其能显著提高算法效率。此外，我们提出了一种改进的快速扩展随机图（RRG）算法\cite{f-isaom-10}变体，更充分地利用了新子程序在探索狭窄通道方面的优势。
原文摘要 · Abstract (English)
Neighborhood finders and nearest neighbor queries are fundamental parts of sampling based motion planning algorithms. Using different distance metrics or otherwise changing the definition of a neighborhood produces different algorithms with unique empiric and theoretical properties. In \cite{l-pa-06} LaValle suggests a neighborhood finder for the Rapidly-exploring Random Tree RRT algorithm \cite{l-rrtnt-98} which finds the nearest neighbor of the sampled point on the swath of the tree, that is on the set of all of the points on the tree edges, using a hierarchical data structure. In this paper we implement such a neighborhood finder and show, theoretically and experimentally, that this results in more efficient algorithms, and suggest a variant of the Rapidly-exploring Random Graph RRG algorithm \cite{f-isaom-10} that better exploits the exploration properties of the newly described subroutine for finding narrow passages.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。