# Simple Motion Pursuit and Evasion Differential Games with Many Pursuers on Manifolds with Euclidean Metric

Authors: Atamurat Kuchkarov; Gafurjan Ibragimov; Massimiliano Ferrara
Journal: Discrete Dynamics in Nature and Society
 (2016)

---

## Abstract

We consider pursuit and evasion differential games of a group ofm pursuers and one evader on manifolds with Euclidean metric. The motions of all players are simple, and maximal speeds of all players are equal. If the state of a pursuer coincides with that of the evader at some time, we say that pursuit is completed. We establish that each of the differential games (pursuit or evasion) is equivalent to a differential game of m groups of countably many pursuers and one group of countably many evaders in Euclidean space. All the players in any of these groups are controlled by one controlled parameter. We find a condition under which pursuit can be completed, and if this condition is not satisfied, then evasion is possible. We construct strategies for the pursuers in pursuit game which ensure completion the game for a finite time and give a formula for this time. In the case of evasion game, we construct a strategy for the evader.


---

## Body

## 1. Introduction

Multiplayer differential games are natural extension of two-person differential games. New methods of solution for the games of many players were proposed in many works such as [1–7]. The main problem for such games is to find conditions of evasion or completion of pursuit and construct strategies of players as well.Pursuit and evasion differential games of many players attract attention of many researchers. The case when all players have equal dynamic possibilities [8] proved to be an alternative: if the initial position of the evader belongs to the interior of convex hull of the initial positions of the pursuers, then pursuit problem is solvable; else evasion problem is solvable. This work was extended by many researchers such as [2, 3, 6, 9]. It should be noted that one of the main methods for solving differential games of many pursuers and one evader is the method of resolving functions developed by Pshenichnii et al. [6].In the evasion game with many pursuers studied by Chernous’ko [1], it was shown that an evader whose speed is bounded by 1 can, by remaining in a neighborhood of a given motion, avoid an exact contact with any finite number of pursuers whose speeds are bounded by a number less than 1. Later on, this result was extended by Zak [10]. The work [11] presented a sufficient condition of existence of evasion strategy in the game of many pursuers in the plane.In differential games of many pursuers studied by Ivanov and Ledyaev [12], Ibragimov [13], Ibragimov and Rikhsiev [14], Ibragimov and Salimi [15], and Ibragimov et al. [16], optimal strategies of players were constructed.In the real control systems, the state constraints occur and they are given usually in the form of equalities and inequalities. For example, the works [17, 18] study control problems with state constraints of equality type and [19] does properties of shortest curves in the domain described by equality and inequality type of constraints.In differential games, mainly two types of state constraints are considered. According to the first constraint a player moves within a given set, and according to the second one it moves along a submanifold of the state space.In pursuit-evasion differential games, the state constraint can be imposed on the states of pursuers or evaders separately. In the papers [20, 21], the Isaacs method was applied to study the simple motion pursuit differential games of one pursuer and one evader on two-dimensional Riemannian manifolds. In [22], the problem of evasion of one evader from many pursuers was studied on a hypersurface in R
n.In the works [23–25] devoted to generalized “Lion and Man” differential game of Rado, the evader moves along a given absolutely continuous curve and the pursuer moves in the space. In the case where the evader’s speed is greater than that of the pursuer, an evasion strategy was constructed, which enables us to estimate from below the distance between players. If the maximal speeds of the players are equal and the curve does not intersect itself, necessary and sufficient conditions of completion of pursuit from a given initial position as well as from all the initial positions [25] were obtained.Simple motion pursuit and evasion differential games studied in [26] occur in a ball of the Riemannian manifold, and all players have the same dynamic possibilities. The pursuers move in the ball, and with respect to the motion of the evader two cases were considered: in the first case, the evader moves on the sphere of the ball, and in the second case, the evader also moves in the ball. For each case, sufficient conditions of both completion of pursuit and evasion were obtained.In the games of many pursuers and many evaders studied in [5, 7, 27], all of the evaders are controlled by one controlled parameter, but pursuers have different control parameters. By definition, game is said to be completed if the state of a pursuer coincides with that of an evader at some time. In these papers, sufficient conditions of completion of pursuit were obtained. In the work [28], a simple motion evasion game of many pursuers and many evaders was studied under integral constraints on controls of players.In the present paper, we deal with the manifolds, each point of which has a neighborhood isometric to a region of Euclidean space; in other words, the Riemannian metric at each point of the manifold, in a local coordinate system, is expressed as Euclidean one. Such manifolds are called ones with Euclidean metric or ones locally isometric to Euclidean space [29, 30]. For example, two-dimensional manifolds locally isometric to Euclidean space are only plane, cylinder, torus, Mobius strip, and the Klein bottle. Note that a differential game of optimal approach [31] was studied on such manifolds, where duration of the game is fixed, and payoff of the game is distance between the players when the game is terminated. We will study, however, pursuit and evasion differential games of many pursuers and one evader on manifolds with Euclidean metric. Maximal speeds of all players are assumed to be identical. We find a condition on initial positions of players under which pursuit problem is solvable. If this condition is not satisfied, then we show that evasion problem is solvable.To solve the pursuit or evasion differential game ofm pursuers and one evader on manifold M with Euclidean metric, we first reduce the game to an equivalent one in Euclidean space R
n, where a group of countably many pursuers x
i
1
,
x
i
2
,
…
∈
R
n, i
=
1,2
,
…
,
m, and group of countably many evaders y
1
,
y
2
,
…
∈
R
n correspond to each pursuer x
i
∈
M and evader y
∈
M, respectively. Each group of players is controlled by one control parameter. In the new game in R
n, if x
i
j
(
τ
)
=
y
k
(
τ
) at some i
∈
{
1,2
,
…
,
m
}, j
,
k
∈
N and τ
>
0, then game is completed; otherwise evasion is possible. At first glance, the condition y
0
k
∈
i
n
t
c
o
n
v
{
x
i
0
j
,
i
=
1
,
…
,
m
;
j
=
1,2
,
…
} seems to be the condition for completing pursuit. It turns out that this condition does not guarantee that pursuit can be completed in the game on M. We obtain another condition (see Theorem 10), which is necessary and sufficient condition of completion of pursuit on manifolds with local Euclidean metric.


