An improved random neighborhood graph approach

Libo Yang, Steven M Lavalle

Research output: Contribution to journalConference articlepeer-review


As a general framework to determine a collision-free feedback motion strategies, the Random Neighborhood Graph (RNG) approach [19] defines a global navigation function over an approximate representation of the free configuration. In this paper, we improve the RNG approach in several aspects. We present an ANN-accelerated RNG construction algorithm to achieve near logarithmic running time in each iteration of the RNG expansion. Two probabilistic termination conditions of the RNG construction algorithm are presented and analyzed. To help overcome the difficulty of narrow corridors, we also introduce a randomized perturbation algorithm to enhance the sampling quality. Our implementation illustrates a significant performance improvement.

Original languageEnglish (US)
Pages (from-to)254-259
Number of pages6
JournalProceedings - IEEE International Conference on Robotics and Automation
StatePublished - 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


Dive into the research topics of 'An improved random neighborhood graph approach'. Together they form a unique fingerprint.

Cite this