辺縮約による運動計画ロードマップの疎化
Sparsification of Motion-Planning Roadmaps by Edge Contraction
運動計画用ロードマップの辺を縮約して頂点に統合することで、経路品質をほぼ保ちながら最大98%以上の辺と頂点を削減する手法を提案した。
著者: Doron Shaharabani, Oren Salzman, Pankaj K. Agarwal, Dan Halperin
分類: cs.RO, cs.DS
原文アブストラクト
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%.
