动态障碍物路径规划

Question

动态障碍物路径规划

algorithmartificial-intelligencepath-findingd-star

4

我正在实现一个需要路径规划的仿真系统。
当环境没有变化时，A*算法对我来说效果很好。
当我遇到原始地图中不存在的静态障碍物时，LPA*和D* Lite算法对我来说也很好。
然而，如果这些障碍物以某种速度移动，我该怎么办呢？
是否有一种LPA*或D* Lite算法的变体可以处理这个问题？
还是我必须将某种形式的转向行为与这些算法相结合？
在我的仿真系统中，我希望我的“代理”能够从起点移动到终点，在这个环境中会有移动的障碍物。

- tezo

可能重复的问题 https://dev59.com/TlfUa4cB1Zd3GeqPFCMn - amit

1

我不确定该用户是否考虑移动障碍物。 - tezo

1

代理或障碍物的运动是否受到任何限制？速度或加速度限制？非完整约束。 - Andrew Walker

3个回答

6

这篇文章提出了很多关于动态A*的好想法，可能对您有用。

Anytime Dynamic A*: 一个可随时重新规划的算法 Maxim Likhachev, Dave Ferguson† Geoff Gordon†, Anthony Stentz†, 以及 Sebastian Thrun 此外，这篇文章，带有移动障碍物的随机运动规划，作者是 David Hsu Robert, Kindel Jean-Claude Latombe, Stephen Rock

它们应该是一个不错的开始。

- edgarmtze

值得一提的是，David Hsu 的论文《在广阔空间中随机单次查询运动规划》也值得一看。 - Andrew Walker

第二个链接很好（虽然第一个链接与问题无关）。 - BlueRaja - Danny Pflughoeft

0

您可以看到一个动态场景，它是一个经常更新的静态场景，在每一步/修改场景时都必须重新计算路径规划。

例如，使用新位置更新地图并在每一步重新计算路径规划。

对于移动障碍/物体，在更新后的地图上添加一个或两个“像素”的边距，以便轻松处理它们在步骤期间可能移动到“随机但非常接近”的位置的事实。

更好的方法是，在开始时标记最大移动障碍的轨迹，并仅在实时特殊轨迹（例如门、楼梯或移动物体）上进行更新。

- user3161997

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

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

- David T Wilcox · Accepted Answer

你最好考虑将问题分为两部分，而不是试图使用单一算法来解决它。

角色移动有两个组成部分:高层目标选择和路径查找以及本地操作。路径查找解决的是“我在这里，我需要知道如何到达那里”的问题。本地操作解决的是“我正在前往那里，有人挡住了我的路”的问题。

保持你现在的路径查找。你需要添加的是角色在沿着路径移动时检测障碍物的能力，并调整避免障碍物的本地路径段。

书籍《游戏人工智能》（作者网站：http://ai4g.com/ ，Amazon：http://amzn.to/k9K62F）详细介绍了几种将路径查找与避碰相结合的方法。这篇论文也很好地涵盖了操纵算法的高层次信息。我实施的一种非常有效的技术是操纵管道，也称为协作仲裁。

任何完整的答案都取决于你的世界表示和其他特定于你的实现的因素，但我希望这可以帮助到你。