DocumentCode :
3570318
Title :
Efficient nearest neighbor searching for motion planning
Author :
Atramentov, Anna ; LaValle, Steven M.
Author_Institution :
Dept. of Comput. Sci., Iowa State Univ., Ames, IA, USA
Volume :
1
fYear :
2002
fDate :
6/24/1905 12:00:00 AM
Firstpage :
632
Abstract :
We present and implement an efficient algorithm for performing nearest-neighbor queries in topological spaces that usually arise in the context of motion planning. Our approach extends the Kd tree-based ANN algorithm, which was developed by Arya and Mount (1993) for Euclidean spaces. We argue the correctness of the algorithm and illustrate its efficiency through computed examples. We have applied the algorithm to both probabilistic roadmaps (PRMs) and rapidly-exploring random trees (RRTs). Substantial performance improvements are shown for motion planning examples.
Keywords :
computational complexity; neural nets; path planning; search problems; trees (mathematics); Euclidean spaces; Kd tree-based ANN algorithm; PRM; RRT; efficient nearest neighbor searching; motion planning; neural nets; probabilistic roadmaps; rapidly-exploring random trees; topological spaces; Computer science; Data structures; Extraterrestrial measurements; Machine learning algorithms; Nearest neighbor searches; Packaging; Path planning; Pattern recognition; Process planning; Topology;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Robotics and Automation, 2002. Proceedings. ICRA '02. IEEE International Conference on
Print_ISBN :
0-7803-7272-7
Type :
conf
DOI :
10.1109/ROBOT.2002.1013429
Filename :
1013429
Link To Document :
بازگشت