Sparsification of Motion-Planning Roadmaps by Edge Contraction
This addresses efficiency in motion planning for robotics, but it is incremental as it builds on existing roadmap methods.
The paper tackles the problem of reducing the size of motion-planning roadmaps with minimal impact on path quality, achieving over 98% compression of edges and vertices while degrading average shortest path length by at most 2%.
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%.