Framework for planning feedback motion strategies based on a random neighborhood graph

Libo Yang, Steven M Lavalle

Research output: Contribution to journalArticlepeer-review


Randomized techniques have led to the development of many successful algorithms for path planning in high-dimensional configuration spaces. This paper presents a randomized framework for computing feedback motion strategies, by defining a global navigation function over a collection of spherical balls in the configuration space. If the goal is changed, an updated navigation function can be quickly computed, offering benefits similar to the fast multiple queries permitted by the probabilistic roadmap approach to path planning. Our choice of balls is motivated in part by recent tools from computational geometry which compute point locations and arrangements efficiently without significant dependence on dimension. We present a construction algorithm that includes a Bayesian termination condition based on the probability that a specified fraction of the free space is covered. A basic implementation illustrates the framework for rigid and articulated bodies with up to five-dimensional configuration spaces.

Original languageEnglish (US)
Pages (from-to)544-549
Number of pages6
JournalProceedings - IEEE International Conference on Robotics and Automation
StatePublished - 2000
Externally publishedYes

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'Framework for planning feedback motion strategies based on a random neighborhood graph'. Together they form a unique fingerprint.

Cite this