Differential Games on Minmax of the Positional Quality Index

Abstract

The paper goes back to the research of N. N. Krasovskii devoted to two-person zero-sum positional differential games on minmax of non-terminal quality indices, which evaluate a set of system’s states realized at given times. The first part of the paper gives a survey of the results concerning existence of the value and saddle point in such differential games. A special attention is paid to the case when the quality index has a certain positional structure. The second part of the paper overviews a method for constructing the value and optimal strategies in the case when the dynamical system is linear in the state vector, and the quality index has the appropriate convexity properties. The method is based on the recurrent procedure of constructing the upper convex hulls of certain auxiliary functions. To illustrate that this method can be numerically realized on modern computers, a model example is considered.

1 Introduction

The paper goes back to the research of N. N. Krasovskii that concerns two-person zero-sum differential games on minmax of non-terminal quality indices. Typical examples of quality indices under consideration are the integral deviation or the maximal deviation of a system’s motion from a given trajectory. Also, there are the discrete variants of these indices, the sum or the maximum of deviations of a system’s motion at given times from given target states. For such differential games, based on the appropriate notion of feedback strategies, N. N. Krasovskii developed the positional approach (see, e.g., [17, 19,20,21, 24]). One of the key questions was to find out what information about the game process is sufficient for constructing optimal feedback strategies, which constitute the saddle point of the game. This information was called the sufficient informational image (see, e.g., [17]). The theory and simple examples showed that, in general, for the case of non-terminal quality indices, the sufficient informational image must include the whole history of a system’s motion. On the other hand, in many cases, e.g., for the typical quality indices mentioned above, it turned out that the sufficient informational image includes only the current system’s state (the current position of the system). In this connection, as a generalization of the typical examples, the notion of the positional quality index was introduced [14, 17]. It was proved that, if the quality index is positional, then, by using the appropriate modification of the extremal shift method [17, 21], one can construct the optimal feedback strategies that depend only on the position of the system. A review of the mentioned results constitutes the first part of the paper.

The second part of the paper is devoted to the problem of computing the value and optimal strategies in the linear-convex case when the dynamical system is described by linear in the state vector differential equations, and the quality index has the appropriate convexity properties. Summarizing the results of [4, 6, 8, 11, 17, 22, 28], we overview the so-called upper convex hulls method. This method is based on the recurrent procedure of constructing the upper convex hulls of certain auxiliary functions. It is conceptually related to the stochastic program synthesis [17, 18, 20, 21] and closely connected with the backward maxmin constructions known in differential games (see, e.g., [1, 2, 10, 24, 32, 33]). The upper convex hulls method (a) gives representative formulas for the value function and players’ optimal strategies (we compute only the parameters of these formulas); (b) can be applied to the differential games in the classes of pure, mixed and counter-strategies; (c) is convenient for solving differential games with non-terminal quality indices that evaluate a set of system’s states realized at given times (especially in the case of the positional quality indices); (d) allows to take into account possible players’ control delays; (e) can be applied to the differential games with both geometric and integral constraints on the players’ control actions. On the other hand, this method can be applied only in the linear-convex case, and its numerical realization is rather complicated. (It requires multiple constructions of the upper convex hulls of functions.)

The upper convex hulls method was proposed in [16, 23] for the differential games with terminal–integral quality indices and geometric constraints on the players’ control actions. In [17, 22], this method was developed for a number of typical non-terminal quality indices that evaluate a set of states of the system realized at given times. For the positional quality indices, the most general case of the upper convex hulls method was described in [28, 29]. The stability of this method with respect to computational and informational errors was proved in [8]. An algorithm of its numerical realization was given in [6, 11]. In [25, 26], the method was developed for the differential games with integral-quadratic constraints on the players’ control actions. The case when control actions are subject to both geometric and integral constraints was considered in [13, 27]. The applicability of the upper convex hulls method for the differential games in the classes of mixed strategies was shown in [12, 16, 17]. The case of counter-strategies was considered in [4]. In [3, 5], the method was extended to dynamical systems with players’ control delays.

The paper is organized as follows. In Sects. 2 and 3, we describe a dynamical system and a quality index for which the differential game is considered. In Sect. 4, we give examples that show the typical features of the problem. In Sect. 5, we present the mathematical formalization of the differential game and the existence results for the game value and saddle point. Section 6 is devoted to the case when the quality index is positional. In Sect. 7, we describe the upper convex hulls method for solving the considered differential game in the linear-convex case. In Sect. 8, we consider an example. The conclusion is given in Sect. 9.

2 Dynamical System

We consider a dynamical system described by the differential equation

$$\begin{aligned} \begin{aligned} \dot{x}(t)&= f(t, x(t), u(t), v(t)), \quad t_0 \le t \le \vartheta , \\ x(t)&\in \mathbb {R}^n, \quad u(t) \in P \subset \mathbb {R}^r, \quad v(t) \in Q \subset \mathbb {R}^s, \end{aligned} \end{aligned}$$

(1)

under the initial condition

$$\begin{aligned} x(t_0) = x_0. \end{aligned}$$

(2)

Here t is the current time; x(t) is the state vector at the time t;  $\dot{x}(t) = \hbox {d}x(t) / \hbox {d}t;$u(t) and v(t) are the current control actions of the first and second players, respectively; $t_0$ and $\vartheta$ are the initial and terminal times; P and Q are compact sets of possible control actions of the players; $x_0 \in \mathbb {R}^n$ is the initial value of the state vector.

It is assumed that the right-hand side of Eq. (1) satisfies the following conditions:

(A.1):

The function $f: [t_0, \vartheta ] \times \mathbb {R}^n \times P \times Q \rightarrow \mathbb {R}^n$ is continuous.

(A.2):

There exists a constant $c > 0$ such that

$$\begin{aligned} \Vert f(t, x, u, v)\Vert \le (1 + \Vert x\Vert )c, \quad t \in [t_0, \vartheta ], \quad x \in \mathbb {R}^n, \quad u \in P, \quad v \in Q. \end{aligned}$$

(A.3):

For any compact set $D \subset \mathbb {R}^n,$ there exists a constant $\lambda > 0$ such that

$$\begin{aligned} \begin{aligned}&\Vert f(t, x, u, v) - f(t, y, u, v)\Vert \le \lambda \Vert x - y\Vert , \\&t \in [t_0, \vartheta ], \quad x, y \in D, \quad u \in P, \quad v \in Q. \end{aligned} \end{aligned}$$

Here and below the symbol $\Vert \cdot \Vert$ denotes the Euclidian norm of a vector.

Functions $[t_0, \vartheta ) \ni t \mapsto u(t) \in P$ and $[t_0, \vartheta ) \ni t \mapsto v(t) \in Q$ are called control realizations of the players. A control realization is admissible if it is Borel measurable. Admissible control realizations of the first and second players are denoted by $u[t_0 [\cdot ] \vartheta )$ and $v[t_0 [\cdot ] \vartheta ),$ respectively. A function $[t_0, \vartheta ] \ni t \mapsto x(t) \in \mathbb {R}^n$ is called a motion realization of system (1), or briefly a motion of the system, if it is absolutely continuous, satisfies initial condition (2) and, together with $u[t_0 [\cdot ] \vartheta )$ and $v[t_0 [\cdot ] \vartheta ),$ satisfies Eq. (1) for almost all $t \in [t_0, \vartheta ].$ Due to conditions (A.1), (A.2), such a motion exists for any admissible control realizations $u[t_0 [\cdot ] \vartheta )$ and $v[t_0 [\cdot ] \vartheta ).$ Due to condition (A.3), it is unique. This motion is denoted by $x[t_0 [\cdot ] \vartheta ].$ The triple $\{x[t_0[\cdot ]\vartheta ], u[t_0[\cdot ]\vartheta ), v[t_0[\cdot ]\vartheta )\}$ is called a realization of the game process.

3 Quality Index

Quality of a game process realization $\{x[t_0[\cdot ]\vartheta ], u[t_0[\cdot ]\vartheta ), v[t_0[\cdot ]\vartheta )\}$ is evaluated by the index

$$\begin{aligned} \gamma = \mu (x[t_0[\cdot ]\vartheta ]) + \int _{t_0}^{\vartheta } h(t, x(t), u(t), v(t)) \hbox {d}t. \end{aligned}$$

(3)

It is assumed that the following conditions are valid:

(B.1):

The function $\mu : C([t_0, \vartheta ], \mathbb {R}^n) \rightarrow \mathbb {R}$ is continuous.

(B.2):

The function $h: [t_0, \vartheta ] \times \mathbb {R}^n \times P \times Q \rightarrow \mathbb {R}$ is continuous.

(B.3):

There exists a constant $c > 0$ such that

$$\begin{aligned} |h(t, x, u, v)| \le (1 + \Vert x\Vert )c, \quad t \in [t_0, \vartheta ], \quad x \in \mathbb {R}^n, \quad u \in P, \quad v \in Q. \end{aligned}$$

(B.4):

For any compact set $D \subset \mathbb {R}^n,$ there exists a constant $\lambda > 0$ such that

$$\begin{aligned} \begin{array}{c} |h(t, x, u, v) - h(t, y, u, v)| \le \lambda \Vert x - y\Vert , \\ t \in [t_0, \vartheta ], \quad x, y \in D, \quad u \in P, \quad v \in Q. \end{array} \end{aligned}$$

