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 (v3, v4) to the point v34. 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
    arXiv, 2012 [pdf]


Doron Shaharabani
Dan Halperin
Oren Salzman
Pankaj K. Agarwal

Yair Oz - Webcreator


Skip to content