<?xml version="1.0" encoding="UTF-8"?><xml><records><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>47</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Plaku, E.</style></author><author><style face="normal" font="default" size="100%">L. E. Kavraki</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">Quantitative Analysis of Nearest Neighbors Search in High-Dimensional Sampling-based Motion Planning</style></title><secondary-title><style face="normal" font="default" size="100%">Workshop on Algorithmic Foundations of Robotics (WAFR)</style></secondary-title></titles><keywords><keyword><style  face="normal" font="default" size="100%">kavrakilab</style></keyword><keyword><style  face="normal" font="default" size="100%">path planning</style></keyword><keyword><style  face="normal" font="default" size="100%">project_Proximity</style></keyword><keyword><style  face="normal" font="default" size="100%">proximity relations</style></keyword></keywords><dates><year><style  face="normal" font="default" size="100%">2006</style></year></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://www.wafr.org/papers/p31.pdf</style></url></web-urls></urls><pub-location><style face="normal" font="default" size="100%">New York, NY</style></pub-location><language><style face="normal" font="default" size="100%">eng</style></language><abstract><style face="normal" font="default" size="100%">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.</style></abstract><work-type><style face="normal" font="default" size="100%">inproceedings</style></work-type></record></records></xml>