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

Question

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

如何定义图形的方向以及哪些参数决定图形的方向。我是否应该使用某些参数的值，例如 g 成本(这似乎不是一个好的选择......因为 g 成本与 rhs 值是算法更新的值)还是距离的启发式估计值？

Answer 1

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

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

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

如何构建图形是特定于应用程序的，从简单的网格到更复杂的策略(如晶格近似到正向运动学)各不相同。