Today I read a paper titled “Sparsification of Motion-Planning Roadmaps by Edge Contraction”
The abstract is:
We present Roadmap Sparsification by Edge Contraction (RSEC), a simple and effective algorithm for reducing the size of a motion-planning roadmap
The algorithm exhibits minimal effect on the quality of paths that can be extracted from the new roadmap
The primitive operation used by RSEC is edge contraction – the contraction of a roadmap edge to a single vertex and the connection of the new vertex to the neighboring vertices of the contracted edge
For certain scenarios, we compress more than 98% of the edges and vertices at the cost of degradation of average shortest path length by at most 2%