全ペアr近傍探索による高速・高品質な動作計画
Efficient high-quality motion planning by fast all-pairs r-nearest-neighbors
ランダム変換グリッド(RTG)を用いてサンプリングベース動作計画の近傍探索を高速化し、高品質解への収束とPRM構築の2〜3倍の高速化を実現した。
著者: Michal Kleinbort, Oren Salzman, Dan Halperin
分類: cs.RO
原文アブストラクト
Sampling-based motion-planning algorithms typically rely on nearest-neighbor (NN) queries when constructing a roadmap. Recent results suggest that in various settings NN queries may be the computational bottleneck of such algorithms. Moreover, in several asymptotically-optimal algorithms these NN queries are of a specific form: Given a set of points and a radius r report all pairs of points whose distance is at most r. This calls for an application-specific NN data structure tailored to efficiently answering this type of queries. Randomly transformed grids (RTG) were recently proposed by Aiger et al. as a tool to answer such queries and have been shown to outperform common implementations of NN data structures in this context. In this work we employ RTG for sampling-based motion-planning algorithms and describe an efficient implementation of the approach. We show that for motion-planning, RTG allow for faster convergence to high-quality solutions when compared with existing NN data structures. Additionally, RTG enable significantly shorter construction times for batched-PRM variants; specifically, we demonstrate a speedup by a factor of two to three for some scenarios.
