Collision detection or nearest-neighbor search? On the computational bottleneck in sampling-based motion planning
This addresses efficiency issues for robotics and AI systems using motion planning, though it is incremental in refining existing methods.
The paper tackles the computational bottleneck in sampling-based motion planning by showing that nearest-neighbor search can be as significant as collision detection in practice, and demonstrates that a radial connection scheme can produce solutions up to ten times faster than k-nearest neighbors in certain scenarios.
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.