# Linear Discrete Pursuit Game with Phase Constraints

Authors: Asqar Raxmanov; Gafurjan Ibragimov
Journal: The Scientific World Journal
 (2014)

---

## Abstract

We consider a linear pursuit game of one pursuer and one evader whose motions are described by different-type linear discrete systems. Position of the evader satisfies phase constraints:y
∈
G, where G is a subset of R
n. We considered two cases: (1) controls of the players satisfy geometric constraints, and (2) controls of the players satisfy total constraints. Terminal set M is a subset of R
n and it is assumed to have a nonempty interior. Game is said to be completed if y
k
-
x
(
k
)
∈
M at some step k; thus, the evader has not the right to leave set G. To construct the control of the pursuer, at each step i, we use the value of the control parameter of the evader at the step i. We obtain sufficient conditions of completion of pursuit from certain initial positions of the players in finite time interval and construct a control for the pursuer in explicit form.


---

## Body

## 1. Introduction

A number of works were devoted to investigate differential and discrete pursuit games with various constraints on controls (see, e.g., [1–8]). Differential games with phase constraints on a position of one or several players are studied in many works (see, e.g., [9–18]). Most of these works were devoted to studying simple motion pursuit-evasion game problem. For example, in [10], an evasion problem is solved, when the evader moves on a curve and the pursuer moves on the plane. In this work, it is assumed that the maximum speed of the pursuer is equal to 1, and the maximum speed of the evader is more than 1. In the work [11], a simple motion pursuit-evasion game problem of many pursuers and one evader is considered on a compact set. The main result of this paper is estimation for guaranteed pursuit time. The work [12] is devoted to studying a game problem on a convex closed set when controls of players satisfy total constraints. In [13], simple motion pursuit game problem is solved for all initial positions of space when the maximum speeds of players are equal and the evader moves on a convex bounded set with nonempty interior. In [15], sufficient conditions of completion of pursuit are obtained for a linear differential game when the evader moves in a bounded convex set.In [16], the case, where the terminal and control sets are convex compact sets, is studied. In [17], necessary and sufficient conditions of solvability of the evasion problem in a convex polyhedron were received.In the present paper, we consider a linear discrete pursuit game of one pursuer and one evader. We will study both total and geometric constraints on controls of players under assumption that the terminal setM consists of an interior point in R
n. The evader can move only in a given bounded convex set. Some sufficient conditions of completion of pursuit have been obtained.


## 2. Statement of the Problem

Consider a discrete game described by the equations(1)
x
(
k
)
=
A
x
(
k
)
+
U
(
k
)
,
(2)
y
(
k
)
=
B
y
(
k
-
1
)
+
V
(
k
)
,wherex
,
y
,
u
,
v
∈
R
n, n
≥
1, k
=
1,2
,
…
,
k is step number, A
,
B are constant square matrices of order n, and U and V are control parameters of the pursuer and evader, respectively. Control parameters U and V are constructed in the form of sequences U
=
U
(
·
)
=
{
U
(
1
)
,
U
(
2
)
,
…
,
U
(
k
)
,
…
} and V
=
V
(
·
)
=
{
V
(
1
)
,
V
(
2
)
,
…
,
V
(
k
)
,
…
} which satisfy the following geometric constraints:
(3)
|
U
(
k
)
|
≤
ρ
,
ρ
>
0
,
(4)
|
V
(
k
)
|
≤
σ
,
σ
>
0
,or the total constraints(5)
∑
k
=
1
∞
|
U
(
k
)
|
2
<
ρ
1
2
,
(6)
∑
k
=
1
∞
|
V
(
k
)
|
2
<
σ
1
2
.The pursuer moves according to (1) with control parameter U, and the evader moves according to (2) with control parameter V. The purpose of the pursuer is inclusion realization:
(7)
y
(
k
)
-
x
(
k
)
∈
M
,for some final stepk, and the evader’s purpose is opposite. State of the evader is subjected to constraint y
∈
G, where G is a bounded convex set in R
n. It is assumed that the terminal set M is a subset of R
n and it has nonempty interior. The condition int
⁡
M
≠
Ø implies that there are a number l
>
0 and vector m
∈
M to satisfy the inclusion l
S
⊂
-
m
+
M, where S is the ball of radius 1 centered at the origin. Since G is a bounded convex set, there exists a number R
>
0 such that G
⊂
R
S.Definition 1.
Admissible control of the pursuer (evader) is defined as a sequenceU
=
U
(
·
)
(
resp
.
V
=
V
(
·
)) that satisfies the constraint (3) (or (5)) (resp., (4) (or (6))).Definition 2.
A sequence(8)
U
=
(
U
(
1
)
,
U
(
2
)
,
…
)
,
U
(
k
)
=
U
(
x
(
k
)
,
y
(
k
)
,
V
(
k
)
)
,
U
(
k
)
:
R
3
n
⟶
R
n
,
where V
=
(
V
(
1
)
,
V
(
2
)
,
…
,
V
(
k
)
,
…
) is an admissible control of the evader, is called strategy of the pursuer in the games (1)–(4) or (1)-(2), (5)-(6).Definition 3.
If for an initial positionz
0
=
(
x
0
,
y
0
), y
0
-
x
0
∉
M, a strategy of the pursuer, and any admissible control of the evader the solutions of (1), (2)
(9)
x
=
x
(
·
)
=
{
x
(
1
)
,
x
(
2
)
,
…
,
x
(
k
)
,
…
}
,
y
=
y
(
·
)
=
{
y
(
1
)
,
y
(
2
)
,
…
,
y
(
k
)
,
…
}
satisfy the inclusion (7) at some k
≤
N
=
N
(
z
0
), then we say that pursuit can be completed for N steps.Problem 4.
Find sufficient conditions of completion of pursuit in the games (1)–(4).Problem 5.
Find sufficient conditions of completion of pursuit in the games (1)-(2), (5)-(6).


