Extended Increasing Cost Tree Search for Non-Unit Cost Domains
Extended Increasing Cost Tree Search for Non-Unit Cost Domains
复制标题
非单位成本域的扩展递增成本树搜索
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Ariel Felner
中科院分区：
文献类型：
--
作者：
Thayne T. Walker;Nathan R Sturtevant;Ariel Felner
多代理探路（MAPF）具有应用程序
在导航，机器人技术，游戏和计划中。最多
处理基于搜索的最佳算法
MAPF专注于具有单元的简单域
成本操作和单位时间步骤。虽然这些
约束保留算法的许多方面
简单，它们还严重限制了
可以使用。在本文中，我们介绍了一个新的定义
MAPF问题的非单位成本和
非单位时间步长域以及新的多种多样
这些国家继任者的生成计划
域。最后，我们定义了扩展版本
成本不断增加的树搜索算法（ICT）
对于非单位成本，有两个新的次级变体
ICT：Epsilon-Ict和W-Icts。我们的实验
证明较高质量的亚最佳解决方案
可以在分散的域中实现
移动模型在不超过
域中的低质量，最佳解决方案
粗离散的运动模型。
Multi-agent pathfinding (MAPF) has applications
in navigation, robotics, games and planning. Most
work on search-based optimal algorithms for
MAPF has focused on simple domains with unit
cost actions and unit time steps. Although these
constraints keep many aspects of the algorithms
simple, they also severely limit the domains that
can be used. In this paper we introduce a new definition
of the MAPF problem for non-unit cost and
non-unit time step domains along with new multiagent
state successor generation schemes for these
domains. Finally, we define an extended version
of the increasing cost tree search algorithm (ICTS)
for non-unit costs, with two new sub-optimal variants
of ICTS: epsilon-ICTS and w-ICTS. Our experiments
show that higher quality sub-optimal solutions
are achievable in domains with finely discretized
movement models in no more time than
lower-quality, optimal solutions in domains with
coarsely discretized movement models.