Differential games

A branch of the mathematical theory of control (cf. Automatic control theory), the subject of which is control in conflict situations. The theory of differential games is also related to the general theory of games (cf. Games, theory of). The first studies in this theory appeared in the mid-1950s.

Formulations of problems in the theory of differential games.

One distinguishes between games played by two and those played by several players. Basic results have been obtained for the former case. Such problems may be described by the following scheme. There is a dynamical system in which part of the control is subjected to a player I, while a second part is subjected to a player II. In formulating the task facing player I or player II it is assumed that the selection of controls by this player, which will enable him to attain a certain objective in the face of any previously unknown control by his opponent, may only be based on a certain amount of information about the current state of the system. The theory of differential games also studies control problems under uncertain conditions, when disturbances acting on the system are considered as moves of the opponent. For example, the formulation of the task of player I may be described as follows. It is usually assumed that the motion of the controlled system is defined by a differential equation

(1)

where is the phase vector (state) of the system, and and are the control vectors of the players I and II respectively. One defines the class of strategies of player I, and one also defines, for each strategy , a bundle of trajectories generated by this strategy in the face of all possible control moves of the opponent, and starting at the initial state of the system (1). These concepts are selected so as to correspond to the specified restrictions on the moves of the players and on the nature of the information on the current state of the system facing player I. Trajectories , , of (1) determine the value of a functional (the cost or the pay-off of the game), the value of which player I is attempting to minimize ( may also depend on the realization of , , , by moves by the players). Considering the least favourable realization of the move , the choice of which in the problem is left to the opponent, the quality of the strategies is evaluated by the magnitude

The problem of player I is to find the strategy for which the minimum of the functional is attained (this problem is called the problem of degrees). Occasionally the so-called problem of quality is considered; here the objective is to determine the existence conditions of a strategy corresponding to the inequality , where is some given number.

The problems facing player II, who maximizes the cost of the game, are formulated in a similar manner. The strategies of player II are evaluated by the magnitude

Here, the problem of degree is the selection of the strategy which maximizes the value of the functional , while the problem of quality is to find the conditions under which for some strategy .

If the classes of strategies and in the problems of the players I and II are such that for any pair it is possible to determine at least one trajectory

generated by this pair, one says that these two problems constitute a differential game defined on the class of strategies . If the equality

is satisfied in the differential game, is said to be the value of the differential game.

A typical example of a differential game is the pursuit and evasion game. In this game , where and are the phase vectors of the pursuer and the pursued, respectively, whose motions are described by the equations

In the case most often considered the selection of the controls is restricted by limitations of the type

(2)

where and are certain compact sets. In this game the cost is the time prior to contact, i.e.

where and are vectors composed of the first components of and . Thus, when the distance between and has reached a given value , it is considered that contact has been established. If the players have available information on the current position of the game , i.e. in the positional game of pursuit and evasion, the cost of the game exists.

Formalization of differential games.

For a mathematical formalization of differential games, the concepts discussed above must be rigorously defined. The main subject studied in the theory of differential games are problems in which the position of the game is known to the players, while the moves are restricted as in (2). It is then natural to define the strategies of the players as functions , with values in compact sets and , respectively. It was found, however, that if this approach is adopted, discontinuous strategies often have to be considered, while the moves generated by these strategies cannot be defined in terms of known concepts in the theory of differential games. Below formalizations in which positional strategies are not used are described. Subsequently a formalization of positional differential games is given which comprises discontinuous positional strategies and which is based on a special definition of moves.

Of the many trends in the theory of differential games, the first one to be mentioned is a group of studies (see, for instance, [2], [3]), initiated by a paper by W. Fleming [1] and culminating in [4]. They deal with the approximation of a differential game by multi-step games, where the players select their moves sequentially (in steps) in given periods of time , . Attention is focused on the player which is the first to select his move each time, and announces his choice to his opponent. Depending on whether this player minimizes or maximizes the cost of the game, one distinguishes between majorant and minorant multi-step games. The adoption of this approach is reduced to proving the existence of the value of the differential game, which is here defined as the common value to which the values of the majorant and minorant games converge as the subdivision , , is refined (as the number of steps is increased). However, the construction of positional strategies which would be independent of the discrete time is usually ignored in this approach.

