Volume 27 Issue 11-12 - Publication Date: 1 November 2008
Efficient Cell Labelling and Path Non-existence Computation using C-obstacle Query
Liangjun Zhang Department of Computer Science,University of North Carolina at Chapel Hill, Chapel Hill, NC, USA, Young J. Kim Department of Computer Science and Engineering, Ewha Women’s University, South Korea and Dinesh Manocha Department of Computer Science, University of North Carolina at Chapel Hill, Chapel Hill, NC, USA
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.
Return to Contents