Close this search box.

Sparsification of Motion-Planning Roadmaps by Edge Contraction

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.


  • Doron Shaharabani, Oren Salzman, Pankaj K. Agarwal, and Dan Halperin
    Sparsification of Motion-Planning Roadmaps by Edge Contraction
    In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA),  pages 4083-4090, 2013 [link][bibtex]
    arXiv, 2012 [pdf][bibtex]


Doron Shaharabani
Dan Halperin
Oren Salzman
Pankaj K. Agarwal

Yair Oz - Webcreator


Skip to content