Efficient sampling-based bottleneck pathfinding over cost maps
Efficient sampling-based bottleneck pathfinding over cost maps
复制标题
基于成本图的高效基于采样的瓶颈寻路
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
D. Halperin
中科院分区：
文献类型：
--
作者：
Kiril Solovey;D. Halperin
我们引入了一个简单而有效的基于采样的规划器，是专为瓶颈寻路：给定一个隐式定义的成本地图M：Rd R，它分配给空间中的每个点一个真实的值，我们希望找到一条连接两个给定点的路径，它最小化相对于M的最大值。我们证明了我们的算法，我们称之为瓶颈树（BTT），在几个具有挑战性的情况下，涉及多个代理的问题，它优于国家的最先进的成本地图规划技术T-RRT的能力。除了效率之外，BTT只需要调整一个参数：样本数量。在理论方面，我们研究了我们的方法的渐近性质，并考虑特殊的设置，计算的轨迹必须是单调的所有坐标。这种约束出现在这样的情况下，其中的问题涉及到多个代理，被限制为向前运动沿着预定义的路径的协调。
We introduce a simple yet effective sampling-based planner that is tailored for bottleneck pathfinding: Given an implicitly-defined cost map M : Rd Å R, which assigns to every point in space a real value, we wish to find a path connecting two given points, which minimizes the maximal value with respect to 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∗. In addition to its efficiency, BTT requires the tuning of only a single parameter: the number of samples. 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.