L.S. Pontryagin posed a formulation of control problems in games (see, for instance, [5], [6], [7], [8]) which allows for informational discrimination of the opponent, i.e. it is assumed in formulating the problem of player I (or player II) that this player is aware not only of the game position being realized, but also of the move of his opponent (or ) which will be selected during the interval , where is a small positive number. In this way the course of the game can be conveniently described, which in turn makes it possible to construct a rigorous mathematical theory for a large number of problems involving control under conditions of conflict. However, the introduction of informational discrimination gives player I informational advantage over his opponent as well as imposing restrictions on the behaviour of the latter; in particular, the opponent is unable to formulate his moves according to the principle of reverse connection

(or ). On passing to the interesting treatment of the results obtained under conditions of discrimination of the opponent, it is possible to use information on the move realized during the interval by the opponent rather than on his move during the interval . Such an exchange can be readily justified for systems where

The practical applications of the fundamental theoretical results concerning conditions of discrimination of the opponent are obtained as a result of an appropriate treatment of positional differential games (see the description of a control procedure with a guide, which is given below).

The formalization of positional differential games was developed by N.N. Krasovskii et al. [9]. Here, the subject of study are the positional strategies and , i.e. the functions and , the values of which are comprised in compact sets and respectively. No continuity conditions are assumed with respect to these functions. The moves (, ) generated by the strategy of player I are defined as the limits, uniform on any interval , of sequences of approximating moves , which are absolutely-continuous functions satisfying the equation

(3)

where () are arbitrary measurable functions,

and

The moves (, ) are introduced in a similar manner. If the strategies and the moves are thus defined, the following situation holds.

Alternative 1. Let the equality

(4)

where is the scalar product of the vectors and , be valid for arbitrary vectors and . Then, for any closed sets and , any initial position and any moment , one of the following two statements is always true. Either there exists a strategy such that, for any move , the point falls in at the moment and remains in up to the moment of contact with ; or else there exists a strategy which ensures, for any move , that the point fails to fall in if , or that the phase restriction is violated prior to the point falling in .

The study of many types of differential games for which the existence of the value of the games follows from alternative 1 is reduced to solving such an approach-evasion game. In proposing positional differential games, other definitions of a strategy and of a move are also possible. Thus, in dealing with discontinuous strategies, it may be convenient to replace the discontinuous right-hand side of the differential equations by a multi-valued one and use the apparatus of differential equations in contingencies, or else to approximate discontinuous strategies [10]. However, such attempts may be unsuccessful. Examples are known where the optimal solution of a differential game, obtained by such a formalization, cannot be obtained or even approximated in the framework of other formalizations based on equations in contingencies or on continuous strategies.

If condition (4) is violated, one distinguishes between a formulation of a differential game in the class of strategies of one player and of counter-strategies of the other player, to which corresponds a deterministic solution of the differential game, and a formulation of a differential game in the class of mixed strategies of both players, the content of which is revealed on approximating the mixed strategies by corresponding stochastic control procedures. Counter-strategies are identified with functions , which are Borel functions in the variables and respectively. The moves (, ) are defined as the limits of the approximate moves (3), where

the moves are defined in a similar manner. Mixed strategies , are identified with functions , the values of which are probability measures defined on compact sets and respectively. The moves (, ) are defined as the limits of the approximating moves () satisfying the equation

where

and where is some weakly measurable function. The moves are introduced in a similar manner.

