D*lite:我应该使用什么启发式函数

Question

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

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

Answer 1

这取决于图。它应该满足正三角形等式，以获得启发式的可接受性，就像a*搜索一样。欧几里得距离在大多数情况下都很有效。与a*的区别在于，计算我们正在搜索的当前节点和开始节点之间的距离(因为最佳的第一次搜索是从目标到开始对D*lite进行的(。