## 3. Main Result

### 3.1. The Case of Geometric Constraints

Assumption 6.
Let the following conditions be satisfied:(1)
B
=
A,
(2)
ρ
>
σ
/
α, where α
=
R
/
(
R
-
l
).Theorem 7.
Let Assumption6 hold and, for the position z
0, at some step k
=
N
(
z
0
), the inclusion
(10)
-
m
+
A
k
(
1
α
y
0
-
x
0
)
∈
(
ρ
-
σ
α
)
(
A
k
-
1
+
A
k
-
2
+
⋯
+
A
+
E
)
S
holds true. Then pursuit can be completed in the games (1)–(4) from initial position z
0 for N
(
z
0
) steps.Proof.
LetV
=
V
(
k
),  k
=
1,2
,
…, be an arbitrary admissible control of the evader. Set
(11)
U
(
k
)
=
1
α
V
(
k
)
+
w
,
where the vectorw
∈
(
ρ
-
(
σ
/
α
)
)
S will be specified later. Then for the solutions of (1), (2) with initial conditions x
(
0
)
=
x
0, y
(
0
)
=
y
0, we have
(12)
y
(
k
)
-
x
(
k
)
=
A
k
y
0
-
A
k
x
0
-
(
A
k
-
1
+
A
k
-
2
+
⋯
+
A
+
E
)
w
+
(
1
-
1
α
)
(
A
k
-
1
V
(
1
)
+
A
k
-
2
V
(
2
)
hhh
+
⋯
+
A
V
(
k
-
1
)
+
V
(
k
)
A
k
-
1
V
)
=
A
k
(
1
α
y
0
-
x
0
)
-
(
A
k
-
1
+
A
k
-
2
+
⋯
+
A
+
E
)
w
+
(
1
-
1
α
)
(
A
k
y
0
+
A
k
-
1
V
(
1
)
+
A
k
-
2
V
(
2
)
hhh
+
⋯
+
A
V
(
k
-
1
)
+
V
(
k
)
A
k
-
1
V
)
.
Consider the equation(13)
-
m
+
A
N
(
1
α
y
0
-
x
0
)
=
(
A
N
-
1
+
A
N
-
2
+
⋯
+
A
+
E
)
w
with respect to the unknown vectorw
∈
(
ρ
-
σ
/
α
)
S. It follows from the inclusion (10) that there exists a solution of (13). Denote it by w
~. In (12), letting w
=
w
~ and using y
∈
R
S we obtain at k
=
N that
(14)
|
-
m
+
y
(
N
)
-
x
(
N
)
|
≤
|
(
1
-
1
α
)
(
A
N
y
0
+
A
N
-
1
V
(
1
)
+
A
N
-
2
V
(
2
)
hhhhh
+
⋯
+
A
V
(
N
-
1
)
+
A
V
(
N
)
A
N
-
1
)
(
1
-
1
α
)
|
+
|
-
m
+
A
N
(
1
α
y
0
-
x
0
)
-
(
A
N
-
1
+
A
N
-
2
+
⋯
+
A
+
E
)
w
~
(
1
α
y
0
-
x
0
)
|
=
|
(
1
-
1
α
)
y
(
N
)
|
=
(
1
-
R
-
l
R
)
|
y
(
N
)
|
≤
l
R
R
=
l
.
Therefore,y
(
N
)
-
x
(
N
)
∈
M.
For the pursuit controlU
(
k
), we have
(15)
|
U
(
k
)
|
=
|
1
α
V
(
k
)
+
w
~
|
≤
1
α
|
V
(
k
)
|
+
|
w
~
|
≤
σ
α
+
(
ρ
-
σ
α
)
=
ρ
.
The proof is complete.Assumption 8.
Let the following conditions be satisfied:(1)
det
⁡
(
A
)
≠
0 and there exists a number d
>
0 such that ∥
(
A
k
)
-
1
B
k
∥
≤
d for any k
≥
1, where A
-
1 is the inverse of the matrix A and ∥
A
∥ is operator norm of the matrix A;
(2)
ρ
>
d
σ
/
α.Theorem 9.
Let Assumption8 hold and for the position z
0 there exists a step N
(
z
0
) such that at k
=
N
(
z
0
) the inclusion
(16)
-
m
+
1
α
B
k
y
0
-
A
k
x
0
∈
(
ρ
-
d
σ
α
)
(
A
k
-
1
+
A
k
-
2
+
⋯
+
A
+
E
)
S
holds true. Then pursuit can be completed in the games (1)–(4) from the initial position z
0 for N
(
z
0
) steps.Proof.
Let the pursuer use the following strategy:(17)
U
(
i
)
=
1
α
(
A
k
-
i
)
-
1
B
k
-
i
V
(
i
)
+
w
,
whereV
=
V
(
i
), i
=
1,2
,
…
,
k, k
>
1, is any admissible control of the evader, and w
∈
(
ρ
-
d
σ
/
α
)
S is specified later. Then for the solutions of (1), (2) with initial conditions x
(
0
)
=
x
0, y
(
0
)
=
y
0 we have
(18)
-
m
+
y
(
k
)
-
x
(
k
)
=
-
m
+
B
k
y
0
+
B
k
-
1
V
(
1
)
+
B
k
-
2
V
(
2
)
+
⋯
+
B
V
(
k
-
1
)
+
V
(
k
)
-
A
k
x
0
-
1
α
[
A
k
-
1
(
A
k
-
1
)
-
1
B
k
-
1
V
(
1
)
+
A
k
-
2
(
A
k
-
2
)
-
1
B
k
-
2
V
(
2
)
+
A
A
-
1
B
V
(
k
-
1
)
+
V
(
k
)
(
A
k
-
1
)
-
1
]
-
(
A
k
-
1
+
A
k
-
2
+
⋯
+
A
+
E
)
w
=
-
m
+
1
α
B
k
y
0
-
A
k
x
0
-
(
A
k
-
1
+
A
k
-
2
+
⋯
+
A
+
E
)
w
+
(
1
-
1
α
)
y
(
k
)
.
Consider the equation(19)
-
m
+
1
α
B
N
y
0
-
A
N
x
0
=
(
A
N
-
1
+
A
N
-
2
+
⋯
+
A
+
E
)
w
with respect to the unknown vectorw
∈
(
ρ
-
d
σ
/
α
)
S. It follows from the inclusion (16) of Theorem 9 that there exists a solution of (19). Let us denote it by w
˘. Since y
∈
G
⊂
R
S, letting w
=
w
˘ in (18), we obtain
(20)
|
-
m
+
y
(
N
)
-
x
(
N
)
|
=
(
1
-
1
α
)
|
y
(
N
)
|
≤
(
1
-
1
α
)
R
≤
l
.
Hence, pursuit can be completed in the games (1), (2). Next, for U
(
i
), i
≥
1, using the conditions (
1
), (
2
) of Assumption 8, we can see from (17) that
(21)
|
U
(
i
)
|
≤
1
α
|
A
(
N
-
i
)
-
1
B
N
-
i
V
(
i
)
|
+
|
w
^
|
≤
1
α
∥
A
(
N
-
i
)
-
1
B
N
-
i
∥
|
V
(
i
)
|
+
|
w
^
|
≤
1
α
d
σ
+
ρ
-
d
σ
α
=
ρ
.
Proof of Theorem9 is complete.


