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%.
Edge Contraction: Graph before (left) and after (right) the contraction of the edge \((v_3, v_4)\) to the point \(v_{3,4}\). Obstacle is depicted by the green triangle.
Roadmap example before and after RSEC*
|
|
|
* Scenario provided with the OMPL distribution.