Here and below $C([t_0,\vartheta ], \mathbb {R}^n)$ denotes the space of continuous functions from $[t_0, \vartheta ]$ to $\mathbb {R}^n$ equipped with the uniform norm.

In the differential game under consideration, the first player aims to minimize $\gamma ,$ and the second player aims to maximize $\gamma .$

4 Typical Features

Before giving the further mathematical formulation of the differential game, let us consider examples illustrating the features that should be taken into account.

The first example shows that discontinuous feedback control strategies of the players are useful.

Example 1

Let a differential game be described by the dynamical system

$$\begin{aligned} \dot{x}(t) = u(t) - v(t), \quad 0 \le t \le 1, \quad x(t) \in \mathbb {R}, \quad |u(t)| \le 1, \quad |v(t)| \le 1, \end{aligned}$$

(4)

the initial condition

$$\begin{aligned} x(0) = 0, \end{aligned}$$

and the quality index

$$\begin{aligned} \gamma = |x(1)|. \end{aligned}$$

Let us consider the problem from the point of view of the first player. Suppose that the first player uses only the program (open-loop) strategies, i.e., the first player chooses the whole control realization $u[t_0[\cdot ]\vartheta )$ at the initial time $t_0.$ Then, it is easy to show that the first player cannot guarantee the value of the quality index less than $\gamma = 1.$ On the other hand, if the first player forms a realization $u[t_0[\cdot ]\vartheta )$ during the game process on the basis of the feedback (closed-loop) strategy $U^0(x) = - {\text {sign}}(x)$ by setting $u(t) = - {\text {sign}}(x(t)),$ then the first player guarantees the optimal value $\gamma = 0$ for any control actions of the second player. Note that the strategy $U^0(x)$ is discontinuous. If we simply substitute this strategy in system (4), we obtain the closed-loop system with the discontinuous in x right-hand side. So, the question arises how to define the control realization and the system’s motion that correspond to this strategy (see Sect. 5 below).

The second example shows that feedback strategies with memory of motion history can be required because of the structure of quality index (3).

Example 2

Let us consider a control problem for the dynamical system

$$\begin{aligned} \dot{x}(t) = u(t), \quad 0 \le t \le 3, \quad x(t) \in \mathbb {R}, \quad |u(t)| \le 1, \end{aligned}$$

the initial condition

$$\begin{aligned} x(0) = 0, \end{aligned}$$

and the quality index

$$\begin{aligned} \gamma = |x(3) - x(1)|. \end{aligned}$$

(5)

Suppose that, at the time $t = 2,$ we have $x(2) = 0.$ If we know the realized value x(1),  then, setting $u(t) = x(1)$ for $t \in [2, 3],$ we obtain the minimal value $\gamma = 0.$ Note that this control is admissible since, in the considered problem, we automatically have $|x(1)| \le 1.$ But if the value x(1) is unknown, then it is not clear how to choose the control actions to ensure this value $\gamma = 0.$ Thus, if we apply a feedback control, then, for $t \in (1, 3],$ the additional information about the past value x(1) should be used in order to obtain the optimal result.

The third example shows that the information about the current control actions of the opponent can be useful.

Example 3

Let a differential game be described by the dynamical system

$$\begin{aligned} \dot{x}(t) = u(t) v(t), \ \ 0 \le t \le 1, \ \ x(t) \in \mathbb {R}, \ \ u(t) \in \{-1, 1\}, \ \ v(t) \in \{-1, 1\}, \end{aligned}$$

the initial condition

$$\begin{aligned} x(0) = 0, \end{aligned}$$

and the quality index

$$\begin{aligned} \gamma = x(1). \end{aligned}$$

Let us consider the problem from the point of view of the second player. Suppose that, at the current time $t \in [0, 1],$ the second player cannot use the information about the current control action u(t) of the first player. Then, since the second player may face with the counteractions of the first player $u(t) = - v(t),$ the best value of the quality index that the second player can guarantee is $\gamma = - 1.$ But if the information about u(t) is available, then, setting $v(t) = u(t),$ the second player guarantees the maximal value $\gamma = 1$.

5 Differential Game

5.1 Control Strategies

Motivated by the examples from Sect. 4, within the positional approach [17, 19, 21], we consider the following classes of strategies in the differential game (1)–(3). A strategy of the first player is a function

$$\begin{aligned} \begin{aligned} U&= U(t, x[t_0[\cdot ]t], \varepsilon ) \in P, \\ t&\in [t_0, \vartheta ], \quad x[t_0[\cdot ]t] \in C([t_0, t], \mathbb {R}^n), \quad \varepsilon > 0, \end{aligned} \end{aligned}$$

(6)

and a strategy of the second player is a function

$$\begin{aligned} \begin{aligned} V&= V(t, x[t_0[\cdot ]t], u, \varepsilon ) \in Q, \\ t&\in [t_0, \vartheta ], \quad x[t_0[\cdot ]t] \in C([t_0, t], \mathbb {R}^n), \quad u \in P, \quad \varepsilon > 0, \end{aligned} \end{aligned}$$

(7)

that is Borel measurable in u for any t,  $x[t_0[\cdot ]t]$ and $\varepsilon .$ Here we denote by $x[t_0[\cdot ]t]$ a function $[t_0, t] \ni t \mapsto x(t) \in \mathbb {R}^n,$ which is treated as a motion history realized up to the time t,  and $\varepsilon > 0$ is an auxiliary parameter related to the accuracy of achieving of the guaranteed result of the corresponding strategy (see (11) and (15) below). Following the terminology of [19, 21, 24], such strategies U and V are called strategies with memory of motion history, or briefly strategies with memory. Moreover, the strategies of type (7) are often called counter-strategies to underline their dependence on u. Let us stress that it is not supposed that U and V have any smoothness properties in t and $x[t_0[\cdot ]t].$ Therefore, in order to describe how these strategies define the corresponding control realizations and system’s motion, the technique of the so-called constructive motions [24] is applied, and discrete-in-time feedback control schemes are considered [17, 19, 21].

5.2 Statement of the Problem for the First Player

Let the first player choose a strategy U of type (6). Let a value of the parameter $\varepsilon > 0$ be chosen, and, for the time interval $[t_0, \vartheta ],$ a partition

$$\begin{aligned} \varDelta _\delta = \big \{ \tau _j: \ \tau _1 = t_0, \ 0 < \tau _{j+1} - \tau _j \le \delta , \ j = \overline{1,k}, \ \tau _{k+1} = \vartheta \big \} \end{aligned}$$

(8)

with the diameter not greater than $\delta > 0$ be fixed. The triple $\{U, \varepsilon , \varDelta _\delta \}$ is called a control law of the first player. This law forms a piecewise constant (and, therefore, admissible) control realization $u[t_0[\cdot ]\vartheta )$ by the following step-by-step rule:

$$\begin{aligned} u(t) = U(\tau _j, x[t_0[\cdot ]\tau _j], \varepsilon ), \quad t \in [\tau _j, \tau _{j+1}), \quad j = \overline{1, k}, \end{aligned}$$

(9)

where $x[t_0[\cdot ]\tau _j]$ is the motion history realized up to the time $\tau _j.$

Considering the problem from the point of view of the first player, we suppose that the control law $\{U, \varepsilon , \varDelta _\delta \}$ may face with any admissible control realization $v[t_0[\cdot ]\vartheta )$ of the second player. Therefore, the value of the guaranteed result of the control law $\{U, \varepsilon , \varDelta _\delta \}$ is defined by

$$\begin{aligned} \varGamma _u (t_0, x_0; U, \varepsilon , \varDelta _\delta ) = \sup _{v[t_0[\cdot ]\vartheta )} \gamma , \end{aligned}$$

(10)

where $\gamma$ is the value of quality index (3) that corresponds to the game process realization $\{x[t_0[\cdot ]\vartheta ], u[t_0[\cdot ]\vartheta ), v[t_0[\cdot ]\vartheta )\}$ that is uniquely determined by the control law $\{U, \varepsilon , \varDelta _\delta \}$ and the realization $v[t_0[\cdot ]\vartheta ).$

Further, we define the guaranteed result of the strategy U by

$$\begin{aligned} \varGamma _u (t_0, x_0; U) = \limsup _{\varepsilon \downarrow 0} \, \lim _{\delta \downarrow 0} \, \sup _{\varDelta _\delta } \varGamma _u (t_0, x_0; U, \varepsilon , \varDelta _\delta ), \end{aligned}$$

(11)

assuming that the values $\varepsilon > 0$ and $\delta > 0$ can be as small as needed, but a partition $\varDelta _\delta$ can be arbitrary. Note that the limit in $\delta$ exists since the expression under the limit is bounded and monotone in $\delta .$

Finally, the optimal guaranteed result of the first player is

$$\begin{aligned} \varGamma _u^0(t_0, x_0) = \inf _{U} \varGamma _u (t_0, x_0; U). \end{aligned}$$

(12)

A strategy of the first player $U^0$ is called optimal if

$$\begin{aligned} \varGamma _u (t_0, x_0; U^0) = \varGamma _u^0(t_0, x_0). \end{aligned}$$

