期刊
IEEE TRANSACTIONS ON ROBOTICS
卷 23, 期 1, 页码 151-157出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TRO.2006.886840
关键词
configuration space; kd-trees; nearest-neighbor (NN); searching; probabilistic roadmaps (PRMs); rapidly exploring random trees (RRTs); sampling-based motion planning
类别
The cost of nearest-neighbor (NN) calls is one of the bottle-necks 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 R, S-1, and RP3, the most common topological spaces in the context A 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据