Sparsification of Motion-Planning 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 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%.
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 [ ]