2025/06/16 by Stav Ashur, Ashur, Stav, Nancy M. Amato +3
Computer Science · Engineering · #Advanced Vision and Imaging #FOS: Computer and information sciences #Robotic Path Planning Algorithms #Robotics (cs.RO) #Robotics and Sensor-Based Localization
paper · pdf · doi:10.48550/arxiv.2506.13753
openalex publication_date 2025/06/16 · openalex created_date 2025/10/13 · openalex updated_date 2026/07/28
Neighborhood finders and nearest neighbor queries are fundamental parts of sampling based motion planning algorithms. Using different distance metrics or otherwise changing the definition of a neighborhood produces different algorithms with unique empiric and theoretical properties. In \citel-pa-06 LaValle suggests a neighborhood finder for the Rapidly-exploring Random Tree RRT algorithm \citel-rrtnt-98 which finds the nearest neighbor of the sampled point on the swath of the tree, that is on the set of all of the points on the tree edges, using a hierarchical data structure. In this paper we implement such a neighborhood finder and show, theoretically and experimentally, that this results in more efficient algorithms, and suggest a variant of the Rapidly-exploring Random Graph RRG algorithm \citef-isaom-10 that better exploits the exploration properties of the newly described subroutine for finding narrow passages.