DOI
10.1109/LRA.2020.3017472
Abstract
Nearest-neighbor finding is a major bottleneck for sampling-based motion planning algorithms. The cost of finding nearest neighbors grows with the size of the roadmap, leading to a significant computational bottleneck for problems which require many configurations to find a solution. In this work, we develop a method of mapping configurations of a jointed robot to neighborhoods in the workspace that supports fast search for configurations in nearby neighborhoods. This expedites nearest-neighbor search by locating a small set of the most likely candidates for connecting to the query with a local plan. We show that this filtering technique can preserve asymptotically-optimal guarantees with modest requirements on the distance metric. We demonstrate the method’s efficacy in planning problems for rigid bodies and both fixed and mobile-base manipulators.
Document Type
Post-print Article
Publication Date
10-2020
Publisher Statement
The definitive version is available at: IEEE Robotics and Automation.
Under a Creative Commons License.
CCBY - IEEE is not the copyright holder of this material. Please follow the instructions via https://creativecommons.org/licenses/by/4.0/ to obtain full-text articles and stipulations in the API documentation.
Recommended Citation
Sandstrom, Read, Jory Denny, and Nancy M. Amato. “Asymptotically-Optimal Topological Nearest-Neighbor Filtering.” IEEE Robotics and Automation Letters 5, no. 4 (October 2020): 6916–23. https://doi.org/10.1109/LRA.2020.3017472.