动态路径规划算法的方法探讨

Question

动态路径规划算法的方法探讨

algorithmpath-findingd-star

5

我的A*实现在静态环境下表现良好。如果我现在想在动态环境中工作，例如当我们从起点到终点遍历时，节点之间的某些成本会发生变化。

据我目前所读，LPA*、D*和D* Lite算法可能对我有帮助。我的最坏情况是实现它们并查看哪个效果最好。 是否有研究比较这些算法的能力？ 我读过的论文只关注单个算法，由于他们的实验环境不同，因此很难进行比较。

一些背景信息：我正在使用C++，我的环境是一个3D场景，我的搜索图使用navmeshes表示。

- AntonD

请查看http://cstheory.stackexchange.com/questions/11855。 - BlueRaja - Danny Pflughoeft

2个回答

2

自从你提出问题以来已经有一段时间了，也许你已经有时间尝试了所有的方法......但是说实话，《D*-Lite》论文（http://www.aaai.org/Papers/AAAI/2002/AAAI02-072.pdf）在结尾处有一个章节，实验结果，比较了与LPA*、D*和A*的性能。

- carlpett

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- edgarmtze · Accepted Answer

也许这篇文章能够帮助您，标题为《Reactive Deformation Roadmaps: Motion Planning of Multiple Robots in Dynamic Environments》，是由Russell Gayle、Avneesh Sud、Ming C. Lin和Dinesh Manocha撰写的，涉及到IT技术。摘要如下：

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

他们提出了一种基于物理的算法，自适应的路网表示方法会随着动态环境的变化而收缩和改变拓扑结构。它可用于规划单个机器人或多个机器人在动态障碍物中的运动。