Isaacs' princess and monster game on the circle

The solution is given of a multistage pursuit-evasion game in which ablind pursuer searches for ablind evader within a finite set of locations arranged in a circle. The players traverse this set by transfering their positions, at each of a succession of instants, from the points which they occupy to ones which are adjacent to them. Some standard results of measure theory are used to construct the players' optimal strategies when the payoff to the evader is the time taken for the pursuer to find him or, more generally, an increasing function of this time.This work was carried out with the support of a CSIRO postgraduate studentship.     

Stochastic pursuit-evasion differential games in 3D

A stochastic version of Isaacs's homicidal chauffeur game in the (x, y, z)-space is considered. This is used to solve a pursuit-evasion problem in the (x, y, z)-space in which the pursuer has incomplete information on the evader motion. Optimal feedback strategies for the game, and optimal feedback guidance laws for the pursuer, which uses only the measurements available to the pursuer, are computed. A simple suboptimal guidance law for the pursuer is suggested.     

Game problem of “soft landing” for second-order systems

The paper considers the approach game problem of one control object moving in the space with the other whose motion is executed in the horizontal plane. In this case, the horizontal plane plays the role of state constraints for the pursuer, who, therefore, can move only in the upper half-space. The dynamics of the player models the motion of different-type objects in a medium with friction. The goal of the pursuer is the approach of geometric coordinates and the velocities of the players (soft landing) at a certain finite instant of time. The paper distinguishes initial states of the pursuer and also establishes sufficient conditions on the parameters of the conflict-control process under which the “soft landing” problem is solvable at a finite time. Moreover, the authors use a method that allows them to reduce the game problem to an equivalent control problem. Based on a detailed study of the reachable set of the latter problem, the authors construct pursuer controls allowing one to solve the initial problem in explicit (analytical) form. Moreover, in the first stage, based on the N. N. Krasovskii extremal aiming principle, the authors align the velocity of the players, and in the concluding stage, they directly perform the “soft landing.” At each stage, the time needed for solution of the problem can be found a priori. In conclusion, the authors discuss the results of modeling the “soft landing” process. __________ Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 23, Optimal Control, 2005.     

A pursuit-evasion differential game with noisy measurements of the evader's bearing from the pursuer

A stochastic pursuit-evasion differential game involving two players, E and P, moving in the plane is considered. It is assumed that player E (the evader) has complete observation of the position and velocity of player P, whereas player P (the pursuer) can measure the distanced (P, E) between P and E but receives noise-corrupted measurements of the bearing of E from P. Three cases are dealt with: (a) using the noise-corrupted measurements of , player P applies the proportional navigation guidance law; (b) P has complete observation ofd (P, E) and (this case is treated for the sake of completeness); (c) using the noise-corrupted measurements of , P applies an erroneous line-of sight guidance law. For each of the cases, sufficient conditions on optimal strategies are derived. In each of the cases, these conditions require the solution of a nonlinear partial differential equation on a in ². Finally, optimal strategies are computed by solving the corresponding equations numerically.     

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.     

Informational Sets in a Model Problem of Homing

A linear pursuit problem in the plane under incomplete pursuer information about the evader is investigated. At discrete time instants, the pursuer measures with errors the angle of vision to the evader, the angular velocity of the line of sight, and the relative distance. Other combinations of measurable parameters are possible (for example, angle of vision and relative distance or angle of vision only). The measurements errors obey certain geometric constraints. The initial uncertainties on the evader coordinates and velocities are given in advance. Having a resource of impulse control, the pursuer tries to minimize the miss distance. The evader control is bounded in modulus.The problem is formulated as an auxiliary differential game. Here, the notion of informational set is central. The informational set is the totality of pointwise phase states consistent with the history of the observation-control process. The informational set depends on the current measurements; it changes in time and plays the role of a generalized state, which is used for constructing the pursuer control.A control method designed for the linear pursuit problem is used in the planar problem of a vehicle homing toward a dangerous space object. The nonlinear dynamics is described by the Kepler equations. Nonlinear terms of the equations in relative coordinates are small and are replaced by an uncertain vector parameter, which is bounded in modulus and is regarded as an evader control. As a result, we obtain the mentioned control problem in the plane.The final part of the paper is devoted to the simulation of a space vehicle homing toward a dangerous space object. In testing the control method developed, two variants are considered: random measurement errors and game method of constructing the measurements; the latter is also described in the paper.     

