A Decomposition-Based Approach to Reasoning about Free Space Path-Connectivity for Rigid Objects in 2D
This addresses path planning and caging verification for robotics, but it is incremental as it builds on existing decomposition and approximation methods.
The paper tackles the problem of determining collision-free paths and verifying caging for rigid objects in 2D by computing a conservative approximation of free space path-connected components, achieving runtime of less than 2 seconds in experiments.
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.