### 3.2. The Case of Total Constraints on Controls

Let us consider the games (1), (2) with total constraints (5)-(6) on controls.Assumption 10.
Let the following conditions be satisfied:(1)
B
=
A,
(2)
ρ
1
>
σ
1
/
α.Theorem 11.
Let Assumption10 hold, and for the position z
0 let the inclusion
(22)
-
m
+
A
k
(
1
α
y
0
-
x
0
)
∈
1
k
(
ρ
1
-
σ
1
α
)
(
A
k
-
1
+
A
k
-
2
+
⋯
+
A
+
E
)
S
be satisfied at some step k
=
N
(
z
0
). Then pursuit can be completed in the games (1), (2), (5), and (6) from the initial position z
0 for N
(
z
0
) steps.Proof.
LetV
=
V
(
k
), k
=
1,2
,
…, be any admissible control of the evader. Construct the strategy for the pursuer in the following form:
(23)
U
=
U
(
k
)
=
1
α
V
(
k
)
+
w
,
where w is a vector in (
1
/
N
)
(
ρ
1
-
σ
1
/
α
)
S which will be specified later. For the solutions x
(
k
)
,
y
(
k
), we have in view of (1), (2) that
(24)
y
(
k
)
-
x
(
k
)
=
A
k
(
y
0
-
x
0
)
-
(
A
k
-
1
+
A
k
-
2
+
⋯
+
A
+
E
)
w
+
(
1
-
1
α
)
(
A
k
-
1
V
(
1
)
+
A
k
-
2
V
(
2
)
hhhhh
+
⋯
+
A
V
(
k
-
1
)
+
V
(
k
)
A
k
-
1
)
=
A
k
(
1
α
y
0
-
x
0
)
+
(
A
k
-
1
+
A
k
-
2
+
⋯
+
A
+
E
)
w
+
(
1
-
1
α
)
(
A
k
y
0
+
A
k
-
1
V
(
1
)
+
A
k
-
2
V
(
2
)
hhhh
+
⋯
+
A
V
(
k
-
1
)
+
V
(
k
)
A
k
y
0
)
.
Consider the equation
(25)
-
m
+
A
N
(
1
α
y
0
-
x
0
)
=
(
A
N
-
1
+
A
N
-
2
+
⋯
+
A
+
E
)
w
with respect to the unknown vector w
∈
(
1
/
N
)
(
ρ
1
-
σ
1
/
α
)
S. According to (22), (25) has a solution. Denote by w
^ lexicographically minimum solution of (25). In (24), letting w
=
w
^ and using the condition y
∈
R
S, we have at k
=
N
(26)
|
-
m
+
y
(
N
)
-
x
(
N
)
|
=
|
(
1
-
1
α
)
y
(
N
)
-
m
+
A
N
(
1
α
y
0
-
x
0
)
-
(
A
N
-
1
+
A
N
-
2
+
⋯
+
A
+
E
)
w
^
(
1
-
1
α
)
y
(
N
)
|
=
|
(
1
-
1
α
)
y
(
N
)
|
=
(
1
-
R
-
l
R
)
|
y
(
N
)
|
≤
l
,
and therefore y
(
N
)
-
x
(
N
)
∈
M.
Next, we prove that if the evader’s controlV
=
V
(
k
), k
=
1,2
,
…
,
N, satisfies the constraint (6); then the pursuer’s control U
(
k
)
=
(
1
/
α
)
V
(
k
)
+
w
^, k
=
1,2
,
…
,
N, satisfies the constraint (5). Indeed, by the inclusion w
^
∈
(
1
/
N
)
(
ρ
1
-
σ
1
/
α
)
S and the Minkowski inequality we have
(27)
∑
k
=
1
N
|
U
(
k
)
|
2
=
∑
k
=
1
N
|
V
(
k
)
+
w
^
⌢
|
2
≤
[
(
1
α
2
∑
k
=
1
N
|
V
(
k
)
|
2
)
1
/
2
+
(
∑
k
=
1
N
|
w
^
⌢
|
2
)
1
/
2
]
2
≤
[
σ
1
α
+
1
N
(
ρ
1
-
σ
1
α
)
N
]
2
=
ρ
1
2
.
The proof is complete.Theorem 12.
Let conditions(
1
) and (
2
) of Assumption 8 be satisfied at ρ
=
ρ
1, σ
=
σ
1 and let for point z
0
(28)
1
α
1
B
k
y
0
-
A
k
x
0
∈
1
k
(
ρ
1
-
d
σ
1
α
1
)
(
A
k
-
1
+
A
k
-
2
+
⋯
+
A
+
E
)
S
.
at somek
=
N
(
z
0
). Then pursuit can be completed in the games (1), (2), (5), and (6) from initial position z
0 for N
(
z
0
) steps.
Theorem12 can be proved as Theorems 9 and 11 in a similar fashion.


