サンプリングベースのボトルネック経路探索とフレシェ距離マッチングへの応用
Sampling-based bottleneck pathfinding with applications to Frechet matching
ロボット経路計画の手法に着想を得て、連続コストマップ上で最大コストを最小化するボトルネック経路を効率的に探索するサンプリングベースの枠組みを提案し、全次元で単調な経路にも拡張した。
著者: Kiril Solovey, Dan Halperin
分類: cs.CG, cs.RO
原文アブストラクト
We describe a general probabilistic framework to address a variety of Frechet-distance optimization problems. Specifically, we are interested in finding minimal bottleneck-paths in $d$-dimensional Euclidean space between given start and goal points, namely paths that minimize the maximal value over a continuous cost map. We present an efficient and simple sampling-based framework for this problem, which is inspired by, and draws ideas from, techniques for robot motion planning. We extend the framework to handle not only standard bottleneck pathfinding, but also the more demanding case, where the path needs to be monotone in all dimensions. Finally, we provide experimental results of the framework on several types of problems.
