In this paper, we compute a conservative approximation of the path-connected components of the free space of a rigid object in a 2D workspace in order to solve two closely related problems: to determine whether there exists a collision-free path between two given configurations, and to verify whether an object can escape arbitrarily far from its initial configuration -- i.e., whether the object is caged. Furthermore, we consider two quantitative characteristics of the free space: the volume of path-connected components and the width of narrow passages. To address these problems, we decompose the configuration space into a set of two-dimensional slices, approximate them as two-dimensional alpha-complexes, and then study the relations between them. This significantly reduces the computational complexity compared to a direct approximation of the free space. We implement our algorithm and run experiments in a three-dimensional configuration space of a simple object showing runtime of less than 2 seconds.
The problem of proving path non-existence has been addressed by @cite_17 in the context of motion planning, motivated by the fact most of the modern sampling-based planning algorithms do not guarantee that two configurations are disconnected, and rely on stopping heuristics in such situations @cite_10 . prove that two configurations are disconnected when the object is too big' or too long' to pass through a gate' between them. In @cite_19 , use approximate cell decomposition and prove path non-existence. They decompose a configuration space into a set of cells and for each cell decide if it lies in the collision space. In @cite_1 propose a somewhat similar approach. There, they randomly sample the configuration space and reconstruct its approximation as an alpha complex. They later use it to check the connectivity between pairs of configurations.
@cite_1 @cite_19 @cite_10 @cite_17
2114306020 2068375174 2101993361
In this paper, we address the problem determining the connectivity of a robot's free configuration space. Our method iteratively builds a constructive proof that two configurations lie in disjoint components of the free configuration space. Our algorithm first generates samples that correspond to configurations for which the robot is in collision with an obstacle. These samples are then weighted by their generalized penetration distance, and used to construct alpha shapes. The alpha shape defines a collection of simplices that are fully contained within the configuration space obstacle region. These simplices can be used to quickly solve connectivity queries, which in turn can be used to define termination conditions for sampling-based planners. Such planners, while typically either resolution complete or probabilistically complete, are not able to determine when a path does not exist, and therefore would otherwise rely on heuristics to determine when the search for a free path should be abandoned. An implementation of the algorithm is provided for the case of a 3D Euclidean configuration space, and a proof of correctness is provided. 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. Probabilistic road-map (PRM) planners have shown great promise in attacking previously infeasible motion planning problems with many degrees of freedom. Yet when such a planner fails to find a path, it is not clear that no path exists, or that the planner simply did not sample adequately or intelligently the free part of the configuration space. We propose to attack the motion planning problem from the other end, focusing on disconnection proofs, or proofs showing that there exists no solution to the posed motion planning problem. Just as PRM planners avoid generating a complete description of the configuration space, our disconnection provers search for certain special classes of proofs that are compact and easy to find when the motion planning problem is 'obviously impossible," avoiding complex geometric and combinatorial calculations. We demonstrate such a prover in action for a simple, yet still realistic, motion planning problem. When it fails, the prover suggests key milestones, or configurations of the robot that can then be passed on and used by a PRM planner. Thus by hitting the motion planning problem from both ends, we hope to resolve the existence of a path, except in truly delicate border-line situations.