A linear control system describing the deviation from a rated trajectory is considered. The state vector is unobserved and the controller can watch only an output with disturbances constrained in LQ-norm. Using the theory of guaranteed estimation, the controller (1st player) builds informational sets and tries to minimize the payoff functional depending of the informational set at the end of observation process. The second player (an opponent) choosing the disturbances intends to prevent the controller and tries to maximize the functional. The situation is reduced to a differential game with complete information where the players are used the positional strategies depending on parameters of informational sets. An example with a flying vehicle is examined.
containing an uncertain function v(·) and a control u(·), where A(·), B(·), C(·), G(·), c(·) are bounded Borelean matrices. The unobserved state vector x(t) ∈ Rn, the output y(t) ∈ Rm, u(t) ∈ Rp, v(t) ∈ Rk. Suppose that the uncertain function v(·) in (1) and (2) is constrained by the inequality x˙ (t) = A(t)x(t) + B(t)u(t) + C(t)v(t), y(t) = G(t)x(t) + c(t)v(t), t ∈ [0, T ], c(t)c′(t) ≥ δIm, ∀t ∈ [0, T ],
Consider linear non-stationary equations (1) (2) (3) (4) (5) where | · | is the Euclidean norm. Besides, the matrix c(·) must satisfy the condition where δ > 0 and Im ∈ Rm×m is the identity matrix. Hereafter the symbol ′ means the transposition. According to general theory of guaranteed estimation [Kurzhanski & Varaiya, 2014], we give De nition 1 The collection XT (u, y) of state vectors {x(T )} is said to be the informational set if for any x ∈ XT (u, y) there exists a function v(·) satisfying (3) such that equality (2) holds a.e.
Denote by C(t) the matrix (c(t)c′(t))−1. Under assumption (4) we have the equalities v(t) = c′(t)w(t) + C1(t)f (t) and ∥v(·)∥2 = ∥c′(·)w(·)∥2 + ∥C1(·)f (·)∥2, where C1(t) = Ik − c′(t)C(t)c(t) is the orthogonal projection on the subspace ker c(t). Using (2), we may rewrite inequality (3) as ∫ T{ 0
|y(t) − G(t)x(t)|2C(t) + |f (t)|2C1(t)}dt ≤ 1.
From now on, the symbol |x|2Q means x′Qx, where Q is a symmetrical and non-negatively defined matrix.
It is easily seen that x ∈ XT (u, y) iff there exists a function f (·) satisfying (5) and subjecting to the equation x˙ (t) = A(t)x(t) + B(t)u(t) + C(t)(C1(t)f (t) + c′(t)C(t)(y(t) − G(t)x(t))) with final condition x(T ) = x. On the other hand, such a function exists iff the minimum on f (·) of the left-hand side of inequality (5) is less or equal 1. To find this minimum we use the Bellman equation for an equation with a cost functional For any end position {t, x} we find x˙ = f (t, x, v), v(t) ∈ P, t ∈ [0, T ], x(T ) = xT ,
Jt = min {L(t, x, v) − Jxf (t, x, v)}, J (0, x) = ϕ(x).
v∈P Let the solution J (t, x) of Bellman’s equation be continuous in t, x and differentiable in x. Then it gives the minimum of the functional. This fact is sufficient for us. Note that there is a more advanced theory of viscosity solutions, [Fleming & Soner, 2006]. Trying to solve the Bellman’s equation with a quadratic form |x|2P (t) − 2d′(t)x + q(t), we come to the conclusion. Lemma 1 The informational set has the form XT (u, y) = {x ∈ Rn : |x|2P (T ) − 2d′(T )x + q(T ) ≤ 1}, where parameters may be found from equations
P˙ (t) = −P (t)A(t) − A′(t)P (t) − P (t)C(t)C′(t)P (t) + (G(t) + c(t)C′(t)P (t))′C(t)(G(t) + c(t)C′(t)P (t)), d(t) 2P −1(t) which satisfy the equations If the matrix P (t) is invertible on (0, T ], we can introduce the values xˆ(t) = P −1(t)d(t) and h(t) = q(t) − xˆ˙(t) = A(t)xˆ(t) + (c(t)C′(t) + G(t)P −1(t))′C(t)(y(t) − G(t)xˆ(t)) + B(t)u(t),
h˙(t) = y(t) − G(t)xˆ(t) 2C(t). 3
Let the observer (the 1st player) begin their control actions at the instant t0 > 0, t0 < T , and (6) (7) (8) (9) (10) (11) (12) where P is a compact set. If Assumption 1 holds (from now on, we suppose this) and u ≡ 0 on [0, t0), the observer can build the compact ellipsoidal informational set X0 = Xt0 (0, y) = {x ∈ Rn : |x − xˆ(t0)|2P (t0) ≤ 1 − h(t0)} at the instant t0 according to equations (6)–(8). The goal of the observer is to minimize the functional where γ(·) is a non-negative continuous function defined on all compact sets in Rn. The continuity is understood in the sense of Hausdorff’s convergence. For example, γ(X) = diam X = maxx;y∈X |x − y| or γ(X) = maxx∈X |x|. In our case, diam XT (u, y) = 2√(1 − h(T ))|P −1(T )|, where |P | = max|x|≤1 |P x|, does not depend on control { } u(·). The value maxx∈XT (u;y) |x| = max|l|≤1 l′xˆ(T ) + √1 − h(T )|l|P −1(T ) .
It can turn out that h(t0) = 1. In this case the resource of disturbances is exhausted and we have v(t) = 0 for t ≥ t0. If so, we obtain x(t0) = xˆ(t0) and y(t) ≡ G(t)xˆ(t) for t ≥ t0. Our problem reduces to the ordinary control one for a linear system (9) with complete information on state vector. If h(t0) < 1, we obtain more complicated situation. It is easily seen from equations (9), (10), that the evolution of informational set Xt(u, y) depends only on the control u(·) and the innovation function w(t) = y(t) − G(t)xˆ(t) that satisfies the LQ-constraints The value xˆ(T ) is the center of bounded ellipsoid XT (u, y). A simple sufficient condition for invertibility of matrix P (t) on (0, T ] is the following.
Assumption 1 The solutions W (t, τ ) of matrix differential equation
∂W (t, τ )/∂t = A′(t)W (t, τ ) + W (t, τ )A(t) + G′(t)G(t), W (τ, τ ) = 0, is positive-definite for all 0 ≤ τ < t ≤ T .
It is well-known
The calculation of value h(t) is extremely unstable. Practically, one can take a small matrix P0 > 0 and solve equations (9), (10) with zero initial data. If h(t) from (10) is grater 1, one needs to take a smaller matrix. Another way to overcome this difficulty is to set ν0 = 0. This increases a bit the initial set at instant t0. u(t) ∈ P ⊂ Rp,
γ(XT (u, y)), We introduce the 2nd player (an opponent) who tries to maximize the functional (11) choosing the function w(t) under constraints (12). Thus, we have a differential game for equations
xˆ˙(t) = A(t)xˆ(t) + B(t)u(t) + C(t)w(t), ν˙ (t) = − w(t) 2C(t), where ν(t) = 1 − h(t) ≥ 0, C(t) = (c(t)C′(t) + G(t)P −1(t))′C(t). The initial states xˆ(t0), ν(t0) = 1 − h(t0), for equations (13) are known from (6)–(8). Note that max diam XT (u, y) = 2√ν(t0)|P −1(T )| is obtained under w(t) = 0 if t ≥ t0. In the common case, we can consider that
γ(XT (u, y)) = σ(xˆ(T ), ν(T )), where σ(·, ·) is a continuous bounded function. Introduce the vector z(t) = [xˆ(t); ν(t)] ∈ Rn+1, t ∈ [t0, T ], ν(t) ∈ [0, 1]. The pair {t, z(t)} is called a position of the game at the instant t. Let us rewrite system (13) once more: z˙(t) = A(t)z(t) + B(t)u(t) + g(t, w(t)), (13) (14) (15) where A(t) = [A(t), 0; 01×n, 0], B(t) = [B(t); 01×p], g(t, w) = notation from Matlab, where [A1, . . . , Ak] means the row-concatenation of matrices of appropriate dimensions (sometimes, the comma is replaced by the blank), and [A1; . . . ; Ak] means the column-concatenation.
Let us remark yet that the function σ(z) in terminal functional (14) may be considered Lipschitzean on Rn+1. It is fulfilled in many interesting cases. [
] C(t)w; −|w|2C(t) . Hereafter we use the standard 4
A strategies of players are defined as arbitrary functions u(t, z) ∈ P and w(t, z, u) with the condition ν ∈ [0, 1]. For any admissible position {t∗, z∗}, where ν∗ ∈ (0, 1], the players independently choose the different partitions ∆u and ∆w = {t∗ = t1 < · · · < tk+1 = T }. Let any Borelean control u(·) ∈ P be already fixed. Then the motion is defined for the interval [ti, ti+1) from the partition ∆w as the solution of the stepwise differential equation (see eq. (15))
z˙(t) = A(t)z(t) + B(t)u(t) + g(t, w(ti, z(ti), u(ti))).
If for some index i∗ ∈ 1 : k there is an instant t∗ ∈ [ti∗ , ti∗+1) such that ν(t∗) = 0, then the resource of 2nd player is exhausted, and we set w(t) = 0 for t ∈ [t∗, T ]. On the other hand, if any Borelean function w(·) such that ν(t) ≥ 0, ∀t ∈ [t∗, T ], is fixed, then the motion is defined for the interval [ti, ti+1) from the partition ∆u as the solution of the stepwise differential equation
z˙(t) = A(t)z(t) + B(t)u(ti, z(ti)) + g(t, w(t)).
For strategies u(·), w(·), and a position {t∗, z∗}, introduce the values c(u(·), t∗, z∗) = lim sup sup σ(z(T )), c(w(·), t∗, z∗) = lim inf inf σ(z(T )), →0 ∆u w[·] →0 ∆w u[·] (16) where δ = |∆u| or δ = |∆w| and |∆| is a diameter of the partition ∆. The supremum in (16) is taken over all admissible realizations w[·] or u[·]. Strategies u0(·), w0(·) are called optimal if c(u0(·), t∗, z∗) = inf c(u(·), t∗, z∗), c(w0(·), t∗, z∗) = sup c(w(·), t∗, z∗),
u(·) w(·) for any position {t∗, z∗}. In work [Lokshin, 1992], it is proved the existence of the optimal strategies u0(·), w0(·) such that
c(u0(·), t∗, z∗) = c(w0(·), t∗, z∗) = c0(t∗, z∗) for any position {t∗, z∗}. Here c0(t∗, z∗) is the value of the game and the pair {u0(·), w0(·)} is a saddle point. In [Lokshin, 1992], a method of computing of the value c0(t∗, z∗) is developed which based on a recurrent construction of concave envelopes for functions in auxiliary designs. In our paper, we use the method of HJBI equation. In addition, note that couterstrategies of 2nd player can be replaced by pure strategies with the same result.
For our problem we need to compute the value of the game c(t0, z0), where from now on, we omit the symbol 0 near c. Fix some N > 0 and temporarily impose an additional constraint on the function w(t): |w(t)| ≤ N . The corresponding optimal strategies and the value of the game are denoted by u0N (·), wN0 (·), and cN (t, z), respectively. For our temporarily case, in [Subbotin, 1999, Theorem 9.1] it was proved that the value of the game equals cN (t0, z0), where the function cN : [t0, T ] × Rn × [0, ν0] → R satisfies (in corresponding minimax formalization) the equation
∂cN (t, z)/∂t + HN (t, z, DcN ) = 0 with boundary condition cN (T, z) = σ(z), ν ∈ [0, ν0], as ν(T ) ≤ ν0. In equation (17) the symbol Dc means the generalized gradient of function c(t, z) with respect to variables z, and the Hamiltonian HN is defined by the following way
HN (t, z, l) = min max h(t, z, u, w˜, l), l = [l1; l2], w˜ = wχ(ν),
u∈P |w˜|≤N where h(t, z, u, w˜, l) = l1′(A(t)xˆ + B(t)u) + (l1′C(t)w˜ − l2|w˜|2C(t)); the Heaviside function χ(ν) = 1, if ν > 0, and χ(ν) = 0 otherwise. From now on, the function w˜(t) is called the control with switch. It is easily seen that lim HN (t, z, l) = H(t, z, l) = l1′A(t)xˆ + mu∈iPn l1′B(t)u + |l1|2C′(t)C−1(t)C(t)/(4l2)
N→∞
if ν > 0 and l2 > 0. For equation (17) it is known that its solution in minimax sense coincides with viscosity
solution
u∈P |w˜|≤N wN0 (t, z, u) ∈ Argmax h(t, z, u, w˜, DcN (t, z)).
|w˜|≤N We do the computation backward from right to the left. For i = K(∆) we have c∆(t, z) = min max {σ(z + (T − t)F (t, z, u, w˜)}, t ∈ [tK(∆), T ).
u∈P |w˜|≤N
With the help of this strategies we can built a stepwise approximate trajectory until the instant t∗, where the resource of the 2nd player is exhausted. After this instant the function w(t) = 0.
Unfortunately, we cannot assert the uniqueness and existence of solution in any sense if the function HN in (17) is replaced with H. But in [Lokshin, 1992] it is shown that the limit lim cN (t, z) = c(t, z)
N→∞ exists for any position {t, z} ∈ [t0, T ] × Rn × [0, 1] uniformly on {t, z}. Thus, equations (17), (18) and relation (19) gives a method of computing of the value of the game. 4.1
A numerical procedure can be built on the base of [Souganidis, 1985, Souganidis, 1999, Fleming & Soner, 2006]. For technical reason the all the matrices in (1), (2) will be considered Lipschitzean in t. Then the left-hand side of equation (15) F (t, z, u, w) = A(t)z + B(t)u + g(t, w), where u ∈ P, |w| ≤ N , satisfies the uniform Lipschitz condition |F (t1, z1, u, w) − F (t2, z2, u, w)| ≤ C1(|z1 − z2| + |t1 − t2|). In addition, the function σ(z) from (14) is Lipshitzean, i.e. |σ(z1) − σ(z2)| ≤ C2|z1 − z2|.
For approximation of cN (t, z), we consider the partition ∆ = {t0 < t1 < · · · < tK(∆)+1 = T } of the interval [t0, T ]. The diameter maxi |ti+1 − ti| of the partition is denoted by |∆| as before. Define the function c∆ : [0, T ] × Rn × [0, ν0] → R as c∆(T, z) = σ(z) on Rn × [0, ν0], c∆(t, z) = min max {c∆(ti+1, z + (ti+1 − t)F (t, z, u, w˜)}, u∈P |w˜|≤N if t ∈ [ti, ti+1), and i ∈ 0 : K(∆).
Theorem 1 Under |∆| → 0, the function (20) converges to cN (t, z) locally uniformly on [t0, T ] × Rn × [0, ν0]. The function cN (t, z) is the unique solution of equation (17) in minimax or viscosity sense. Besides, there exists a constant L(C2, ||σ||, ||σz||), such that |c∆(t, z) − cN (t, z)| ≤ L|∆|1=2 for all (t, z) ∈ [t0, T ] × Rn × [0, ν0]. Here || · || is the sup-norm of corresponding function.
Let us introduce the attainability set W(t) of system (13) with support function ρ(l|W(t)) = max l′x = ρ(l|X(t, t0)X0) + x∈W(t) ρ(l|B(s)P)ds + ν0
|C′(s)l|2ds, ∫ t t0 √ ∫ t t0 and the union W = ∪t∈[t0;T ]W(t). The set W is compact. We can suggest the following Numerical Algorithm 1. Choose a finite set (a grid) N = {zk} ⊂ W × [0, ν0], k ∈ 1 : K1. 2. Select a partition ∆ = {t0 < t1 < · · · < tK+1 = T } of [0, T ]. 3. Form and remember the function σK (z) = min max σ(z + (tK+1 − tK )F (tK+1, z, u, w˜)) and corresponding u∈P |w˜|≤N optimal controls u∗K and w˜K∗ (u), where z ∈ N . 4. On subsequent steps the grid function is formed: σi(z) = min max σi+1(z + (ti+1 − ti)F (ti+1, z, u, w˜)) and u∈P |w˜|≤N corresponding optimal controls ui∗ and w˜i∗(u). If the value z + (ti+1 − ti)F (ti+1, z, u, w˜) does not lie in the grid, then this value is changed for the nearest element from N .
Before the calculation of σ0(z) we need to choose the sufficiently large number N . 5
Let us consider the rectilinear movement of an airplane in the vertical plane at h height: x1(nom) = L + V t, x2(nom) = h. The real initial state [x˜0; y˜0] may be differ from [L; h] and unknown. The deviation from the basic movement is described by the system
x˙ 1 = x3, x˙ 3 = u1, x˙ 2 = x4, x˙ 4 = u2, t ∈ [0, T ], where x1 = x˜1 − x1(nom), x2 = x˜2 − x2(nom), x3 = x˜3 − V , x4 = x˜4. The control accelerations are limited by the constraint u21 + u22 ≤ 10. The model of measurements is of the form y˜ = √(L − x˜1)2 + x˜22. Linearizing this with respect to basic movement, we obtain
y(t) = g1(t)x1 + g2(t)x2 + v(t), g1(t) = V t/√V 2t2 + h2, g2(t) = h/√V 2t2 + h2, where v(t) is a disturbance with the constraint ∫0T v2(t)dt ≤ 1. It is possible to check that the system is completely observable. Therefore, for any 0 < t0 < T the initial informational set X0 is bounded. Given numerical data: L = 2500 m, h = 10000 m, V = 1200 m/s, T = 30 s, we calculate the set X0 for t0 = 10 s, y(t) = g1(t)(−500 + 200t) + g2(t)(−1000 + 10t) + sin t/√20.
Here A = [0, 0, 1, 0; 0, 0, 0, 1; 0, 0, 0, 0; 0, 0, 0, 0], B = [0, 0; 0, 0; 1, 0; 0, 1], C(t) = 04×1, G(t) = [g1(t), g2(t), 0, 0], c(t) = 1. Let us write system (6)–(8):
P˙ (t) = −P (t)A − A′P (t) + G′(t)G(t), P (0) = 0; d˙(t) = −A′d(t) + G′(t)y(t) + P (t)Bu(t), d(0) = 0;
q˙(t) = y2(t) + 2d′(t)Bu(t), q(0) = 0.
For t0 = 10 we get xˆ0 ≈ [2331; −1898; 200; −89], h(t0) = 0.3574. The diameter of initial set equals 29.0228. To the end of time interval it increases to 143.2507 and does not depend of the control of 1st player. Of course, the { } control of 2nd player must be zero. Let σ(z) = max|l|≤1 l′xˆ(T ) + √1 − h(T )|l|P −1(T ) , i.e. we minimize the maximal deviation. We have P −1(T ) = [1003, −3594, 1, −120; −3594, 12902, −2, 431; 1, −2, 0, 0; −120, 431, 0, 14]. Using Numerical Algorithm and setting ν0 = 0, we obtain the value of the game as c(t0, z0) = 71.3471. More detail consideration of this example will be done in subsequent works. A control problem for non-stationary linear systems is considered. These systems as a rule describe the deviation from a rated trajectory. According to the output a controller builds the informational set containing the real state vector and tries to minimize the functional of final informational set. A 2nd player using disturbances tries to disturb the 1st player and maximizes the functional. The situation is reduced to a differential game with complete information for linear differential equation describing the evolution of center of informational ellipsoid. To solve this problem we use the theory of differential games. An approximation of the value of the game may be found by integration of corresponding HJBI equation, the solution of which is understood in a generalized sense. The optimal strategies are also defined due to this solution. The numerical approximation is specified and the estimation of the rate of convergence is given for the approximating scheme. An example with a rectilinear movement of an airplane is examined.
This work was supported by Russian Science Foundation (RSF) under Project No. 16-11-10146.