We study a pursuit-evasion problem which can be viewed as an extension of the keep-away game. In the game, pursuer(s) will attempt to intersect or catch the evader, while the evader can visit a fixed set of locations, which we denote as the anchors. These anchors may or may not be stationary. When the velocity of the pursuers is limited and considered low compared to the evaders, we are interested in whether a winning strategy exists for the pursuers or the evaders, or the game will draw. When the anchors are stationary, we show an algorithm that can help answer the above question. The primary motivation for this study is to explore the boundaries between kinematic and dynamic constraints. In particular, whether the solution of the kinematic problem can be used to speed up the search for the problems with dynamic constraints and how to discretize the problem to utilize such relations best. In this work, we show that a geometric branch-and-bound type of approach can be used to solve the stationary anchor problem, and the approach and the solution can be extended to solve the dynamic problem where the pursuers have dynamic constraints, including velocity and acceleration bounds.
翻译:我们研究的追逐避险问题可以被视为躲避游戏的延伸。 在游戏中,追逐者将尝试交叉或捕捉逃避者,而逃避者可以访问固定的一组地点,我们作为锚表示。这些锚可能或不会是静止的。当追追者的速度有限,并且被认为与逃避者相比较低时,我们感兴趣的是,追逐者是否为追逐者或逃避者制定了赢取策略,或者游戏会吸引。当锚是静止的时,我们展示了能够帮助回答上述问题的算法。本研究的主要动机是探索运动和动态制约之间的界限。特别是,运动问题的解决方案是否可以用来加速寻找具有动态制约的问题,以及如何将问题分散到最佳利用这种关系。在这项工作中,我们表明可以使用几何分支和范围的方法来解决固定的锚问题,而方法和解决办法可以扩展到追逐者具有动态制约的动态问题,包括速度和加速度。