大規模密ロードマップ上のいつでも経路計画のための密化戦略
Densification Strategies for Anytime Motion Planning over Large Dense Roadmaps
大規模な密ロードマップで最短経路を効率的に求めるため、徐々に密になる部分グラフを既存の経路計画アルゴリズムに与える密化戦略を提案し、2次元・4次元空間や7自由度ロボットアームの操作計画で評価した。
著者: Shushman Choudhury, Oren Salzman, Sanjiban Choudhury, Siddhartha S. Srinivasa
分類: cs.RO
原文アブストラクト
We consider the problem of computing shortest paths in a dense motion-planning roadmap $\mathcal{G}$. We assume that~$n$, the number of vertices of $\mathcal{G}$, is very large. Thus, using any path-planning algorithm that directly searches $\mathcal{G}$, running in $O(V\textrm{log}V + E) \approx O(n^2)$ time, becomes unacceptably expensive. We are therefore interested in anytime search to obtain successively shorter feasible paths and converge to the shortest path in $\mathcal{G}$. Our key insight is to provide existing path-planning algorithms with a sequence of increasingly dense subgraphs of $\mathcal{G}$. We study the space of all ($r$-disk) subgraphs of $\mathcal{G}$. We then formulate and present two densification strategies for traversing this space which exhibit complementary properties with respect to problem difficulty. This inspires a third, hybrid strategy which has favourable properties regardless of problem difficulty. This general approach is then demonstrated and analyzed using the specific case where a low-dispersion deterministic sequence is used to generate the samples used for $\mathcal{G}$. Finally we empirically evaluate the performance of our strategies for random scenarios in $\mathbb{R}^{2}$ and $\mathbb{R}^{4}$ and on manipulation planning problems for a 7 DOF robot arm, and validate our analysis.
