• Improving Motion Planning Algorithms by Efficient Nearest Neighbor Searching (pdf)
    Anna Yershova and Steven M. LaValle
    IEEE Transactions on Robotics, 23(1):151-157, February 2007

  • Efficient Nearest Neighbor Searching for Motion Planning (pdf)
    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).