## 2. Statement of Problem

LetM be n
,
n
≥
2, dimensional manifold with positive defined symmetric bilinear form ·
,
·
x on the tangent space T
M
x at the point x
∈
M, and let ·
x be the norm defined by(1)
a
,
b
x
=
G
x
a
,
b
,
a
x
=
a
,
a
x
,
x
∈
M
,
a
,
b
∈
T
M
x
,where 〈
·
,
·
〉 is inner product in R
n; the matrix G
(
·
), called metric tensor, defines the Riemannian metric on the manifold M, which becomes identity matrix at each point of the manifold in a local coordinate system; that is, M is a manifold with local Euclidean metric.The motion of a group of pursuersP
1
,
P
2
,
…
,
P
m and one evader E are described on the manifold M by the following equations:(2)
P
i
:
x
˙
i
=
u
i
,
x
i
0
=
x
i
0
,
E
:
y
˙
=
v
,
y
0
=
y
0
,
y
0
≠
x
i
0
,where x
i, y
∈
M, u
i
∈
T
M
x
i, v
∈
T
M
y, and u
i, v are control parameters, i
=
1,2
,
…
,
m
.Definition 1.
Borel measurable functionsv
(
t
) and u
i
(
t
), t
≥
0, are called controls of the evader E and pursuer P
i, i
=
1,2
,
…
,
m, respectively, if for the solutions y
(
t
) and x
i
(
t
) of initial value problems,(3)
y
˙
=
v
t
,
y
0
=
y
0
,
x
˙
i
=
u
i
t
,
x
i
0
=
x
i
0
,the following inequalities,(4)
v
t
y
t
≤
1
,
u
i
t
x
i
t
≤
1
,and inclusions,(5)
v
t
∈
M
y
t
,
u
i
t
∈
M
x
i
t
,hold true for almost all t, t
≥
0.In the tangent spaceT
M
z, denote the ball {
w
∈
T
M
z
∣
|
z
-
w
|
≤
ρ
} of radius ρ centered at z by B
∗
z
,
ρ.Definition 2.
A functionU
=
(
U
1
,
U
2
,
…
,
U
m
)
,
U
i
=
U
i
(
t
,
x
1
,
x
2
,
…
,
x
m
,
y
,
v
),(6)
U
i
:
0
,
∞
×
M
m
+
1
×
B
∗
y
,
1
⟶
B
∗
x
i
,
1
,is called a strategy of the group of the pursuers {
P
1
,
P
2
,
…
,
P
m
} if for any control of the evader the following initial value problem,(7)
y
˙
=
v
t
,
y
0
=
y
0
,
x
˙
i
t
=
U
i
t
,
x
1
,
x
2
,
…
,
x
m
,
y
,
v
t
,
x
i
0
=
x
i
0
,
i
=
1,2
,
…
,
m
,has a unique absolutely continuous solution x
1
·
,
x
2
·
,
…
,
x
m
·
,
y
· on 0
,
∞. The function x
i
· is referred to as the trajectory of the pursuer P
i generated by the triple: the strategy U, initial position x
10
,
x
20
,
…
,
x
m
0
,
y
0, and control v
·
.Definition 3.
A functionV
t
,
x
1
,
x
2
,
…
,
x
m
,
y
,
V
:
0
,
∞
×
M
m
+
1
→
B
∗
y
,
1 is called a strategy of the evader E
.
LetΔ
=
t
0
=
0
,
t
1
,
… be a partition of the interval 0
,
∞. The trajectory y
· of the evader E generated by the controls of pursuers u
1
(
·
)
,
u
2
(
·
)
,
…
,
u
m
·, a strategy of the evader V, initial position (
x
10
,
x
20
,
…
,
x
m
0
,
y
0
), and partition Δ is defined as follows:(1)
At each timet
k, we define a unit vector,(8)
v
k
=
V
t
,
x
1
t
k
,
x
2
t
k
,
…
,
x
m
t
k
,
y
t
k
,
v
k
∈
B
∗
y
t
k
,
1
,
and construct a geodesicγ
k
:
0
,
t
k
+
1
-
t
k
→
M such that(9)
γ
k
′
0
=
v
k
,
γ
k
0
=
y
t
i
,
γ
i
′
s
=
1
,
s
∈
0
,
t
k
+
1
-
t
k
,
k
=
1,2
,
…
(note that such a geodesic exists and is unique [29]).
(2)
The trajectoryy
(
·
) is defined as the solution of initial value problem(10)
y
˙
=
γ
i
′
t
-
t
i
,
t
∈
t
i
,
t
i
+
1
,
i
=
1,2
,
…
,
y
0
=
y
0
.Thus, strategy of the group of pursuers is defined as a contrstrategy, and corresponding motion is the solution of the initial value problem, whereas strategy of the evader is defined as a positional (closed loop) strategy, and corresponding to it trajectory of the evader is defined as a stepwise motion [32].The problems of the players are as follows.Problem 4 (pursuit problem).
For each initial positionx
10
,
x
20
,
…
,
x
m
0
,
y
0, find a number T and function (strategy) U such that pursuit can be completed for time T; that is, for any control v
· of the evader E, solution of system (7) satisfies the equation x
i
(
t
)
=
y
(
t
) at some t
∈
0
,
T and i
∈
1,2
,
…
,
m
.Problem 5 (evasion problem).
For any initial positionx
10
,
x
20
,
…
,
x
m
0
,
y
0, y
0
≠
x
i
0, construct a function (strategy) V and find a partition Δ such that evasion is possible; that is, for any controls u
1
·
,
u
2
·
,
…
,
u
m
· of the pursuers P
1
,
P
2
,
…
,
P
m, the trajectories x
1
·
,
x
2
·
,
…
,
x
m
·
,
y
· generated by the controls u
1
(
·
)
,
u
2
(
·
)
,
…
,
u
m
(
·
), strategy V, partition Δ, and initial position (
x
10
,
x
20
,
…
,
x
m
0
,
y
0
) satisfy the inequality x
i
(
t
)
≠
y
t for all t
≥
0 and i
∈
1,2
,
…
m
.


