Nearest Neighbor Search Methods

The motion planning problem consists of finding a valid path for a robot (movable object) from a start configuration to a goal configuration without colliding with any obstacle. Probabilistic road map (PRM) methods use randomization to construct a graph (road map) of collision-free paths that attempts to capture the connectivity of the configuration space.Random sampling strategies are the methods used to select collision-free robot configurations.Unlike uniform samplers, they also yield configurations in the narrow passages which is very important in crowded situations. The configurations generated by random sampling are to be connected to the nearby configurations. Some road maps contain thousands of configurations, which can lead to substantial computation time for determining the nearby configurations. Therefore, an approach that efficiently finds nearest neighbors can dramatically improve the performance of path planners. The brute force method of nearest neighbor search has a complexity of O(n2).This increases the running time and hence the cost. 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. This paper analyses the existing k-closest nearest neighbor search methods in our library,compares it with the brute force method and evaluates the pros and cons of each of the existing methods.