The paper discusses a numerical grid method for solving time-optimal zero-sum di erential games with lifeline. The dynamics of the considered games are supposed to be of a generic non-linear kind. The players' controls are taken from given compact sets of nite-dimensional Euclidean spaces. The objective of the rst player is to reach the target set as fast as possible, with that, avoiding the set called lifeline. The second player counteracts to that: it tries either to guide the system to the lifeline avoiding the target set of the rst player, or if it is impossible, to keep the system away from the target set in nitely, or if it is impossible too, to postpone maximally reaching the target set. In the text, we reference out work about theoretical constructions on existence of the value function of such a game. Also, we set forth the idea of the numerical method. Results of solving some model and practical examples are given.
The following autonomous dynamic system is considered: 0; x 2 Rd; p 2 P; q 2 Q: (1) Here, x is the d-dimensional state vector of the system, p and q are controls of the rst and second players, respectively, which are constrained by compact sets in their nite-dimensional Euclidean spaces. Two sets are given: a compact set T Rd of the full dimension and an open set W such that T W Rd. Denote F = Rd n W and G = W n T . The set T is the target set. The rst player tries to guide the system to it as soon as possible avoiding the set F , which is called lifeline. The second player hinders this, it strives to reach the set F avoiding the set T , of if it is impossible, to keep the system in the set G forever, or if this is impossible too, to postpone reaching the target set T as long as possible.
The following assumptions are supposed to be true:
? Copyright c 2020 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0).
C.1. the function f : Rd P Q 7! Rd is continuous in the totality of variables
and Lipschitzian on x with the constant ; also, the Isaacs' condition [
C.3. the boundary @T and the function f obey the following condition: min max nT (x); f (x; p; q) < 0; p2P q2Q min max nF (x); f (x; p; q) < 0; p2P q2Q t = t x( ; x0) = min t : x(t; x0) 2 T ; t = t x( ; x0) = min t : x(t; x0) 2 F ; which are the rst instants when the trajectory hits the sets T and F , respectively. They equal +1 if the corresponding set is never hit by the trajectory. The payo for the trajectory x( ; x0) is de ned as x( ; x0) = (+1; if t = +1 or t < t ;
t ; otherwise:
The players' strategies are feedback. To de ne a motion of the system
under feedback strategies of the players, we use the formalization suggested by
Krasovskii and Subbotin [
In paper [
In [
H x; Du(x)
u(x) = 0; x 2 G; (5) where H(x; s) = H(x; s) + 1. The function H(x; s) is the Hamiltonian de ned in (2).
Also, it is proved by the authors that problem (4), (5) under assumptions C.1{
C.4 has a continuous generalized solution (in the viscous [
First, note that the payo (3) can have in nite values, what is inconvenient for numerical analysis. Let us consider a new payo
J x( ; x0) = (1 1; exp x( ; x0) ; if
< +1; otherwise; (6) which has its values in the interval [0; 1]. This variable change is well-known as the Kruzhkov's transform. Denote by v(x) the value function for this payo . The suggested method constructs some approximations to the function v(x).
For further numerical construction, we change the continuous time by a discrete one with instants 0, h, 2h, 3h, . . . , and the continuous space by a grid L = (i1k; i2k; : : : ; idk) , ij 2 Z. So, h and k are the steps of time and spatial discretization. The steps of spatial discretization along di erent axes can di er, but this does not a ect the idea of the method. Below, a linear enumeration of the nodes of the grid is assumed: L = flsgs2Z.
Original trajectories x( ; x0) of the system are changed by discrete ones: xn = xn 1 + hf (xn 1; pn 1; qn 1); n = 1; 2; 3; : : : ; where x0 is the initial position, pn 2 P , and qn 2 Q.
The value function w(ls) of the discretized game can be characterized on the basis of the Dynamic Programming Principle: max min wloc ls + hf (ls; p; q) + 1 q2Q p2P 8 >w(ls) = > <
w(ls) = 0; > >:w(ls) = 1; Fs(W ) = 8 > > <
0; >>:1; Here, LT , LG , and LF are the subcollections of the nodes of the grid L, which are located in the sets T , G, and F , respectively. The coe cient = e h. The symbol wloc denotes some local approximation of the function w between the nodes of the grid. The approximation can be piecewise-linear, polylinear, or some other. Each type of the approximation (or, at least, each class of approximations) needs its own proof of convergence of the method.
Let M be the set of in nite vectors with indices in Z. For any in nite vector W , the operator F : M ! R is element-wisely de ned as follows: max min wloc z(ls; p; q); W q2Q p2P + 1 ; ; if ls 2 LG ; if ls 2 LT ; if ls 2 LF : if ls 2 LG ; if ls 2 LT ; if ls 2 LF : Here, z(ls; p; q) = ls + hf (ls; p; q). We have proved that in the case when wloc is the piecewise-linear or polylinear approximation between the grid nodes the operator F is a contraction map and its xed point impose an approximation to the value function v(x).
Note that actually, only values w(ls) for the nodes ls 2 LG are important. The values of w at other nodes are xed and do not need to be stored and/or computed. So, if the set G is bounded, then it can be covered by some nite grid LG, which can be represented in a computer.
So, values at these nodes can be set to some initial states and further repeatedly recomputed by the operator F . After such a recomputation, one gets converging sequences at the nodes, which after a su cient number of iterations approximate well the ideal values w(ls). The latters in their turn by local approximation estimate well the value function v of game (1) with payo (6) if the steps h and k are small enough.
In our work, we do not consider the questions about the rate of convergence
of the algorithm. Hovewer, this algorithm is based on the numerical method from
the work [
We have an own cross-platform realization of this numerical method written using the environment .NetCore 3.0 and language C# of version 6.0 or later. A single-threaded program was written and then, by means of the capabilities of C#, it was made multi-threaded in order to compute faster on multi-core processors. A processor used for computing examples is Intel(R) Core(TM) i78700 CPU @ 3.20GHz with 6 cores and 12 threads.
Two following examples are connected with the classic time-optimal game
\Homicidal chau eur" originally suggested by R. Isaacs in his book [
R x_ e = w2 cos b; y_e = w2 sin b: Here, (xp; yp) and (xe; ye) are the geometric positions of the pursuer and the evader in the plane; is the course angle of the car's velocity; w1 is the magnitude of the linear velocity of the car; the value R=w1 describes the minimal turn radius of the car. The control a 2 [ 1; +1] of the pursuer shows how sharply the car turns: the value a = 1 corresponds to the maximally sharp right turn, the value a = +1 corresponds to the maximally sharp left turn, and a = 0 corresponds to the instantaneous rectilinear motion. The control b 2 [ ; ] of the pedestrian is the instantaneous direction of its velocity, which magnitude is w2.
A strong disadvantage of the original dynamics is their quite high dimension,
namely, 5. However, the dynamics permit [
R w1 + w2 cos b: Here, x, y are the two-dimensional coordinates of a new object, which now is jointly controlled by the players. The rst player (pursuer) tries to guide the system to the set T = (x; y) 2 R2 : (x 0:2)2 + (y 0:3)2 0:0152 keeping the trajectory inside the set W = [ 1:5; 1:5] [ 1; 1:5]. The second one (pedestrian) hinder this.
The parameters of the game taken for a numerical experiment are w1 = 2,
w2 = 0:6, R = 0:2. The example has been taken from [
The graph of the value function in the three-dimensional space x, y, v(x; y) is given in Fig. 1. v(x; y) y x
Now let us present a modi ed version of the problem having the following reduced dynamics:
x_ = y_ =
W y Vp sin W x Vp sin
+ Ve sin ; + Ve cos
Vp;
V_p = W cos : Here, x and y are the coordinates of the object; Vp is the current magnitude of the linear velocity of the car. Now, the pursuer manages two controls. The rst one W is the magnitude of the acceleration of the car, which results in changing both the coordinates x, y. The second control is , which is the angle between the vectors of the acceleration and velocity of the car; it is assumed that =2 =2.
Note that due to chosen constraints for the control the velocity Vp can only grow. There are constraints for its magnitude: Vp 2 [Vmin; Vmax].
The value Ve is the magnitude of the velocity of the pedestrian; is the angle between the velocity vector of the pedestrian and the direction of the y-axis (0 2 ).
The target set is a cylinder T = (x; y; Vp) : x2 + y2 0:32 . For
computations, we take W 1, Ve 0:3, Vmin = 0:5, Vmax = 1:5. The example has been
taken from [
Vp y x