Personal tools
You are here: Home Projects RSEC
« August 2017 »
August
SuMoTuWeThFrSa
12345
6789101112
13141516171819
20212223242526
2728293031
Log in


Forgot your password?
 

Sparsification of Motion-Planning Roadmaps by Edge Contraction


edge_contraction2           edge_contraction2b

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*:

before_compression
after_compression

Before After   

* Scenario provided with the OMPL distribution.

Links

  • 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]

Contacts

Doron Shaharabani 

danha@post.tau.ac.il
Oren Salzman  
http://acg.cs.tau.ac.il/danhalperin danha@post.tau.ac.il
Pankaj K. Agarwal
http://acg.cs.tau.ac.il/danhalperin danha@post.tau.ac.il
Dan Halperin http://acg.cs.tau.ac.il/danhalperin danha@post.tau.ac.il









Document Actions