Alternative 2 (alternative 3) is always valid for differential games of the approach-evasion type. It is formulated from alternative 1 by replacing the strategy of one of the players by the corresponding counter-strategy (by replacing, respectively, the strategies and by mixed strategies and ). For differential games reducible to an approach-evasion game and considered within the class of positional strategies of one of the players and counter-strategies of his opponent (in the class of mixed strategies and ), the existence of the value of the differential game is proved without assuming condition (4). Solutions of differential games in these strategy classes may prove to be unstable with respect to informational disturbances. The procedure of control with a guide [9] is introduced to stabilize these solutions. Here, an etalon system (a guide) is considered along with the real system, and the motion of the former system is modelled in a computer and is known to any required degree of accuracy. The control by the player in the real system and the moves of the guide are so formed that the movements of the initial and of the modelled systems mutually follow each other, the guide being kept on some bridge connecting the initial position with the target set. Such a control procedure proves to be stable to experimental errors and to disturbances acting on the system. In modelling the motion of the guide, constructions allowing for discrimination against the opponent can be utilized.

Methods of the theory of differential games.

One method for solving differential games was proposed by R. Isaacs [11]. This approach is related to the method of dynamic programming and is based on the integration of a special partial differential equation, the solution of which determines the value of the game as a function of the initial position of the game. The optimal strategies of player I (or II) are chosen so as to ensure a non-increasing (non-decreasing) value of the game along the movement of the system they generate. However, the value of the game is often a discontinuous function of the position of the game, so that the adoption of this approach involves a special investigation of solutions near the discontinuity surface of the function or of its partial derivatives. A complete study of the singularities of this method and its justification proves to be very difficult, and is possible only in a few isolated cases.

Linear differential games, i.e. the case

where , and are continuous matrices of corresponding dimensions, have been most thoroughly studied. For the linear problems of pursuit and evasion, Krasovskii formulated the rule of extremal aiming [12], which served to solve such problems (with the exception of those involving discrimination of the opponent) subject to a condition of regularity and, in particular, in the case of single-type objects. The elements of this solution may be described as follows. Let be the set of programmed absorption, i.e. the totality of points for which any control corresponds to a control , , such that the pair of these controls converts the system from the state to at the moment . One introduces the function

where is a Euclidean -neighbourhood of the target set . In the domain the quantity is given by the relation:

(5)

where the function can be simply expressed in terms of the supporting functions of the sets , and the convex set [12]. If is convex with respect to the variable (a strong regularity condition) in the domain , the maximum in (5) is attained on a unique vector , selected as the boundary value condition in the maximum principle which determines the selection of the extremal control . The strategy set up in this way ensures that is hit at the moment from any position , where . These constructions are based on the information on the position of the game alone, and can be effectively performed in a computer. Approach problems may also be solved with the aid of programmed construction under weakened regularity conditions.

Linear pursuit problems under different regularity assumptions were studied by E.F. Mishchenko, Pontryagin and B.N. Pshenichnyi [13], [14]; see, in particular, [13] for the solution of a linear pursuit problem under conditions of so-called local convexity, for which the above strong regularity condition applies.

One of the most convenient methods for solving control problems in games is the direct method. In problems in which this method is applicable the control of the player is chosen so that, for any counter-move on the part of the opponent, a deterioration of some auxiliary process, leading to a successful termination of the game, takes place. If the objects are of one type (, , ) and under conditions of discrimination of the opponent, the direct method for solving the pursuit problem determines the choice of the control by player I as a sum of two terms, one of which imitates the control of the opponent, while the other is identical with the solution of the programmed problem of a rapid conversion of the system

into the target set . Pontryagin [5] was the first to describe the direct method for the linear pursuit problem. Subsequently, conditions under which the direct method gives optimal results were found [15]. The direct method was then developed for solving non-linear problems, and for problems with integral restrictions [16], [17]. In all these studies the direct method was employed under conditions of discrimination of the opponent; it was also developed for solving positional games [9].

The evasion problem. The purpose of this problem is to determine conditions under which the object being pursued can evade contact with the pursuer at all . The study of this problem was initiated by Pontryagin and Mishchenko [7], [8] who found conditions of solvability of the linear evasion problem and estimated the least distance between the pursuing and the pursued points. This approach was subsequently extended to other types of evasion problems.

