Sparsification of Motion-Planning Roadmaps by Edge Contraction

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