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 language | English |
---|---|
Pages (from-to) | 1246-1257 |
Number of pages | 12 |
Journal | International Journal of Robotics Research |
Volume | 27 |
Issue number | 11-12 |
DOIs | |
State | Published - Nov 2008 |
Keywords
- Cell decomposition
- Cell labelling
- Path non-existence
- Penetration depth