The concept of an alternating integral, proposed by Pontryagin [6], made it possible to describe the structure of the set of initial positions from which it is possible to terminate the initial pursuit game at the given moment of time . An alternating integral is defined as the limit of a recurrent procedure in which the initial set coincides with the target set , while each subsequent set is determined by the preceding one by the operation of programmed absorption, i.e. , where , , and is the step of the recurrent procedure. Pshenichnyi [18] also used programmed absorption as an elementary operation in the investigation of the structure of differential pursuit games; as distinct from the preceding case, here the only requirement was that the duration of transition from points to does not exceed a number , but may, in general, differ from that number. Such a recurrent procedure permits one, in the general case of a non-linear system, to describe the structure of the set of positions from which the pursuit game may be terminated at a given moment of time.

An extremal construction for the solution of positional differential games (see, for example, [9]) has also been proposed. This approach is employed both for solving definite examples and in proving general statements, in particular, the alternatives 1–3 above. For instance, in solving approach problems with in the class of strategies subject to condition (4), according to the extremal construction a set is selected in the space of positions; this set forms a bridge connecting the initial position with the target set , and it is totally comprised in the set . The bridge has the so-called property of -stability, i.e. for any , and there exists a solution of the equation in contingencies

for which either or for a certain . One introduces the strategy extremal to the bridge ; it is defined by the relation

where is a vector for which is the point of nearest to the position . The extremal strategy retains the moves on the bridge and thus supplies the solution of the approach problem.

The fundamental moment in this construction is the determination of suitable stable bridges, after which the construction of extremal strategies does not present any special difficulties. The study of the familiar recurrent procedures for the determination of such bridges is limited by major computational difficulties, so that the study of effective methods for the construction of stable bridges is important. The direct method is one of them. Another one is the construction of stable bridges in the form of regular programmed absorption sets. In the non-linear case programmed absorption is defined with the aid of special control measures (see, e.g., [9]). If the programmed absorption is regular, solving conflicting control problems may be reduced to computer-realizable algorithms.

Main research trends in differential games.

The results exposed above mainly concerned differential games in which the control could be described by the ordinary differential equation (1) with control vectors subject to the restriction (2). Similar results were obtained for game problems in control in which the moves are described by ordinary differential equations with deviating arguments (cf. Differential equations, ordinary, with distributed arguments), and also for problems involving integral restrictions on the controls of the players [17].

In the study of the structure of differential games, problems of conflicting control, where the moves are determined by a generalized dynamical system (see, for example, [19], [20]) are of interest. A study was made of differential games in the class of quasi-strategies, which yield the control of the player in response to the control by his opponent; iteration procedures have also been proposed to determine the value function and stable bridges [21].

Not only differential games with two players, but also -person differential games are studied. In the formulation of -person differential games it is usually assumed that, in choosing his control, each attempts to minimize a certain functional defined on the trajectories of the controlled system. The players may only employ information about the current positions of the game. For instance, a typical problems is to determine the conditions under which such games have a Nash equilibrium point in the given class of player strategies.

Game problems of control with incomplete information are an important part of the theory of differential games. It is assumed in such problems that the lack of completeness of the information consists in the ignorance of some of the components of the phase vector or in the measurement of the current position of the game with a certain lag, or else in an inaccurate determination of the location of the phase point ; a case is possible where the permissible range is the only indication of the measurement error, and also a case in which some statistical description of this error is given.

References

