Campus Event Calendar

Event Entry

What and Who

Sparsification of Motion-Planning Roadmaps by Edge Contraction

Doron Shaharabani
Tel-Aviv University, Tel-Aviv, Israel
AG1 Mittagsseminar (own work)
AG 1, AG 4, AG 5, MMCI  
MPI Audience

Date, Time and Location

Thursday, 14 November 2013
30 Minutes
E1 4


Asymptotically optimal motion-planning roadmaps constructed by the recently introduced PRM* algorithm provide high-quality, dense roadmaps.

We consider the problem of sparsifying the roadmap, or reducing its size, while minimizing the effect on the quality of paths that can be extracted from the resulting roadmap.
We present Roadmap Sparsification by Edge Contraction (RSEC), a simple and effective sparsifying algorithm.
The primitive operation used by RSEC is edge contraction---the contraction of a roadmap edge (v', v'') to a new vertex v and the connection of the new vertex v to the neighboring vertices of the contracted edge's vertices (i.e. to all neighbors of v' and v'').
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%.

Joint work with Oren Salzman, Pankaj K. Agarwal, and Dan Halperin


Eric Berberich
--email hidden
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

Joint work with Oren Salzman, Pankaj K. Agarwal, and Dan Halperin

Eric Berberich, 11/09/2013 11:27
Eric Berberich, 10/02/2013 12:50
Eric Berberich, 10/02/2013 12:50 -- Created document.