ε-ネットによる確率的ロードマップのサンプル複雑性
Sample Complexity of Probabilistic Roadmaps via $\epsilon$-nets
確率的ロードマップ(PRM)の完全性・最適性保証がサンプリング分布と接続半径にどう依存するかを有限時間で解析し、ε-ネットを用いて必要サンプル数の上下界を導出した。また、グリッド並みの被覆を少ないサンプルで実現する分布を提案した。
著者: Matthew Tsao, Kiril Solovey, Marco Pavone
分類: cs.DS, cs.RO
原文アブストラクト
We study fundamental theoretical aspects of probabilistic roadmaps (PRM) in the finite time (non-asymptotic) regime. In particular, we investigate how completeness and optimality guarantees of the approach are influenced by the underlying deterministic sampling distribution ${\mathcal{X}}$ and connection radius ${r>0}$. We develop the notion of ${(\delta,\epsilon)}$-completeness of the parameters ${\mathcal{X}, r}$, which indicates that for every motion-planning problem of clearance at least ${\delta>0}$, PRM using ${\mathcal{X}, r}$ returns a solution no longer than ${1+\epsilon}$ times the shortest ${\delta}$-clear path. Leveraging the concept of ${\epsilon}$-nets, we characterize in terms of lower and upper bounds the number of samples needed to guarantee ${(\delta,\epsilon)}$-completeness. This is in contrast with previous work which mostly considered the asymptotic regime in which the number of samples tends to infinity. In practice, we propose a sampling distribution inspired by ${\epsilon}$-nets that achieves nearly the same coverage as grids while using significantly fewer samples.
