Topology preserving approximation of free configuration space

Gokul Varadhan, Young J. Kim, Shankar Krishnan, Dinesh Manocha

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

13 Scopus citations

Abstract

We present a simple algorithm for approximating the free configuration space of robots with low degrees of freedom (DOFs). We represent the free space as an arrangement of contact surfaces. We approximate the free space using an adaptive volumetric grid that is computed by performing simple geometric tests on the contact surfaces. We use an isosurface extraction algorithm to compute a piecewise-linear approximation to the boundary of the free space. We prove that our approximation is topologically equivalent to the exact free space boundary. We also ensure that our approximation is geometrically close to the exact free space boundary by bounding its two-sided Hausdorff error. We have applied our algorithm to compute the free configuration space for the following instances: (1) a 2D polygonal robot with translational and rotational DOFs navigating among polygonal obstacles, and (2) a 3D polyhedral robot translating among polyhedral obstacles. In practice, our algorithm works well on robots with three DOFs.

Original languageEnglish
Title of host publicationProceedings 2006 IEEE International Conference on Robotics and Automation, ICRA 2006
Pages3041-3048
Number of pages8
DOIs
StatePublished - 2006
Event2006 IEEE International Conference on Robotics and Automation, ICRA 2006 - Orlando, FL, United States
Duration: 15 May 200619 May 2006

Publication series

NameProceedings - IEEE International Conference on Robotics and Automation
Volume2006
ISSN (Print)1050-4729

Conference

Conference2006 IEEE International Conference on Robotics and Automation, ICRA 2006
Country/TerritoryUnited States
CityOrlando, FL
Period15/05/0619/05/06

Fingerprint

Dive into the research topics of 'Topology preserving approximation of free configuration space'. Together they form a unique fingerprint.

Cite this