| Publications |
Anna Yershova and Steven M. LaValle IEEE Transactions on Robotics, 23(1):151-157, February 2007 Anna Yershova and Steven M. LaValle In Proc. IEEE International Conference on Robotics and Automation (ICRA 2002) |
| Software |
mpnn.tar.gz The cost of nearest neighbor calls is one of the bottlenecks in the performance of sampling-based motion planning algorithms. Therefore, it is crucial to develop efficient techniques for nearest neighbor searching in configuration spaces arising in motion planning. This software is an implementation of an algorithm for performing nearest-neighbor queries in Cartesian products of Euclidean one-space, circle, and three-dimensional rotation group, SO(3), which are 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. In our experiments using this library we have observed substantial performance improvement over brute force approach and several existent nearest neighbor packages developed for general metric spaces. Our experimental results demonstrate clear advantage of using this library for both probabilistic roadmaps (PRMs) and Rapidly-exploring Random Trees (RRTs). |