Jump Point Search with Temporal Obstacles
Jump Point Search with Temporal Obstacles
复制标题
具有时间障碍的跳跃点搜索
DOI：
10.1609/icaps.v31i1.15961
复制
发表时间：
2021
影响因子：
3.9
通讯作者：
Nathan R Sturtevant
中科院分区：
文献类型：
--
作者：
Shuli Hu;Daniel Damir Harabor;G. Gange;Peter James Stuckey;Nathan R Sturtevant
在基于4连通网格的路径规划中，人们经常需要考虑时间和移动的障碍：出现、消失和可能阻止智能体到达目标的障碍。这类问题在各种环境(游戏、机器人等)中很常见。它们可能会令人惊讶地具有挑战性，难以解决。第一，因为时间方面增加了搜索空间的大小；第二，因为搜索空间包含许多对称路径，除了网格移动的出现顺序之外，它们彼此之间无法区分。为了解决这些问题，我们考虑了一种新的优化算法--跳点搜索风格--它可以识别并打破这些对称性，从而提高性能；从几个因素到一个数量级以上的SIPP，可以说是该领域的黄金标准基线。
In 4-connected grid-based path planning one often needs to account for temporal and moving obstacles: ones that appear, disappear and which can prevent the agent from reaching its target. Such problems are common in a variety of settings (games, robotics etc.) and they can be surprisingly challenging to solve. First, because the temporal aspect increases the size of the search space; second because the search space contains many symmetric paths, indistinguishable from one another except by the order in which grid moves appear. To tackle such problems we consider a new optimal algorithm – in the style of Jump Point Search – which can identify and break these symmetries and thus improves performance; from several factor to more than one order of magnitude vs. SIPP, arguably the gold standard baseline in the area.