追逐一个移动的目标？

Question

假设你有一个拥有两个玩家的世界,追逐者和目标.假设追踪者的移动速度略快于目标.如果你是追逐者并且你知道目标是聪明的并且试图不被抓住的事实,那么追逐并最终捕捉目标的好方法是什么？(我将离开世界的细节模糊不清,因为我希望学习一般算法或一系列技术来解决这个问题,而不是在世界结构上进行过多优化.)

最初我认为使用类似Dijkstra算法或A*之类的东西并且在目标移动时不断地重新计算路线将是一个好主意,但实际上可能有一个更好的解决方案,通过采用更迂回的路线以便转向目标.这也可以建模为可以用minimax或UCT解决的双人游戏,但搜索空间可能非常大,以至于进行任何合理的搜索都是完全不可行的.

这个问题已被广泛研究过吗？如果是这样,是否有一套可以在这里使用的众所周知的技术？

谢谢!

(我很抱歉,如果这是重复的话;我似乎找不到像这样的另一个问题,但是如果有的话,我很乐意关闭这个问题).

Answer 1

由于你正在寻找各种各样的意见,我将总结一些我从维基百科关于Sidewinder导弹的文章中发现的令人惊讶的事情:早期的寻热导弹试图引导目标将保持在探测器的中心.这意味着,在实践中,导弹试图追逐他们的目标.Sidewinder导弹的一个重要发展是它试图稳定目标在其传感器上的相对位置.(水手们已经知道长时间停泊的船舶实际上是在碰撞过程中.)

这种改进的算法倾向于从捕食者到猎物划出一条直线,并在猎物试图逃避时提供良好的行为.(猎物所采用的每条曲线都为捕食者提供了另一种捷径.)

Answer 2

快速搜索“AI chasing”就会发现这个算法：

http://www.peachpit.com/articles/article.aspx?p=102090&seqNum=4

这看起来相当不错。根据您想要捕获目标的效率和速度，您还可以考虑其他算法。

尝试在谷歌上搜索Flocking 算法，我很确定我似乎有一些“动态”A* 算法（但我现在似乎找不到它们），它们可能也很有用。

此外，假设您的世界中没有太多障碍，神经网络在这里可能可以正常工作。可能有 2 个输入（到目标的距离、面对目标的弧度增量）和 2 个输出（所需速度和所需航向）的东西