Robust pursuit of a hybrid evader

A pursuit-evasion differential game with bounded controls and prescribed duration is considered. The evader has two possible dynamics, while the pursuer dynamics is fixed. The evader can change the dynamics once during the game. The pursuer knows the possible dynamics of the evader, but not the actual one. The optimal pursuer strategy in this game is obtained. It is robust with respect to the control of the evader, the order of its dynamics and the time of the mode change. The capture conditions of the game are established and the pursuer capture zone is constructed. An illustrative example of the game is also presented.     

Search game in a rectangle

We consider a search game in which the searcher (player S) moves along a continuous trajectory in a rectangleQ. The velocity vectogram of player S is a rhombus-type set. In this paper, we construct the strategies of both players which make it possible to find the asymptotic value of the game in the case of small discovery radius.The author would like to thank the referee for considerable simplification of the proof of Theorem 4.1.     

Singular Arcs in the Optimal Evasion Against a Proportional Navigation Vehicle

The two-dimensional optimal evasion problem against a proportional navigation pursuer is analyzed using a nonlinear model. The velocities of both players have constant modulus, but change in direction. The problem is to determine the time-minimum trajectory (disengagement) or time-maximum trajectory (evasion) of the evader while moving from the assigned initial conditions to the final conditions. A maximum principle procedure allows one to reduce the optimal control problem to the phase portrait analysis of a system of two differential equations. The qualitative features of the optimal process are determined.     

Homicidal Chauffeur Game with Target Set in the Shape of a Circular Angular Sector: Conditions for Existence of a Closed Barrier

A planar constant-speed pursuit-evasion problem with dynamic model similar to the one of the homicidal chauffeur game and with prescribed angular constraints in the capture criterion is analyzed as a differential game of kind. Because of the angular constraints, the target set of the game has the shape of a circular angular sector. Conditions for the existence of the game barrier (closed) are obtained. Using these conditions, a necessary and sufficient condition for capture of a slower evader from any initial state of the game is established. This condition is represented by an expression for the minimal nondimensional capture radius, normalized by the pursuer minimal turning radius, which guarantees capture of all slower evaders. This minimal capture radius depends on the angular constraints. Capture from any initial state implies that the barrier of the game does not exist and vice versa. In this game, two types of barrier are derived, with termination at either points of smoothness or points of nonsmoothness (corner points) of the boundary of the target set. The results are illustrated by numerical examples.     

New properties of the Busemann ellipsea

A combination of the Busemann ellipse, the inscribed unit circle and a circle of radius √2 about the same centre is considered. For supersonic two-dimensional potential gas flows, it is shown that the inclinations of the velocity vector in motion along an arbitrary characteristic, the characteristic itself and the characteristic of the other family have values equal to, respectively. the difference between the areas of the elliptical and circular (R = 1) sectors, the difference between the areas of the elliptical and circular (R = √2) sectors, and the area of the elliptical sector, apart from unimportant multiplicative and additive constants. The straight sides of the sectors in question are the semiminor antis of the ellipse and the radius vector of the velocity. The obvious analogy with one of Ke:pler's laws is pointed out. The existence of a point of intersection of the ellipse and the second circle illustrates a well-known result of Khristianovich concerning the points of inflexion of characteristics with a monotone velocity distribution. It is shown how the combination of the ellipse and the inscribed circle illustrates the simplification of the compatibility conditions and the Darboux equation for trans- and hypersonic flows.     

Nonzero-sum stochastic games with unbounded costs: Discounted and average cost cases

We treat non-cooperative stochastic games with countable state space and with finitely many players each having finitely many moves available in a given state. As a function of the current state and move vector, each player incurs a nonnegative cost. Assumptions are given for the expected discounted cost game to have a Nash equilibrium randomized stationary strategy. These conditions hold for bounded costs, thereby generalizing Parthasarathy (1973) and Federgruen (1978). Assumptions are given for the long-run average expected cost game to have a Nash equilibrium randomized stationary strategy, under which each player has constant average cost. A flow control example illustrates the results. This paper complements the treatment of the zero-sum case in Sennott (1993a).     

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.     

An approach via state estimation to differential games with information time lag

