Evasion from many pursuers in simple motion differential game with integral constraints

We study a two dimensional evasion differential game with several pursuers and one evader with integral constraints on control functions of players. Assuming that the total resource of the pursuers does not exceed that of the evader, we solve the game by presenting explicit strategy for the evader which guarantees evasion.     

On a Characterization of Evasion Strategies for Pursuit-Evasion Games on Graphs

We give a characterization of robber-win strategies for general pursuit-evasion games with one evader and any finite number of pursuers on a finite graph. We also give an algorithm that solves robber-win games.     

On some problems of guaranteed search on graphs

Pursuit-evasion differential games on graphs with no information on the evader are considered. Special attention is given to the following ɛ-search problem posed by Golovach. A topological graph embedded in three-dimensional Euclidean space is considered. For simplicity, its edges are assumed to be polygonal, only simple motions of the pursuers and the evader are allowed, and the graph is a phase constraint for all players. The goal of the pursuers is to construct a program depending only on the structure of the graph which ensures capturing the invisible evader, i.e., approaching the evader at a distance of at most ɛ (in the intrinsic metric of the graph), where ɛ is a given nonnegative number. The problem consists in finding the minimum number of pursuers (called the ɛ-search number) needed to capture the evader. Properties of the Golovach function, which assigns the ɛ-search number to every nonnegative ɛ, are investigated. Golovach and Petrov proved that the Golovach function for the complete graph on more than five vertices may have non-unit jumps. The authors of this paper are aware of examples of similar degeneration for trees. These examples disprove the conjecture that the Golovach function of any planar graph has only unit jumps. A subclass of trees for which the Golovach function has only unit jumps is distinguished.     

A Two-on-One Linear Pursuit–Evasion Game with Bounded Controls

A linearized engagement with two pursuers versus a single evader is considered, in which the adversaries’ controls are bounded and have first-order dynamics and the pursuers’ intercept times are equal. Wishing to formulate the engagement as a zero-sum differential game, a suitable cost function is proposed and validated, and the resulting optimization problem and its solution are presented. Construction and analysis of the game space is shown, and the players’ closed-form optimal controls are derived for the case of two “strong” pursuers. The results are compared to those of a 1-on-1 engagement with a “strong” pursuer, and it is shown that the addition of a second pursuer enlarges the capture zone and introduces a new singular zone to the game space, in which the pursuers can guarantee equal misses, regardless of the evader’s actions. Additionally, it is concluded that in the regular zones the closed-form optimal pursuit strategies are unchanged compared to two 1-on-1 engagements, whereas the optimal evasion strategy is more complex. Several simulations are performed, illustrating the adversaries’ behavior in different regions of the game space.     

Monotonicity of the search number in the Golovach problem

The Golovach problem, also known as the ɛ-search problem, is as follows. A team of pursuers pursues an evader on a topological graph. The objective of the pursuers is to catch the evader, that is, approach the evader to a distance not exceeding a given nonnegative number ɛ. It is assumed that the evader is invisible to the pursuers and is fully informed beforehand about the search program of the pursuers. The problem is to find the ɛ-search number, i.e., the least number of pursuers sufficient for capturing the evader. Graphs with monotone ɛ-search number are studied; the ɛ-search number of a graph G is said to be monotone if it is not exceeded by the ɛ-search numbers of all connected subgraphs H of G. It is known that the ɛ-search number of any tree is monotone for all nonnegative ɛ. The edgesearch number, which is equal to the 0-search number, is monotone for all connected subgraphs of an arbitrary graph. A sufficient monotonicity condition for the ɛ-search number of any graph is obtained. This result is improved in the case of complete subgraphs. The Golovach function is constructed for graphs obtained by removing one edge from complete graphs with unit edges.     

A game of optimal pursuit of one object by several

A differential game in which m dynamical objects pursue a single one is investigated. All the players perform simple motions. The termination time of the game is fixed. The controls of the first k (k ⩽ m) pursuers are subject to integral constraints and the controls of the other pursuers and the evader are subject to geometric constraints. The payoff of the game is the distance between the evader and the closest pursuer at the instant the game is over. Optimal strategies for the players are constructed and the value of the game is found.     

Group pursuit under bounded evader coordinates

