Quantitative Analysis of Nearest Neighbors Search in High-Dimensional Sampling-based Motion Planning

Publication Type:

Conference Paper

Authors:

Plaku, E.; Kavraki, L.E.

Source:

Workshop on Algorithmic Foundations of Robotics (WAFR), New York, NY (2006)

URL:

http://www.kavrakilab.org/sites/default/files/PaperWAFR_DPES-h.pdf

Keywords:

proximity relations; path planning; project_Proximity

Abstract:

We quantitatively analyze the performance of exact and
approximate nearest-neighbors algorithms on increasingly
high-dimensional problems in the context of sampling-based motion
planning. We study the impact of the dimension, number of samples,
distance metrics, and sampling schemes on the efficiency and
accuracy of nearest-neighbors algorithms. Efficiency measures
computation time and accuracy indicates similarity between exact and
approximate nearest neighbors.

Our analysis indicates that after a critical dimension, which varies
between 15 and 30, exact nearest-neighbors algorithms examine almost
all the samples. As a result, exact nearest-neighbors algorithms
become impractical for sampling-based motion planners when a
considerably large number of samples needs to be generated. The
impracticality of exact nearest-neighbors algorithms motivates the use
of approximate algorithms, which trade off accuracy for efficiency. We
propose a simple algorithm, termed Distance-based Projection onto
Euclidean Space (DPES), which computes approximate nearest neighbors
by using a distance-based projection of high-dimensional metric spaces
onto low-dimensional Euclidean spaces. Our results indicate DPES
achieves high efficiency and only a negligible loss in accuracy.