Download full text of the report (PDF format, 2375 KB)
Our paper is a collection of four examples from the differential game theory. We consider linear differential games with fixed terminal time. For such games, a level set of the value function is a tube in the game space "phase vector × time". If a game is regular, then every level set tube is smooth. Non-smoothness and some other geometrical features of the tubes can tell us about difficulties of the solution of the game.
Let us imagine a problem where a rocket pursues another one. At the beginning, their nominal velocities and courses are such that a collision is forecasted. The velocities are quite large (and the nominal relative velocity is very large also). The pursuer and evader controls are not too strong to change the trajectories sufficiently. They can only correct the trajectories slightly. The pursuer minimizes the miss distance, the evader maximizes it. It is reasonable to measure the miss distance not as the shortest distance between the objects during the homing process, but as the distance between projections of the geometrical states of the objects at the instant of the nominal collision into the plane orthogonal to the direction of the nominal relative velocity. Let take axes in this plane as follows: the first axis is defined by the vectors of the nominal velocities (that is the first axis is situated in the plane of the nominal velocities vectors), and the second one is orthogonal to it.
We consider the game from the point of view of the first player (the pursuer). So, one can take into account the inertia of the servo-mechanisms of the pursuer in the statement of the problem. About the second player (the evader) it is supposed that its control signals are realized instantly.
It is natural to linearize the dynamics of the objects along the nominal motions.
Thus, we have a linear differential game with fixed terminal time.
An investigation of such linearized problem was made in the works of J.Shinar and his collaborators. In the Figure, the nominal motions and the forecasted collision point are shown. It is supposed that the accelerations of both vehicles are bounded and orthogonal to the respective nominal velocity vectors. The corresponding dynamics vectograms are circular.
We consider planar motions in the plane orthogonal to the initial nominal relative velocity. When projecting the original circular control constraints into this plane, the new constraints become elliptical.
In the slide, the linearized dynamics is shown. The phase vector is six-dimensional (two geometrical difference coordinates, two difference velocities, two difference accelerations). The constant kP describes the inertia of servo-mechanisms of the pursuer. The miss is computed as the distance from the origin to the difference geometrical state at the terminal time.
In the papers of J.Shinar and his collaborators, the results of analytical investigations of this linear differential game were presented. The relations describing the level sets of the value function were obtained. It was established that the value function is not differentiable. Singular surfaces were analyzed. The system of singular surfaces for this problem contains dispersal, equivocal and focal pieces.
All computations were made by means of the equivalent coordinates of the dimension two. The transformation from the original six-dimensional vector to the equivalent one is provided by the standard variable change which involves the fundamental Cauchy matrix for the system dz/dt = A(t)z (without the controls). The game space is three-dimensional: two equivalent coordinates and the time.
After the transformation to the equivalent coordinates, the dynamics of the game has the form shown in the slide. The terminal instant and control constraints are the same as in the original game. The payoff function is the norm of the equivalent phase vector x at the terminal instant.
Further, some results numerically obtained for this game are presented. Standard programs for solving differential games developed in the Institute of Mathematics and Mechanics (Ekaterinburg, Russia) were used. Numerical data for the example are shown in the slide.
To understand the structure of level sets of the value function, it is useful to consider tubes of players vectograms. The tube of vectograms of the first player is the set P(t)=X1,4(T,t)BP enrolled in time. In the same way, the tube of vectograms of the second player is understood.
In the Figure, the first player's tube of vectograms is shown by red color, and the second player's one is green. The latter is made transparent. Contours of some t-sections are drawn on it. The symbol t denotes the backward time.
In this example, the second player's tube of vectograms is an elliptical cone. The first player's tube also has elliptical t-sections which grow non-linearly. For small values of the backward time t, the second player has full advantage: t-sections of his tube include corresponding t-sections of the tube of the second player. After some instant, the first player gets advantage in vertical direction and in directions close to the vertical one. With increasing the backward time, the first player takes the full advantage.
In this slide, a level set of the value function is shown. It corresponds to a value c* of the payoff function. This level set is infinite in time. It has a narrow throat. After the throat, the level set enlarges with growing the backward time.
The considered value c* is the critical one: for less values of c, corresponding level sets are finite in time. With small decreasing of the parameter c, level set breaks near the throat.
In the picture, the changing of t-section orientation can be seen: before the throat they are oriented horizontally, after the throat they become oriented vertically. Namely, these facts give difficulties to the solution of the considered differential game. In this situation, the numerical results show adequately the structure of level sets near the throat and correspond well to the analytical results only if very precise computations are used.
This slide contains a zoomed view of the narrow throat. Contours of some t-sections are shown.
These two slides show the critical level set with close ones. The slide 8 contains the critical level set (yellow transparent) and a set corresponding to a bit less value of the parameter c (red). The slide 9 demonstrates the critical level set (red) with a set corresponding to a bit greater value of the parameter c (yellow transparent).
In the theory of differential games, there is a
well-known example "the boy and the crocodile". This
game has also a narrow throat for critical tube. But t-sections
are circular in the game "the boy and the crocodile".
The J.Shinar's example is more complicated.
The following question is very natural: how typical is the situation of presence of throats, and how many throats can a level set have?
With this object in mind, the authors have turned to the class of differential games known in Russian literature on differential games as the "L.S.Pontryagin's generalized test example".
The slide shows the dynamics of the L.S.Pontryagin's generalized test example. The case is considered when the objects move in a plane, that is the x and y are two-dimensional vectors. The terminal time of the game is fixed. The payoff function is defined as the geometrical distance between the objects at the terminal instant. The first player minimizes the payoff function, the second one maximizes it.
Here is a list of authors who investigated the L.S.Pontryagin's generalized test example or used it as a check one for new theoretical methods. Very often, the time of termination is not fixed. The game with fixed terminal time appears in this case as a basis for the solution.
As a rule, the constraints P and Q were taken circular. We consider the case when the constraints P and Q are ellipses.
In the model example investigated by J.Shinar, the evader governs a material point with inertialess control, and the pursuer has inertial control circuit. The dynamics can be rewritten as it is shown at the bottom of the slide. So, this problem is a particular case of the L.S.Pontryagin's test example.
With introducing new variables, the dynamics of the test example can be presented in the standard form.
The payoff function depends only on two components of the phase vector at the terminal instant. So, by means of the well-known change of variables which involves two rows of the fundamental Cauchy matrix, one can pass to the equivalent game. The phase vector of the equivalent game is two-dimensional.
Three following slides describe shortly the idea of the backward computational procedure for constructing a collection of t-sections of a level set of the value function.
This slide explains the scheme of the backward procedure. The algorithm starts with the payoff function level set (Lebesgue set) corresponding to a number c. Then a collection of t-sections of the value function level set is constructed for a given time grid. This level set corresponds to the chosen number c. In general, this is the method of dynamical programming in application to differential games.
For numerical procedure, some approximations are made. The dynamics of the equivalent games is changed by a piecewise-constant one. The constraints P and Q are substituted by convex polygons. The payoff function j is approximated by a function which has convex polygonal level sets.
The transformation from one section to the next one is provided by a specialized procedure. In its basis, it has an algorithm for constructing convex hull of a positively homogenious piecewise-linear function. The formula for computation of this function is shown in the slide. Here, D is the step of the time grid.
Further, three example of differential games
are presented. Some their level sets have narrow throats. It was
not too easy to find these examples. But authors are sure that
the presence of such throats is quite typical.
The dynamics of the first example is written in this slide. The first player governs an inertial point in the plane. The second object is a two-dimensional mathematical pendulum. Both objects have friction proportional to the velocity. The constraints on the player controls are taken as ellipses.
In this slide, two views of the tubes of vectograms for both players are presented. The green tube belongs to the first player, the red one is of the second.
Since the second player dynamics is oscillating, the advantage changes in time. At the beginning of the backward time, the second player has full advantage, but for sufficiently large values of the backward time t, the first player gets the advantage.
This slide shows the level set for c = 2.451. One can see the varying orientation of t-sections of the set. At the beginning, they are have vertically elongated orientation. Further, t-sections become horizontally elongated. This change is determined by delicate interaction of the vectograms.
This example was computed in the interval t Î [0,20]. The time step D = 0.05. The level set of the payoff function j was 100-gon. The ellipses P and Q were approximated by polygons with 100 vertices.
In this picture, a zoomed view of the tube is drawn. It can be seen that the level set degenerates almost to a point.
Here, the second example is presented. In this case, both players govern oscillating objects. It is noticeable that the constraints on the player controls are taken as coinciding ellipses.
Despite the ellipses of the constraints coincide, the computations are not trivial, because there is no uniformity of the players vectograms and level sets of the payoff function.
These slides demonstrate the tubes of vectograms for the second example. The green tube belongs to the first player, the yellow one is of the second. In the 24th slide, the latter is transparent.
This slide gives the general view of the level set for c = 1.2. This level set has two narrow throats. They correspond to the instants t1 = 5.65 and t2 = 8.50.
This example was computed in the interval t Î [0,20]. The time step D = 0.05. Near the throats, 10 times less step was used: D = 0.005. The level set of the payoff function j was approximated by a regular 100-gon. The ellipses P and Q were approximated by polygons with 100 vertices.
Here, the dynamics of the third example is shown. Again, two oscillators with elliptical constraints.
In this figure, the tubes of the players vectograms are drawn.
In this slide, the level set having three narrow throats is demonstrated. The level set corresponds to c = 0.397.
Here, the tubes of vectograms are put on the level set. All colors correspond to ones used before: the blue tube is the tube of the first player vectograms, the yellow tube is of the second player vectograms, and the green one is the level set. The tubes of vectograms are transparent.
Variation of the level set in time is clearly connected to the character of this or that player advantage. When the second player has full advantage (when the yellow tube contains the blue one completely), the level set contracts. Vice versa, when the first player gets full advantage, the level set enlarges. If no player has full advantage (that is both players have partial advantage), the situation with the level set changing can be more complicated: growth to some directions and decreasing to others could take place.
S.S. Kumkov, V.S. Patsko