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

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

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.      

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.     

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).     

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.     

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.     

A cooperative pursuit-evasion game in wireless sensor and actor networks

This paper studies the problem of the pursuit-evasion game under the wireless sensor and actor networks (WSANs). In order to plan paths for pursuers to capture an evader in the pursuit-evasion game, a novel multi-step cooperative strategy is presented. Under this strategy, the pursuit-evasion game is studied in two stages. In the first stage we assume that the evader is always static in the workplace, and in the second stage the evader will move once it senses the existence of pursuers. A Daisy-Chain Formation algorithm and a sliding mode-based method are presented to control the pursuit. Based on Lyapunov stability theory, the proposed algorithm is proved to be convergent. At last, simulation results are provided to demonstrate the effectiveness of the proposed method.     

Game and Information Theory Analysis of Electronic Countermeasures in Pursuit-Evasion Games

Two-player pursuit-evasion games in the literature typically either assume both players have perfect knowledge of the opponent's positions or use primitive sensing models. This unrealistically skews the problem in favor of the pursuer who needs only maintain a faster velocity at all turning radii. In real life, an evader usually escapes when the pursuer no longer knows the evader's position. In our previous work, we modeled pursuit evasion without perfect information as a two-player bimatrix game by using a realistic sensor model and information theory to compute game-theoretic payoff matrices. That game has a saddle point when the evader uses strategies that exploit sensor limitations, whereas the pursuer relies on strategies that ignore the sensing limitations. In this paper, we consider, for the first time, the effect of many types of electronic countermeasures (ECM) on pursuit-evasion games. The evader's decision to initiate its ECM is modeled as a function of the distance between the players. Simulations show how to find optimal strategies for ECM use when initial conditions are known. We also discuss the effectiveness of different ECM technologies in pursuit-evasion games.      

On a class of pursuit-evasion games

A class of pursuit-evasion games is studied. The problem is to find an optimal control pair which is a saddle point of the terminal miss distance functional, minimizes cost functionals of the pursuer and the evader, and steers the pursuer and the evader to their respective targets. Necessary conditions for an optimal control pair are obtained.     

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.     

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.     

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

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

Multiple capture in Pontryagin’s almost periodic example

This paper considers Pontryagin’s generalized nonstationary example with several participants under the same dynamic and inertial capabilities of the players, in which the set of admissible control actions is a convex compact set and the terminal sets are convex compact sets. We obtain sufficient conditions for the multiple capture of one evader by a group of pursuers under the assumption that some functions associated with the initial data and game parameters are almost periodic. Each pursuer cannot make a capture more than once before being eliminated from the game. Such a situation may happen when the evader must be “terminated” but contact between the pursuer and the evader does not guarantee termination.     

To a nonstationary group pursuit problem with phase constraints

We consider two linear nonstationary pursuit-evasion problems with one evader and a group of pursuers under the conditions that the players have equal dynamic abilities and that the evader cannot leave a certain set. We prove that if the number of pursuers is less than the space dimension, then the evader can avoid capture in the interval [t ₀,∞).     

Policy Improvements for Probabilistic Pursuit-Evasion Game

This paper focuses on a pursuit-evasion game (PEG) which involves two teams: one side consists of pursuers trying to minimize the time required to capture evaders, and the other side consists of evaders trying to maximize the capture time by escaping the pursuers. In this paper, we propose a hybrid pursuit policy for a probabilistic PEG, which possesses the combined merits of local-max and global-max pursuit policies proposed in previous literature. A method to find optimal pursuit and evasion polices for two competitive parties of the pursuers and evaders is also proposed. For this, we employ an episodic parameter optimization (EPO) algorithm to learn good values for the weighting parameters of a hybrid pursuit policy and an intelligent evasion policy. The EPO algorithm is performed during the numerous repeated simulation runs of the PEG and the reward of each episode is updated using reinforcement learning, and the optimal weighting parameters are selected by using particle swarm optimization. We analyze the trend of the optimal parameter values with respect to the number of the pursuers and evaders. The proposed strategy is validated both in simulations and experiments with small ground robots.     

Evaluation of the effectiveness of open-loop evasion strategies in a pursuit-evasion problem

A stochastic pursuit-evasion optimal control problem in the (X, z)-plane is considered. Owing to thrust, drag and gravitational forces, both players have variable speeds. The pursuer applies a feedback pursuit strategy whereas the evader applies an open-loop evasion strategy. By reducing the state-space of the encounter, a method is proposed for evaluating the effectiveness of open-loop evasion strategies.     

On a class of pursuit-evasion problems

This paper shows that a pursuit-evasion problem can be made amenable to solution with nonlinear programming algorithms by operating the pursuer and evader systems in a "discrete" mode of control and by choosing the cost function judiciously.     

Evolving team behaviors with specialization

This article evaluates Collective Neuro-Evolution (CONE), a cooperative co-evolutionary method for solving collective behavior tasks and increasing task performance via facilitating behavioral specialization in agent teams. Specialization is used as a problem solving mechanism, and its emergence is guided and regulated by CONE. CONE is comparatively evaluated with related methods in a simulated evolutionary robotics pursuit-evasion task. This task required multiple pursuer robots to cooperatively capture evader robots. Results indicate that CONE is appropriate for evolving specialized behaviors. The interaction of specialized behaviors produces behavioral heterogeneity in teams and collective prey capture behaviors that yield significantly higher performances compared to related methods.     

The problem of optimal approach in locally Euclidean spaces

A differential game of optimal approach with simple motions when players move in locally Euclidean spaces is studied. The game-end moment is fixed, and the game payment is a distance between the pursuer and the evader at the game-end moment. The value of game is obtained in the explicit form for any initial positions of players. Moreover, the differential game of optimal approach for the denumerable number of pursuers and one evader in the Euclidean space is solved. All pursuers are controlled by one parameter.     

Control of antagonistic swarm dynamics via Lyapunov's method

We consider hostile conflicts between two multi‐agent swarms. First, we investigate the complex nature of a single pursuer attempting to intercept a single evader (1P‐1E), and establish some rudimentary rules of engagement. We elaborate on the stability repercussions of these rules. Second, we extend the modelling and stability analysis to multi‐agent swarms with conflicting interests. The present document considers only swarms with equal membership strengths for simplicity. This effort is based on a set of suggested momenta deployed on individual agents. Because pursuers and evaders differ in the influences that they exert on one another, we emphasize asymmetry in momenta between the two types of swarm members. The proposed centralized control law evolves from a Lyapunov concept. Swarm interactions are modelled in two phases: the approach phase during which the two swarms act like individuals in the 1P‐1E interaction; and the individual pursuit phase where each pursuer is assigned to an evader. Copyright © 2010 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society