The sampling-based neighborhood graph: An approach to computing and executing feedback motion strategies

Research output: Contribution to journalArticlepeer-review

Abstract

This paper presents a sampling-based approach to computing and executing feedback-motion strategies by defining a global navigation function over a collection of neighborhoods in configuration space. The collection of neighborhoods and their underlying connectivity structure are captured by a sampling-based neighborhood graph (SNG), on which navigation functions are built. The SNG construction algorithm incrementally places new neighborhoods in the configuration space, using distance information provided by existing collision-detection algorithms. A termination condition indicates the probability that a specified fraction of the space is covered. Our implementation illustrates the approach for rigid and articulated bodies with up to six-dimensional configuration spaces. Even over such spaces, rapid online responses to unpredictable configuration changes can be made in a few microseconds on standard PC hardware. Furthermore, if the goal is changed, an updated navigation function can be quickly computed without performing additional collision checking.

Original languageEnglish (US)
Pages (from-to)419-432
Number of pages14
JournalIEEE Transactions on Robotics and Automation
Volume20
Issue number3
DOIs
StatePublished - Jun 2004

Keywords

  • Feedback control
  • Motion planning
  • Navigation functions
  • Potential fields

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'The sampling-based neighborhood graph: An approach to computing and executing feedback motion strategies'. Together they form a unique fingerprint.

Cite this