## 3. An Equivalent Game in Euclidean Space

We first reduce game (2), (4), (5), (7), and (10) on manifold M to a specific one in Euclidean space R
n by unfolding M in R
n [29, 30]. Such unfolding can be conducted by the multivalued mapping which is inverse to the universal covering π
:
R
n
→
M that is local isometry. If M itself is not Euclidean space and z
∈
M, then the set of its preimages π
-
1
z consists of the class of denumerable points equivalent to each other: z
1
,
z
2
,
…
∈
R
n.Thus, game (2), (4), (5), (7), and (10) is reduced to a game in Euclidean space R
n in which m groups of pursuers π
-
1
x
i
=
{
x
i
1
,
x
i
2
,
…
}, i
=
1,2
,
…
,
m, consisting of countably many pursuers try to capture the group of the evaders π
-
1
(
y
)
=
{
y
1
,
y
2
,
…
}. All members of each group have the same control parameter.Dynamics of the groups of pursuers and evaders are described by the following equations:(11)
x
˙
i
j
=
u
¯
i
,
x
i
j
0
=
x
i
0
j
,
i
=
1,2
,
…
,
m
,
y
˙
j
=
v
¯
,
y
j
0
=
y
0
j
,
j
=
1,2
,
…
,where x
i
j
,
y
j
,
u
¯
i
,
v
¯
∈
R
n; x
i
0
j
≠
y
0
k for all i
∈
1,2
,
…
,
m, j
,
k
∈
1,2
,
…; u
¯
1
,
u
¯
2
,
…
,
u
¯
m and v
¯ are the control parameters of the groups of pursuers and group of evaders, respectively, which satisfy the constraints(12)
u
¯
i
≤
1
,
v
¯
≤
1
.Controls, strategies of the groups of pursuers and group of evaders, trajectories generated by the initial position, strategies of pursuers, and control of evaders (or vice versa) are defined as in Definitions2 and 3.We say that pursuit can be completed if(13)
x
i
j
t
=
y
k
t
at  some
i
∈
1,2
,
…
,
m
,
j
,
k
∈
1,2
,
…
,
t
>
0
.In the differential game (11)-(12), the task of groups of pursuers is to assure equality (13) and that of the group of evaders is the opposite.Show that games (2), (4), (5), (7), (10), and (11)-(12) are equivalent. Let y
t
,
t
≥
0 be a trajectory of the evader on M corresponding to some control function v
(
t
), t
≥
0. Then π
-
1
(
y
(
t
)
), t
≥
0, is a family of trajectories in R
n. Since π is a local isometry and |
y
˙
(
t
)
|
=
|
v
(
t
)
|
≤
1, then d
y
i
t
/
d
t
≤
1, i
=
1,2
,
…. Also note that d
y
1
(
t
)
/
d
t
=
d
y
2
(
t
)
/
d
t
=
d
y
3
(
t
)
/
d
t
=
⋯. Hence, for given v
(
t
)
∈
M
y
(
t
), v
t
≤
1, there is a unique vector v
¯
(
t
)
∈
R
n, v
¯
t
≤
1, such that d
y
i
(
t
)
/
d
t
=
v
¯
(
t
), i
=
1,2
,
…. The same conclusion can be drawn for the pursuers.Note that (13) is equivalent to the equation π
-
1
x
i
t
=
π
-
1
(
y
(
t
)
) in R
n, and, hence, it is equivalent to the equation x
i
(
t
)
=
y
(
t
) on manifold M. Thus, differential game (2), (4), (5), (7), and (10) of pursuers x
1
,
…
,
x
m and evader y on manifold M is equivalent to game (11)-(12) of groups of countably many pursuers π
-
1
x
i
=
{
x
i
1
,
x
i
2
,
…
}, i
=
1,2
,
…
,
m, and a group of countably many evaders π
-
1
(
y
)
=
{
y
1
,
y
2
,
…
} in R
n, where each group is controlled by one control parameter.