According to definition (11), it means that, for any number $\zeta > 0,$ there exist a number $\varepsilon ^0 > 0$ and a function $\delta ^0(\varepsilon ) > 0,$$\varepsilon \in (0, \varepsilon ^0],$ such that, for any value of the parameter $\varepsilon \in (0, \varepsilon ^0]$ and any partition $\varDelta _\delta$ with $\delta \le \delta ^0(\varepsilon ),$ the following inequality is valid:

$$\begin{aligned} \varGamma _u(t_0, x_0; U^0, \varepsilon , \varDelta _\delta ) \le \varGamma _u^0(t_0, x_0) + \zeta . \end{aligned}$$

In other words, by definition (10), the control law $\{U^0, \varepsilon , \varDelta _\delta \}$ of the first player guarantees for the value of quality index (3) the inequality

$$\begin{aligned} \gamma \le \varGamma _u^0(t_0, x_0) + \zeta \end{aligned}$$

for any admissible control realization $v[t_0[\cdot ]\vartheta )$ of the second player.

5.3 Statement of the Problem for the Second Player

The statement of the problem for the second player is carried out in a similar way as for the first player. But we should take into account that the second player has the opposite aim and uses the counter-strategies.

Let the second player choose a strategy V of type (7). Let a value of the parameter $\varepsilon > 0$ be chosen, and a partition $\varDelta _\delta$ (8) be fixed. The triple $\{V, \varepsilon , \varDelta _\delta \}$ is called a control law of the second player. This law forms a control realization $v[t_0[\cdot ]\vartheta )$ by the following step-by-step rule:

$$\begin{aligned} v(t) = V(\tau _j, x[t_0[\cdot ]\tau _j], u(t), \varepsilon ), \quad t \in [\tau _j, \tau _{j+1}), \quad j = \overline{1, k}, \end{aligned}$$

(13)

where $x[t_0[\cdot ]\tau _j]$ is the motion history realized up to the time $\tau _j$ and u(t) is the current control action of the first player. Note that, since the strategy V is Borel measurable in u,  the obtained control realization $v[t_0[\cdot ]\vartheta )$ of the second player is admissible for any admissible control realization $u[t_0[\cdot ]\vartheta )$ of the first player.

The control law $\{V, \varepsilon , \varDelta _\delta \}$ and a control realization $u[t_0[\cdot ]\vartheta )$ uniquely determine the game process realization $\{x[t_0[\cdot ]\vartheta ], u[t_0[\cdot ]\vartheta ), v[t_0[\cdot ]\vartheta )\},$ and, therefore, the value $\gamma$ of quality index (3). The guaranteed result of the control law $\{V, \varepsilon , \varDelta _\delta \}$ and the guaranteed result of the strategy V are defined as follows:

$$\begin{aligned} \varGamma _v (t_0, x_0; V, \varepsilon , \varDelta _\delta )= & {} \inf _{u[t_0[\cdot ]\vartheta )} \gamma , \end{aligned}$$

(14)

$$\begin{aligned} \varGamma _v (t_0, x_0; V)= & {} \liminf _{\varepsilon \downarrow 0} \, \lim _{\delta \downarrow 0} \, \inf _{\varDelta _\delta } \varGamma _v (t_0, x_0; V, \varepsilon , \varDelta _\delta ). \end{aligned}$$

(15)

The optimal guaranteed result of the second player is

$$\begin{aligned} \varGamma _v^0(t_0, x_0) = \sup _{V} \varGamma _v (t_0, x_0; V). \end{aligned}$$

(16)

A strategy of the second player $V^0$ is called optimal if

$$\begin{aligned} \varGamma _v (t_0, x_0; V^0) = \varGamma _v^0(t_0, x_0). \end{aligned}$$

According to definitions (14) and (15), it means that, for any $\zeta > 0,$ under the sufficiently small $\varepsilon > 0$ and $\delta > 0,$ a control law $\{V^0, \varepsilon , \varDelta _\delta \}$ of the second player guarantees the inequality

$$\begin{aligned} \gamma \ge \varGamma _v^0(t_0, x_0) - \zeta \end{aligned}$$

for any admissible control realization $u[t_0[\cdot ]\vartheta )$ of the first player.

5.4 Game Value and Saddle Point

Note that, for any strategies U and V,  any values $\varepsilon ^u >0$ and $\varepsilon ^v > 0,$ any partitions $\varDelta ^u_{\delta ^u}$ and $\varDelta ^v_{\delta ^v},$ the players’ control laws $\{U, \varepsilon ^u, \varDelta ^u_{\delta ^u}\}$ and $\{V, \varepsilon ^v, \varDelta ^v_{\delta ^v}\}$ are compatible. Namely, we can consider the realization $\{x[t_0[\cdot ]\vartheta ], u[t_0[\cdot ]\vartheta ), v[t_0[\cdot ]\vartheta )\}$ of the game process in which $u[t_0[\cdot ]\vartheta )$ is formed by $\{U, \varepsilon ^u, \varDelta ^u_{\delta ^u}\}$ and, at the same time, $v[t_0[\cdot ]\vartheta )$ is formed by $\{V, \varepsilon ^v, \varDelta ^v_{\delta ^v}\}.$ Therefore, it follows from definitions (10)–(12) and (14)–(16) that the players’ optimal guaranteed results, as “minmax” and “maxmin”, satisfy the inequality

$$\begin{aligned} \varGamma _u^0(t_0, x_0) \ge \varGamma _v^0(t_0, x_0). \end{aligned}$$

(17)

If the equality holds in (17), then we say that the considered differential game (1)–(3) has the value

$$\begin{aligned} \varGamma ^0(t_0, x_0) = \varGamma _u^0(t_0, x_0) = \varGamma _v^0(t_0, x_0). \end{aligned}$$

If, in addition, the optimal strategies $U^0$ and $V^0$ exist, then this game has the saddle point $\{U^0, V^0\}.$

Based on the results of [19, 21, 24] (see also [30]), one can prove the following theorem.

Theorem 1

Let dynamical system (1) satisfy conditions (A.1)–(A.3),  and quality index (3) satisfy conditions (B.1)–(B.4). Then, for any $x_0 \in \mathbb {R}^n,$ the differential game (1)–(3) has the value $\varGamma ^0(t_0, x_0)$ and saddle point $\{U^0, V^0\}$ in the classes of strategies with memory of motion history.

Note that if the following saddle point condition in a small game [24], or, in another terminology, the Isaacs’ condition [10], is fulfilled:

$$\begin{aligned} \begin{aligned}&\displaystyle \min _{u \in P} \max _{v \in Q} \big ( \langle s, f(t, x, u, v) \rangle + q h(t, x, u, v) \big ) \\ \displaystyle&\quad = \max _{v \in Q} \min _{u \in P} \big ( \langle s, f(t, x, u, v) \rangle + q h(t, x, u, v) \big ), \\&t \in [t_0, \vartheta ], \quad x \in \mathbb {R}^n, \quad s \in \mathbb {R}^n, \quad q \in \mathbb {R}, \end{aligned} \end{aligned}$$

(18)

where the symbol $\langle \cdot , \cdot \rangle$ denotes the inner product of vectors, then there exists the optimal strategy of the second player $V^0 = V^0(t, x[t_0[\cdot ]t], \varepsilon )$ that does not depend on u. Thus, under the additional condition (18), Theorem 1 is valid if we formulate the differential game in the classes of strategies $U = U(t, x[t_0[\cdot ]t], \varepsilon )$ and $V = V(t, x[t_0[\cdot ]t], \varepsilon ).$

Note that Theorem 1 is also valid if we formulate the differential game in the classes of counter-strategies $U = U(t, x[t_0[\cdot ]t], v, \varepsilon )$ of the first player and strategies $V = V(t, x[t_0[\cdot ]t], \varepsilon )$ of the second player.

6 Positional Quality Index

Theorem 1 establishes the existence of the players’ optimal strategies $U^0 = U^0(t, x[t_0[\cdot ]t], \varepsilon )$ and $V^0 = V^0(t, x[t_0[\cdot ]t], u, \varepsilon )$ with memory, which depend on the current motion history $x[t_0[\cdot ]t].$ Example 2 in Sect. 4 shows that the information about motion history is sometimes actually needed. On the other hand, optimal guaranteed results (12) and (16) are often achieved on the strategies $U^0 = U^0(t, x(t), \varepsilon )$ and $V^0 = V^0(t, x(t), u, \varepsilon )$ that depend on the current position (t, x(t)) of system (1). The question about when it is sufficient to use the strategies $U = U(t, x(t), \varepsilon )$ and $V = V(t, x(t), u, \varepsilon )$ without memory, called the positional strategies [24], is closely related to the properties of quality index (3).

For example, let us consider the terminal–integral quality index

$$\begin{aligned} \gamma = \mu (x(\vartheta )) + \int _{t_0}^{\vartheta } h(t, x(t), u(t), v(t)) \hbox {d}t. \end{aligned}$$

(19)

The difference from the general case (3) is that the function $\mu$ estimates a system’s motion $x[t_0[\cdot ]\vartheta ]$ by its terminal value $x(\vartheta )$ only. For the differential game (1), (2), (19), it is well-known (see, e.g., [15, 19, 21, 24]) that there exist the optimal strategies $U^0 = U^0(t, x(t), \varepsilon )$ and $V^0 = V^0(t, x(t), u, \varepsilon )$ without memory. Thus, for quality index (19), it is sufficient to formulate the differential game (formally, by substituting $x(\tau _j)$ instead of $x[t_0[\cdot ]\tau _j]$ in (9) and (13)) in the classes of the positional strategies

