コストマップ上のボトルネック経路探索のための効率的サンプリングプランナ
Efficient sampling-based bottleneck pathfinding over cost maps
暗黙的に定義されたコストマップ上で最大コストを最小化する経路を探索するサンプリングベースプランナBTTを提案し、複数エージェント問題でT-RRT*を上回る性能を示した。
著者: Kiril Solovey, Dan Halperin
分類: cs.RO, cs.CG
原文アブストラクト
We introduce a simple yet effective sampling-based planner that is tailored for bottleneck pathfinding: Given an implicitly-defined cost map $\mathcal{M}:\mathbb{R}^d\rightarrow \mathbb{R}$, which assigns to every point in space a real value, we wish to find a path connecting two given points, that minimizes the maximal value with respect to~$\mathcal{M}$. We demonstrate the capabilities of our algorithm, which we call bottleneck tree (BTT), on several challenging instances of the problem involving multiple agents, where it outperforms the state-of-the-art cost-map planning technique T-RRT*. On the theoretical side, we study the asymptotic properties of our method and consider the special setting where the computed trajectories must be monotone in all coordinates. This constraint arises in cases where the problem involves the coordination of multiple agents that are restricted to forward motions along predefined paths.
