Sparsification of MotionPlanning Roadmaps by Edge Contraction


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. 
We present Roadmap Sparsification by Edge Contraction (RSEC), a simple and effective algorithm for reducing the size of a motionplanning 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%.
Roadmap example before and after RSEC*:
Before  After 
* Scenario provided with the OMPL distribution.
Links
 Doron Shaharabani, Oren Salzman, Pankaj K. Agarwal and Dan Halperin.
Sparsification of MotionPlanning Roadmaps by Edge Contraction.
In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pages 40834090, 2013
arXiv, 2012 [pdf]