# An Approach for Solving Discrete Game Problems with Total Constraints on Controls

Authors: Asqar Raxmonov; Gafurjan I. Ibragimov
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

We consider a linear pursuit game of one pursuer and one evader whose motions are described by different-type linear discrete systems. Controls of the players satisfy total constraints. Terminal setM is a subset of ℝn and it is assumed to have nonempty interior. Game is said to be completed if yk-xk∈M at some step k. To construct the control of the pursuer, at each step i, we use positions of the players from step 1 to step i and the value of the control parameter of the evader at the step i. We give sufficient conditions of completion of pursuit and construct the control for the pursuer in explicit form. This control forces the evader to expend some amount of his resources on a period consisting of finite steps. As a result, after several such periods the evader exhausted his energy and then pursuit will be completed.


---

## Body

## 1. Introduction

A large number of works are devoted to differential games where the position of the players changes continuously in time (see, e.g., [1–18]). Zero-sum differential games were first considered in the book of Isaacs [5] who derived the main equation of the theory of differential games. Though the Isaacs method is not complete (since the main equation may not have classical solutions or may have infinitely many generalized solutions [18]) he effectively applied it to solve many interesting game problems.Krasovskiĭ and Subbotin [7] and Pontryagin [10] proposed two different formalizations for differential games. According to Pontryagin we have to identify ourselves with the pursuer in pursuit games and with the evader in evasion games. Many approaches have been proposed in literature to solve differential game problems under the integral constraints (see, e.g., [1–4, 6, 8, 9, 11–15, 17]).In the present paper, we study a linear pursuit game with total constraints on controls. Such constraints are discrete analogues of integral constraints for differential games. There are a few papers that study discrete games under total constraints (see, e.g., [14–16, 19–22]).In the linear discrete game studied by Satimov et al.  [14] , the eigenvalues of the main matrix are assumed to be real. Some sufficient conditions of completion of pursuit were obtained in this paper. In the paper of Satimov et al. [15], motions of players are simple. It was a starting point for multiperson differential games with integral constraints. Some sufficient conditions were obtained for the game to be terminated.In the paper of Ibragimov [20], a discrete game described by the equation
(1)x(k+1)=Ax(k)-u(k)+v(k)
is studied. Control of the evader satisfies total constraint. There are two game problems that are considered. In the first game, the control of the pursuer satisfies geometric constraint, and in the second it satisfies total constraint. Sufficient conditions of completion of game from any position were obtained.Azamov and Kuchkarov [19] studied relationship between 0-controllability of linear discrete systems
(2)x(k+1)=Ax(k)+Bu(k)
and completion of linear pursuit discrete game described by the equation
(3)z(k+1)=Az(k)+Bu(k)+Cv(k).
The control of the pursuer is subjected to geometric constraint and that of the evader is subjected to total constraint. Necessary and sufficient conditions were obtained under which solvability of 0-controllability is equivalent to completion of pursuit.Kuchkarov et al. [22] studied a discrete game whose position z(k+1)∈ℝn is described by the above equation. Different from the above game, both controls of the players are subjected to total constraints. They proved that if eigenvalues of the matrix A in absolute value are less than 1 and dim⁡BS=n, where S is unit ball in ℝn centered at the origin, then pursuit can be completed from any initial position. This result much more improves the result of the work by Ibragimov and Kuchkarov [21].In the present paper, we study a linear pursuit discrete game of one pursuer and one evader. It is assumed that total constraints are imposed on controls of players. The main point in the pursuit method is that, in one step, the pursuer forces the evader to expend a certain amount of his resources to prevent the game from being completed. Therefore, after finite times of such steps the resources of the evader will be exhausted, and then pursuit will be completed. We obtain sufficient conditions of completion of pursuit.


## 2. Statement of the Problem