$$\begin{aligned} U = U(t, x, \varepsilon ) \in P, \quad t \in [t_0, \vartheta ], \quad x \in \mathbb {R}^n, \quad \varepsilon > 0, \end{aligned}$$

(20)

of the first player and the positional counter-strategies

$$\begin{aligned} V = V(t, x, u, \varepsilon ) \in Q, \quad t \in [t_0, \vartheta ], \quad x \in \mathbb {R}^n, \quad u \in P, \quad \varepsilon > 0, \end{aligned}$$

(21)

of the second player.

In the differential game (1), (2), (19), the positional optimal strategies $U^0 = U^0(t, x, \varepsilon )$ and $V^0 = V^0(t, x, u, \varepsilon )$ can be constructed by the method of extremal shift to accompanying points [15, 17, 21]. Let us describe this method under the following condition, which strengthens conditions (A.3) and (B.4): there exists a constant $\lambda > 0$ such that

$$\begin{aligned} \begin{aligned}&\Vert f(t, x, u, v) - f(t, y, u, v)\Vert ^2 + |h(t, x, u, v) - h(t, y, u, v)|^2 \le \lambda ^2 \Vert x - y\Vert ^2, \\&t \in [t_0, \vartheta ], \quad x, y \in \mathbb {R}^n, \quad u \in P, \quad v \in Q. \end{aligned} \end{aligned}$$

(22)

Let us consider the function $\rho : [t_0, \vartheta ) \times \mathbb {R}^n \rightarrow \mathbb {R}$ defined as follows:

$$\begin{aligned} \rho (t_*, x_*) = \varGamma ^0 (t_*, x_*), \quad t_*\in [t_0, \vartheta ), \quad x_*\in \mathbb {R}^n, \end{aligned}$$

(23)

where $\varGamma ^0 (t_*, x_*)$ is the value of the differential game for system (1), the initial condition

$$\begin{aligned} x(t_*) = x_*, \end{aligned}$$

(24)

and the quality index

$$\begin{aligned} \gamma = \mu (x(\vartheta )) + \int _{t_*}^{\vartheta } h(t, x(t), u(t), v(t)) \hbox {d}t. \end{aligned}$$

Let $t \in [t_0, \vartheta ),$$x \in \mathbb {R}^n$ and $\varepsilon > 0.$ The accompanying points for the first and second players are chosen from the conditions

$$\begin{aligned} \begin{aligned}&\big ( z_u (t, x, \varepsilon ), w_u (t, x, \varepsilon ) \big ) \in \underset{(z, w)}{{\text {argmin}} \,} \big ( \rho (t, z) + w \big ), \\&\big ( z_v (t, x, \varepsilon ), w_v (t, x, \varepsilon ) \big ) \in \underset{(z, w)}{{\text {argmax}} \,} \big ( \rho (t, z) + w \big ). \end{aligned} \end{aligned}$$

(25)

Here the minimum and maximum are calculated over the pairs $(z, w) \in \mathbb {R}^n \times \mathbb {R}$ satisfying the inequality

$$\begin{aligned} \Vert z - x\Vert ^2 + w^2 \le r^2(t, \varepsilon ), \end{aligned}$$

where

$$\begin{aligned} r^2 (t, \varepsilon ) = \big ( \varepsilon + (t - t_0) \varepsilon \big ) e^{2 \lambda (t - t_0)}, \end{aligned}$$

(26)

and the constant $\lambda$ is taken from (22). These minimum and maximum are achieved since, under the considered conditions, the function $\rho (t, z)$ is continuous in z (see, e.g., [14, 21]). The optimal strategies $U^0 = U^0(t, x, \varepsilon )$ and $V^0 = V^0(t, x, u, \varepsilon )$ can be defined as follows:

$$\begin{aligned} \begin{aligned}&\displaystyle U^0(t, x, \varepsilon ) \in \underset{u \in P}{{\text {argmin}} \,} \max _{v \in Q} \big (\langle x - z_u(t, x, \varepsilon ), f(t, x, u, v) \rangle - w_u(t, x, \varepsilon ) h (t, x, u, v) \big ), \\&V^0(t, x, u, \varepsilon ) \in \underset{v \in Q}{{\text {argmax}} \,} \big (\langle z_v(t, x, \varepsilon ) - x, f(t, x, u, v) \rangle + w_v(t, x, \varepsilon ) h (t, x, u, v) \big ). \end{aligned} \end{aligned}$$

(27)

Note that the strategy $V^0 = V^0(t, x, u, \varepsilon )$ can be chosen Borel measurable in u for any t,  x and $\varepsilon .$

In the general case of conditions (A.3) and (B.4), the positional optimal strategies can be defined similarly, but the constant $\lambda$ in (22) and (26) should be chosen by the compact $D \subset \mathbb {R}^n$ that contains all the values x(t) that can be realized in system (1) under initial condition (2) (see, e.g., [17, p. 40]).

The more complicated case when players’ optimal guaranteed results (12) and (16) are achieved on the positional strategies is the case of the positional quality indices [14, 17]. Let us suppose that the quality index $\gamma$ depends only on a system’s motion $x[t_0[\cdot ]\vartheta ],$ i.e.,

$$\begin{aligned} \gamma = \mu (x[t_0[\cdot ]\vartheta ]). \end{aligned}$$

(28)

According to [17, § 4], quality index (28) is called positional if, for any times $t_*\in [t_0, \vartheta )$ and $t^*\in (t_*, \vartheta ],$ we can define a continuous function

$$\begin{aligned} \nu = \nu (x[t_*[\cdot ]\vartheta ]) \in \mathbb {R}, \quad x[t_*[\cdot ]\vartheta ] \in C([t_*, \vartheta ], \mathbb {R}^n), \end{aligned}$$

and a continuous and non-decreasing in $\beta$ function

$$\begin{aligned} \sigma = \sigma (x[t_*[\cdot ]t^*), \beta ) \in \mathbb {R}, \quad x[t_*[\cdot ]t^*) \in C([t_*,t^*), \mathbb {R}^n), \quad \beta \in \mathbb {R}, \end{aligned}$$

such that, firstly,

$$\begin{aligned} \nu (x[t_*[\cdot ]\vartheta ]) = \sigma \big (x[t_*[\cdot ]t^*), \, \nu (x[t^*[\cdot ]\vartheta ])\big ) \end{aligned}$$

(29)

for any function $x[t_*[\cdot ]\vartheta ] \in C([t_*, \vartheta ], \mathbb {R}^n)$ and its restrictions $x[t_*[\cdot ]t^*)$ and $x[t^*[\cdot ]\vartheta ];$ and secondly,

$$\begin{aligned} \nu (x[t_0[\cdot ]\vartheta ]) = \mu (x[t_0[\cdot ]\vartheta ]) \end{aligned}$$

(30)

for any $x[t_0[\cdot ]\vartheta ] \in C([t_0, \vartheta ], \mathbb {R}^n).$

Let us illustrate the given definition by the following examples:

$$\begin{aligned} \gamma ^{(1)} = \Vert x(\vartheta )\Vert + \int _{t_0}^{\vartheta } h(t, x(t)) \hbox {d}t, \quad \gamma ^{(2)} = \max _{t \in [t_0,\vartheta ]} \Vert x(t)\Vert . \end{aligned}$$

For $\gamma ^{(1)},$ we have

$$\begin{aligned} \nu ^{(1)}(x[t_*[\cdot ]\vartheta ]) = \Vert x(\vartheta )\Vert + \int _{t_*}^{\vartheta } h(t, x(t)) \hbox {d}t, \ \ \sigma ^{(1)}(x[t_*[\cdot ]t^*), \beta ) = \beta + \int _{t_*}^{t^*} h(t, x(t)) \hbox {d}t. \end{aligned}$$

For $\gamma ^{(2)},$ we put

$$\begin{aligned} \nu ^{(2)}(x[t_*[\cdot ]\vartheta ]) = \max _{t \in [t_*, \vartheta ]} \Vert x(t)\Vert , \quad \sigma ^{(2)}(x[t_*[\cdot ]t^*), \beta ) = \max \big \{\max _{t \in [t_*, t^*]} \Vert x(t)\Vert , \beta \big \}. \end{aligned}$$

Thus, the both quality indices $\gamma ^{(1)}$ and $\gamma ^{(2)}$ are positional. Note that the quality index $\gamma = \gamma ^{(1)} + \gamma ^{(2)}$ is not positional. Note also that quality index (5) from Example 2 in Sect. 4 is not positional too.

The theorem below follows from the results of [14, 17].

Theorem 2

Let dynamical system (1) satisfy conditions (A.1)–(A.3),  and quality index (28) be positional. Then, for any $x_0 \in \mathbb {R}^n,$ in the differential game (1), (2), (28), there exist the positional optimal strategies $U^0 = U^0(t, x, \varepsilon )$ and $V^0 = V^0(t, x, u, \varepsilon ).$

For the positional quality index, the optimal strategies $U^0 = U^0(t, x, \varepsilon )$ and $V^0 = V^0(t, x, u, \varepsilon )$ can again be defined by formulas (25)–(27) where we put $h \equiv 0$ and define function (23) as the value of the differential game for system (1), initial condition (24) and the quality index