## 4. Properties of the Multivalued Mapping

The multivalued mappingπ
-
1
:
M
→
R
n has the following properties [29, 30]:(1)
π
-
1 maps the straight lines (i.e., geodesics) on manifold M to a family of parallel straight lines in R
n.
(2)
Ifπ
-
1
z
=
{
z
1
,
z
2
,
…
}, z
∈
M, then(14)
z
i
+
z
j
-
z
k
∈
π
-
1
z
∀
i
,
j
,
k
=
1,2
,
…
.
(3)
There exists a positive numberh such that(15)
z
i
-
z
j
>
h
,
i
≠
j
.Let(16)
N
M
=
c
o
n
v
z
j
-
z
k
∣
z
j
∈
π
-
1
z
,
z
k
∈
π
-
1
z
,
z
∈
M
.Then the properties of mapping π
-
1 mentioned above imply the following statement.Lemma 6.
The following statements hold true:(1)
For anyz
∈
M and z
∗
∈
π
-
1
z, inclusion π
-
1
z
⊂
z
∗
+
N
M holds.
(2)
There exists a numberr
>
0 such that, for any a
∈
N
M, the ball x
∣
x
-
a
≤
r
,
x
∈
N
M, contains at least one point of the set π
-
1
z, z
∈
M
.
(3)
N
M is a subspace of R
n. Moreover, if M is a compact set, then N
M
=
R
n
.Proof.
(1) Letz
∈
M and z
∗
∈
π
-
1
z. Then, for any z
∗
∈
π
-
1
z, we obtain from (16) that z
∗
-
z
∗
∈
N
M; that is, z
∗
∈
z
∗
+
N
M. Therefore π
-
1
z
⊂
z
∗
+
N
M.
(2) Without loss of generality, we assume thatz
1
=
0 and dim conv
π
-
1
(
z
)
=
k. Then π
-
1
(
z
) contains a linearly independent set of k vectors, say {
z
2
,
z
3
,
…
,
z
k
+
1
}. Denote the k-dimensional prism constructed on the vectors z
2
,
z
3
,
…
,
z
k
+
1 by P. Since z
1
=
0, therefore by (14) and (16) we obtain conv
π
-
1
(
z
)
=
N
(
M
). Cover the set conv
π
-
1
(
z
) by P and prisms that can be obtained by parallel translation of P. In view of (16), vertices of these prisms belong to π
-
1
(
z
). This implies, in particular, that N
(
M
) is a k-dimensional subspace of R
n. To prove part (2) of lemma it suffices to put r
=
diam
⁡
⁡
P.
(3) IfM is a compact set, then there is a bounded set M
0
⊂
R
n of nonempty interior such that π
:
M
0
→
M is one-to-one [29]. Since R
n can be represented as a union of M
0 and the bounded sets, M
1
,
M
2
,
…, which can be obtained by parallel translation of M
0 and whose interiors are disjoint [29], therefore, for any z
∈
M, each of the compact sets M
i, i
=
0,1
,
…, contains only one element of π
-
1
(
z
). This implies that dim conv
π
-
1
(
z
)
=
n, which is the desired conclusion.We now study some examples to illustrate the setN
(
M
).Example 7.
LetM be a plane. Then, clearly, N
(
M
)
=
{
0
}.Example 8.
Let(17)
M
=
z
=
z
1
,
z
2
,
z
3
∈
R
3
∣
z
1
2
+
z
2
2
=
1
;that is, M is two-dimensional cylinder in R
3. Then [30], for some a
,
a
∈
0,2
π,(18)
π
-
1
z
=
x
=
x
1
,
x
2
∈
R
2
∣
x
2
=
z
3
,
x
1
=
a
+
2
π
n
,
n
∈
Z
,
z
∈
M
,where Z is the set of integers. It is obvious that the set N
M
=
z
=
x
1
,
x
2
∈
R
2
∣
x
2
=
0 is a straight line. Here, the number r mentioned in Lemma 6 can be any number not less than 2
π.Example 9.
Let nowM be two-dimensional torus M
=
S
1
×
S
1, where S
1 is a unit circle; then [30](19)
π
-
1
z
=
x
=
x
1
,
x
2
∈
R
2
:
x
1
=
a
+
2
π
n
,
x
2
=
b
+
2
π
k
,
n
,
k
∈
Z
,
z
∈
M
,where a and b are some numbers in [
0
,
2
π
]. Therefore, N
(
M
) is a plane and the number r mentioned in Lemma 6 can be, for example, π
2
.


