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

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.     

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.     

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.     

Construction of the value function in a pursuit-evasion game with three pursuers and one evader

A differential pursuit-evasion game is considered with three pursuers and one evader. It is assumed that all objects (players) have simple motions and that the game takes place in a plane. The control vectors satisfy geometrical constraints and the evader has a superiority in control resources. The game time is fixed. The value functional is the distance between the evader and the nearest pursuer at the end of the game. The problem of determining the value function of the game for any possible position is solved.

Three possible cases for the relative arrangement of the players at an arbitrary time are studied: “one-after-one”, “two-after-one”, “three-after-one-in-the-middle” and “three-after-one”. For each of the relative arrangements of the players a guaranteed result function is constructed. In the first three cases the function is expressed analytically. In the fourth case a piecewise-programmed construction is presented with one switchover, on the basis of which the value of the function is determined numerically. The guaranteed result function is shown to be identical with the game value function. When the initial pursuer positions are fixed in an arbitrary manner there are four game domains depending on their relative positions. The boundary between the “three-after-one-in-the-middle” domain and the “three-after-one” domain is found numerically, and the remaining boundaries are interior Nicomedean conchoids, lines and circles. Programs are written that construct singular manifolds and the value function level lines.     

An Inexact Spingarn’s Partial Inverse Method with Applications to Operator Splitting and Composite Optimization

In this paper, a pursuit-evasion game involving two non-holonomic agents is examined using the theory of differential games. It is assumed that the two players move on the Euclidean plane with fixed but different speeds and they each have a lower bound on their achievable turn radii. Both players steer at each instant by choosing their turn radii value and directions of turn. By formulating the game as a game of kind, we characterize the regions of initial conditions that lead to capture as well as the regions that lead to evasion, when both the players play optimally. The game is then formulated as a game of degree to obtain time-optimal paths for the pursuer and evader inside a capture region. Besides, all possible scenarios are considered for both players that differ in speed ratios and maneuverability constraints. Solutions are provided for those cases using appropriate simulation parameters, which aid in understanding the characteristics of the game of two cars under a wide range of constraints.     

The game of two identical cars

This paper describes a third-order pursuit—evasion game in which both players have the same speed and minimum turn radius. The game of kind is first solved for thebarrier or envelope of capturable states. When capture is possible, the game of degree is then solved for the optimal controls of the two players as functions of the relative position. The solution is found to include a universal surface for the pursuer and a dispersal surface for the evader.     

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.     

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.     

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.     

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

Game saturation of intersecting families

We consider the following combinatorial game: two players, Fast and Slow, claim k-element subsets of [n] = {1, 2, …, n} alternately, one at each turn, so that both players are allowed to pick sets that intersect all previously claimed subsets. The game ends when there does not exist any unclaimed k-subset that meets all already claimed sets. The score of the game is the number of sets claimed by the two players, the aim of Fast is to keep the score as low as possible, while the aim of Slow is to postpone the game’s end as long as possible. The game saturation numbers, gsat_F(II _n,k ) and gsat_S(II _n,k ), are the score of the game when both players play according to an optimal strategy in the cases when the game starts with Fast’s or Slow’s move, respectively. We prove that $\Omega _k (n^{k/3 - 5} ) \leqslant gsat_F (\mathbb{I}_{n,k} ),gsat_S (\mathbb{I}_{n,k} ) \leqslant O_k (n^{k - \sqrt {k/2} } )$ .     

A differential game of approach with two pursuers and one evader

A differential game of approach with one evader and two pursuers with a nonconvex payoff function is considered. The duration of the game is fixed. The payoff functional is the distance between the object being pursued and the pursuer closest to it when the game terminates. An explicit form of the game value is found for all possible game positions. The paper is closely related to Refs. 1–12.The authors would like to thank Professor A. I. Subbotin for his valuable advice and encouragement.     

On differential games of evasion from many pursuers

This paper contains a survey of some results regarding differential games of evasion from many pursuers. This class of games presents special difficulties and usually cannot be treated by standard methods. The approach developed consists of constructing piecewise program strategies for the evader, based on certain maneuvers of evasion from one pursuer. These strategies satisfy one additional condition (state constraint): the evader's motion does not leave a given neighborhood of a prescribed nominal motion. An upper estimate for the number of program pieces of the evader's control and a lower estimate for the minimal distance between the evader and the pursuers are also obtained. These results are given for several types of equations of the game.Dedicated to G. Leitmann     

Symmetric solutions of some production economies

A symmetricn-person game (n, k) (for positive integerk) is defined in its characteristic function form byv(S)=[¦S¦/k], where ¦S¦ is the number of players in the coalitionS and [x] denotes the largest integer not greater thanx, (i.e., anyk players, but not less, can “produce” one unit). It is proved that in any imputation in any symmetric von Neumann-Morgenstern solution of such a game, a blocking coalition ofp=n?k+1 players who receive the largest payoffs is formed, and their payoffs are always equal. Conditions for existence and uniqueness of such symmetric solutions with the otherk?1 payoffs equal too are proved; other cases are discussed thereafter.     

The optimal pursuit problem reduced to an infinite system of differential equations

The optimal game problem reduced to an infinite system of differential equations with integral constraints on the players’ controls is considered. The goal of the pursuer is to bring the system into the zeroth state, while the evader strives to prevent this. It is shown that Krasovskii's alternative is realized: the space of states is divided into two parts so that if the initial state lies in one part, completion of the pursuit is possible, and if it lies in the other part, evasion is possible. Constructive schemes for devising the optimal strategies of the players are proposed, and an explicit formula for the optimal pursuit time is derived.     

Game chromatic number of strong product graphs

The graph coloring game is a two-player game in which the two players properly color an uncolored vertex of G alternately. The first player wins the game if all vertices of G are colored, and the second wins otherwise. The game chromatic number of a graph G is the minimum integer k such that the first player has a winning strategy for the graph coloring game on G with k colors. There is a lot of literature on the game chromatic number of graph products, e.g., the Cartesian product and the lexicographic product. In this paper, we investigate the game chromatic number of the strong product of graphs, which is one of major graph products. In particular, we completely determine the game chromatic number of the strong product of a double star and a complete graph. Moreover, we estimate the game chromatic number of some King's graphs, which are the strong products of two paths.     

The method of pursuit by several controlled objects of different types

The problem of the pursuit of one evader by several controlled objects of different types is examined. The sufficient conditions are obtained for the pursuit game to terminate in a finite time. The proposed method of pursuer interaction assumes that the pursuing players are separated into two groups, the first of which holds the evader in some domain, while the second searches for the evader in this domain. The paper touches on the researches in /1–9/. Typical examples illustrate the results.     

The solution of the soccer “dream league” game

On January 5, 1996, Maariv, one of the two leading daily newspapers in Israel, announced “The Dream League” game. Every participant in this game was required to “purchase” from a pool of all the soccer players in the Israeli National League, a team which according to his judgment would be chosen as the best team at the end of the season. Purchasing the players was subject to a given budget and to several other constraints. After the soccer season was over, we were requested by Maariv to find the optimal “Dream Team”.The problem of finding the optimal team is shown to be a generalized version of the well-known knapsack problem. It is formulated as an integer program and solved to optimality by the software NAG. Evidently, the optimal Dream Team is much better (in terms of the total cumulative grade) than the actual winning team chosen by the readers of Maariv. A possible heuristic procedure for solving the game in larger settings is also discussed.