$$\begin{aligned} \gamma = \nu (x[t_*[\cdot ]\vartheta ]). \end{aligned}$$

Here $\nu$ is taken from (29), (30).

In the next section, we focus on the linear-convex case of the considered differential game and describe the upper convex hulls method for constructing the value of the game and the optimal strategies of the players.

7 Solution in Linear-Convex Case: Upper Convex Hulls Method

Let the dynamical system be described by the linear in the state vector differential equation

$$\begin{aligned} \begin{aligned} \dot{x}(t)&= A(t) x(t) + f(t, u(t), v(t)), \quad t_0 \le t \le \vartheta , \\ x(t)&\in \mathbb {R}^n, \quad u(t) \in P \subset \mathbb {R}^r, \quad v(t) \in Q \subset \mathbb {R}^s, \end{aligned} \end{aligned}$$

(31)

where A(t) and f(t, u, v) are continuous functions. Note that the right-hand side of Eq. (31) satisfies conditions (A.1)–(A.3). Moreover, in condition (A.3), we can define the constant

$$\begin{aligned} \lambda = \max _{t \in [t_0, \vartheta ]} \, \max _{\Vert x\Vert \le 1} \Vert A(t) x\Vert \end{aligned}$$

(32)

that does not depend on the choice of $D \subset \mathbb {R}^n.$

7.1 Terminal–Integral Quality Index

Let us consider the differential game for system (31) under initial condition (2) and the following terminal–integral quality index:

$$\begin{aligned} \gamma = \mu (x(\vartheta )) + \int _{t_0}^{\vartheta } h(t, u(t), v(t)) \hbox {d}t, \end{aligned}$$

(33)

where $\mu (x)$ is a norm in $\mathbb {R}^n,$ and h(t, u, v) is a continuous function. Note that conditions (B.3) and (B.4) are obviously satisfied since h does not depend on x.

Denote by $X(t, \tau )$ the fundamental solution matrix of the equation $\dot{x}(t) = A(t)x(t)$ such that $X(\tau , \tau ) = I.$ Denote by $\mu ^*(m)$ the norm dual to $\mu (x)$:

$$\begin{aligned} \mu ^*(m) = \max _{\mu (x) \le 1} \langle x, m \rangle . \end{aligned}$$

Define the set

$$\begin{aligned} G = \big \{ m \in \mathbb {R}^n: \ \mu ^*(m) \le 1 \big \}. \end{aligned}$$

Let a partition $\varDelta _\delta$ (8) be fixed. Define the functions $\varphi _j(m) \in \mathbb {R},$$m \in G,$$j = \overline{1, k+1},$ according to the following recurrent procedure:

$$\begin{aligned} \begin{aligned} \varphi _{k + 1}(m)&= 0, \\ \varphi _j (\cdot )&= \big \{ \psi _j(\cdot ) \big \}_{G}^*, \quad \psi _j (m) = \varDelta \psi _j(m) + \varphi _{j+1} (m), \quad j = \overline{1, k}, \end{aligned} \end{aligned}$$

(34)

where

$$\begin{aligned} \varDelta \psi _j(m) = \int _{\tau _j}^{\tau _{j+1}} \min _{u\in P} \max _{v\in Q} \big ( \langle m, X(\vartheta ,\tau )f(\tau , u, v) \rangle + h(\tau , u, v) \big ) \hbox {d} \tau , \end{aligned}$$

and the symbol $\big \{\psi _j(\cdot )\big \}_G^*$ denotes the upper convex hull of the function $\psi _j(\cdot )$ on the set G,  i.e., $\varphi _j(\cdot )$ is the minimal concave function that majorizes $\psi _j(\cdot )$ for $m \in G.$ Put

$$\begin{aligned} e_j (x) = \max _{m \in G} \big ( \langle m, X(\vartheta , \tau _j) x \rangle + \varphi _j (m)\big ), \quad x \in \mathbb {R}^n, \quad j = \overline{1, k + 1}. \end{aligned}$$

(35)

One can prove the following result (see [17, 23] and also [4] for related details).

Proposition 1

For any number $\xi > 0,$ there exists a number $\delta > 0$ such that, for any $x_0 \in \mathbb {R}^n$ and any partition $\varDelta _\delta$ (8), the following inequality holds:

$$\begin{aligned} |\varGamma ^0 (t_0, x_0) - e_1 (x_0) | \le \xi , \end{aligned}$$

where $\varGamma ^0(t_0, x_0)$ is the value of the differential game (31), (2), (33) and $e_1(x_0)$ is value (35) constructed on the basis of the partition $\varDelta _\delta .$

Let us consider the positional strategies $U^*= U^*(t, x, \varepsilon )$ and $V^*= V^*(t, x, u, \varepsilon )$ that are defined at the times $\tau _j$ of the partition $\varDelta _\delta$ by the method of extremal shift to accompanying points (25)–(27) where we substitute $e_j(x)$ instead of $\rho (\tau _j, x).$ Due to (35), we obtain (see [17, 23] and also [11])

$$\begin{aligned} \begin{aligned}&\displaystyle U^*(\tau _j, x, \varepsilon ) \in \underset{u \in P}{{\text {argmin}} \,} \max _{v \in Q} \big (\langle m_j^u, X(\vartheta , \tau _j) f(\tau _j, u, v) \rangle + h(\tau _j, u, v) \big ), \\&V^*(\tau _j, x, u, \varepsilon ) \in \underset{v \in Q}{{\text {argmax}} \,} \big (\langle m_j^v, X(\vartheta , \tau _j) f(\tau _j, u, v) \rangle + h(\tau _j, u, v) \big ), \end{aligned} \end{aligned}$$

(36)

where

$$\begin{aligned}&m_j^u \in \underset{m \in G}{{\text {argmax}} \,} \big ( \langle m, X(\vartheta ,\tau _j) x \rangle + \varphi _j (m) - r(\tau _j, \varepsilon ) \sqrt{1 + \Vert X^T(\vartheta , \tau _j) m\Vert ^2} \big ), \\&m_j^v \in \underset{m \in G}{{\text {argmax}} \,} \big ( \langle m, X(\vartheta ,\tau _j) x \rangle + \varphi _j (m) + r(\tau _j, \varepsilon ) \sqrt{1 + \Vert X^T(\vartheta , \tau _j) m\Vert ^2} \big ), \end{aligned}$$

and $r(\tau _j, \varepsilon )$ is defined by (26) with the constant $\lambda$ from (32). Here and below the upper symbol T denotes transposition.

Based on Proposition 1 and the properties of the values $e_j(x)$ (see [4]), the following result can be proved.

Proposition 2

For any number $\zeta > 0,$ there exist a number $\varepsilon ^*> 0$ and a function $\delta ^*(\varepsilon ) > 0,$$\varepsilon \in (0, \varepsilon ^*],$ such that the following statement is valid. Let $\varepsilon \in (0, \varepsilon ^*]$ and $\varDelta _\delta$ be a partition (8) with $\delta \le \delta ^*(\varepsilon ).$ Let the strategies $U^*$ and $V^*$ be defined by (36) on the basis of the partition $\varDelta _\delta .$ Then, for any $x_0 \in \mathbb {R}^n,$ in the differential game (31), (2), (33), the control law $\{U^*, \varepsilon , \varDelta _\delta \}$ of the first player guarantees the inequality

$$\begin{aligned} \gamma \le \varGamma ^0(t_0, x_0) + \zeta \end{aligned}$$

for any admissible control realization $v[t_0[\cdot ]\vartheta )$ of the second player; and the control law $\{V^*, \varepsilon , \varDelta _\delta \}$ of the second player guarantees the inequality

$$\begin{aligned} \gamma \ge \varGamma ^0(t_0, x_0) - \zeta \end{aligned}$$

for any admissible control realization $u[t_0[\cdot ]\vartheta )$ of the first player.

Thus, according to Propositions 1 and 2, the upper convex hulls method reduces the solution of the differential game (31), (2), (33) to the recurrent construction of the functions $\varphi _j(\cdot )$ under the sufficiently fine partition $\varDelta _\delta .$

7.2 Non-terminal Quality Index

Let us consider a generalization of terminal–integral quality index (33):

$$\begin{aligned} \gamma= & {} \mu \Big ( D_1 \big (x(\vartheta _1) - c_1\big ), D_2 \big (x(\vartheta _2) - c_2\big ), \ldots , D_N \big (x(\vartheta _N) - c_N\big )\Big ) \nonumber \\&+ \int _{t_0}^{\vartheta } h(t, u(t), v(t)) \hbox {d}t. \end{aligned}$$

(37)

Here the times $\vartheta _i \in [t_0,\vartheta ]$ are given, $\vartheta _i < \vartheta _{i+1},$$i = \overline{1,N-1},$$\vartheta _N = \vartheta ;$$c_i \in \mathbb {R}^n$ are target vectors and $D_i$ are constant $(d_i\times n)$-matrices, $1 \le d_i \le n,$$i = \overline{1, N};$$\mu (z_1, z_2, \ldots , z_N)$ is a norm of a vector $(z_1, z_2, \ldots , z_N) \in \mathbb {R}^{d_1} \times \mathbb {R}^{d_2} \times \cdots \times \mathbb {R}^{d_N}.$