Effective methods are proposed for solving the group pursuit problem with constraints on the evader's state. The paper is closely related to the investigations in /1–4/ (^**) and is a development of the results in /5/ in the case of arbitrary linear equations of motion of the evader.     

On intersections of abelian and nilpotent subgroups in finite groups. I

We consider Pontryagin’s generalized nonstationary example with identical dynamic and inertial capabilities of the players under phase constraints on the evader’s states. The boundary of the phase constraints is not a “death line” for the evader. The set of admissible controls is a ball centered at the origin, and the terminal sets are the origin. We obtain sufficient conditions for a multiple capture of one evader by a group of pursuers in the case when some functions corresponding to the initial data and to the parameters of the game are recurrent.     

Successive Pursuit with a Bounded Detection Domain

We study a coplanar model of the successive pursuit of two evaders with unlimited turn rates of the players and a bounded detection domain of a pursuer. Involved in catching the first evader, the pursuer may lose sight of the other. In this case, it must search later for the lost evader in the plane. We describe two guaranteed pursuit strategies obtained as solutions of differential games. Both strategies include a two-stage strategy to shorten to a specified quantity the distance to the nearer evader, and a two-stage strategy to search and capture the other.The strategies are distinguished by their search plans. First, coalition is pursued as a whole. Then, to minimize an uncertainty index, the pursuer approaches the first evader using the strategy of successive pursuit with the unmoved second evader at its last observed position. Subsequently, the pursuer moves directly to that position of the second evader, or according to the more complex plan, alternates between traversing a straight line and arcs of logarithmic spirals. After detection, the remaining evader is captured with the use of a simple pursuit strategy.The barriers fit the strategies. We call them approximate, since they bound the states where the pursuer succeeds with the guaranteed (but not optimal as in the case of ordinary barriers) strategies. These barriers are surfaces of constant values of a special game of degree. The more complex search plan secures a wider winning area.Geometrical interpretations and some numerical results for a set of parameters of the game are provided.     

A short note about pursuit games played on a graph with a given genus

On a finite simple graph G = (X,E), p players pursuers $\text{A}{}_1\text{, ∴, A}{}_{\mathrm{p}}$ and one player evader B who move in turn along the edges of G are considered. The p pursuers $\text{A}{}_1\text{, ∴, A}{}_{\mathrm{p}}$ want to catch B who tries to escape. R. Nowakowski and P. Winkler [Discrete Math.43 (1983), 235–240] and A. Quilliot [“Thèse de 3° cycle,” pp. 131–145, Université de Paris VI, 1978] already characterized the graphs such that one pursuer is sufficient to catch the evader B. Very recently, M. Aigner and M. Fromme [Appl. Discrete Math., in press] proved that if G is a planar graph, three pursuers are sufficient to catch the evader B. This result is extended, showing that if G is a graph with a given genus k, then 3 + 2k pursuers are enough to “arrest” the evader B.     

Two evasion problems in a plane with separate controls and non-convex terminal sets

Two different pursuit-evasion games are considered from the evader's point of view. The phase space is a plane, each of the two players controlling the motion of a point only along its own coordinate. The terminal sets are not convex; in the first problem, the set is an arc of a circle, in the second, the union of tow segments. In both games evasion cannot the achieved by means of programmed controls, but it can be achieved using feedback control. However, the strategies, which are continuous functions of the phase vector, have different properties in each problem. In the first, they cannot guarantee evasion (which is typical for the linear-convex case as well), but in the second they can (which is impossible in linear-convex games with a fixed final time). Verification that evasion is unachievable using such strategies reduces here to proving the solvability of a certain initial-value problem for an advanced differential equation, to which the Schauder principle is applicable.     

On a nonstationary problem of group pursuit

Pontryagin’s classical nonstationary example with many participants and phase constraints on the evader’s states with equal dynamic and inertia capabilities of the players is considered. The case of a simple motion is considered separately. Solvability conditions for problems of pursuit and evasion are obtained.     

Differential game of optimal approach of two inertial pursuers to a noninertial evader

In this paper, the game of the optimal approach of two identical inertial pursuers to a noninertial evader is investigated. The duration of the game is fixed. The payoff functional is the distance between the evader and the closest pursuer when the game terminates. The value function is constructed for all possible positions of the game. The regions where the pursuit is one-to-one and the regions where it is essentially collective are described algorithmically. Some analogies between this game and the linear differential game with elliptical vectograms are indicated. It is noted that the focal surface and the dispersal surface are in proximity of one another.     

