Approximating C_free Space Topology by Constructing Vietoris-Rips Complex

摘要

We present a new way of constructing sparse roadmaps using point clouds that approximates and measures the underlying topology of the C <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">free</sub> space. The main advantage of the constructed roadmap is its homotopy equivalence to the η-offset of the C <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">free</sub> space. Though only used to plan paths as a regular roadmap in this work, because the roadmap preserves the topology of the underlying sampled space, the information can be used to plan paths beyond the simple connection of graph vertices. To construct the roadmap, we first sample the configuration space so that the resulting graph is a n-skeleton graph that constructs a Vietoris-Rips (VR) complex. Then, we perform a series of topological collapses to remove vertices from the graph while still preserving its topological properties. The resulting roadmaps are used to plan paths for different robots and the experimental results show that the proposed topological approach is faster and more feasible in complex high-dimensional spaces.