Download full text of the report (PDF format, 1,08Mb)
While level sets of value function are constructed, the backward procedures based on papers of classics of DG are used. Singular surfaces were studied theoretically (necessary conditions) and in the frames of concrete problems. Nowadays, there are many papers devoted to numerical algorithms for DG solving. However algorithms for global construction and classification of singular surfaces are absent.
In this paper, linear differential games with fixed terminal time and convex payoff function depending on two components of the phase vector are considered. Computer programs for building level sets of the value function (stable bridges or Krasovskii bridges) were worked-out for arbitrary polyhedral constraints P, Q. The algorithm of constructing singular surfaces is elaborated now only for the case of scalar players' controls.
When we speak about singular surfaces, we mean Isaacs' classification. The type of a singularity is determined by behavior of optimal motions near the surface. In the class of games considered (with scalar players' controls), only the following types of singularity can appear: dispersal, equivocal, and switching.
In the base of our method, there is the algorithm for constructing level sets of the value function. Therefore, let us describe it shortly.
After transform to the equivalent coordinates, we have a DG of the second order on the phase variable. Changing the dynamics of the equivalent game by piecewise-constant one, we get the game with simple motion in every interval of time division.
Taking a value c of the payoff function, we build the corresponding
level set of the payoff function. Then, making constructions in the reverse time,
we find consecutively sections Wc(ti) of
the level set Wc of the value function.
So, the level set Wc in general is built as a collection of
sections Wc(ti) on the time grid.
It can be imagined as a “tube” in the three-dimensional space t, y1, y2.
Under this approximation, each time section Wc(ti)
is a convex polygon described by its support function r.
The passage from one section to the next one is based on the operation of
constructing convex hull of a piecewise-linear positively-homogeneous function g.
This function is calculated using support functions of the previous section and polygons, defined by players' controls.
The procedure of convex hull construction is very fast because
we have information about possible places of violation of local convexity.
In this slide, the structure of the function g
graph is shown schematically. Dash lines point out “corrections” of the
function during convexing process. Herewith, this process stops after a few steps.
The piecewise-linearity is defined by the bundle of normals
taken from the following polygons: Wc(ti+1),
which is the previous section, P(ti) and Q(ti),
which are the polygons describing dynamic capabilities of players in the
time interval [ti, ti+1). Normals taken
from the polygon Q(ti) are named “suspicious” because
the local violation of convexity can be only near them.
An elementary step of the convexing procedure consists of
checking three linear inequalities defined by three neighbor vectors from
current bundle and values of the function g on these vectors.
The middle vector is taken from the collection of suspicious ones.
After the check, the middle vector either is removed from the bundle (and its
neighbors become suspicious) or stays and looses the “suspicious” mark.
The algorithm of convex hull construction stops when the collection of
suspicious vectors is empty after some elementary step. There is also a control
for the case when the convex hull does not exist, that is, the tube Wc breaks at some time instant.
In this slide, three tubes for the DG with the oscillator
dynamics are shown. Two outer tubes are cut by a plane. The internal one breaks.
The tube visualization program is elaborated by Averbukh V.L., Yurtaev D.A.,
Zenkov A.I. and Shilov E.A. from the System Support Department of the Institute of Mathematics and Mechanics (Ekaterinburg).
This program gives very convenient interface for manipulation and investigation
of three-dimensional tubes, defined by their sections.
In the base of singular surface construction, there is the algorithm for building singular lines going along concrete level set. Such lines in turn are combined from separate singular points, detected on the level set sections during their computing. When a singular point is found, it is classified.
The algorithm for detection and classification of singular points
on the next time section uses information obtained when the convex hull
of the function g is built. This information
consists of some marks for vectors participated in the convexing process.
Possible combinations of these marks and corresponding singularity types are shown in the table.
In this picture, a numerically calculated level set and singular lines on it are drawn. Here, the DG “material point” is considered. The dispersal line for the second player (green) and the switching line for the first one (blue) come (in reverse time) into the equivocal line (magenta). Due to symmetry of the problem with respect to zero, there is another system of singular lines, located on the invisible side of the level set surface.
The singular lines taken from the tube shown in the previous slide are drawn.
In this picture, the collection of singular lines from different tubes is given. Again, the “material point” dynamics is used. The payoff function describes the following interest of the first player: to lead the motion to the x1-axis as close to zero as possible.
This slide demonstrates how separate singular lines join into singular surfaces.
The equivocal surface is marked by the magenta color, the dispersal one by green.
The gaps near the reverse time t-axis can be filled by
means of more delicate grids in time and value of the parameter c.
The singular surfaces appearing in this problem were investigated analytically in 1983. The numerical results coincide well with the analytical ones.
In particular, the behavior of equivocal lines from different
tubes is very interesting. There is a critical value c* of the parameter c,
near which projections of equivocal lines onto x1, x2
plane look like spirals. The character of these spirals was investigated
analytically. Computed equivocal lines are very similar.
We calculated a lot of examples. The singular surfaces are the most complicated in oscillating systems. Quite naturally, this difficulty is generated by very tricky level sets in these systems. In this picture, the level sets for the “oscillator” DG are shown. Two variants of the sets cut are presented.
Here, the fragment of the middle tube is drawn. One can see that the corner line has a jump. This line is singular. Presence of such peculiarities causes complexity of singular surfaces in general.
In this slide, the singular surfaces for the “oscillator” DG are viewed from the x1-axis.
Here, the same surfaces are observed from the t-axis.
Next example has no any mechanical interpretation. But the level sets are very beautiful: they seem as a drawing-pin.
The dependence of the singular surfaces on parameters of the problem is shown. When the segment Q (the second player control constraint) goes to P (the first player control constraint), the dispersal surface near the t-axis increases. It happens when the second player is "stronger" than the first one: the length of Q is greater than the length of P.
If the situation is vice versa (that is, the first player is stronger), then the closing of P and Q does not change singular surfaces essentially.
