Efficient nearest neighbor searching for motion planning

Anna Atramentov, Steven M Lavalle

Research output: Contribution to journalConference articlepeer-review

Abstract

We present and implement an efficient algorithm for performing nearest-neighbor queries in topological spaces that usually arise in the context of motion planning. Our approach extends the Kd tree-based ANN algorithm, which was developed by Arya and Mount for Euclidean spaces. We argue the correctness of the algorithm and illustrate its efficiency through computed examples. We have applied the algorithm to both probabilistic roadmaps (PRMs) and Rapidly-exploring Random Trees (RRTs). Substantial performance improvements are shown for motion planning examples.

Original languageEnglish (US)
Pages (from-to)632-637
Number of pages6
JournalProceedings - IEEE International Conference on Robotics and Automation
Volume1
StatePublished - Jan 1 2002
Externally publishedYes
Event2002 IEEE International Conference on Robotics and Automation - Washington, DC, United States
Duration: May 11 2002May 15 2002

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Efficient nearest neighbor searching for motion planning'. Together they form a unique fingerprint.

Cite this