### 3.3. Example

We consider a discrete game described by the equations(29)
x
k
=
x
k
-
1
+
u
k
,
y
k
=
y
k
-
1
+
v
k
,wherex
k
,
y
k
,
u
k
,
v
k
∈
R
n, n
≥
1, and u
=
(
u
1
,
u
2
,
…
,
u
k
,
…
) and v
=
(
v
1
,
v
2
,
…
,
v
k
,
…
) are controls of the pursier and evader which satisfy the constraints (3) and (4), respectively. Position of the evader is subjected to constraint y
∈
r
S
,
r
>
0; the terminal set is M
=
{
x
,
y
∣
x
,
y
∈
R
n
,
y
-
x
∈
l
S
,
l
>
0
}. For this game, B
=
A
=
E. Applying Theorems 7 and 9 to the game (29) yields the following result.Statement 1  1.
If(30)
ρ
>
r
-
l
r
σ
,
then pursuit can be completed in the games (29), (3), and (4) from all the initial positions x
0
,
y
0
∈
R
n
,
|
y
0
|
≤
r
,
|
y
0
-
x
0
|
>
l for finite number of steps.Let us consider the games (29), (5), and (6). It is not difficult to verify that Theorems 11 and 12 give the following result.Statement 2  2.
If(31)
ρ
1
>
r
-
l
r
σ
1
,
then pursuit can be completed in the games (29), (5), and (6) from all the initial positions x
0
,
y
0
∈
R
n
,
|
y
0
|
≤
r
,
|
y
0
-
x
0
|
>
l for finite number of steps.As we can see from inequalities (30) and (31) that Theorems 7 and 9 (resp., Theorems 11 and 12 in case of total constraints on controls) are applicable to the game (29) for some values of ρ and σ (resp., ρ
1 and σ
1) that satisfy the inequality ρ
<
σ (resp., ρ
1
<
σ
1).


