处理二维网格世界中 A-star 中基于时间的约束

Question

我从指定节点和边的二维网格世界图开始；并获得了起点和目标。我能够使用 A* 找到最短路径。

现在问题稍微修改了，引入了时间概念，允许在当前节点等待。给定的问题可以用一个例子来考虑，如下所示。

假设线性世界中有节点，其形式为数组a(1:6)。 Agent 必须从 2 开始到 6。如前所述，我能够使用 A* 来计划这个。最优路径为：2->3->4->5->6.

但假设现在时间进入画面。像 3->4 这样的每个转换都意味着 1 个时间单位已经过去。 Agent 在时间 t=0 开始移动，并被告知它不能在时间 t=3 到达节点 5。所以现在最优路径是：2->3->4->4->5->6

但是我想不出如何使用A*来制作这个计划。我的想法是：我将计划 3 个维度 = (x,y,t) 而不仅仅是 (x,y)。只要保留图形结构，A* 无论如何都可以处理任何维度。

然而，我很困惑，因为我知道从 (2,0) 开始，我使用约定（节点，时间）。但目标是什么？我知道它类似于：(6,t)。但我不知道是什么？所以每当我想计算从当前节点到目标的启发式算法时，我都被难住了，因为我不知道目标是什么？如何使用 A* 处理此问题。此示例仅具有代表性且高度简化。我在 2D 世界中工作，但问题与示例中描述的相同。

引用一些处理此类问题的研究论文将非常有帮助，但请尽量避免引用对这个问题明显矫枉过正的研究。谁能给出伪代码最好

Answer 1

由于您的模型不是完全动态的并且您事先知道变化，您可以通过对 A* 算法的这些简单更改找到您的路径：
首先，当您扩展一个状态时，您总是认为您可以留在那个节点。
其次，当您将一个州的邻居添加到您的边缘列表时，您应该检查您在问题中提到的时间和地点的限制：

state: position, time, h

current_state = priority_queue.top
priority_queue.add( state( current_state.position, current_state.time+1, new_h) )
for each neighbor of current state:
   if possible to be at neighbor.position at current_state.time+1
        priority_queue.add( state(neighbor.position, current_state.time+1, h) )

但是，如果您的世界是完全动态的，您应该实施动态 A* 算法，例如 D*。或者你可以在初始模型上运行 A*，然后每当你在路径中间遇到障碍物时，你尝试使用 A* 找到一条新路径，同时根据障碍物改变地图。

处理二维网格世界中 A-star 中基于时间的约束

Dealing with a time-based constraint in A-star on 2D grid world

algorithm

search

graph-algorithm

path-finding

a-star