algorithm - 在 D*Lite 上定义路径方向

Question

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

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

Answer 1

D* 和 D*-lite 都适用于有向图和无向图。

图是G = (V, E)，其中V是可以达到的配置（或状态）列表。E是顶点之间的连接列表。在有向图中，E是一组有序对的边(u, v)，其中u和v都是顶点。在无向图中，E是一组无序对。

在无向图上进行规划相当于在有向图上进行规划，具有双向边。也就是说，如果(u,v)是一条边(v, u)也将是一条边。

您如何构建图形是特定于应用程序的，并且从简单的网格到更复杂的策略（如晶格逼近到正向运动学）不等。