问题标签 [d-star]

我希望处理的大型网络（小世界图类型）本质上是动态的，经常添加和减少新节点。大概使用 D* over A* 会是在这种动态环境中检测路径的更好方法？

D*有多坚固？它有任何现实世界的经验吗？就像加密算法一样——D* 是否通过大量同行评审和测试得到强化？你会用 D* 来解决这个问题吗？

这里有一些关于 D* 的论文的链接，但它们对我来说有点过于数学化了。有没有关于 D*/D* Lite 更适合初学者的信息？

我的 A* 实现适用于我的静态环境。如果我现在想使用动态环境，即当我们从头到尾遍历时，我的节点之间的某些成本会发生变化。

从我目前的阅读中，我发现了可以帮助我的 LPA*、D* 和 D* Lite 算法。好吧，我最坏的情况是全部实施，看看什么效果最好。

有没有研究比较这些算法的能力？ 到目前为止，我阅读的论文一次只关注一种算法，并且由于它们的实验环境不同，因此很难进行比较。

**一些背景信息：我正在使用 C++，我的环境是一个 3d 场景，我的搜索图使用导航网格表示。

我正在实施一个需要我进行一些寻路的模拟。
当我的环境没有改变时，A* 对我来说很好。
当我遇到原始地图中没有的静态障碍物时，LPA* 和 D* Lite 可以正常工作。

但是，当这些障碍物以一定速度移动时，我该如何处理呢？
是否有处理此问题的 LPA* 或 D* Lite 算法的变体？
或者我是否必须将某种形式的转向行为与这些算法结合起来？

最后，在我的模拟中，我想让我的“代理”在一个会有障碍物移动的环境中从起点移动到终点。

我正在尝试实现 D*-Lite 寻路算法，如 Koenig 和 Likhachev 在2002 年针对 Boost::Graph 的文章中所述。我想我已经很好地掌握了它背后的基本思想和理论，但是当Pred和Succ集合更新时我在理解上遇到了问题。

我猜它发生在Move to sstartstep in 中Main，但是第一次调用ComputeShortestPath将毫无意义？并且该Succ集合是否应该同时插入Pred？那么Pred并且Succ可以实现为双向链表吗？

我在下面插入了算法的伪代码。和集合分别是前任和后继Pred。, ,和是不同的成本和权重。是要访问的顶点的优先级队列。SuccghrhscU

我已经实现了 D*-Lite 算法（这里有一个描述，它是一种在边缘成本随时间变化时进行寻路的算法），但是我在进行边缘成本更新时遇到了问题。它主要工作，但有时它会卡在一个循环中，在两个顶点之间来回移动。我正在尝试创建一个展示这种行为的测试用例，目前在大型应用程序中使用时会发生这种情况，这使得调试变得困难。

我会尽快建立一个测试用例，但也许有人可以立即发现我从伪到 C++ 所做的错误。（下面包含一个测试用例）这篇文章展示了一个优化版本，图 4，这是我已经实现的版本。伪代码粘贴在下面。

我的实现源代码可在此处获得。

如果有帮助，我将在我的代码中使用这些类型：

如果需要有关使用的更多信息，请询问，粘贴太多了。

D*-Lite 的伪代码：

编辑：

我成功地创建了一个显示错误行为的测试用例。将它与 pastebin 中的代码一起运行，它会在最后一次get_path调用中挂断，在节点 1 和 2 之间来回切换。在我看来，这是因为节点 3 从未被触及，所以那样走会有一个无限的代价。

编辑2：更多进展。如果我用just （不为空）替换while循环中的中断条件，则找到路径！虽然它很慢，因为它总是检查图中的每个节点，这不应该是必需的。此外，由于我使用无向图，我添加了一些代码来更新和.ComputeShortestPathU != ØU{40"}uv

A 已阅读有关 A* 以及 D* 和类似内容的信息，但我无法在它们之间进行选择。当它带有许多搜索（每个刻度 50 次搜索）和许多不同的可能性时，最好的搜索算法是什么？

我目前正在研究 Sven Koenig 的 D*Lite 算法的实现。 http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf。基本上，我试图在开始实施之前了解所有细节。似乎该算法适用于有向图，这是定义PredandSucc函数的方式。

如何定义图形的方向以及哪些参数决定了图形的方向。我应该使用诸如成本之类的参数的值g（这似乎不是一个好的选择……因为g成本与rhs算法更新的值一起使用）还是距离的启发式估计？

我正在查看 DLite 的优化版本：

我无法猜测为什么在第 44 行和第 46 行评估相同的条件（如果 u ~= s_goal）。在输入第 43 行和第 45 行中出现的 if/if else 之前，是否无法对此进行评估？可能是：

会错吗？

问候

我目前尝试实施 D* Lite 算法进行路径规划（另请参见此处）以掌握它。我在网上找到了两个实现，都是针对 C/C++ 的，但不知何故不能完全遵循这些想法，因为它们似乎与白皮书中的伪代码有很大的不同。我特别使用以下两篇论文： Koening,S.;Likhachev,M. - D* Lite，2002 Koenig & Likkachev，在未知地形中快速重新规划导航，IEEE Transactions on Robotics，Vol。2005年6月21日第3期

我尝试从第一个白皮书（第 5 页，图 4）中实现 D* Lite 的优化版本，对于“调试”，我使用第二个白皮书（第 6 页，图 6 和图）中所示和解释的示例.7)。所有工作都在 MatLab 中完成（更容易与他人交换代码）。

到目前为止，我通过运行一次 computeShortestPath() 来运行代码以找到初始最短路径。但现在我被困在伪代码的 {36''} 和 {37''} 行：

我如何检测这些变化？我似乎不知道这是如何被检测到的？到目前为止，在我的实现中，我主要使用了 3 个矩阵。一个与包含所有 rhs 值的网格图大小相同的矩阵。一个大小相同的矩阵，包含类似的所有 g 值。还有一个具有可变行数的矩阵，用于优先级队列，前两列是优先级键，第三和第四行是 x 和 y 坐标。

比较我的结果，我在第 5 步中第一次运行 computeShortestPath() 得到的结果与第二份白皮书第 6 页图 6 中所示的结果相同。移动机器人一步也不是问题。但我真的不知道下一步应该如何实施扫描更改的边缘成本。

感谢您的任何提示、建议和/或帮助！！！