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

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.