## 3.1. The Case of Geometric Constraints

Assumption 6.
Let the following conditions be satisfied:(1)
B
=
A,
(2)
ρ
>
σ
/
α, where α
=
R
/
(
R
-
l
).Theorem 7.
Let Assumption6 hold and, for the position z
0, at some step k
=
N
(
z
0
), the inclusion
(10)
-
m
+
A
k
(
1
α
y
0
-
x
0
)
∈
(
ρ
-
σ
α
)
(
A
k
-
1
+
A
k
-
2
+
⋯
+
A
+
E
)
S
holds true. Then pursuit can be completed in the games (1)–(4) from initial position z
0 for N
(
z
0
) steps.Proof.
LetV
=
V
(
k
),  k
=
1,2
,
…, be an arbitrary admissible control of the evader. Set
(11)
U
(
k
)
=
1
α
V
(
k
)
+
w
,
where the vectorw
∈
(
ρ
-
(
σ
/
α
)
)
S will be specified later. Then for the solutions of (1), (2) with initial conditions x
(
0
)
=
x
0, y
(
0
)
=
y
0, we have
(12)
y
(
k
)
-
x
(
k
)
=
A
k
y
0
-
A
k
x
0
-
(
A
k
-
1
+
A
k
-
2
+
⋯
+
A
+
E
)
w
+
(
1
-
1
α
)
(
A
k
-
1
V
(
1
)
+
A
k
-
2
V
(
2
)
hhh
+
⋯
+
A
V
(
k
-
1
)
+
V
(
k
)
A
k
-
1
V
)
=
A
k
(
1
α
y
0
-
x
0
)
-
(
A
k
-
1
+
A
k
-
2
+
⋯
+
A
+
E
)
w
+
(
1
-
1
α
)
(
A
k
y
0
+
A
k
-
1
V
(
1
)
+
A
k
-
2
V
(
2
)
hhh
+
⋯
+
A
V
(
k
-
1
)
+
V
(
k
)
A
k
-
1
V
)
.
Consider the equation(13)
-
m
+
A
N
(
1
α
y
0
-
x
0
)
=
(
A
N
-
1
+
A
N
-
2
+
⋯
+
A
+
E
)
w
with respect to the unknown vectorw
∈
(
ρ
-
σ
/
α
)
S. It follows from the inclusion (10) that there exists a solution of (13). Denote it by w
~. In (12), letting w
=
w
~ and using y
∈
R
S we obtain at k
=
N that
(14)
|
-
m
+
y
(
N
)
-
x
(
N
)
|
≤
|
(
1
-
1
α
)
(
A
N
y
0
+
A
N
-
1
V
(
1
)
+
A
N
-
2
V
(
2
)
hhhhh
+
⋯
+
A
V
(
N
-
1
)
+
A
V
(
N
)
A
N
-
1
)
(
1
-
1
α
)
|
+
|
-
m
+
A
N
(
1
α
y
0
-
x
0
)
-
(
A
N
-
1
+
A
N
-
2
+
⋯
+
A
+
E
)
w
~
(
1
α
y
0
-
x
0
)
|
=
|
(
1
-
1
α
)
y
(
N
)
|
=
(
1
-
R
-
l
R
)
|
y
(
N
)
|
≤
l
R
R
=
l
.
Therefore,y
(
N
)
-
x
(
N
)
∈
M.
For the pursuit controlU
(
k
), we have
(15)
|
U
(
k
)
|
=
|
1
α
V
(
k
)
+
w
~
|
≤
1
α
|
V
(
k
)
|
+
|
w
~
|
≤
σ
α
+
(
ρ
-
σ
α
)
=
ρ
.
The proof is complete.Assumption 8.
Let the following conditions be satisfied:(1)
det
⁡
(
A
)
≠
0 and there exists a number d
>
0 such that ∥
(
A
k
)
-
1
B
k
∥
≤
d for any k
≥
1, where A
-
1 is the inverse of the matrix A and ∥
A
∥ is operator norm of the matrix A;
(2)
ρ
>
d
σ
/
α.Theorem 9.
Let Assumption8 hold and for the position z
0 there exists a step N
(
z
0
) such that at k
=
N
(
z
0
) the inclusion
(16)
-
m
+
1
α
B
k
y
0
-
A
k
x
0
∈
(
ρ
-
d
σ
α
)
(
A
k
-
1
+
A
k
-
2
+
⋯
+
A
+
E
)
S
holds true. Then pursuit can be completed in the games (1)–(4) from the initial position z
0 for N
(
z
0
) steps.Proof.
Let the pursuer use the following strategy:(17)
U
(
i
)
=
1
α
(
A
k
-
i
)
-
1
B
k
-
i
V
(
i
)
+
w
,
whereV
=
V
(
i
), i
=
1,2
,
…
,
k, k
>
1, is any admissible control of the evader, and w
∈
(
ρ
-
d
σ
/
α
)
S is specified later. Then for the solutions of (1), (2) with initial conditions x
(
0
)
=
x
0, y
(
0
)
=
y
0 we have
(18)
-
m
+
y
(
k
)
-
x
(
k
)
=
-
m
+
B
k
y
0
+
B
k
-
1
V
(
1
)
+
B
k
-
2
V
(
2
)
+
⋯
+
B
V
(
k
-
1
)
+
V
(
k
)
-
A
k
x
0
-
1
α
[
A
k
-
1
(
A
k
-
1
)
-
1
B
k
-
1
V
(
1
)
+
A
k
-
2
(
A
k
-
2
)
-
1
B
k
-
2
V
(
2
)
+
A
A
-
1
B
V
(
k
-
1
)
+
V
(
k
)
(
A
k
-
1
)
-
1
]
-
(
A
k
-
1
+
A
k
-
2
+
⋯
+
A
+
E
)
w
=
-
m
+
1
α
B
k
y
0
-
A
k
x
0
-
(
A
k
-
1
+
A
k
-
2
+
⋯
+
A
+
E
)
w
+
(
1
-
1
α
)
y
(
k
)
.
Consider the equation(19)
-
m
+
1
α
B
N
y
0
-
A
N
x
0
=
(
A
N
-
1
+
A
N
-
2
+
⋯
+
A
+
E
)
w
with respect to the unknown vectorw
∈
(
ρ
-
d
σ
/
α
)
S. It follows from the inclusion (16) of Theorem 9 that there exists a solution of (19). Let us denote it by w
˘. Since y
∈
G
⊂
R
S, letting w
=
w
˘ in (18), we obtain
(20)
|
-
m
+
y
(
N
)
-
x
(
N
)
|
=
(
1
-
1
α
)
|
y
(
N
)
|
≤
(
1
-
1
α
)
R
≤
l
.
Hence, pursuit can be completed in the games (1), (2). Next, for U
(
i
), i
≥
1, using the conditions (
1
), (
2
) of Assumption 8, we can see from (17) that
(21)
|
U
(
i
)
|
≤
1
α
|
A
(
N
-
i
)
-
1
B
N
-
i
V
(
i
)
|
+
|
w
^
|
≤
1
α
∥
A
(
N
-
i
)
-
1
B
N
-
i
∥
|
V
(
i
)
|
+
|
w
^
|
≤
1
α
d
σ
+
ρ
-
d
σ
α
=
ρ
.
Proof of Theorem9 is complete.


