4

我正在实施一个需要我进行一些寻路的模拟。
当我的环境没有改变时，A* 对我来说很好。
当我遇到原始地图中没有的静态障碍物时，LPA* 和 D* Lite 可以正常工作。

但是，当这些障碍物以一定速度移动时，我该如何处理呢？
是否有处理此问题的 LPA* 或 D* Lite 算法的变体？
或者我是否必须将某种形式的转向行为与这些算法结合起来？

最后，在我的模拟中，我想让我的“代理”在一个会有障碍物移动的环境中从起点移动到终点。

4

3 回答 3

7

与尝试使用单一算法解决问题相比，您可能会更好地考虑将问题分成两部分。

角色移动有两个组成部分：高级目标选择和寻路，以及局部转向。寻路解决了“我在这里，我需要知道如何到达那里”的问题。本地转向解决了“我在路上，有人挡路”的问题。

保持你现在的寻路。您需要添加的是角色在沿着该路径移动时检测障碍物的能力，然后调整路径的该局部部分以避开障碍物。

《人工智能游戏》一书（作者网站：http ://ai4g.com/和亚马逊：http ://amzn.to/k9K62F ）详细介绍了几种将寻路与避免碰撞相结合的方法。这篇论文还很好地涵盖了高水平的转向算法。我实施的一项高效技术是转向管道，也称为协作仲裁。

任何完整的答案都将取决于您的世界代表性和特定于您的实施的其他因素，但我希望这会有所帮助。

于 2012-01-25T11:55:21.623 回答
6

这篇文章对动态 A* 有很好的想法，可能对你有用

Anytime Dynamic A*: An Anytime, Replanning Algorithm Maxim Likhachev, Dave Ferguson† Geoff Gordon†, Anthony Stentz†, 和 Sebastian Thrun 还有这篇文章，由 David Hsu Robert、Kindel Jean-Claude Latombe、Stephen 撰写的带有移动障碍物的随机动力学运动规划岩石

他们应该是一个好的开始。

于 2011-05-14T16:49:14.663 回答
0

您可以看到动态场景，例如定期更新的静态场景，并且您必须在场景的每个步骤/修改中重新计算寻路

参照。定期用你的移动物体的新位置更新地图，并在每一步重新计算寻路

对于移动的障碍物/物体，例如在更新的地图上在移动的障碍物/物体周围添加一个或两个“像素”的边距，以便轻松处理它们可以在步骤

更好的是，在开始时标记最大移动障碍物的轨迹，仅更新实时特殊轨迹，例如门、楼梯或移动物体

于 2021-11-22T22:53:53.437 回答