A general framework for sampling on the medial axis of the free space

Jyh Ming Lien, Shawna L. Thomas, Nancy M. Amato

Research output: Contribution to journalConference articlepeer-review


We propose a general framework for sampling the configuration space in which randomly generated configurations, free or not, are retracted onto the medial axis of the free space. Generalizing our previous work, this framework provides a template encompassing all possible retraction approaches. It also removes the requirement of exactly computing distance metrics thereby enabling application to more realistic high dimensional problems. In particular, our framework supports methods that retract a given configuration exactly or approximately onto the medial axis. As in our previous work, exact methods provide fast and accurate retraction in low (2 or 3) dimensional space. We also propose new approximate methods that can be applied to high dimensional problems, such as many DOF articulated robots. Theoretical and experimental results show improved performance on problems requiring traversal of narrow passages. We also study tradeoffs between accuracy and efficiency for different levels of approximation, and how the level of approximation effects the quality of the resulting roadmap.

Original languageEnglish (US)
Pages (from-to)4439-4444
Number of pages6
JournalProceedings - IEEE International Conference on Robotics and Automation
StatePublished - 2003
Externally publishedYes
Event2003 IEEE International Conference on Robotics and Automation - Taipei, Taiwan, Province of China
Duration: Sep 14 2003Sep 19 2003

ASJC Scopus subject areas

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


Dive into the research topics of 'A general framework for sampling on the medial axis of the free space'. Together they form a unique fingerprint.

Cite this