TY - JOUR
T1 - Improving motion-planning algorithms by efficient nearest-neighbor searching
AU - Yershova, Anna
AU - LaValle, Steven M.
N1 - Funding Information:
Manuscript received December 5, 2005; revised May 24, 2006. This paper was recommended for publication by Associate Editor P. Rives and Editor L. Parker upon evaluation of the reviewers’ comments. This work was supported in part by the National Science Foundation under CAREER Award IRI-9875304, NSF ANI-0208891, and NSF IIS-0118146. This paper was presented in part at the IEEE International Conference on Robotics and Automation, Washington, DC, 2002.
PY - 2007/2
Y1 - 2007/2
N2 - The cost of nearest-neighbor (NN) calls is one of the bottlenecks in the performance of sampling-based motion-planning algorithms. Therefore, it is crucial to develop efficient techniques for NN searching in configuration spaces arising in motion planning. In this paper, we present and implement an algorithm for performing NN queries in Cartesian products of ℝ, S1, and ℝP3, the most common topological spaces in the context of motion planning. Our approach extends the algorithm based on kd-trees, called ANN, developed by Arya and Mount for Euclidean spaces. We prove the correctness of the algorithm and illustrate substantial performance improvement over the brute-force approach and several existing NN packages developed for general metric spaces. Our experimental results demonstrate a clear advantage of using the proposed method for both probabilistic roadmaps and rapidly exploring random trees.
AB - The cost of nearest-neighbor (NN) calls is one of the bottlenecks in the performance of sampling-based motion-planning algorithms. Therefore, it is crucial to develop efficient techniques for NN searching in configuration spaces arising in motion planning. In this paper, we present and implement an algorithm for performing NN queries in Cartesian products of ℝ, S1, and ℝP3, the most common topological spaces in the context of motion planning. Our approach extends the algorithm based on kd-trees, called ANN, developed by Arya and Mount for Euclidean spaces. We prove the correctness of the algorithm and illustrate substantial performance improvement over the brute-force approach and several existing NN packages developed for general metric spaces. Our experimental results demonstrate a clear advantage of using the proposed method for both probabilistic roadmaps and rapidly exploring random trees.
KW - Configuration space
KW - Kd-trees
KW - Nearest-neighbor (NN) searching
KW - Probabilistic roadmaps (PRMs)
KW - Rapidly exploring random trees (RRTs)
KW - Sampling-based motion planning
UR - http://www.scopus.com/inward/record.url?scp=33947427085&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33947427085&partnerID=8YFLogxK
U2 - 10.1109/TRO.2006.886840
DO - 10.1109/TRO.2006.886840
M3 - Article
AN - SCOPUS:33947427085
SN - 1552-3098
VL - 23
SP - 151
EP - 157
JO - IEEE Transactions on Robotics
JF - IEEE Transactions on Robotics
IS - 1
ER -