Improving motion-planning algorithms by efficient nearest-neighbor searching

Anna Yershova, Steven M. LaValle

Research output: Contribution to journalArticlepeer-review


The cost of nearest-neighbor (NN) calls is one of the bottlenecks in the performance of sampling-based motion-planning algorithms. Therefore, it is crucial to develop efficient techniques for NN searching in configuration spaces arising in motion planning. In this paper, we present and implement an algorithm for performing NN queries in Cartesian products of ℝ, S1, and ℝP3, 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. We prove the correctness of the algorithm and illustrate substantial performance improvement over the brute-force approach and several existing NN packages developed for general metric spaces. Our experimental results demonstrate a clear advantage of using the proposed method for both probabilistic roadmaps and rapidly exploring random trees.

Original languageEnglish (US)
Pages (from-to)151-157
Number of pages7
JournalIEEE Transactions on Robotics
Issue number1
StatePublished - Feb 2007


  • Configuration space
  • Kd-trees
  • Nearest-neighbor (NN) searching
  • Probabilistic roadmaps (PRMs)
  • Rapidly exploring random trees (RRTs)
  • Sampling-based motion planning

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Improving motion-planning algorithms by efficient nearest-neighbor searching'. Together they form a unique fingerprint.

Cite this