复杂三维多面体环境中空地协作追逃问题

结合无人机(UAV)的空中移动和无人车(UGV)的地面移动特点,本文提出了一种UAV/UGV空地协作系统,并且针对其在复杂地形中的追逃问题,提出了一种复杂三维多面体环境中UAV/UGV空地协作追逃策略.首先介绍了UAV/UGV空地协作系统的结构与协作追逃问题描述.接着将边界值问题(BVP)改进并离散化作为博弈走法生成器.然后,针对逃方已知追方位置,而追方只具备直线视野(LOS)的不利条件,分析了最坏情况.逃方策略在保证最大生存条件下尽可能获得博弈胜利.追方策略根据逃方状态分成3种情况进行讨论:逃方处于追方的视野范围内、逃方刚刚消失于追方视野以及追方完全丢失逃方的情况.最后,对比仿真结果说明了本文算法的有效性,并分析了追逃结果的影响因素.由于地形是非凸的并且充满障碍,因此该策略虽不能保证追方一定能够胜利,但在最坏情况下是最优的.     

多追捕者-单-逃跑者追逃问题实现成功捕获的约束条件

针对包含有n个追捕者及1个逃跑者的2维平面多机器人追逃问题,对实现成功捕获的约束条件进行了研究.经过理论分析得出:在机器人拥有全局视野的情况下,即使单一逃跑者性能优于每个追捕者,只要满足追捕者与逃跑者的速率比大于sin(π/n),逃跑机器人落在追捕机器人所构成的凸多边形内部且逃跑者和追捕者构成的相邻追-逃阿波罗尼奥斯圆满足两两相交(相切)这2个约束条件,则追捕者通过选择合适的追捕策略就一定可以实现成功抓捕.此外,还给出了在此约束条件下的追捕者和逃跑者的追逃策略.多组仿真实验同样证明了本文提出的约束条件是正确的.     

A Decentralized Fuzzy Learning Algorithm for Pursuit-Evasion Differential Games with Superior Evaders

In this paper, we consider multi-pursuer single-superior-evader pursuit-evasion differential games where the evader has a speed that is similar to or higher than the speed of each pursuer. A new fuzzy reinforcement learning algorithm is proposed in this work. The proposed algorithm uses the well-known Apollonius circle mechanism to define the capture region of the learning pursuer based on its location and the location of the superior evader. The proposed algorithm uses the Apollonius circle with a developed formation control approach in the tuning mechanism of the fuzzy logic controller (FLC) of the learning pursuer so that one or some of the learning pursuers can capture the superior evader. The formation control mechanism used by the proposed algorithm guarantees that the pursuers are distributed around the superior evader in order to avoid collision between pursuers. The formation control mechanism used by the proposed algorithm also makes the Apollonius circles of each two adjacent pursuers intersect or be at least tangent to each other so that the capture of the superior evader can occur. The proposed algorithm is a decentralized algorithm as no communication among the pursuers is required. The only information the proposed algorithm requires is the position and the speed of the superior evader. The proposed algorithm is used to learn different multi-pursuer single-superior-evader pursuit-evasion differential games. The simulation results show the effectiveness of the proposed algorithm.     

Scalable and practical pursuit-evasion with networked robots

In this paper, we consider the design and implementation of practical pursuit-evasion games with networked robots, where a communication network provides sensing-at-a-distance as well as a communication backbone that enables tighter coordination between pursuers. We first develop, using the theory of zero-sum games, an algorithm that computes the minimal completion time strategy for pursuit-evasion when pursuers and evaders have same speed, and when all players make optimal decisions based on complete knowledge. Then, we extend this algorithm to when evader are significantly faster than pursuers. Unfortunately, these algorithms do not scale beyond a small number of robots. To overcome this problem, we design and implement a partition algorithm where pursuers capture evaders by decomposing the game into multiple multi-pursuer single-evader games. We show that the partition algorithm terminates, has bounded capture time, is robust, and is scalable in the number of robots. We then describe the design of a real-world mobile robot-based pursuit evasion game. We validate our algorithms by experiments in a moderate-scale testbed in a challenging office environment. Overall, our work illustrates an innovative interplay between robotics and communication.     

A cooperative Homicidal Chauffeur game

We address a pursuit-evasion problem involving an unbounded planar environment, a single evader and multiple pursuers moving along curves of bounded curvature. The problem amounts to a multi-agent version of the classic Homicidal Chauffeur problem; we identify parameter ranges in which a single pursuer is not sufficient to guarantee evader capture. We propose a novel multi-phase cooperative strategy in which the pursuers move in specific formations and confine the evader to a bounded region. The proposed strategy is inspired by the hunting and foraging behaviors of various fish species. We characterize the required number of pursuers for which our strategy is guaranteed to lead to confinement.     

Cooperative Multiple Pursuers against a Single Evader

