Efficient cell labelling and path non-existence computation using C-obstacle query

Liangjun Zhang, Young J. Kim, Dinesh Manocha

Research output: Contribution to journalArticlepeer-review

25 Scopus citations

Abstract

We present a simple algorithm to check for path non-existence for a low-degree-of-freedom (DOF) robot among static obstacles. Our algorithm is based on approximate cell decomposition of configuration space or C-space. We use C-obstacle cell query to check whether a cell lies entirely inside the C-obstacle region. This reduces the path non-existence problem to checking whether a path exists through the set of all cells that do not lie entirely inside the C-obstacle region. We present a simple and efficient algorithm to perform C-obstacle cell query using generalized penetration depth computation. Our algorithm is simple to implement and we demonstrate its performance on three-DOF and four-DOF robots.

Original languageEnglish
Pages (from-to)1246-1257
Number of pages12
JournalInternational Journal of Robotics Research
Volume27
Issue number11-12
DOIs
StatePublished - Nov 2008

Keywords

  • Cell decomposition
  • Cell labelling
  • Path non-existence
  • Penetration depth

Fingerprint

Dive into the research topics of 'Efficient cell labelling and path non-existence computation using C-obstacle query'. Together they form a unique fingerprint.

Cite this