TY - JOUR
T1 - Asymptotically-Optimal Topological Nearest-Neighbor Filtering
AU - Sandstrom, Read
AU - Denny, Jory
AU - Amato, Nancy M.
N1 - Manuscript received February 24, 2020; accepted June 26, 2020. Date of publication August 18, 2020; date of current version September 30, 2020. This letter was recommended for publication by Associate Editor J. O’Kane and Editor D. Song upon evaluation of the Reviewers’ comments. This work was supported by NSF Awards under Grants CSF-1439145, CCF-1423111, EFRI-1240483, and RI-1217991. (Corresponding author: Nancy M. Amato.) Read Sandström is with the Department of Computer Science and Engineering Parasol Laboratory, Texas A&M University, College Station, TX 77840 USA (e-mail: [email protected]).
PY - 2020/10
Y1 - 2020/10
N2 - 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 letter, 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.
AB - 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 letter, 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.
KW - Motion and path planning
KW - semantic scene understanding
UR - http://www.scopus.com/inward/record.url?scp=85092554804&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85092554804&partnerID=8YFLogxK
U2 - 10.1109/LRA.2020.3017472
DO - 10.1109/LRA.2020.3017472
M3 - Article
AN - SCOPUS:85092554804
SN - 2377-3766
VL - 5
SP - 6916
EP - 6923
JO - IEEE Robotics and Automation Letters
JF - IEEE Robotics and Automation Letters
IS - 4
M1 - 9170802
ER -