## 5. Main Result

We now formulate the main result of the present paper.Theorem 10.
(i) If there exist points,(20)
z
1
,
z
2
,
…
,
z
m
∈
R
n
w
i
t
h
z
i
∈
π
-
1
x
i
0
=
x
i
0
1
,
x
i
0
2
,
…
,
i
=
1,2
,
…
,
m
,and number j
∈
{
1,2
,
…
} such that(21)
y
0
j
∈
i
n
t
c
o
n
v
z
1
,
z
2
,
…
,
z
m
,then pursuit can be completed in game (11)-(12) (and hence in game (2), (4), (5), (7), and (10)) for the time:(22)
T
=
1
A
∑
i
=
1
m
z
i
-
y
0
j
;
A
=
min
v
=
1
⁡
∑
i
=
1
m
e
i
,
v
-
e
i
,
v
,where(23)
y
0
1
,
y
0
2
,
…
=
π
-
1
y
0
,
e
i
=
y
0
j
-
z
i
y
0
j
-
z
i
,
i
=
1,2
,
…
,
m
.(ii) If for any set {
z
1
,
z
2
,
…
,
z
m
} with z
i
∈
π
-
1
(
x
i
0
), i
=
1,2
,
…
,
m, and for any number j
∈
{
1,2
,
…
}, inclusion (21) fails to hold; then evasion is possible in game (11)-(12) (and hence in game (2), (4), (5), (7), and (10)).It should be noted that condition (21) implies that m
>
n and A
>
0.Proof.
Part I. It follows from condition (14) that if for a number j
∈
{
1,2
,
…
} there exists a set z
1
,
z
2
,
…
,
z
m to satisfy (21), then for each j
∈
{
1,2
,
…
} such a set exists as well. Therefore, from now on, one writes y
0 and y
t instead of y
0
j and y
j
t, respectively. This means that the group of evaders consists of only one evader.
Assume that there exists a setz
1
,
z
2
,
…
,
z
m with z
i
∈
π
-
1
(
x
i
0
), i
=
1,2
,
…
,
m, satisfying inclusion (21). Without loss of generality, we may assume that z
i
=
x
i
0
1, i
=
1
,
…
,
m.
Letv
(
·
) be an arbitrary control of the evader. Let the pursuers use the strategy of parallel approach [33]:(24)
U
i
v
=
v
+
λ
i
v
e
i
;
λ
i
v
=
-
v
,
e
i
+
1
-
v
2
+
v
,
e
i
2
.
Analysis similar to [8] shows that pursuit can be completed for time T.
Part II. We now turn to the case, where there is no set {
z
1
,
z
2
,
…
,
z
m
} with z
i
∈
π
-
1
(
x
i
0
), i
=
1,2
,
…
,
m, to satisfy (21). We need to consider the following two cases.
Case  1 (m
≤
n). In this case, observe that int conv
{
z
1
,
z
2
,
…
,
z
m
}
=
∅ and inclusion (21) fails to hold for any set {
z
1
,
z
2
,
…
,
z
m
}; z
i
∈
π
-
1
(
x
i
0
), i
=
1,2
,
…
,
m.
For simplicity of notation, we denote the(
m
+
1
)-tuple (
π
-
1
(
x
1
)
,
π
-
1
(
x
2
)
,
…
,
π
-
1
(
x
m
)
,
y
) by w. Set(25)
W
w
=
x
i
j
∣
x
i
j
-
y
≤
h
2
at  some
i
∈
1,2
,
…
,
m
,
j
∈
1,2
,
…
.From now on, we assume that the number h
>
0 satisfies inequalities (15) for all z
=
z
i, i
=
1
,
…
,
m. It follows from inequality (15) that, for each i
∈
{
1
,
…
,
m
}, the set W
(
w
) contains not more than one element of the set π
-
1
(
x
i
). Therefore, for any w, the number of elements of the set W
(
w
) does not exceed m
.
Let the partitionΔ be defined by numbers t
k
=
k
h
/
4
,
k
=
0,1
,
…. Define the strategy V
(
w
) of the evader by requiring conditions(26)
m
i
n
v
=
1
m
a
x
x
i
j
∈
W
w
x
i
j
-
y
x
i
j
-
y
,
v
=
m
a
x
x
i
j
∈
W
w
x
i
j
-
y
x
i
j
-
y
,
V
w
,
V
w
=
1
.Since the set W
(
w
) is finite, m
a
x in (26) attains. In view of m
≤
n, we conclude that V
(
w
) must satisfy inequality(27)
m
a
x
x
i
j
∈
G
w
x
i
j
-
y
x
i
j
-
y
,
V
w
≤
0
.
Letu
¯
1
(
·
)
,
u
¯
2
(
·
)
,
…
,
u
¯
m
(
·
) be any controls of the groups of pursuers, and let y
(
·
)
,
x
i
j
(
·
), j
=
1,2
,
…, i
=
1,2
,
…
,
m, be the trajectories generated by these controls, initial positions, strategy V
(
w
), and partition Δ
. We shall have established the theorem if we prove the following statement: if the inequalities x
i
j
t
≠
y
t, i
=
1,2
,
…
,
m, j
=
1,2
,
…, hold for all t
∈
[
t
k
-
1
,
t
k
], then they hold true for all t
∈
t
k
,
t
k
+
1, k
=
1,2
,
…, as well (recall t
0
=
0). Then, clearly, x
i
j
t
≠
y
(
t
), for all i
=
1,2
,
…
,
m, j
=
1,2
,
…, and t
≥
0
.
Letx
1
1
(
t
k
)
∈
W
(
w
(
t
k
)
). Then (27) implies that(28)
x
1
1
t
k
-
y
t
k
x
1
1
t
k
-
y
t
k
,
V
w
t
k
≤
0
,and so the greatest (nonacute) angle of the triangle with vertices y
(
t
)
=
y
(
t
k
)
+
(
t
-
t
k
)
V
(
w
(
t
k
)
), x
1
1
(
t
k
), and y
(
t
k
) is at the vertex y
(
t
k
)
. Therefore,(29)
x
1
1
t
k
-
y
t
>
t
-
t
k
V
w
t
k
=
t
-
t
k
,
t
∈
t
k
,
t
k
+
1
.This inequality and (12) now give(30)
x
1
1
t
-
y
t
≥
x
1
1
t
k
-
y
t
-
x
1
1
t
-
x
1
1
t
k
>
t
-
t
k
-
∫
t
k
t
u
¯
1
τ
d
τ
≥
t
-
t
k
-
∫
t
k
t
u
¯
1
τ
d
τ
≥
0
,
t
k
≤
t
≤
t
k
+
1
.
We can now turn to the casex
1
1
(
t
k
)
∉
W
(
w
(
t
k
)
). For t
k
≤
t
≤
t
k
+
1, first using the triangle inequality and then (12), (25), and (26), we get(31)
x
1
1
t
-
y
t
=
x
1
1
t
k
+
∫
t
k
t
u
¯
1
τ
d
τ
-
y
t
k
-
∫
t
k
t
V
w
t
k
d
τ
≥
x
1
1
t
k
-
y
t
k
-
∫
t
k
t
u
¯
1
τ
d
τ
-
∫
t
k
t
V
w
t
k
d
τ
>
h
2
-
∫
t
k
t
u
¯
1
τ
d
τ
-
t
-
t
k
≥
h
2
-
t
-
t
k
-
h
4
≥
h
2
-
h
4
-
h
4
=
0
.
Inequalities (30) and (31) show that for any location of w
(
t
k
) the inequality x
1
1
(
t
)
≠
y
(
t
),
t
∈
t
k
,
t
k
+
1 holds. In a similar way, one can prove that x
i
j
(
t
)
≠
y
(
t
), i
=
1,2
,
…
,
m
,
j
=
1,2
,
…, for all t
∈
[
t
k
,
t
k
+
1
]. This is our assertion in the case m
≤
n.
Case  2 (m
>
n). Let N
=
N
(
M
) (see (16)). If m
>
n and dim
N
=
n, then it is not difficult to verify using the second statement of Lemma 6 that there exists a set,(32)
z
1
,
z
2
,
…
,
z
m
,
z
i
∈
x
i
0
1
,
x
i
0
2
,
…
,
i
=
1,2
,
…
,
m
,to satisfy inclusion (21). Therefore, if m
>
n and y
0
∉
i
n
t
c
o
n
v
{
z
1
,
z
2
,
…
,
z
m
} for any set {
z
1
,
z
2
,
…
,
z
m
} with z
i
∈
{
x
i
0
1
,
x
i
0
2
,
…
}
,
i
=
1,2
,
…
,
m, then necessarily dim
⁡
⁡
N
<
n. Thus, it remains to study the case where m
>
n and dim
⁡
⁡
N
<
n.
Denote byN
⊥ the orthogonal complement of the subspace N and by F
,
F
:
R
n
→
N
⊥ the orthogonal projection operator. Then, clearly, F
:
N
→
{
0
} and it follows from (14) that the set F
π
-
1
(
z
), z
∈
M, consists of a unique point. Therefore, we denote(33)
F
π
-
1
y
0
=
b
,
F
π
-
1
x
i
0
=
a
i
,
i
=
1,2
,
…
,
m
.
Show that the following inclusion,(34)
b
∈
i
n
t
c
o
n
v
a
1
,
a
2
,
…
,
a
m
,fails to hold in the subspace N
⊥, where the operations int and conv act on the subspace N
⊥. Assume the contrary; let (34) hold.
It follows from condition (14) that if for a number j
∈
{
1,2
,
…
} there exists a set {
z
1
,
z
2
,
…
,
z
m
} to satisfy (21), then for each j
∈
{
1,2
,
…
} also such a set exists. Therefore, from now on, one writes y
0
=
b
=
0 and y
(
t
) instead of y
0
j and y
j
(
t
), respectively. This means that group of evaders consists of only one evader.
Sincem
>
n and d
i
m
N
⊥
<
n, then in view of (34) the point b
=
0 belongs to convex hull of some n points from a
1
,
a
2
,
…
,
a
m. Without loss of generality, we assume that(35)
0
∈
c
o
n
v
a
1
,
a
2
,
…
,
a
n
,in the subspace N
⊥.
Next, letp
∈
N be a unit vector, and let A be a positive number. Choose linearly independent set of vectors z
i
∈
π
-
1
x
i
0, i
=
1,2
,
…
,
n, so that z
i
,
p
>
A. Construct the cone(36)
K
=
z
∈
R
n
:
z
=
α
1
z
1
+
α
2
z
2
+
⋯
+
α
n
z
n
,
α
i
≥
0
,
i
=
1,2
,
…
,
nand its conjugate(37)
K
∗
=
z
∈
R
n
:
z
=
α
1
z
1
+
α
2
z
2
+
⋯
+
α
n
z
n
,
α
i
≤
0
,
i
=
1,2
,
…
,
n
.Since the set of vectors {
z
1
,
z
2
,
…
,
z
n
} is linearly independent, therefore these cones have nonempty interiors. Observe that p
∈
K and -
p
∈
K
∗
. It follows from inclusions -
p
∈
K
∗
,
p
∈
N, and statement (2) of Lemma 6 that the set(38)
i
n
t
K
∗
∩
π
-
1
x
n
+
1has infinitely many elements. Choose a vector z
n
+
1 from this set. Then by construction of the cones K and K
∗ in view of (35) we have(39)
0
∈
i
n
t
c
o
n
v
z
1
,
z
2
,
…
,
z
n
+
1
.By hypothesis of the theorem there is no set {
z
1
,
z
2
,
…
,
z
m
} with z
i
∈
π
-
1
(
x
i
0
),
i
=
1,2
,
…
,
m, to satisfy (21), a contradiction.
Thus, (34) does not hold, and so(40)
0
⋶
i
n
t
c
o
n
v
a
1
,
a
2
,
…
,
a
m
.From this it follows that there exists a unit vector V
0
∈
N
⊥ such that(41)
V
0
,
x
i
0
j
-
y
0
=
V
0
,
F
π
-
1
x
i
0
-
F
π
-
1
y
0
=
V
0
,
a
i
≤
0
,
i
=
1,2
,
…
,
m
,
j
=
1,2
,
…
.Let the evader use the constant control V
w
=
V
0, t
≥
0
. We conclude from (41) that, for any i
∈
{
1,2
,
…
,
m
}, j
∈
{
1,2
,
…
}, and t
≥
0, the greatest angle of the triangle with vertices x
i
0
j
,
y
0, and y
(
t
)
=
y
0
+
V
0
t is at the vertex y
0. This gives(42)
y
t
-
x
i
0
j
>
y
t
-
y
0
=
t
.Next, by the restriction u
i
·
≤
1, we obtain(43)
x
i
j
t
-
x
i
0
j
=
∫
0
t
u
¯
i
s
d
s
≤
∫
0
t
u
¯
i
s
d
s
≤
t
.From the last two relations we obtain y
(
t
)
≠
x
i
j
(
t
) for all i
=
1,2
,
…
,
m, j
=
1,2
,
…, and t
≥
0, and the proof is complete.Remark 11.
Obviously, ifm
≤
n, inclusion (21) fails to hold. In this case, by Theorem 10, evasion is possible from any initial points. In addition, in the proof of this statement, we have used only inequality (15), and other properties of multivalued mapping π
-
1
:
M
→
R
n have not been used. Therefore, if m
≤
n, then evasion is possible in the game of type (11)-(12) from any initial points that satisfy (15).It should be noted that condition (21) of Theorem 10 is fairly easy to check. In the following example, we give conditions which are equivalent to condition (21).Example 12.
LetM be the cylinder given in Example 8. Then in view of (18) one can verify that condition (21) is equivalent to the following inequalities:(44)
min
1
≤
i
≤
m
⁡
x
i
0
3
<
y
0
3
<
max
1
≤
i
≤
m
⁡
x
i
0
3
,
m
≥
3
.Next, in the case where the setM is compact, d
i
m
N
M
=
n by Lemma 6, and there exists a number r such that each ball of radius r in R
n contains at least one point of the set π
-
1
(
x
), x
∈
M
. Therefore, if m
>
n, inclusion (21) holds. According to this property, we obtain the following corollary of Theorem 10:Corollary 13.
IfM is a compact set and m
>
n, then, for any initial position of the players (
x
10
,
x
20
,
…
,
x
m
0
,
y
0
), x
i
0
≠
y
0, i
=
1
,
…
,
m, there exists a positive number T
=
T
(
x
10
,
x
20
,
…
,
x
m
0
,
y
0
) such that pursuit can be completed for time T.Remark 14.
Condition (21) is equivalent to the following one: there exist geodesics γ
i
:
[
0
,
α
i
]
→
M such that γ
i
(
0
)
=
y
0
,
γ
i
(
α
i
)
=
x
i
0, i
=
1,2
,
…
,
m, and the inclusion(45)
0
∈
i
n
t
c
o
n
v
γ
1
′
0
,
γ
2
′
0
,
…
,
γ
m
′
0holds in the tangent space T
M
y
0. Note that such geodesics, in general, are not unique.


