algorithm - 动态寻路算法的方法

Question

我的 A* 实现适用于我的静态环境。如果我现在想使用动态环境，即当我们从头到尾遍历时，我的节点之间的某些成本会发生变化。

从我目前的阅读中，我发现了可以帮助我的 LPA*、D* 和 D* Lite 算法。好吧，我最坏的情况是全部实施，看看什么效果最好。

有没有研究比较这些算法的能力？ 到目前为止，我阅读的论文一次只关注一种算法，并且由于它们的实验环境不同，因此很难进行比较。

**一些背景信息：我正在使用 C++，我的环境是一个 3d 场景，我的搜索图使用导航网格表示。

Answer 1

也许这篇论文可以帮助你，Reactive Deformation Roadmaps: Motion Planning of Multiple Robots in Dynamic Environments by Russell Gayle Avneesh Sud Ming C. Lin Dinesh Manocha；摘要是这样的：

我们提出了一种新的算法，用于在动态障碍物中进行多个机器人的运动规划。我们的方法基于一种新的路线图表示，它使用可变形链接并动态缩回以捕获自由空间的连通性。我们使用牛顿物理学和胡克定律来更新里程碑的位置并使链接变形以响应其他机器人和障碍物的运动。基于此路线图表示，我们描述了我们的规划算法，该算法可以为复杂动态环境中的数十个机器人计算无碰撞路径。

他们提出了一种基于物理的自适应路线图表示算法，该算法可以根据动态环境收回和更改其拓扑结构。可用于规划单个机器人或多个机器人在 动态障碍物中的运动。

Answer 2

您已经有一段时间没有问过了，所以也许您已经有时间尝试所有这些了……但是对于它的价值，D*-Lite 论文 (http://www.aaai.org/Papers/AAAI/ 2002/AAAI02-072.pdf）最后有一节，实验结果，比较性能与 LPA*、D* 和 A*。