[1]	W.H. Flemming, "A note on differential games of prescribed duration" , Contributions to the theory of games , 3 , Princeton Univ. Press (1957) pp. 407–412
[2]	P. Varaiya, G. Lin Jiguan, "Existence of saddle points in differential games" SIAM J. Contr. , 7 : 1 (1969) pp. 141–157 Zbl 0192.52402
[3]	N.N. Petrov, "On the existence of a pursuit game" Soviet Math. Dokl. , 11 (1970) pp. 292–294 Dokl. Akad. Nauk SSSR , 190 : 6 (1970) pp. 1289–1291 Zbl 0205.16204
[4]	A. Friedman, "Existence of value and of saddle points for differential games of survival" J. Differential Equations , 7 : 1 (1970) pp. 111–125 MR0253759 Zbl 0253.90076 Zbl 0226.90056
[5]	L.S. Pontryagin, "Linear differential games. 1" Soviet Math. Dokl. , 8 (1967) pp. 796–771 Dokl. Akad. Nauk SSSR , 174 : 6 (1967) pp. 1278–1280 MR0979315 MR0979314 MR0865932 MR0760516 MR0759966 MR0489974
[6]	L.S. Pontryagin, "Linear differential games. 2" Soviet Math. Dokl. , 8 (1967) pp. 910–912 Dokl. Akad. Nauk SSSR , 175 : 4 pp. 764–766 MR0979315 MR0979314 MR0865932 MR0760516 MR0759966 MR0489974
[7]	L.S. Pontryagin, "A linear differential evasion game" Proc. Steklov Inst. Math. , 112 (1973) pp. 27–60 Trudy Mat. Inst. Steklov. , 112 (1971) pp. 30–63 Zbl 0261.90081
[8]	L.S. Pontryagin, E.F. Mishchenko, "Deviation from coincidence in linear differential games" Differential Equations , 7 (1971) pp. 335–342 Differentsial. Uravn. , 7 : 3 (1971) pp. 436–445
[9]	N.N. Krasovaskii, A.I. Subbotin, "Game-theoretical control problems" , Springer (1988) (Translated from Russian) MR918771
[10]	V.F. Krotov, V.I. Gurman, "Methods and problems of optimal control" , Moscow (1973) (In Russian) MR0417883
[11]	R. Isaacs, "Differential games" , Wiley (1965) MR0210469 Zbl 0125.38001
[12]	N.N. Krasovskii, "Game problems on control of movements" , Moscow (1970) (In Russian)
[13]	E.F. Mishchenko, L.S. Pontryagin, "Linear differential games" Soviet Math. Dokl. , 8 (1967) pp. 585–588 Dokl. Akad. Nauk SSSR , 174 : 1 (1967) pp. 27–29 MR0979315 MR0865932 MR0760516 MR0759966 Zbl 0189.46602
[14]	B.N. Pshenichnyi, "On the problem of pursuit" Kibernetika , 6 (1967) pp. 54–64 (In Russian)
[15]	P.B. Gusyatnikov, M.S. Nikol'skii, Teor. Optimal Reshenii - Tr. Sem. Protsessy Optimal. Upravleniya VI Sektsiya , 3 (1969) pp. 17–25 (In Russian)
[16]	A.A. Chikrii, "Optimality of pursuit games" Soviet Math. Dokl. , 10 (1969) pp. 103–106 Dokl. Akad. Nauk SSSR , 184 : 3 (1969) pp. 518–521
[17]	M.S. Nikol'skii, "The direct method in linear differential games with common integral restrictions" Differential Equations , 8 (1972) pp. 729–734 Differentsial. Uravn. , 8 : 6 pp. 964–971 Zbl 0288.90096
[18]	B.N. Pshenichnyi, "The structure of differential games" Soviet Math. Dokl. , 10 (1969) pp. 70–72 Dokl. Akad. Nauk SSSR , 184 : 2 (1969) pp. 285–287
[19]	C. Ryll-Nardzewski, "The theory of pursuit and evasion" M. Dresher (ed.) et al. (ed.) , Advances in game theory , Ann. Math. Studies , Princeton Univ. Press (1964) pp. 113–126
[20]	E. Roxin, "Axiomatic approach in differential games" J. Optimiz. Theory Appl. , 3 : 3 (1969) pp. 153–163 MR0243846 Zbl 0175.10504
[21]	A.G. Chentsov, "On a game problem of converging at a given instant of time" Math. USSR-Sb. , 28 (1971) pp. 353–376 Mat. Sb. , 99 : 3 (1976) pp. 394–420 Zbl 0371.90136

References

[a1]	T. Basar, G.J. Olsder, "Dynamic noncooperative game theory" , Acad. Press (1982) MR0649247 Zbl 0479.90085