问题标签 [d-star]

我已经用虚幻引擎构建了我的寻路系统，不知何故，寻路部分工作得很好，而我找不到解决动态避障问题的合适方法。我的角色在整个地图上行走，并在移动时相互碰撞。当发生碰撞时，我尝试引导它们，但这效果不佳。例如，两个角色挡在路上，而第三个角色的路径正好在他们中间，他会被卡住。有人能告诉我最流行的动态回避方法吗？非常感谢。

我在论坛上问过这个问题，但到目前为止还没有运气。

我是一名学生，目前正在尝试为我的 fyp 实现动态寻路。过去几周我一直在使用 UE4，因为我决定尝试在一个级别中实现 D * lite 寻路算法。我想知道这里有没有人了解这个主题。我不知道在哪里真正考虑覆盖 ue4用我自己的尝试寻路。我认为它可能在 UNNavigationComponent 但我不确定

我已经阅读了 d * lite 的论文。我只是不确定如何在 UE4 中执行此操作。

我使用的是虚幻 4.6.1

感谢您的时间和您可能提供的任何帮助。祝您有美好的一天

伊森

我正在尝试实现D* Lite和LPA*算法（均由 Sven Koenig 提出），但我很难理解每个节点包含的前任和后继列表的概念。我尝试从各种来源寻找答案，但找不到明确的答案。

谁能帮我解决这个问题？

谢谢你。

如果原因是因为起始节点位置一直在变化，那我们就不能只修改OPEN集中每个节点的g成本而不是h成本吗？（例如减去您刚刚遍历的边的成本）

D* 和 D* Lite 的时间和空间复杂度是多少？如何推导出这些？

我正在阅读关于 D* Lite 的 Koening 和 Likhachev 论文，每次迭代它都会通过遍历图上的连接节点来更新起始节点。我想知道在现实世界机器人技术中的使用，机器人可能会超出连接节点并最终到达图中的不同点。如果您在根据机器人的实际位置自行设置起始节点时保持算法的其余部分相同，D* Lite 是否仍然有效。特别是可以从论文中的这两行伪代码

变得

这是论文中的完整伪代码：

我正在尝试实现 D*-Lite 寻路算法，如 Koenig 和 Likhachev 在 2002 年针对基于网格的导航图的文章中所述。

但我在那篇论文中没有看到任何启发式函数。那么，我应该选择哪些功能呢？我可以使用直线距离或曼哈顿距离吗？

我正在尝试实现 D*-Lite 寻路算法，如 Koenig 和 Likhachev 在 2002 年关于基于网格的导航图的文章中所述。

在这个算法中使用了双键。它有左右部分。如何正确比较此键以在优先级队列中进行排序？我应该先比较左边的部分，然后只在相等的情况下比较右边吗？还是我应该选择其他方式？

对于一个机器人项目，我一直在使用我想使用Koenig，2002 年论文中的D Lite（优化版） * 来为不断变化的占用网格/成本图进行动态路径规划。如本文所述，D* Lite 搜索算法的思想是，它基本上通过从目标开始反向运行 A* 搜索并尝试回到起点来工作。然后求解器给出当前的解决方案并等待它所呈现的权重或障碍的某种变化。与重复的 A* 搜索相反，D* Lite 算法避免从头开始重新规划并逐步修复路径，使其修改保持在机器人姿态附近。

我的问题

我已经在 python 中实现了该算法，并在 pygame 中进行了模拟以测试性能。但我有一个与伪代码有关的问题。我已经实现了优化版和非优化版的算法，现在已经执行了 3 次了，我仍然得到一个错误，即当算法遇到一些配置的障碍物（十字形或大的垂直障碍物）时，算法会突然卡在一个while 循环内部的无限循环（Procedure Main，第 32 行伪代码），并在顶点 s_start 的两个选项之间来回切换（Procedure Main，第 34 行）。我现在已经将我的 python 实现与伪代码进行了多次比较，但我找不到任何可能导致此错误的伪代码偏差。

我的临时“修复”

现在，为了避免算法陷入无限循环，我在 Procedure Main() 的第 48 行将computeShortestPath()缩进了左侧一个，这样我就超出了Procedure Main() 第 37 行的if范围.

当我这样做时，算法几乎总是能够在发现路径中的新障碍时计算出新的最短路径。

我的问题

1. 首先，任何人都知道为什么算法有时会陷入无限的while循环以及如何解决它？

2. 我想我的临时“修复”将再次认为该算法的计算成本更高，因此 D* Lite 算法的许多目的现在已经不复存在。我的缩进修复与原始算法的计算复杂度是多少？

3. 现在有了我的临时修复，与动态 A* 相比，代码实际上在计算方面是否有任何不同，在动态 A* 中，每次必须重新规划新路径时都重新计算所有内容？

4. 有时，当遇到大量复杂的迷宫时，需要对新顶点进行大量探索，我的“临时固定”代码有时会变得有点慢。但是，即使在原始代码中也不会在某种程度上发生这种情况吗？

我的实现

如果你想自己运行代码并体验算法，你可以在这里运行 python main.py来测试我的实现。

这个特定的实现包括我的“临时修复”。但是，如果您想在没有的情况下体验它，可以转到 d_star_lite.py 中的第 156 行并将 compute_shortest_path() 向右缩进一个，以便它进入第 132 行的“if”内。

伪代码

这是 D* Lite（优化版）算法的原始伪代码。