Удмуртский государственный университет (Ижевск) Рассматривается задача простого преследования группой преследователей одного убегающего при условии, что все игроки обладают равными возможностями. В случае если множеством допустимых управлений игроков является многогранник, получены дополнения к теореме Григоренко. Предложен иной способ вычисления числовой характеристики игры, характеризующей её исход. Получены необходимые и достаточные условия на параметры игры, в которой два преследователя осуществляют поимку одного убегающего. Также получены некоторые дополнительные необходимые условия разрешимости задачи преследования.
Постановка задачи В пространстве Rk (k > 2) рассматривается дифференциальная игра n + 1 лиц: n преследователей P1; : : : ; Pn и убегающий E.
Закон движения каждого из преследователей Pi имеет вид Закон движения убегающего E имеет вид x_ i = ui; ui 2 U; xi(0) = xi0:
y_ = v; v 2 U; y(0) = y0; где xi; y; u; v 2 Rk, U Rk выпуклый компакт с непустой внутренностью. Обозначим zi0 = xi0 y0, z0 = fx10; : : : ; x0n; y0g. Считаем, что zi0 6= 0 для всех i = 1; : : : ; n.
Пусть некоторое разбиение 0 = t0 < t1 < < ts < : : : промежутка [0; +1), не имеющее конечных точек сгущения.
О п р е д е л е н и е 1. Кусочно-программной стратегией V убегающего E, соответствующей разбиению , называется семейство отображений fclgl1=0, ставящих в соответствие набору (tl; x1(tl); : : : ; xn(tl); y(tl)) (tl; x1(tl); : : : ; xn(tl); y(tl)) измеримую функцию vl : [tl; tl+1) ! U .
О п р е д е л е н и е 2. Кусочно-программной контрстратегией Ui преследователя Pi, соответствующей l разбиению , называется семейство отображений fbigl1=0, ставящих в соответствие набору и функции vl(t); t 2 [tl; tl+1), измеримую функцию uli : [tl; tl+1) ! U .
Обозначим данную игру (n; z0).
О п р е д е л е н и е 3. В игре (n; z0) происходит уклонение от встречи, если существует разбиение , стратегия V убегающего E, соответствующая разбиению , такие, что для любых траекторий x1(t); : : : ; xn(t) преследователей P1; : : : ; Pn выполнено xi(t) 6= y(t) для всех t > 0 и всех i = 1; : : : ; n, где y(t) траектория E, порожденная разбиением и стратегией V .
О п р е д е л е н и е 4. В игре (n; z0) происходит поимка, если существует T > 0 такое, что для любого разбиения , для любой кусочно-программной стратегии V убегающего E найдутся кусочно-программные контрстратегии U1; : : : ; Un преследователей P1; : : : ; Pn, для которых xp( ) = y( ) при некоторых p; 2 [0; T ].
В работе [
8 Li = < : =
X j=1;:::;m; j6=i j(Aj
Ai);
X j=1;:::;m; j6=i j = 1; j 2 [0; 1] = ; ; 9 и Л е м м а 1. Для любого i верно равенство U Ai = Li = f mLi j 2 [0; 1]g.
m Д о к а з а т е л ь с т в о. Пусть v 2 U . Тогда v = P jAj, P j=1 j=1
j = 1, j > 0. Поэтому Ci = f Li j
> 0g: v
Ai = X jAj (1
i)Ai: j6=i Если i = 1, то v
X j(Aj
1
Ai)A (1 где j > 0, P j = 1. Точка P
j6=i j6=i Пусть теперь v 2 Li. Значит v =
Ai: i) = (1 j(Aj
Ai); i) X
j6=i j(Aj X j6=i Так как 1 + P j = 1, то v = Ai(1
j6=i Лемма доказана.
) +
P jAj 2 U . Поэтому v = v j6=i
Ai 2 U
Ai.
Теорема 1. Для того чтобы в игре (n; z0) происходила поимка, необходимо и достаточно, чтобы существовали множества J1; : : : ; Jn такие, что J1 [
[ Jn = f1; : : : ; mg: Д о к а з а т е л ь с т в о. Докажем необходимость. Пусть J1 [ [ Jn 6= f1; : : : ; mg. Тогда существует такой номер l, что zj0 2= Cl, j = 1; : : : ; n. Заметим, что по определению множество Cl является выпуклым конусом с вершиной в 0. В силу леммы 1 справедливо включение U Cl + Al. Тогда для любого > 0 выполнено: zj0 + Al 2= U , j = 1; : : : ; n. Следовательно, j(Al) = 0, j = 1; : : : ; n. Поэтому (z0) = 0, то есть происходит уклонение. Необходимость доказана.
Докажем достаточность. Пусть выполнены условия теоремы. Рассмотрим произвольную вершину многогранника U и одну из прилегающих к ней граней. Без ограничения общности можно рассмотреть вершину A1 и прилегающую к ней грань, которая определяется вершинами A1; A2; : : : ; As (обозначим её G1). Также без ограничения общности можно считать, что z10 2 C1. Для каждого 2 (0; 1) определим множества Q1( ) = fv j v 2 G1 \ f + A1 j 2 L1; 2 [0; ]gg. Пусть > 0 такое, что z10 2 L1. Данное существует в силу условия теоремы. В силу определения множества Q1( ), любая точка v 2 Q1( ) представима в виде v = w + A1, где w 2 L1, 2 [0; ]. Тогда верно включение (1 )( z10) + v A1 = (1 )( z10) + w 2 L1. Следовательно (1 )( z10) + v 2 U . То есть 1(v) > (1 ) 1(A1). Поэтому v2mQi1n( ) 1(v) > (1 ) 1(A1). Так как z10 6= 0 и z10 2 C1, то существует > 0 такое, что z10 2 L1, и поэтому 1(A1) > 0.
Аналогично определим множества Q2( ); : : : ; Qs( ) для вершин A2; : : : ; As соответственно. В силу условий теоремы, данным вершинам соответствуют такие индексы i2; : : : ; is, что zi0j 2 Cj, j = 2; : : : ; s. Обозначим i1 = 1. На данных множествах соответствующие функции i2 ; : : : ; is принимают значения не меньшие, чем (1 ) i2 (A2); : : : ; (1 ) is (As) соответственно. Докажем, что Q1(1 1=s) [ [ Qs(1 1=s) = G1. Возьмем произвольную точку v 2 G1. v = 1A1 + + sAs, где j > 0 и 1 + + s = 1. Тогда существует индекс q такой, что q > 1=s. Следовательно, v 2 Qq(1 1=s) Поэтому для любой точки v 2 G1 существует такое j 2 f1; : : : ; sg, что ij (v) > (1 (1 1=s)) ij (Aj) = ij (Aj)=s > 0.
Аналогично рассмотрев остальные грани и вершины множества U , получим, что для некоторого > 0
для любой точки v 2 @U , где @U граница множества U , существует такое j 2 f1; : : : ; ng, что j(v) > 0.
Достаточно рассматривать граничные точки, так как функции j вогнутые (см. [
v2U i=1;:::;n i(v) достигается в некоторой точке v 2 @U . Тогда данная точка v принадлежит некоторой грани G . В силу построений, описаных выше для грани G1, существует такой индекс j 2 f1; : : : ; mg, что j(v) > j(Ai)=s > 0. Здесь Ai одна из точек, образующих грань G , s количество точек, образующих данную грань, zj 2 Ci. Следовательно, (z0) > 0, то есть происходит поимка. Теорема доказана. Теорема 2. Пусть m = k + 1. Для того чтобы в игре (k + 1; z0) происходила поимка, необходимо и достаточно выполнение следующих условий: При этом
zi0 2 Cij ; j = 1; : : : ; m;
[ fik+1g = f1; : : : ; mg: любого v, принадлежащего верхней или нижней грани (они параллельны друг другу и L2((1; 0; 0); (0; 1; 0))), необходимо, чтобы
0 z1 2 f j
граница множества U ; 2) существуют вектор q 2 Rk, kqk = 1, (q; p) = 0, и число
(w; q) = . Введём следующие обозначения: 2 R такие, что для любого v 2 U , (v; q) 6 , Докажем достаточность. Пусть выполнены условия теоремы. Возьмём точку v 2 @U такую, что (z0) = i=1;:::;n i(v). Если v 2 W (p), то, в силу определения, точка v лежит на отрезке, соединяющем точки max Dmax(p; v) и Dmin(p; v). Тогда либо 1(v) > kDmax(p; v) Dmin(p; v)k=(2kz10k), либо 2(v) > kDmax(p; v) Dmin(p; v)k=(2kz20k) > 0. Это выполнено в силу определенных в условии теоремы z10, z20.
Рассмотрим случай, когда v 2 @U и v 2= W (p). Предположим, что 1(v) = 2(v) = 0, следовательно (v + l(p)) \ U = v, где l(p) = f j = p; 2 Rg. Докажем, что существует опорная гиперплоскость к множеству U в точке v с внешней нормалью q, которая содержит прямую v + l(p), то есть (q; p) = 0. Множества v + l(p) и Int U (Int U внутренность множества U ) отделимы, так как данные множества являются выпуклыми и не пересекаются. В силу того, что v + l(p) пересекает границу множества U , то отделяющая гиперплоскость будет проходить через v + l(p). Следовательно существует вектор q 6= 0 такой, что (l; q) = 0 и (w; q) < 0, где l 2 l(p) и w 2 Int U v. Тогда для любого v 2 U будет выполнено неравенство (v v; q) 6 0, то есть данная отделяющая гиперплоскость является искомой опорной гиперплоскостью. Поэтому из определения множества W (p) следует, что v 2 W (p). Таким образом получили противоречие с предположением v 2= W (p).
Следовательно, если v 2= W (p), то im=a1;x2 i(v) > 0. Без ограничения общности можно считать, что 1(v) > 0.
Докажем включение U co W (p) + l(p), где co W (p) выпуклая оболочка множества W (p). Обозначим M (q) опорное полупространство к множеству U с нормальным вектором q; (q) соответствующее число, определяющее опорную гиперплоскость,
M (W (p)) =
\ (p;q)=0;kqk=1
M (q): Заметим, что U M (W (p)). Предположим противное включению U co W (p) + l(p). Пусть существует такая точка v 2 U , что v 2= co W (p) + l(p). Следовательно, точка v + l 2= co W (p) + l(p), где l 2 l(p). Тогда существует гиперплоскость M^ = fxj(x; q^) = ^; (q^; p) = 0g, которая не пересекает множество co W (p). Так как v + l(p) M (W (p)), то для любой точки w 2 M^ выполнено неравенство (w; q^) 6 (q^). Но существует такая точка 2 W (p), что ( ; q^) = (q^), что противоречит определению множества M^ . Следовательно, U co W (p) + l(p). Следовательно, существует вектор w1 2 co W (p) и число > 0 такие, что w1 + p = v (либо и далее для функции 2), где v 2 U , v 2= W (p). Поэтому 1(v) > kDmax(p; w) Dmin(p; w)k=(2kz10k), для некоторого w 2 W (p): Отсюда следует, что (z0) > 0 и достигается на W (p), то есть происходит поимка.
Теорема доказана. Благодарности
Работа выполнена при финансовой поддержке РФФИ (грант № 16-01-00346а). Список литературы [1] R. Isaacs. Differential games. John Wiley and Sons, New York, 1965. To the simple pursuit problem Kirill A. Shchelchkov Udmurt State University (Izhevsk, Russia)
A simple pursuit problem, in which a group of pursuers and one evader are involved, is considered. All the participants have equal capabilities. In the case when the admissible control set of all participants is a polyhedral with non–empty interior, additions to the Grigorenko’s theorem have been received. Another method of finding a numerical game characteristic, characterizing the game result, hase been proposed. Required and sufficient conditions on game parameters, when two pursuers realize the capture of one evader, have been received. Also, some additional necessary conditions of solvability pursuit problem have been received.