Self-indexed motion planning

摘要

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.