## 3.2. The Case of Total Constraints on Controls

Let us consider the games (1), (2) with total constraints (5)-(6) on controls.Assumption 10.
Let the following conditions be satisfied:(1)
B
=
A,
(2)
ρ
1
>
σ
1
/
α.Theorem 11.
Let Assumption10 hold, and for the position z
0 let the inclusion
(22)
-
m
+
A
k
(
1
α
y
0
-
x
0
)
∈
1
k
(
ρ
1
-
σ
1
α
)
(
A
k
-
1
+
A
k
-
2
+
⋯
+
A
+
E
)
S
be satisfied at some step k
=
N
(
z
0
). Then pursuit can be completed in the games (1), (2), (5), and (6) from the initial position z
0 for N
(
z
0
) steps.Proof.
LetV
=
V
(
k
), k
=
1,2
,
…, be any admissible control of the evader. Construct the strategy for the pursuer in the following form:
(23)
U
=
U
(
k
)
=
1
α
V
(
k
)
+
w
,
where w is a vector in (
1
/
N
)
(
ρ
1
-
σ
1
/
α
)
S which will be specified later. For the solutions x
(
k
)
,
y
(
k
), we have in view of (1), (2) that
(24)
y
(
k
)
-
x
(
k
)
=
A
k
(
y
0
-
x
0
)
-
(
A
k
-
1
+
A
k
-
2
+
⋯
+
A
+
E
)
w
+
(
1
-
1
α
)
(
A
k
-
1
V
(
1
)
+
A
k
-
2
V
(
2
)
hhhhh
+
⋯
+
A
V
(
k
-
1
)
+
V
(
k
)
A
k
-
1
)
=
A
k
(
1
α
y
0
-
x
0
)
+
(
A
k
-
1
+
A
k
-
2
+
⋯
+
A
+
E
)
w
+
(
1
-
1
α
)
(
A
k
y
0
+
A
k
-
1
V
(
1
)
+
A
k
-
2
V
(
2
)
hhhh
+
⋯
+
A
V
(
k
-
1
)
+
V
(
k
)
A
k
y
0
)
.
Consider the equation
(25)
-
m
+
A
N
(
1
α
y
0
-
x
0
)
=
(
A
N
-
1
+
A
N
-
2
+
⋯
+
A
+
E
)
w
with respect to the unknown vector w
∈
(
1
/
N
)
(
ρ
1
-
σ
1
/
α
)
S. According to (22), (25) has a solution. Denote by w
^ lexicographically minimum solution of (25). In (24), letting w
=
w
^ and using the condition y
∈
R
S, we have at k
=
N
(26)
|
-
m
+
y
(
N
)
-
x
(
N
)
|
=
|
(
1
-
1
α
)
y
(
N
)
-
m
+
A
N
(
1
α
y
0
-
x
0
)
-
(
A
N
-
1
+
A
N
-
2
+
⋯
+
A
+
E
)
w
^
(
1
-
1
α
)
y
(
N
)
|
=
|
(
1
-
1
α
)
y
(
N
)
|
=
(
1
-
R
-
l
R
)
|
y
(
N
)
|
≤
l
,
and therefore y
(
N
)
-
x
(
N
)
∈
M.
Next, we prove that if the evader’s controlV
=
V
(
k
), k
=
1,2
,
…
,
N, satisfies the constraint (6); then the pursuer’s control U
(
k
)
=
(
1
/
α
)
V
(
k
)
+
w
^, k
=
1,2
,
…
,
N, satisfies the constraint (5). Indeed, by the inclusion w
^
∈
(
1
/
N
)
(
ρ
1
-
σ
1
/
α
)
S and the Minkowski inequality we have
(27)
∑
k
=
1
N
|
U
(
k
)
|
2
=
∑
k
=
1
N
|
V
(
k
)
+
w
^
⌢
|
2
≤
[
(
1
α
2
∑
k
=
1
N
|
V
(
k
)
|
2
)
1
/
2
+
(
∑
k
=
1
N
|
w
^
⌢
|
2
)
1
/
2
]
2
≤
[
σ
1
α
+
1
N
(
ρ
1
-
σ
1
α
)
N
]
2
=
ρ
1
2
.
The proof is complete.Theorem 12.
Let conditions(
1
) and (
2
) of Assumption 8 be satisfied at ρ
=
ρ
1, σ
=
σ
1 and let for point z
0
(28)
1
α
1
B
k
y
0
-
A
k
x
0
∈
1
k
(
ρ
1
-
d
σ
1
α
1
)
(
A
k
-
1
+
A
k
-
2
+
⋯
+
A
+
E
)
S
.
at somek
=
N
(
z
0
). Then pursuit can be completed in the games (1), (2), (5), and (6) from initial position z
0 for N
(
z
0
) steps.
Theorem12 can be proved as Theorems 9 and 11 in a similar fashion.