This paper considers a pursuit-evasion game for non-holonomic systems where a group of pursuers attempts to capture an evader in a bounded connected domain. The problem is challenging because all vehicles have the same maneuvering capability in terms of speed and turn radius constraint. The paper initially discusses a simple approach for holonomic systems that is based on the minimization of the safe-reachable area (the area containing the set of points to where an evader can travel without being caught). This idea is then extended to develop a pursuit-evasion strategy for non-holonomic systems. However, solving such a problem is computationally intractable. Therefore, we propose a computationally efficient algorithm to obtain approximate solutions. This paper also proposes an alternative approach to obtain a simple yet effective solution to the cooperative pursuit problem that is based on missile guidance laws. As there is no analytical proof of capture, we empirically evaluate the performance of the algorithms and perform a comparative study using solutions obtained from umpteen simulations. A total of four different cooperative pursuit strategies and three different evader strategies are taken into account for the comparative study. In the process, an evader strategy which is superior to that based on the optimization of safe-reachable area is also identified.     

Coordinated pursuer control using particle filters for autonomous search-and-capture

In a real-world pursuit-evasion (PE) game, the pursuers often have a limited field-of-view of the evaders and thus are required to search for and detect the evaders before capturing them. This paper presents a unified framework and control algorithm using particle filters (PFs) for the coordination of multiple pursuers to search for and capture multiple evaders given the ability of PF to estimate highly non-Gaussian densities prevalent in search problems. The pursuer control problem is formulated as a stochastic control problem where global objectives function of both searching and capturing are common. To take the evaders’ actions into account, an action measure (AM) is defined over the evaders’ PDs is used to represent the probability that the evader may transit each state in the PD. The global objective functions for search and capture are then decomposed into local objective functions for unification through objective priority weights. Coordination between the pursuers takes place through the multi-sensor update where the observation likelihoods of all pursuers are used in the PF update stage. The control actions of each pursuer are then determined individually, based on the updated PDs given the objective weights, action measures as well as evader importance weights in the case of multiple evaders. The proposed algorithm is tested in three scenarios for its effectiveness. In addition, a parametric study on the average capture time against the initial variances of the target state uncertainty is conducted to test for robustness. Results show that the pursuers are able to capture all the evaders in each case with the capture time for the second and last scenario differing by only 2.9% implying firstly that under the proposed algorithm, the capture time is not proportional to the increase in the number of evaders and also suggested robustness and potential scalability of the proposed algorithm.     

Evasion strategies of a three-player lifeline game

This study examines a multi-player pursuit-evasion game, more specifically, a three-player lifeline game in a planar environment, where a single evader is tasked with reaching a lifeline prior to capture. A decomposition method based on an explicit policy is proposed to address the game qualitatively from two main aspects: (1) the evader’s position distribution to guarantee winning the game (i.e., the escape zone), which is based on the premise of knowing the pursuers’ positions initially, and (2) evasion strategies in the escape zone. First, this study decomposes the three-player lifeline game into two two-player sub-games and obtains an analytic expression of the escape zone by constructing a barrier, which is an integration of the solutions of two sub-games. This study then explicitly partitions the escape zone into several regions and derives an evasion strategy for each region. In particular, this study provides a resultant force method for the evader to balance the active goal of reaching the lifeline and the passive goal of avoiding capture. Finally, some examples from a lifeline game involving more than one pursuer are used to verify the effectiveness and scalability of the evasion strategies.     

On Discrete-Time Pursuit-Evasion Games With Sensing Limitations

In this paper, we address discrete-time pursuit-evasion games in the plane where every player has identical sensing and motion ranges restricted to closed disks of given sensing and stepping radii. A single evader is initially located inside a bounded subset of the environment and does not move until detected. We propose a sweep-pursuit-capture pursuer strategy to capture the evader and apply it to two variants of the game. The first involves a single pursuer and an evader in a bounded convex environment, and the second involves multiple pursuers and an evader in a boundaryless environment. In the first game, we give a sufficient condition on the ratio of sensing to stepping radius of the players that guarantees capture. In the second, we determine the minimum probability of capture, which is a function of a novel pursuer formation and independent of the initial evader location. The sweep and pursuit phases reduce both games to previously studied problems with unlimited range sensing, and capture is achieved using available strategies. We obtain novel upper bounds on the capture time and present simulation studies that address the performance of the strategies under sensing errors, different ratios of sensing to stepping radius, greater evader speed, and a different number of pursuers.      

Randomized pursuit-evasion in a polygonal environment

This paper contains two main results. First, we revisit the well-known visibility-based pursuit-evasion problem, and show that in contrast to deterministic strategies, a single pursuer can locate an unpredictable evader in any simply connected polygonal environment, using a randomized strategy. The evader can be arbitrarily faster than the pursuer, and it may know the position of the pursuer at all times, but it does not have prior knowledge of the random decisions made by the pursuer. Second, using the randomized algorithm, together with the solution to a problem called the "lion and man problem" as subroutines, we present a strategy for two pursuers (one of which is at least as fast as the evader) to quickly capture an evader in a simply connected polygonal environment. We show how this strategy can be extended to obtain a strategy for a polygonal room with a door, two pursuers who have only line-of-sight communication, and a single pursuer (at the expense of increased capture time).