A simple path non-existence algorithm using C-obstacle query

Liangjun Zhang, Young J. Kim, Dinesh Manocha

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

16 Scopus citations

Abstract

We present a simple algorithm to check for path non-existence for a robot among static obstacles. Our algorithm is based on adaptive cell decomposition of configuration space or C-space. We use two basic queries: free cell query, which checks whether a cell in C-space lies entirely inside the free space, and C-obstacle cell query, which checks whether a cell lies entirely inside the C-obstacle region. Our approach reduces the path non-existence problem to checking whether there exists a path through cells that do not belong to the C-obstacle region. We describe simple and efficient algorithms to perform free cell and C-obstacle cell queries using separation distance and generalized penetration depth computations. Our algorithm is simple to implement and we demonstrate its performance on 3 DOF robots.

Original languageEnglish
Title of host publicationAlgorithmic Foundation of Robotics VII - Selected Contributions of the Seventh International Workshop on the Algorithmic Foundations of Robotics
Pages269-284
Number of pages16
DOIs
StatePublished - 2008
Event7th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2006 - New York, NY, United States
Duration: 16 Jul 200618 Jul 2006

Publication series

NameSpringer Tracts in Advanced Robotics
Volume47
ISSN (Print)1610-7438
ISSN (Electronic)1610-742X

Conference

Conference7th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2006
Country/TerritoryUnited States
CityNew York, NY
Period16/07/0618/07/06

Fingerprint

Dive into the research topics of 'A simple path non-existence algorithm using C-obstacle query'. Together they form a unique fingerprint.

Cite this