## 6. Conclusion

We have studied pursuit and evasion differential games ofm pursuers and one evader on manifolds with Euclidean metric. The following are our main contributions:(1)
We have proposed a method of reduction of simple motion differential game with many pursuers and one evader on a class of manifolds (e.g., cylinder and torus) to an equivalent differential game inR
n, which contains m groups of countably many pursuers, x
i
1
,
x
i
2
,
…, i
=
1
,
…
,
m, and one group of countably many evaders, y
1
,
y
2
,
….
(2)
We have obtained necessary and sufficient condition of evasion in the equivalent game. It should be noted that even though the conditiony
0
l
∈
{
x
i
0
j, i
=
1
,
…
,
m; j
=
1,2
,
…
}, for some positive integer l, is more similar to the condition of Pshenichnii [8] than condition (21), it is not sufficient for completion of pursuit in the game.
(3)
If condition (21) is not satisfied, we have constructed an evasion strategy and proved that evasion is possible. Note that many researchers (see, e.g., Pshenichnii [8] and Grigorenko [3]) suggested to the evader a constant velocity depending on initial positions of players, which guarantees the evasion in R
n. In the game we studied, evasion using constant velocity does not work. In general, the evader will be captured if it moves with constant velocity. Evasion strategy used in the present paper depends on current positions of players and requires a specific construction.



---

*Source: 1386242-2016-08-02.xml*