In the Euclidian spaceℝn, we consider a discrete game described by the following equations:
(4)x(k)=Ax(k-1)+u(k),(5)y(k)=By(k-1)+v(k),
where x,y,u,v∈ℝn,n≥1,A and B are n×n constant matrices, and u (resp., v) is control parameter of the pursuer (evader). The parameters u and v are chosen in the form of sequences as follows:
(6)u=u(·)={u(1),u(2),…,u(k),…},v=v(·)={v(1),v(2),…,v(k),…}
and subjected to the following constraints:
(7)∥u(·)∥l2≤ρ,(8)∥v(·)∥l2≤σ,
where ρ and σ are positive numbers. The pursuer and evader move according to (4) and (5), respectively. In the space ℝn, a terminal set M, whose interior is not empty, is defined. The condition int⁡M≠Ø implies that there are a number ℓ>0 and vector m∈M to satisfy the inclusion ℓS⊂-m+M. The purpose of the pursuer is to realize the inclusion
(9)y(k)-x(k)∈M
at some finite step k, and that of the evader is opposite.Definition 1.
A sequenceu=u(·) (resp., v=v(·)) subjected to the constraint (7) (resp., (8)) is called admissible control of the pursuer (evader).Definition 2.
If for any admissible control of the evaderv=v(·)={v(1),v(2),…,v(k),…} one can construct an admissible control of the pursuer u(·)={u(1),u(2),…,u(k),…} such that for the solutions
(10)x=x(·)={x(1),x(2),…,x(k)},y=y(·)={y(1),y(2),…,y(k)}
of (4) and (5) with the initial positions z0=(x0,y0), where x(0)=x0, y(0)=y0, y0-x0∉M, and controls u(·),v(·) the inclusion (9) is satisfied at some k≤N(z0), then we say that pursuit starting from the position z0 can be completed in the game (4), (5) for N=N(z0) steps. Here, we assume that the pursuer uses v(k) to construct u(k), k≥1.
Problem. Find sufficient conditions, under which pursuit can be completed from any initial position z0=(x0,y0),x0,y0∈ℝn, y0-x0∉M.


## 3. Main Result

