Sparsification of motion-planning roadmaps by edge contraction

Abstract

Roadmaps constructed by the recently introduced PRM* algorithm for asymptotically-optimal motion planning encode high-quality paths yet can be extremely dense. We consider the problem of $\text{sparsifying}$ the roadmap, i.e. reducing its size, while minimizing the degradation of the quality of paths that can be extracted from the resulting roadmap. We present a simple, effective sparsifying algorithm, called $\text{roadmap sparsification}$ $\text{by edgecontraction}$ (RSEC). The primitive operation used by RSEC is $\text{edgecontraction}$ —the contraction of a roadmap edge (v′,v″) to a new vertex $\text{v}’$ and the connection of the new vertex $\text{v}$ to the neighboring vertices of the contracted edge’s vertices (i.e. to all neighbors of $\text{v}\prime$ and $\text{v}\prime$ ). For certain scenarios, we compress more than 97% of the edges and vertices of a given roadmap at the cost of degradation of average shortest path length by at most 4%.