瓶颈
计算机科学
碰撞
采样(信号处理)
k-最近邻算法
人工智能
模式识别(心理学)
计算机视觉
计算机安全
滤波器(信号处理)
嵌入式系统
作者
Michal Kleinbort,Oren Salzman,Dan Halperin
出处
期刊:Springer proceedings in advanced robotics
日期:2020-01-01
卷期号:: 624-639
被引量:4
标识
DOI:10.1007/978-3-030-43089-4_40
摘要
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 to, 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 specially-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.
科研通智能强力驱动
Strongly Powered by AbleSci AI