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.      

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

针对包含有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.     

Pursuing a maneuvering target which uses a random process for itscontrol

Since a pursuer pursuing a maneuvering target does not know what maneuvers an evading target will make, the maneuvers (the target's control law) appear as a random process to the pursuer. However, he has opinions about what the evader will do. From these, he can assign a prior probability distribution to the evader's maneuvers. For a linear pursuit evasion problem in which the evader's control law is modeled as a random process, in which the pursuer has partial noisy linear measurements of his own and the evader's relative position, and a quadratic optimality criterion is used, past results of the authors imply that the optimal control is a linear function of the “predicted miss”. Determining the predicted miss involves estimating the evader's terminal position from past system measurements. Nonlinear filtering techniques are used to give expressions for computing the conditional expectation of the evader's terminal position even in the presence of the random unknown maneuvers of the evader     

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.     

The pursuit-evasion problem under integral-geometric constraints on pursuer controls

We study the pursuit-evasion problem for a model game with simple motions when pursuer controls are subject to both integral and geometric constraints while evader controls are only subject to geometric ones. Depending on initial conditions of the players and parametric values participating in control constraints, we prove the theorem of alternative. To solve the pursuit problem, we propose a parallel pursuit strategy (Π-strategy) that ensures optimal convergence of the players and study its structure depending on the parameters. To solve the evasion problem, we find lower bounds on the convergence that also depend on given parameters. This work develops and extends the works of Isaacs, Petrosyan, Pshenichnyi and other researchers, including the author.     

A discrete dynamic game modelling anti-missile defense scenarios

A discretized game model of an anti-missile defense scenario is presented. Such an engagement is a pursuit of a blind evader, committed to satisfy a terminal constraint. It can be formulated as an incomplete information zero-sum pursuit-evasion game with state constraint. Such a game becomes non trivial if the evader has higher maneuverability than the pursuer. In this case the game admits a saddle-point solution in mixed strategies. Two simple examples illustrate the major elements of the solution.     

Pursuit evasion game with costly information

In this paper we study a pursuit evasion game in which information is costly. The pursuer has to pay, i.e. lose some time, whenever he wants information on the evader's position. Therefore the capture will be done in successive stages. The pursuer gets information, then moves using an open loop control, and so on. We characterize the setC ₁ of the initial states that the pursuer can capture in one stage whatever the evader does. This set is taken as a new target for an other stage. In this way we characterize the setC _n of the initial states the pursuer can capture inn stages in the worst case. We also give a pursuer's strategy that minimizes the total duration of the game, as opposed to the number of stages.This research has been supported in part by the French Direction des Recherches et Etudes Techniques (DRET).     

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.     

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

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.     

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.     

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.     

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.     

Anticipated velocity based guidance strategy for wheeled mobile evader amidst stationary and moving obstacles in bounded environment

This paper is concerned with a class of pursuit‐evasion game problems amidst stationary and moving obstacles in a bounded environment. We concentrate on evader's strategy taking into account the following challenges: (i) pursuer and evader are nonholonomic wheeled mobile robots and the evader is slower than the pursuer; (ii) pursuer follows a proportional navigation law; and (iii) geometry of the environment is not known to the players, a priori. We propose an efficient evader‐centric anticipated velocity based guidance strategy. Pursuer's trajectory is anticipated at each step by the evader using quadratic polynomial interpolation. The aim of the evader is to escape interception with the pursuer for maximum possible time. To deal with static obstacles, a technique based on a well‐known tangent bug algorithm is presented. While dealing with dynamic obstacles, a recently introduced reciprocal orientation method is employed to avoid collision in situations when the dynamic obstacle also cooperates in the process. In case dynamic obstacles do not participate in the process of collision avoidance, a well‐known velocity obstacle method is employed for planning safe collision‐free paths. Efficiency of the proposed algorithms is analyzed with respect to the interception time and the distance traveled by the players. Copyright © 2014 John Wiley & Sons, Ltd.     

A Group Pursuit Game

A differential game of pursuit of an evader by m dynamic pursuers under simple motion is studied. The time of game completion is fixed. Pursuers’ controls obey integral constraints, whereas the evader control obeys either an integral constraint or a geometric constraint. A differential game with cost defined by the distance between the evader and his nearest pursuer at the game completion instant is studied. Optimal strategies for players are constructed and the game cost is determined.__________Translated from Avtomatika i Telemekhanika, No. 8, 2005, pp. 24–35.Original Russian Text Copyright © 2005 by Ibragimov.     

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

结合无人机(UAV)的空中移动和无人车(UGV)的地面移动特点,本文提出了一种UAV/UGV空地协作系统,并且针对其在复杂地形中的追逃问题,提出了一种复杂三维多面体环境中UAV/UGV空地协作追逃策略.首先介绍了UAV/UGV空地协作系统的结构与协作追逃问题描述.接着将边界值问题(BVP)改进并离散化作为博弈走法生成器...     

Equilibria problems on games: Complexity versus succinctness

We study the computational complexity of problems involving equilibria in strategic games and in perfect information extensive games when the number of players is large. We consider, among others, the problems of deciding the existence of a pure Nash equilibrium in strategic games or deciding the existence of a pure Nash or a subgame perfect Nash equilibrium with a given payoff in finite perfect information extensive games. We address the fundamental question of how can we represent a game with a large number of players? We propose three ways of representing a game with different degrees of succinctness for the components of the game. For perfect information extensive games we show that when the number of moves of each player is large and the input game is represented succinctly these problems are PSPACE-complete. In contraposition, when the game is described explicitly by means of its associated tree all these problems are decidable in polynomial time. For strategic games we show that the complexity of deciding the existence of a pure Nash equilibrium depends on the succinctness of the game representation and then on the size of the action sets. In particular we show that it is NP-complete, when the number of players is large and the number of actions for each player is constant, and that the problem is -complete when the number of players is a constant and the size of the action sets is exponential in the size of the game representation. Again when the game is described explicitly the problem is decidable in polynomial time.     

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.