关于路径规划：D*算法的通俗易懂详细描述

Question

我希望处理的大型网络（小世界图类型）具有动态性质，新节点经常添加和减少。在这种动态环境中，使用 D* 而非 A* 来检测路径可能是更好的方法。

D* 的可靠性如何？它是否有任何真实世界的经验？就像加密算法一样，D* 是否经过了大量的同行评审和测试来保证其可靠性？你会将其用于这个问题吗？

- Setori

---

但是让我们为外行人听到详细的解释。 - Setori

我认为你能够得到的最接近的方法就是阅读我提供链接的D原始白皮书中的伪代码和相关解释。它用相当通俗易懂的语言描述，但是如果你没有一定的图论背景，你将无法理解D算法。 - mmcdole

Answer 1

据我所知，第一次运行D*时，它找到的路径与A*几乎相同，并且运行时间也差不多。然而，当节点更改其边缘值或添加节点时，A*会重新计算整个路径，而D*只会在第二次计算时重新计算不一致的节点，而不是整个路径。

Anthony Stentz的D*算法（原始白皮书在这里）已经被他的后继者所取代。D* Lite和LPA*是最常见的，并且更容易编写/实现。

就实际经验而言，NASA喷气推进实验室的Joseph Carsten和Art Rankin在“Spirit”和“Opportunity”火星车上安装了一个使用D* Lite元素的Field D*版本（漫游车使用D*的幻灯片在这里）。 2007年2月，它被用于完全自主导航火星车。 alt text http://asm.arc.nasa.gov/Gallery/images/generic/rover.jpg 显然，在机器人领域中，D*非常有用，因为机器人的板载传感器不断重新评估边缘值。在我看来，这使它相当经过“战斗测试”。

同样，我发现另一份白皮书提到了在移动游戏中使用D* Lite算法。

最后，我想说我以前从未实现过D*，只有A*。由于复杂度的显著增加，我认为只有在图形频繁且显著变化的情况下才应该使用D*（或D* Lite）。你描述的情况与此类似，所以我建议你一定要选择D* Lite。如果NASA使用它，你可以放心地认为它已经被彻底研究过了。

- Simucal

---

你说当图形频繁变化时应该使用D算法。这是否意味着如果图形根本不变化就不应该使用D算法？ - Alaa

Answer 2

我已经实现了D*和A*算法。因此，我建议您，如果您的地图没有动态障碍物，应该实现A*。否则，实现D*。主要原因是： 在第一次搜索时，D*计算地图中的所有节点，然后显示最短路径，而A*仅计算地图中目标和起始点周围的有限区域。因此，它比D*快得多。 在动态环境中，D*比A*更快，更有效。因为当机器人行进时，如果检测到新的障碍物，它只会更新意外障碍物周围的几个节点。而A*将重新计算所有内容。

- Truc Nguyen