寻找动态障碍物

Question

我正在实现一个模拟,需要我进行一些寻路.
当我的环境没有变化时,A*对我来说很好.
当我遇到不在原始地图中的静态障碍物时,LPA*和D*Lite对我来说很好.

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

在我的模拟中,我希望让我的"代理人"从一个起点到一个终点,在一个会有障碍移动的环境中.

Answer 1

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

随时动态A*:一个任何时候,重新规划算法 马克西姆利哈乔夫,戴夫·弗格森†杰夫·戈登†,安东尼Stentz†,和塞巴斯蒂安史朗 而且这篇文章,随机Kinodynamic运动规划与运动障碍由 许大卫罗伯特,金德尔吉恩·克劳德·拉姆,斯蒂芬·岩石

他们应该是一个良好的开端.

Answer 2

您可能最好考虑将问题分解为两个部分,而不是尝试使用单个算法解决问题.

角色移动有两个组成部分:高级目标选择和寻路,以及本地转向.寻路解决了"我在这里,我需要知道如何到达那里"的问题.本地转向解决了"我正在那里,有人阻碍我"的问题.

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

"人工智能游戏"一书(作者网站:http://ai4g.com/和亚马逊:http://amzn.to/k9K62F)详细介绍了将寻路与避碰相结合的几种方法.该文还包括转向算法相当好,在较高的水平.我实施的一种高效技术是转向管道,也称为协同仲裁.

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