Let us consider the differential game for system (31), initial condition (2) and quality index (37).

For a motion history $x[t_0[\cdot ]t]$ realized up to the current time $t \in [t_0, \vartheta ],$ we introduce the informational image $\mathbf {W}(t) = \mathbf {W}(t, x[t_0[\cdot ]t]):$

$$\begin{aligned} \mathbf {W}(t) = \big (w_1(t), w_2(t), \ldots , w_N(t) \big ) \in \mathbb {R}^{d_1} \times \mathbb {R}^{d_2} \times \cdots \times \mathbb {R}^{d_N}, \end{aligned}$$

where

$$\begin{aligned} w_i(t) = {\left\{ \begin{array}{ll} D_i \big (X(\vartheta _i, t) x(t) - c_i \big ), &{} \text{ if } t < \vartheta _i, \\ D_i \big (x(\vartheta _i) - c_i \big ), &{} \text{ if } t \ge \vartheta _i. \end{array}\right. } \end{aligned}$$

(38)

Note that, for $t = \vartheta ,$ we have

$$\begin{aligned} w_i(\vartheta ) = D_i \big (x(\vartheta _i) - c_i\big ), \quad i = \overline{1, N}. \end{aligned}$$

Therefore, quality index (37) can be rewritten as follows:

$$\begin{aligned} \gamma = \mu \big (\mathbf {W}(\vartheta )\big ) + \int _{t_0}^{\vartheta } h(t, u(t), v(t)) \hbox {d}t. \end{aligned}$$

(39)

Moreover, due to (2), (31) and (38), we have

$$\begin{aligned} \dot{w}_i(t) = {\left\{ \begin{array}{ll} D_i X(\vartheta _i, t)f(t, u(t), v(t)), &{} \text{ if } t < \vartheta _i, \\ 0, &{} \text{ if } t \ge \vartheta _i, \end{array}\right. } \quad t \in [t_0, \vartheta ], \quad i = \overline{1, N}, \end{aligned}$$

(40)

and

$$\begin{aligned} w_i(t_0) = w_i(t_0, x_0) = D_i \big (X(\vartheta _i, t_0) x_0 - c_i \big ), \quad i = \overline{1, N}. \end{aligned}$$

(41)

Thus, the differential game for system (31), initial condition (2) and non-terminal quality index (37) in the state space $\mathbb {R}^n$ of the vectors x(t) is reduced to the differential game for system (40), initial condition (41) and terminal–integral quality index (39) in the state space $\mathbb {R}^{d_1} \times \mathbb {R}^{d_2} \times \cdots \times \mathbb {R}^{d_N}$ of the informational images $\mathbf {W}(t).$ Namely, the following proposition is valid (see, e.g., [22]).

Proposition 3

In the differential game (31), (2), (37), the value $\varGamma ^0(t_0, x_0)$ and the optimal strategies $U^0 = U^0(t, x[t_0[\cdot ]t], \varepsilon ),$$V^0 = V^0(t, x[t_0[\cdot ]t], u, \varepsilon )$ can be determined as follows:

$$\begin{aligned} \varGamma ^0 (t_0, x_0)= & {} {\varvec{\Gamma }}^0(t_0, \mathbf {W}(t_0, x_0)),\\ U^0(t, x[t_0[\cdot ]t], \varepsilon )= & {} \mathbf {U}^0(t, \mathbf {W}(t, x[t_0[\cdot ]t]), \varepsilon ), \\ V^0(t, x[t_0[\cdot ]t], u, \varepsilon )= & {} \mathbf {V}^0(t, \mathbf {W}(t, x[t_0[\cdot ]t]), u, \varepsilon ), \end{aligned}$$

where ${\varvec{\Gamma }}^0(t_0, \mathbf {W}(t_0, x_0))$ and $\mathbf {U}^0 = \mathbf {U}^0(t, \mathbf {W}, \varepsilon ),$$\mathbf {V}^0 = \mathbf {V}^0(t, \mathbf {W}, u, \varepsilon )$ are the value and optimal strategies in the differential game (40), (41), (39).

This proposition allows to apply the upper convex hulls method described in Sect. 7.1 for the differential games with non-terminal quality indices (37). This technique based on auxiliary informational images of type (38) is extended to the dynamical systems described by linear differential equations with state [31], control [7] and neutral-type [9] delays.

Note that, when we apply the upper convex hulls method, the main difficulty is the necessity to construct the upper convex hulls $\varphi _j(m),$$m \in G,$ at every step of the partition $\varDelta _\delta .$ Procedure (34) can be realized analytically only in rare cases. Efficiency of the numerical construction of the upper convex hull $\varphi (m)$ of a function $\psi (m)$ on a set G depends essentially on the dimension of $m \in G.$ In the terminal–integral case (see Sect. 7.1), this dimension coincides with the dimension n of the state vector x(t). For non-terminal quality indices (37), when we apply the technique based on auxiliary informational image (38), this dimension is equal to $d_1 + d_2 + \cdots + d_N.$ In this case, it depends on the number N of the times $\vartheta _i$ and can be large even if the dimension n of the state vector x(t) is small. This fact narrows the applicability of the approach discussed in this subsection. Nevertheless, this approach is efficient in some cases (see, e.g., [7, 9, 31]). Besides, as it is shown below, if quality index (37) has a certain positional structure, then the upper convex hulls method can be reduced such that the dimension of the domains of the convexified functions equals to the dimension n of the state vector x(t) regardless of the number N of the times $\vartheta _i.$

7.3 Positional Quality Index

Let us consider a particular case [28] of quality index (37). Let the times $\vartheta _i \in [t_0, \vartheta ],$ the target vectors $c_i \in \mathbb {R}^n$ and the $(d_i\times n)$-matrices $D_i,$$i = \overline{1, N},$ be fixed. Let $\mu _i (z_i, z_{i+1}, \ldots , z_N),$$i = \overline{1, N},$ be norms of vectors $(z_i, z_{i+1}, \ldots , z_N) \in \mathbb {R}^{d_i} \times \mathbb {R}^{d_{i+1}} \times \cdots \times \mathbb {R}^{d_N}$ that satisfy the following relations:

$$\begin{aligned} \mu _i(z_i, z_{i+1}, \ldots , z_N) = \sigma _i\big (z_i, \mu _{i+1}(z_{i+1}, \ldots , z_N) \big ), \quad i = \overline{1, N - 1}, \end{aligned}$$

(42)

where $\sigma _i(z_i, \beta ),$$i = \overline{1, N - 1},$ are norms of vectors $(z_i, \beta ) \in \mathbb {R}^{d_i} \times \mathbb {R}$ that are non-decreasing in $\beta$ for $\beta \ge 0.$

Let us consider the differential game for system (31), initial condition (2) and the following quality index:

$$\begin{aligned} \gamma = \mu _1 \Big ( D_1 \big (x(\vartheta _1) - c_1\big ), D_2 \big (x(\vartheta _2) - c_2\big ), \ldots , D_N \big (x(\vartheta _N) - c_N\big )\Big ). \end{aligned}$$

(43)

Note that, due to (42), quality index (43) is positional (see [28] for details).

The typical examples of such quality indices are

$$\begin{aligned} \displaystyle \gamma ^{(1)}= & {} \sum _{i = 1}^{N} \Vert D_i \big (x(\vartheta _i) - c_i\big )\Vert , \\ \displaystyle \gamma ^{(2)}= & {} \max _{i = \overline{1, N}} \Vert D_i \big (x(\vartheta _i) - c_i\big )\Vert , \\ \displaystyle \gamma ^{(3)}= & {} \bigg ( \sum _{i = 1}^{N} \Vert D_i \big (x(\vartheta _i) - c_i\big )\Vert ^2 \bigg )^{1/2}, \end{aligned}$$

where we have

$$\begin{aligned} \displaystyle \mu _i^{(1)}(z_i, z_{i+1}, \ldots , z_N)= & {} \sum _{j = i}^{N} \Vert z_j\Vert , \quad \sigma _i^{(1)}(z_i, \beta ) = \Vert z_i\Vert + |\beta |, \\ \displaystyle \mu _i^{(2)}(z_i, z_{i+1}, \ldots , z_N)= & {} \max _{j = \overline{i, N}} \Vert z_j\Vert , \quad \sigma _i^{(2)}(z_i, \beta ) = \max \{\Vert z_i\Vert , |\beta | \}, \\ \displaystyle \mu _i^{(3)}(z_i, z_{i+1}, \ldots , z_N)= & {} \bigg (\sum _{j = i}^{N} \Vert z_j\Vert ^2\bigg )^{1/2}, \quad \sigma _i^{(3)}(z_i, \beta ) = \big (\Vert z_i\Vert ^2 + \beta ^2\big )^{1/2}. \end{aligned}$$

Due to (42), in the case of quality index (43), the upper convex hulls method can be realized as follows (see [28] and also [4]).

Denote by $\mu _i^*(l_i, l_{i+1}, \ldots , l_N)$ and $\sigma _i^*(l_i, \nu )$ the norms dual to $\mu _i(z_i, z_{i+1}, \ldots , z_N)$ and $\sigma _i(z_i, \beta ),$ respectively. Let $\varDelta _\delta$ be a partition (8) that contains the times $\vartheta _i$ from (43), i.e., the inclusions

$$\begin{aligned} \vartheta _i \in \varDelta _\delta , \quad i = \overline{1, N}, \end{aligned}$$

(44)

are valid. Based on the partition $\varDelta _\delta ,$ define the sets $G_j^\pm \subset \mathbb {R}^n$ and the functions $\varphi _j^\pm (m) \in \mathbb {R},$$m \in G_j^\pm ,$$j = \overline{1, k+1},$ according to the following recurrent procedure. For $j = k + 1,$ put

$$\begin{aligned} \begin{aligned} G_{k+1}^+&= \{m = 0\}, \quad \varphi _{k + 1}^+ (m) = 0, \\ G_{k + 1}^-&= \big \{ m \in \mathbb {R}^n: \, m = D_N^T l_N, \, l_N \in \mathbb {R}^{d_N}, \, \mu _{N}^*(l_N) \le 1 \big \}, \\ \varphi _{k + 1}^- (m)&= - \langle m, c_N \rangle . \end{aligned} \end{aligned}$$

(45)

For $j = \overline{1, k},$ firstly, define

$$\begin{aligned} \begin{array}{c} G_j^+ = G_{j+1}^-, \quad \varphi _j^+ (\cdot ) = \big \{ \psi _j(\cdot ) \big \}_{G_j^+}^*, \quad \psi _j (m) = \varDelta \psi _j(m) + \varphi _{j+1}^- (m), \end{array} \end{aligned}$$

(46)

where

$$\begin{aligned} \varDelta \psi _j(m) = \int _{\tau _j}^{\tau _{j+1}} \min _{u\in P} \max _{v\in Q} \langle m, X(\vartheta ,\tau )f(\tau , u, v) \rangle \hbox {d} \tau . \end{aligned}$$

(47)

Further, if $\tau _j \ne \vartheta _i$ for any $i = \overline{1, N-1},$ then set

$$\begin{aligned} G_j^- = G_j^+, \quad \varphi _j^- (m) = \varphi _j^+(m). \end{aligned}$$

(48)

Otherwise, if $\tau _j = \vartheta _i$ for some $i = \overline{1, N - 1},$ then put

$$\begin{aligned} G_j^-= & {} \Big \{ m \in \mathbb {R}^n: \, m = \nu m_*+ X^T(\vartheta _i, \vartheta ) D_i^T l_i,\nonumber \\&\quad \nu \ge 0, \, m_*\in G_j^+, \, l_i \in \mathbb {R}^{d_i}, \, \sigma _i^*(l_i, \nu ) \le 1\Big \}, \end{aligned}$$

(49)

$$\begin{aligned} \varphi _j^- (m)= & {} \max _{(\nu , m_*, l_i)} \big ( \nu \varphi _j^+(m_*) - \langle l_i, D_i c_i \rangle \big ), \end{aligned}$$

(50)

where the maximum is calculated over all the triples $(\nu , m_*, l_i) \in \mathbb {R} \times G_j^+ \times \mathbb {R}^{d_i}$ that correspond to the vector $m \in G_j^-$ according to (49).

Denote

$$\begin{aligned} e_j^\pm (x) = \max _{m \in G_j^\pm } \big ( \langle m, X(\vartheta , \tau _j) x \rangle + \varphi _j^\pm (m)\big ), \quad x \in \mathbb {R}^n, \quad j = \overline{1, k + 1}. \end{aligned}$$

(51)

Note that the steps of the method between the times $\vartheta _{i+1}$ and $\vartheta _i$ are the same as in the terminal case (see Sect. 7.1). The presence of the times $\vartheta _i$ in quality index (43) leads to the necessity of the additional constructions (49), (50), which provide in accordance with (42) the following relations between the values $e_j^-(x)$ and $e_j^+(x):$

$$\begin{aligned} e_j^-(x) = {\left\{ \begin{array}{ll} e_j^+(x), &{} \text{ if } \tau _j \ne \vartheta _i, \\ \sigma _i\big ( D_i(x - c_i), e_j^+(x)\big ), &{} \text{ if } \tau _j = \vartheta _i. \end{array}\right. } \end{aligned}$$

The following proposition is valid (see [4, 28]).

Proposition 4

For any number $\xi > 0,$ there exists a number $\delta > 0$ such that, for any $x_0 \in \mathbb {R}^n$ and any partition $\varDelta _\delta$ (8), (44), the following inequality holds:

$$\begin{aligned} |\varGamma ^0 (t_0, x_0) - e_1^- (x_0)| \le \xi , \end{aligned}$$

where $\varGamma ^0(t_0, x_0)$ is the value of the differential game (31), (2), (43) and $e_1^-(x_0)$ is value (51) constructed on the basis of the partition $\varDelta _\delta .$

Let us consider the positional strategies $U_*= U_*(t, x, \varepsilon )$ and $V_*= V_*(t, x, u, \varepsilon )$ that are defined at the times $\tau _j$ of the partition $\varDelta _\delta$ by the method of extremal shift to accompanying points (25)–(27) where we put $h \equiv 0$ and substitute $e_j^+(x)$ instead of $\rho (\tau _j, x).$ Due to (51), we obtain (see, e.g., [11])

$$\begin{aligned} \begin{aligned}&\displaystyle U_*(\tau _j, x, \varepsilon ) \in \underset{u \in P}{{\text {argmin}} \,} \max _{v \in Q} \langle m_j^u, X(\vartheta , \tau _j) f(\tau _j, u, v) \rangle , \\&V_*(\tau _j, x, u, \varepsilon ) \in \underset{v \in Q}{{\text {argmax}} \,} \langle m_j^v, X(\vartheta , \tau _j) f(\tau _j, u, v) \rangle , \end{aligned} \end{aligned}$$

(52)

where

$$\begin{aligned}&m_j^u \in \underset{m \in G_j^+}{{\text {argmax}} \,} \big ( \langle m, X(\vartheta ,\tau _j) x \rangle + \varphi _j^+ (m) - r(\tau _j, \varepsilon ) \sqrt{1 + \Vert X^T(\vartheta , \tau _j) m\Vert ^2} \big ), \\&m_j^v \in \underset{m \in G_j^+}{{\text {argmax}} \,} \big ( \langle m, X(\vartheta ,\tau _j) x \rangle + \varphi _j^+ (m) + r(\tau _j, \varepsilon ) \sqrt{1 + \Vert X^T(\vartheta , \tau _j) m\Vert ^2} \big ), \end{aligned}$$

and $r(\tau _j, \varepsilon )$ is defined by (26) with the constant $\lambda$ from (32).

Based on Proposition 4 and the properties of the values $e_j^\pm (x)$ (see [4, 28]), the following result can be proved.

Proposition 5

For any number $\zeta > 0,$ there exist a number $\varepsilon _*> 0$ and a function $\delta _*(\varepsilon ) > 0,$$\varepsilon \in (0, \varepsilon _*],$ such that the following statement is valid. Let $\varepsilon \in (0, \varepsilon _*]$ and $\varDelta _\delta$ be a partition (8),(44) with $\delta \le \delta _*(\varepsilon ).$ Let the strategies $U_*$ and $V_*$ be defined by (52) on the basis of the partition $\varDelta _\delta .$ Then, for any $x_0 \in \mathbb {R}^n,$ in the differential game (31), (2), (43), the control law $\{U_*, \varepsilon , \varDelta _\delta \}$ of the first player guarantees the inequality

$$\begin{aligned} \gamma \le \varGamma ^0(t_0, x_0) + \zeta \end{aligned}$$

for any admissible control realization $v[t_0[\cdot ]\vartheta )$ of the second player; and the control law $\{V_*, \varepsilon , \varDelta _\delta \}$ of the second player guarantees the inequality

$$\begin{aligned} \gamma \ge \varGamma ^0(t_0, x_0) - \zeta \end{aligned}$$

for any admissible control realization $u[t_0[\cdot ]\vartheta )$ of the first player.

According to Propositions 4 and 5, the solution of the differential game for system (31), initial condition (2) and positional quality index (43) is reduced to recurrent construction (45)–(50) of the upper convex hulls $\varphi ^\pm _j(m)$ of the functions $\psi _j(m)$ on the sets $G_j^\pm .$ Let us stress again that here the dimension of m coincides with the dimension n of the state vector x(t) and does not depend on the number N of the times $\vartheta _i$ from quality index (43).

The stability of the resolving constructions (45)–(52) with respect to computational and informational errors is proved in [8]. A numerical method for solving the considered differential games on the basis of these constructions is given in [11], where one can find also some details concerning its software implementation. The method is based on (a) the “pixel” approximation for the domains of the convexified functions; (b) the approximate construction of the upper convex hull of a function as the envelope of a finite family of supporting hyperplanes to the subgraph of this function. The convergence of this numerical method is proved in [6]. In [3, 5], the resolving constructions (45)–(52) are extended to the dynamical systems with control delays. In [13], they are developed for the differential games of type (31), (2), (43) with additional integral constraints on control realizations of the players. In [12], the upper convex hulls method is applied for solving the differential games of type (31), (2), (43) in mixed strategies (see, e.g., [17, Ch. IV]).

8 Example

Let us illustrate the applicability of the resolving constructions given in the paper by the following example. Let us consider the material point of unit mass in the plane. By $r = (r_1, r_2),$ we denote the radius vector of the point. There are two forces acting on the point. The first one is the friction force that is proportional to the velocity vector $\dot{r} = (\dot{r}_1, \dot{r}_2)$ with the coefficient $\alpha \ge 0.$ The second one is the control force. It has the constant value $\beta \ge 0,$ and we can choose its direction $u = (u_1, u_2)$ from the four possible variants: forward, backward, to the left, to the right. On the other hand, there are disturbances that can rotate the direction u by the angle $v \in [-\omega , \omega ],$ where $\omega \ge 0$ is known. The control process is considered during the finite interval of time $[t_0, \vartheta ].$ Thus, a motion of the material point is described by the equations

$$\begin{aligned}&{\left\{ \begin{array}{ll} \ddot{r}_1 (t) = - \alpha \dot{r}_1(t) + u_1(t) \cos v(t) - u_2(t) \sin v(t), \\ \ddot{r}_2 (t) = - \alpha \dot{r}_2(t) + u_1(t) \sin v(t) + u_2(t) \cos v(t), \end{array}\right. } \quad t_0 \le t \le \vartheta , \\&u(t) = \big ( u_1(t), u_2(t) \big ) \in \big \{ (0, \beta ), \, (0, - \beta ), \, (\beta , 0), \, (-\beta , 0) \big \}, \quad v(t) \in [- \omega , \omega ]. \end{aligned}$$

For the radius and velocity vectors, the initial values are given:

$$\begin{aligned} r_1(t_0) = r_1^0, \quad r_2(t_0) = r_2^0, \quad \dot{r}_1(t_0) = \dot{r}_1^0, \quad \dot{r}_2(t_0) = \dot{r}_2^0. \end{aligned}$$

Let points $A = (a_1, a_2)$ and $B = (b_1, b_2)$ in the plane and times $\vartheta _1 \in (t_0, \vartheta )$ and $\vartheta _2 = \vartheta$ be specified. The goal of the control is to bring the material point as close as possible to the point A at the time $\vartheta _1$ and to the point B at the time $\vartheta _2.$ In this connection, we consider the minimization problem for the quality index

$$\begin{aligned} \gamma = \sqrt{\Vert r(\vartheta _1) - A\Vert ^2 + \Vert r(\vartheta _2) - B\Vert ^2}. \end{aligned}$$

Since the disturbances are unknown, the worst case can happen when the disturbances aim to maximize $\gamma .$ Thus, following the guaranteed result principle (see, e.g., [17, 19, 21, 24]), we formalize the problem as the differential game of type (31), (2), (43). The actions $u(t) = (u_1(t), u_2(t))$ and v(t) are treated as the control actions of the first and second players, respectively. The state vector $x(t) = ( x_1(t), x_2(t), x_3(t), x_4(t))$ is introduced as follows:

$$\begin{aligned} x_1(t) = r_1(t),\quad x_2(t) = \dot{r}_1(t), \quad x_3(t) = r_2(t), \quad x_4(t) = \dot{r}_2(t). \end{aligned}$$

Hence, we have the differential game for the dynamical system

$$\begin{aligned} \begin{aligned}&{\left\{ \begin{array}{ll} \dot{x}_1 (t) = x_2(t), \\ \dot{x}_2 (t) = - \alpha x_2(t) + u_1(t) \cos v(t) - u_2(t) \sin v(t), \\ \dot{x}_3 (t) = x_4(t), \\ \dot{x}_4 (t) = - \alpha x_4(t) + u_1(t) \sin v(t) + u_2(t) \cos v(t), \end{array}\right. } \quad t_0 \le t \le \vartheta , \\&u(t) = \big ( u_1(t), u_2(t) \big ) \in P = \big \{ (0, \beta ), \, (0, - \beta ), \, (\beta , 0), \, (-\beta , 0) \big \}, \\&v(t) \in Q = [- \omega , \omega ]. \end{aligned} \end{aligned}$$

(53)

the initial condition

$$\begin{aligned} x_1(t_0) = r_1^0, \quad x_2(t_0) = \dot{r}_1^0, \quad x_3(t_0) = r_2^0, \quad x_4(t_0) = \dot{r}_2^0, \end{aligned}$$

(54)

and the positional quality index

$$\begin{aligned} \gamma = \sqrt{\big (x_1(\vartheta _1) - a_1\big )^2 + \big (x_3(\vartheta _1) - a_2\big )^2 + \big (x_1(\vartheta _2) - b_1\big )^2 + \big (x_3(\vartheta _2) - b_2\big )^2}. \end{aligned}$$

(55)

The results of the computer simulations given below were obtained with the help of the resolving constructions described in Sect. 7.3. The following values of the parameters were chosen:

$$\begin{aligned} \begin{aligned} \alpha&= 0.1, \quad \beta = 3, \quad \omega = 0.5, \quad t_0 = 0, \quad \vartheta _1 = 1, \quad \vartheta _2 = \vartheta = 2, \\ r_1^0&= 0, \quad \dot{r}_1^0 = -0.5, \quad r_2^0 = -0.5, \quad \dot{r}_2^0 = 1, \quad a_1 = a_2 = 0.5, \quad b_1 = b_2 = 0. \end{aligned} \end{aligned}$$

Procedure (45)–(50) was numerically realized on the basis of the partition $\varDelta _\delta$ with the constant step $\delta = 0.01.$ For computing the optimal strategies $U_*$ and $V_*$ according to (52), the value of the accuracy parameter $\varepsilon = 0.05$ was chosen. To obtain the results below, we ran multithreaded implementation [11] on a computer with two 18-core Intel(R) Xeon(R) CPU E5-2697 v4 @ 2.30 GHz processors and 256 GB RAM. The calculations took approximately 17.5 hours.

Fig. 1

Results of the computer simulations in the differential game (53)–(55)

Value (51) that, according to Proposition 4, approximates the value of the differential game (53)–(55) is

$$\begin{aligned} \varGamma ^0 \approx e_1^- (0, -0.5, -0.5, 1) \approx 0.522. \end{aligned}$$

We considered the following cases. In the first case, the first player uses the optimal control law $\{U_*, \varepsilon , \varDelta _\delta \},$ and the second player uses the counter-optimal control law $\{V_*, \varepsilon , \varDelta _\delta \}.$ The realized value of quality index (55) is

$$\begin{aligned} \gamma \approx \sqrt{\big (-0.019 - 0.5 \big )^2 + \big (0.369 - 0.5 \big )^2 + (-0.046)^2 + 0.05^2} \approx 0.54 \approx \varGamma ^0. \end{aligned}$$

In the second case, the first player still uses the control law $\{U_*, \varepsilon , \varDelta _\delta \},$ and the strategy of the second player is $v(t) \equiv 0.$ The corresponding result is

$$\begin{aligned} \gamma \approx \sqrt{\big (0.113 - 0.5 \big )^2 + \big (0.21 - 0.5 \big )^2 + 0.004^2 + 0.004^2} \approx 0.484 < \varGamma ^0. \end{aligned}$$

For comparison, we considered also the third case when $\omega = 0$ in (53) (i.e., $v(t) \equiv 0,$ and the first player knows about it). In this case, when the first player uses the corresponding optimal strategy, we have

$$\begin{aligned} \gamma \approx \sqrt{\big (0.377 - 0.5 \big )^2 + \big (0.464 - 0.5 \big )^2 + 0.022^2 + 0.028^2} \approx 0.133. \end{aligned}$$

The realized trajectories $r^{(i)}[0[\cdot ]2],$$i = \overline{1,3},$ of the material point in these three cases are shown in Fig. 1. The target points A and B are marked by black diamonds. The points on the trajectories realized at the times $\vartheta _1 = 1$ and $\vartheta _2 = 2$ are marked by white circles.

9 Conclusion

The goal of the paper was to survey the results concerning the differential games of type (1)–(3) from theory to numerical methods.

The main theoretical results obtained for such differential games are summarized in Theorems 1 and 2. Theorem 1 establishes the existence of the value and saddle point of the game in the classes of strategies with memory of motion history (6), (7). Theorem 2 gives a sufficient condition for achieving the value and saddle point of the game on the strategies without memory (20), (21). This condition is the positional structure (28)–(30) of the quality index. The key point here is the appropriate modification of the method of extremal shift (25)–(27) for constructing the corresponding optimal strategies.

The greatest progress in numerical methods for solving such differential games was achieved in the linear-convex case. In the paper, we focused on the so-called upper convex hulls method. It is based on the recurrent construction of the upper convex hulls of certain auxiliary functions and allows to compute the value of the game and the optimal strategies of the players. Firstly, we described this method for the games with terminal–integral quality index (33) (see Propositions 1 and 2). Then, we showed that it can be applied for the games with non-terminal quality index (37) (see Proposition 3) and gave its reduction for the case of positional quality index (43) (see Propositions 4 and 5). The upper convex hulls method is quite complicated. Nevertheless, it can be numerically realized on modern computers. To illustrate this, we considered the example in Sect. 8. Let us note that the most time-consuming part of the computations is constructing the upper convex hulls $\varphi ^\pm _j(m),$$m \in G_j^\pm ,$$j = \overline{1, k + 1},$ according to the procedure (45)–(50). After this is done, all simulations of the game process can be performed in real time.