This paper deals with zero-sum two-person differential games in which one player has a deferred information on the state vector. This player mends this lack of information by using an adaptative deterministic extrapolation to estimate the plant state, and then, makes his decisions by means of the datas so obtained. An analysis of the phenomenon yields a criterion for optimizing the estimation which is based upon the Hamiltonian estimation of the perfect information game. A class of extrapolators is given by its dynamical equation. Then, the initial game is reduced to a new game containing pure time delay in the state and the controls.     

One pursuer and two evaders on the line: A stochastic pursuit-evasion differential game

A differential game of pursuit and evasion on the real line is discussed with one pursuer and two evaders, the motion of the players being affected by noise. The game of degree is considered, where the pursuer strives to maximize the probability of his winning the game, i.e., of capturing at least one of the evaders, the probability function being given as a solution to a certain partial differential equation; the heat conduction analogy is also being discussed. The degenerate situation here arises in a natural way, and it is possible to present a quite detailed analysis of this case.     

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.     

Static search games played over graphs and general metric spaces

We define a general game which forms a basis for modelling situations of static search and concealment over regions with spatial structure. The game involves two players, the searching player and the concealing player, and is played over a metric space. Each player simultaneously chooses to deploy at a point in the space; the searching player receiving a payoff of 1 if his opponent lies within a predetermined radius r of his position, the concealing player receiving a payoff of 1 otherwise. The concepts of dominance and equivalence of strategies are examined in the context of this game, before focusing on the more specific case of the game played over a graph. Methods are presented to simplify the analysis of such games, both by means of the iterated elimination of dominated strategies and through consideration of automorphisms of the graph. Lower and upper bounds on the value of the game are presented and optimal mixed strategies are calculated for games played over a particular family of graphs.     

Control of an aircraft landing in windshear

The problem of the feedback control of an aircraft landing in the presence of windshear is considered. The landing process is investigated up to the time when the runway threshold is reached. It is assumed that the bounds on the wind velocity deviations from some nominal values are known, while information about the windshear location and wind velocity distribution in the windshear zone is absent. The methods of differential game theory are employed for the control synthesis.The complete system of aircraft dynamic equations is linearized with respect to the nominal motion. The resulting linear system is decomposed into subsystems describing the vertical (longitudinal) motion and lateral motion. For each subsystem, an, auxiliary antagonistic differential game with fixed terminal time and convex payoff function depending on two components of the state vector is formulated. For the longitudinal motion, these components are the vertical deviation of the aircraft from the glide path and its time derivative; for the lateral motion, these components are the lateral deviation and its time derivative. The first player (pilot) chooses the control variables so as to minimize the payoff function; the interest of the second player (nature) in choosing the wind disturbance is just opposite.The linear differential games are solved on a digital computer with the help of corresponding numerical methods. In particular, the optimal (minimax) strategy is obtained for the first player. The optimal control is specified by means of switch surfaces having a simple structure. The minimax control designed via the auxiliary differential game problems is employed in connection with the complete nonlinear system of dynamical equations.The aircraft flight through the wind downburst zone is simulated, and three different downburst models are used. The aircraft trajectories obtained via the minimax control are essentially better than those obtained by traditional autopilot methods.     

Distributionally robust chance-constrained games: existence and characterization of Nash equilibrium

We consider an n-player finite strategic game. The payoff vector of each player is a random vector whose distribution is not completely known. We assume that the distribution of a random payoff vector of each player belongs to a distributional uncertainty set. We define a distributionally robust chance-constrained game using worst-case chance constraint. We consider two types of distributional uncertainty sets. We show the existence of a mixed strategy Nash equilibrium of a distributionally robust chance-constrained game corresponding to both types of distributional uncertainty sets. For each case, we show a one-to-one correspondence between a Nash equilibrium of a game and a global maximum of a certain mathematical program.     

Game of two cars: Case of variable speed

A stochastic version of Isaacs's (Ref. 1) game of two cars is dealt with here. In this version, the pursuer, owing to thrust and drag forces, has a variable speed, whereas the evader's speed is constant. Also, the pursuer can maneuver as long as his speed is bounded by some lower and upper limits. The probability of interception, corresponding to optimal (saddle-point) feedback strategies, is computed and serves as a reference for evaluating the performance of four different versions of the proportional navigation pursuit law as well as two other strategies.