An evasion game with a destination

This paper solves an aiming and evasion game in which a gunner with a number of shots attempts to hit an evader moving along the positivex-axis. The gunner's aiming of the evader is complicated by the fact that there is a delay due to the time taken for the shot to reach the evader from the gunner.     

Revisiting a Three-Player Pursuit-Evasion Game

Journal of Optimization Theory and Applications - We consider the game of a holonomic evader passing between two holonomic pursuers. The optimal trajectories of this game are known. We give a...     

A multistage pursuit-evasion game that admits a gaussian random process as a maximin control policy

In this paper we consider the existence and structure of both minimax and maximin policies for the special class of LQG pursuit-evasion games which is characterized by (i) a blind evader; and (ii) a pursuer who can make use of noise corrupted state measurements. The particular class of games which we consider has been studied previously by other investigators who have shown that pure strategies exist for both players. The major contribution of our paper is the delineation of the existence and structure of a mixed strategy for the evader in this class of games. This new maximin strategy is defined by a gaussian measure, which can be determined explicitly by the method of least favorable prior distributions. We show that the validity of the pure solutions determined previously is limited by the duration of the game, due to the existence of a ‘pure solution conjugate point’; further, we prove that our new strategies are valid solutions which extend the possible duration of the game beyond the limit imposed by the pure solution conjugate point. We believe that our paper constitutes the first report on the existence of a mixed strategy for an LQG game, and the first report on the role conjugate points play in the transition between pure strategies and mixed strategies.     

Optimal Evasion from a Pursuer with Delayed Information

A class of prescribed duration pursuit–evasion problems with first-order acceleration dynamics and bounded controls is considered. In this class, the pursuer has delayed information on the lateral acceleration of the evader, but knows perfectly the other state variables. Moreover, the pursuer applies a strategy derived from the perfect information pursuit–evasion game solution. Assuming that the evader has perfect information on all the state variables as well as on the delay of the pursuer and its strategy, an optimal evasion problem is formulated. The necessary optimality conditions indicate that the evader optimal control has a bang–bang structure. Based on this result, two particular cases of the pursuer strategy (continuous and piecewise continuous in the state variables) are considered for the solution of the optimal evasion problem. In the case of the continuous pursuer strategy, the switch point of the optimal control can be obtained as a root of the switch function. However, in the case of the piecewise continuous (bang–bang) pursuer strategy, this method fails, because of the discontinuity of the switch function at this very point. In this case, a direct method for obtaining the switch point, based on the structure of the solution, is proposed. Numerical results illustrating the theoretical analysis are presented leading to a comparison of the two cases.     

A nonstationary group pursuit problem

We consider a linear nonstationary problem of conflict interaction of controlled objects, where the number of pursuers equals ν and the number of evaders equals µ. All participants are assumed to have equal dynamic abilities. The purpose of the pursuers is to catch all evaders, while the purpose of the latter is to avoid being caught for at least one of them. We establish sufficient solvability conditions for the local evasion problem.     

Simple-motion pursuit-evasion differential games,part 1: Stroboscopic strategies in collision-course guidance and proportional navigation

We consider pursuit-evasion differential games in the plane in which the players, i.e., the pursuer and the evader, have simple motion and are pedestrians à la Isaacs. Two information patterns are considered, namely the classical feedback strategy and the stroboscopic pursuit strategy; loosely speaking, the latter incorporates the instantaneous control employed by the evader, which we assume to be known to the pursuer. Within this framework, the question of modelling a pursuit-evasion encounter is addressed, and we examine three well-known guidance schemes of the line-of-sight, collision course, and proportional navigation types.     

Note on a pursuit game played on graphs

In [1] Aigner and Fromme considered a game played on a finite graph G where m pursuers try to catch one evader. They introduced c(G) as the minimal number m of pursuers that are sufficient to catch the evader and, among other things, they asked if it is true that c(G) ≤ k whenever the maximal degree of G is at most k. In the present note we give a negative answer to this question by showing that, for all positive integers k, n (k ≥ 3), there exists a k-regular graph G with c(G) ≥ n.