Self-indexed motion planning

Angello Hoyos

doi:10.1016/j.is.2019.04.011

2020-01-01

PRE

DOI：10.1016/j.is.2019.04.011

原文链接

原文求助

摘要

En 中文

Motion planning is a central problem for robotics. A practical way to address it is building a graph-based representation (a roadmap) capturing the connectivity of the configuration space. The Probabilistic Road Map (PRM) is perhaps the most widely used method by the robotics community based on that idea. A key sub-problem for discovering and maintaining a collision-free path in the PRM is inserting new sample points and connecting them with the k-nearest neighbors in the previous set. Instead of following the usual solution of indexing the points and then building the PRM with successive k-NN queries, we propose an approximation of the k-Nearest Neighbors Graph using the PRM as a self-index. The motivation for this construction comes from the Approximate Proximity Graph (APG), which is an index for searching proximal objects in a metric space. Using this approach the estimation of the k-NN is improved while simultaneously reducing the total time and space needed to compute a PRM. We present simulations for high-dimensional configuration spaces with and without obstacles, showing significant improvement over the standard techniques used by the robotics community. (C) 2019 Elsevier Ltd. All rights reserved.

Keyword:

Motion planning

Approximate proximity graphs

Probabilistic roadmaps