2

我目前尝试实施 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''} 行：

{36”} Scan graph for changed edge costs;
{37”} if any edge costs changed

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

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

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

4

1 回答 1

1

以下是别人向我指出的：

在现实世界的代码中，您几乎不必“扫描图表以查找更改”。您的图表仅在您在代码中更改时才会更改，因此您已经确切知道何时何地可以更改！

实现这一点的一种常见方法是在 Graph 类中设置 OnGraphChanged 回调，可以将其设置为调用 PathFinder 类中的 OnGraphChanged 方法。然后在您的 Graph 类中图表发生变化的任何地方，确保调用 OnGraphChanged 回调。

我个人通过使用“真实地图”和“已知地图”来实现它，并且在每次移动之后让机器人检查/扫描所有下一个可能的继任者，并在真实地图和已知地图上比较它们。

于 2012-09-19T16:42:35.653 回答