衝突検出か最近傍探索か？サンプリングベース運動計画における計算ボトルネックの解明
Collision detection or nearest-neighbor search? On the computational bottleneck in sampling-based motion planning
サンプリングベース運動計画において最近傍探索が実用上のボトルネックとなり得る状況（NN-sensitive）を特定し、非ユークリッド空間への接続半径の適応法を示した上で、放射状接続とk-NN接続の比較を行った研究。
著者: Michal Kleinbort, Oren Salzman, Dan Halperin
分類: cs.RO, cs.CG
原文アブストラクト
The complexity of nearest-neighbor search dominates the asymptotic running time of many sampling-based motion-planning algorithms. However, collision detection is often considered to be the computational bottleneck in practice. Examining various asymptotically optimal planning algorithms, we characterize settings, which we call NN-sensitive, in which the practical computational role of nearest-neighbor search is far from being negligible, i.e., the portion of running time taken up by nearest-neighbor search is comparable, or sometimes even greater than the portion of time taken up by collision detection. This reinforces and substantiates the claim that motion-planning algorithms could significantly benefit from efficient and possibly specifically-tailored nearest-neighbor data structures. The asymptotic (near) optimality of these algorithms relies on a prescribed connection radius, defining a ball around a configuration $q$, such that $q$ needs to be connected to all other configurations in that ball. To facilitate our study, we show how to adapt this radius to non-Euclidean spaces, which are prevalent in motion planning. This technical result is of independent interest, as it enables to compare the radial-connection approach with the common alternative, namely, connecting each configuration to its $k$ nearest neighbors ($k$-NN). Indeed, as we demonstrate, there are scenarios where using the radial connection scheme, a solution path of a specific cost is produced ten-fold (and more) faster than with $k$-NN.