In this section, we formulate and prove the main result of the paper. First of all, we state our basic assumption. Let the norm of the matrixA be defined by ∥A∥=max⁡|x|=1|Ax|.Assumption 3.
There exist numbersρ1>0, ρ2>0, d>0, 0≤α1<1, 0≤α2<1/2, a positive integer m, and vector m1∈M such that ρ1+ρ2=ρ and(1)
for anyx,y∈ℝn, y-x∉M, there exists a step k=k(x,y)>0 such that
(11)-m1+Bky-Akx∈ρ1m·k(Ak-1+Ak-2+⋯+E)S;(2)
there exist linear operatorsF(k,i):Rn→Rn, 1≤i≤k, such that for any k≥1 the following inequalities hold true:
(a)
∑i=1k∥Bk-i-Ak-iF(k,i)∥2≤dmα1,(b)
∥F(k,i)∥≤ρ2/(σ·mα2), 1≤i≤k;(3)
m·min⁡{σ2/m1-2α2,ℓ2/(d·mα1)}>σ2.Under this assumption we prove the following statement.Theorem 4.
If Assumption3 holds, then pursuit can be completed in the game (4), (5) from any initial position z0=(x0,y0),x0,y0∈ℝn, y0-x0∉M, for a finite step.Proof.
Lety0-x0∉M. Then it follows from condition (1) of Assumption 3 that there exists k1=k1(x0,y0)>0 such that
(12)-m1+Bk1y0-Ak1x0∈ρ1m·k1×(Ak1-1+Ak1-2+⋯+A+E)S.
Consider the equation
(13)(Ak1-1+Ak1-2+⋯+A+E)w=-m1+Bk1y0-Ak1x0,
with respect to the unknown vector w∈(ρ1/mk1)S. According to (12), (13) has a solution. Let w=w^ be the lexicographically minimum solution of (13).
We now construct a control for the pursuer. Let the evader use an arbitrary admissible controlv=v(·)={v(1),v(2),…,v(k),…}; that is, behavior of the evader is any.
By Definition2, the pursuer may use v(i) to construct u(i) on each step i. Set
(14)u(i)=F(k1,i)v(i)+w,^i=1,2,…,
while
(15)∑i=1k|v(i)|2<σ2m1-2α2,
where k is an integer. Then it is natural to consider the following three cases.
Case
1. The inequality (15) holds for all k∈{1,2,…k1}.
Case
2. At some k=n1, n1<k1, the inequality sign in (15) turns to equality.
Case
3. At some k=n1-1, n1<k1, the inequality (15) holds, but at k=n1 it fails to hold and opposite inequality holds:
(16)∑i=1n1|v(i)|2>σ2m1-2α2.
It follows from (4) and (5) that for the solutions x(k) and y(k) corresponding to the initial position (x0,y0) and control (14) we obtain
(17)y(k)-x(k)=Bky0-Akx0+∑i=1k(Bk-iv(i)-Ak-i(F(k1,i)v(i)+w^))=Bky0-Akx0+∑i=1k(Bk-i-Ak-iF(k1,i))v(i)+∑i=1kAk-iw^.
In Case 1, since w^ is a solution of (13), it follows from (17) at k=k1 that
(18)-m1+y(k1)-x(k1)=-m1+Bk1y0-Ak1x0-(Ak1-1+Ak1-2+⋯+A+E)w^+∑i=1k1(Bk1-i-Ak1-iF(k1,i))v(i)=∑i=1k1(Bk1-i-Ak1-iF(k1,i))v(i).
Next, if pursuit is not completed in the game (4), (5) at the step k1, then in view of (18) we obtain
(19)|-m1+y(k1)-x(k1)|=|∑i=1k1(Bk1-i-Ak1-iF(k1,i))v(i)|>ℓ.
Then using the Cauchy-Schwartz inequality and condition (5) (a) of Assumption 3 yields
(20)ℓ<|∑i=1k1(Bk1-i-Ak1-iF(k1,i))v(i)|<(∑i=1k1∥Bk1-i-Ak1-iF(k1,i)∥2)1/2·(∑i=1k1|v(i)|2)1/2≤(d·mα1)1/2·(∑i=1k1|v(i)|2)1/2.
Hence,
(21)∑i=1k1|v(i)|2>ℓ2(d·mα1).
Clearly, if inequality (19) is not satisfied, then pursuit starting from the initial position z0=(x0,y0), y0-x0∉M, is completed on the step k1 in the game (4), (5). Therefore, assuming that pursuit is not completed up to the step k1 in the game (4), (5), which implies inequalities (19) and (21), we conclude that the evader must expend the resources greater than ℓ2/(d·mα1) for the steps 1,…,k1.
In Case 2, the evader expends resources equal toσ2/(m1-2α2) for the steps 1,…,n1.
We turn to Case 3. Since inequality (15) is satisfied at k=n1-1 and (16) is satisfied at k=n1, then
(22)∑i=1n1-1|v(i)|2+1d12|v(n1)|2=σ2m1-2α2
at some d1>1. Define the value u(n1) of the pursuer’s control as follows:
(23)u(n1)=F(k1,n1)(1d1v(n1))+w^.
Admissibility of the pursuer’s control will be shown later. Thus, in Case 3, to guarantee that pursuit is not completed up to the step n1, the evader must expend resources greater than σ2/m1-2α2.
The process of the game up to the stepk1 in Case 1 and up to the step n1 in Cases 2 and 3 will be referred to as the process of first approach of the pursuer to evader.
We now calculate the amount of resources expended by the pursuer on the process of the first approach.
In Case 1, using the Minkowski inequality, we obtain from (14) that
(24)∑i=1k1|u(i)|2=∑i=1k1|F(k1,i)v(i)+w^|2≤[(∑i=1k1|F(k1,i)v(i)|2)1/2+(∑i=1k1|w^|2)1/2]2.
In Case 2, in view of (14) we have
(25)∑i=1n1|u(i)|2=∑i=1n1|F(k1,i)v(i)+w^|2≤[(∑i=1n1|F(k1,i)v(i)|2)1/2+(∑i=1n1|w^|2)1/2]2.
In Case 3, we use (14) and (23) to estimate the resources of the pursuer. Since d1>1, using the Minkowski inequality, we see that
(26)∑i=1n1|u(i)|2=∑1n1-1|F(k1,i)v(i)+w^|2JJJJ+|F(k1,n1)(1d1v(n1))+w^|2≤[(∑i=1n1|w^|2)1/2(∑i=1n1-1|F(k1,i)v(i)|2hhhhhh+1d12|F(k1,n1)v(n1)|2)1/2kk+(∑i=1n1|w^|2)1/2]2≤((∑i=1n1|F(k1,i)v(i)|2)1/2+(∑i=1n1|w^|2)1/2)2.
Similarly, according to condition (5) (b) of Assumption 3 and the fact that w^∈(ρ1/mk1)S, n1<k1, the right-hand sides of inequalities (24)–(26) can be estimated from the above by ρ2/m. For example, the right-hand side of (24) is estimated as follows:
(27)[(∑i=1k1∥F(k1,i)∥2·|v(i)|2)1/2+(∑i=1k1|w^|2)1/2]2≤[ρ2σmα2(∑i=1k1|v(i)|2)1/2+ρ1m]2≤(ρ2σ·mα2·σm1-2α2+ρ1m)1/2=ρ2m.
Therefore,
(28)∑i=1k1|u(i)|2≤ρ2minCase1,∑i=1n1|u(i)|2≤ρ2minCases2and3.
We conclude from these estimations that if pursuit is not completed in the game (4), (5) during the process of first approach, the amount of resources expended by the evader is greater than or equal to min⁡{σ2/m1-2α2,ℓ2/(d·mα1)}, and that expended by the pursuer does not exceed ρ2/m.
Further, we continue as follows. In Case 1, the pointsx01=x(k1),y01=y(k1) will be taken as the initial position at k1, and in Cases 2 and 3, the points x01=x(n1),y01=y(n1) will be taken as the initial position at n1. We now consider (4), (5) with the initial position (x01,y01) for the steps k=1,2,….
Given the initial position(x01,y01), y01-x01∉M, we find the least integer k2=k2(x01,y01)>0 such that
(29)-m2+Bk2y01-Bk2x01∈ρ1mk2hhhhhhhhhhhhhhh×(Ak2-1+Ak2-2+⋯+A+E)S,
at some m2∈M. Existence of such k2 is guaranteed by condition (1) of Assumption 3.
Letv=v(i), 1≤i≤k2, be an arbitrary control of the evader. For the steps i∈{1,…,k2}, we define the control of the pursuer u=u(i) by (14), with k1 replaced by k2 while the inequality (15) holds.
We apply the above argument again. If pursuit is not completed in the game (4), (5) during the process of second approach, then the amount of resources expended by the evader is not less than min⁡{σ2/m1-2α2,ℓ2/(d·mα1)}, and that expended by the pursuer is less than ρ2/m.
Now,m-time repeated application of this reasoning enables us to conclude that at most at the mth process of approach pursuit is completed in the game (4), (5).
Indeed, assuming the contrary we have(30)σ2≥∑j=1m(∑i=1kj|v(i)|2)≥∑j=1mmin⁡{ℓ2d·mα1,σ2m1-2α2}=m·min⁡{ℓ2d·mα1,σ2m1-2α2},
which contradicts condition (3) of Assumption 3.
However foru=u(·) we have ∑j=1m∑i=1kj|u(i)|2≤∑j=1m(ρ2/m)=ρ2. The proof is complete.Remark 5.
Let condition(2) of Assumption 3 hold for m=1 and d<ℓ2/σ2. Then conditions (1) and (3) of Assumption 3 can be weakened. More precisely, we require the inclusion y0-x0∈M and drop condition (3). Then Theorem 4 guarantees that pursuit can be completed only from the initial points x0,y0.Example 6.
Consider a discrete game described by equations(31)xk=λxk-1+uk,yk=λyk-1+vk,
where xk,yk,uk,vk∈Rn, n≥1. Let u=(u1,u2,…,uk,…), v=(v1,v2,…,vk,…), and
(32)∥u(·)∥l2≤ρ,∥v(·)∥l2≤σ.The terminal set isM={x,y∣x,y∈Rn,y-x∈lS,l>0}. For this example, B=A=λE. Applying Theorem 4 to the game (31) and (32), we obtain the following statement.Assertion 1.
Ifρ>σ and |λ|≤1, then pursuit can be completed in the game (31) and (32) from any initial positions in finite number of steps.Proof of assertion is straightforward if we takeF(k,i)=E, m=1, ρ=ρ1+ρ2, ρ1>0, ρ2>σ, and α1=α2≠0, and d>0 is sufficiently small number. For Assertion 1 we used Remark 5.


## 4. Conclusion

We have obtained sufficient conditions of completion of pursuit for a linear pursuit discrete game with total constraints where motions of the players are described by different-type linear equations. The control parameter of the pursueru(k) is constructed based on v(k).It should be noted that conclusion of Theorem4 is still true with appropriate changes if controls u=u(·) and v=v(·) are subjected to constraints ∥u(·)∥lp≤ρ and ∥v(·)∥lp≤σ, p>1. Further studies can be done to weaken conditions of Assumption 3.



---

*Source: 674651-2014-04-17.xml*