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     

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

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.     

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

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

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.     

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.     

Method for lexicographic suboptimal control of the evader in a conflict problem

An approach is considered that allows generating a suboptimal strategy for the evader in a nonlinear feedback position control problem that can be implemented in real time. The evader does not know exactly what actions the pursuer will take up, and the evader’s strategy is selected from the known functionality of both players and worse possible actions of the pursuer. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 156–167, May–June 2006.     

Tracking an omnidirectional evader with a differential drive robot

In this paper we consider the surveillance problem of tracking a moving evader by a nonholonomic mobile pursuer. We deal specifically with the situation in which the only constraint on the evader’s velocity is a bound on speed (i.e., the evader is able to move omnidirectionally), and the pursuer is a nonholonomic, differential drive system having bounded speed.     

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.      

A linear differential game with a fixed termination time and restrictions on resources

A linear game with a fixed termination time and integral restrictions on player controls is considered. The pursuer constructs his control with knowledge of the control of the evader, and the evader uses information on all previous actions of his opponent at each instant of time. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 178–183, July–August, 2000.     

Maintaining strong mutual visibility of an evader moving over the reduced visibility graph

In this paper, we address the problem of determining whether a mobile robot, called the pursuer, is able to maintain strong mutual visibility (a visibility notion between regions over a convex partition of the environment) of an antagonist agent, called the evader. We frame the problem as a non cooperative game. We consider the case in which the pursuer and the evader move at bounded speed, traveling in a known polygonal environment with or without holes, and in which there are no restrictions as to the distance that might separate the agents. Unlike our previous efforts (Murrieta-Cid et al. in Int J Robot Res 26:233–253, 2007), we give special attention to the combinatorial problem that arises when searching for a solution through visiting several locations in an environment with obstacles. In this paper we take a step further, namely, we assume an antagonistic evader who moves continuously and unpredictably, but with a constraint over its set of admissible motion policies, as the evader moves in the shortest-path roadmap, also called the reduced visibility graph (RVG). The pursuer does not know which among the possible paths over the RVG the evader will choose, but the pursuer is free to move within all the environment. We provide a constructive method to solve the decision problem of determining whether or not the pursuer is able to maintain strong mutual visibility of the evader. This method is based on an algorithm that computes the safe areas (areas that keep evader surveillance) at all times. We prove decidability of this problem, and provide a complexity measure to this evader surveillance game; both contributions hold for any general polygonal environment that might or not contain holes. All our algorithms have been implemented and we show simulation results.     

Variable feedback gain control design based on particle swarm optimizer for automatic fighter tracking problems

The main focus of this paper is to develop an optimization method for the automatic fighter tracking (AFT) problem. The AFT problem is similar to a general evader–pursuer maneuvering automation problem between the dynamic systems of two highly interactive objects. This paper proposes a particle swarm optimizer-based variable feedback gain controller (PSO-based VFGC) for dealing with AFT problems. The PSO-based VFGC is designed to obtain the control value of a pursuer through an error-feedback gain controller. Once conditions of system closed-loop stability have been satisfied, the optimal feedback gains can be obtained through PSO, and the actual control values can be derived from the obtained values. Simulation results confirm the capabilities of the proposed method by comparing the results against two other methods in the field: the weight matrix value defined Ricatti equation, and the linear matrix inequality (LMI) based linear quadratic regulator (LQR). The performance of the proposed method is superior to that of its alternatives.     

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.      

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.     

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.     

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.     

Finite state stochastic games: Existence theorems and computational procedures

Let{X_{n}}be a Markov process with finite state space and transition probabilitiesp_{ij}(u_{i}, v_{i})depending on uiandv_{i}.State 0 is the capture state (where the game ends;p_{oi} equiv delta_{oi});u = {u_{i}}andv = {v_{i}}are the pursuer and evader strategies, respectively, and are to be chosen so that capture is advanced or delayed and the costC_{i^{u,v}} = E[Sum_{0}^{infty} k (u(X_{n}), v(X_{n}), X_{n}) | X_{0} = i]is minimaxed (or maximined), wherek(alpha, beta, 0) equiv 0. The existence of a saddle point and optimal strategy pair or e-optimal strategy pair is considered under several conditions. Recursive schemes for computing the optimal or ε-optimal pairs are given.     

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