## 3.3. Example

We consider a discrete game described by the equations(29)
x
k
=
x
k
-
1
+
u
k
,
y
k
=
y
k
-
1
+
v
k
,wherex
k
,
y
k
,
u
k
,
v
k
∈
R
n, n
≥
1, and u
=
(
u
1
,
u
2
,
…
,
u
k
,
…
) and v
=
(
v
1
,
v
2
,
…
,
v
k
,
…
) are controls of the pursier and evader which satisfy the constraints (3) and (4), respectively. Position of the evader is subjected to constraint y
∈
r
S
,
r
>
0; the terminal set is M
=
{
x
,
y
∣
x
,
y
∈
R
n
,
y
-
x
∈
l
S
,
l
>
0
}. For this game, B
=
A
=
E. Applying Theorems 7 and 9 to the game (29) yields the following result.Statement 1  1.
If(30)
ρ
>
r
-
l
r
σ
,
then pursuit can be completed in the games (29), (3), and (4) from all the initial positions x
0
,
y
0
∈
R
n
,
|
y
0
|
≤
r
,
|
y
0
-
x
0
|
>
l for finite number of steps.Let us consider the games (29), (5), and (6). It is not difficult to verify that Theorems 11 and 12 give the following result.Statement 2  2.
If(31)
ρ
1
>
r
-
l
r
σ
1
,
then pursuit can be completed in the games (29), (5), and (6) from all the initial positions x
0
,
y
0
∈
R
n
,
|
y
0
|
≤
r
,
|
y
0
-
x
0
|
>
l for finite number of steps.As we can see from inequalities (30) and (31) that Theorems 7 and 9 (resp., Theorems 11 and 12 in case of total constraints on controls) are applicable to the game (29) for some values of ρ and σ (resp., ρ
1 and σ
1) that satisfy the inequality ρ
<
σ (resp., ρ
1
<
σ
1).


## 4. Conclusion

We have obtained sufficient conditions of completion of pursuit in linear discrete games, when phase constraints are imposed on position of evader. We have applied the obtained results to concrete discrete pursuit game problems with phase constraint on a position of the evader. We have constructed an example, for which pursuit problem is solvable even if speed (resource, in case of total constraints) of the pursier is a little bit less than the speed (resource) of the evader.



---

*Source: 435103-2014-10-30.xml*