Efficient Cell Labelling and Path Non-existence Computation Using C-obstacle Query #1

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 [Liangjun Zhang, Young J. Kim, and Dinesh Manocha].

http://gamma.cs.unc.edu/NOPATH/

Category:

Science & Technology