Максимальное время преследования для стратегии параллельного сближения в случае равенства скоростей игроков
Работа посвящена дифференциальным играм преследования, в которых несколько игроков догоняют одного, применяя стратегию параллельного сближения. Сформулировано и доказано необходимое условие оптимальности, позволяющее эффективно рассчитывать оптимальные стратегии уклонения....
Gespeichert in:
| Datum: | 2014 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2014
|
| Schriftenreihe: | Компьютерная математика |
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/84819 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Максимальное время преследования для стратегии параллельного сближения в случае равенства скоростей игроков / С.В. Пашко // Компьютерная математика. — 2014. — № 1. — С. 140-149. — Бібліогр.: 3 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84819 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-848192025-02-09T09:40:48Z Максимальное время преследования для стратегии параллельного сближения в случае равенства скоростей игроков Максимальний час переслідування для стратегії паралельного зближення у випадку рівності швидкостей гравців Maximum time of pursuit for the strategy of parallel approach in the case of equal speeds of the players Пашко, С.В. Теория и методы оптимизации Работа посвящена дифференциальным играм преследования, в которых несколько игроков догоняют одного, применяя стратегию параллельного сближения. Сформулировано и доказано необходимое условие оптимальности, позволяющее эффективно рассчитывать оптимальные стратегии уклонения. Робота присвячена диференційним іграм переслідування, в яких кілька гравців доганяють одного, застосовуючи стратегію паралельного зближення. Сформу-льована та доведена необхідна умова оптимальності, що дозволяє ефективно розраховувати оптимальні стратегії втечі. The paper deals with differential pursuit-evasion games with several players using the strategy of parallel approach. Necessary optimality condition is formulated and proved. This condition allows us to calculate effectively the optimal evading strategies. 2014 Article Максимальное время преследования для стратегии параллельного сближения в случае равенства скоростей игроков / С.В. Пашко // Компьютерная математика. — 2014. — № 1. — С. 140-149. — Бібліогр.: 3 назв. — рос. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84819 518.9 ru Компьютерная математика application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Теория и методы оптимизации Теория и методы оптимизации |
| spellingShingle |
Теория и методы оптимизации Теория и методы оптимизации Пашко, С.В. Максимальное время преследования для стратегии параллельного сближения в случае равенства скоростей игроков Компьютерная математика |
| description |
Работа посвящена дифференциальным играм преследования, в которых несколько игроков догоняют одного, применяя стратегию параллельного сближения. Сформулировано и доказано необходимое условие оптимальности, позволяющее эффективно рассчитывать оптимальные стратегии уклонения. |
| format |
Article |
| author |
Пашко, С.В. |
| author_facet |
Пашко, С.В. |
| author_sort |
Пашко, С.В. |
| title |
Максимальное время преследования для стратегии параллельного сближения в случае равенства скоростей игроков |
| title_short |
Максимальное время преследования для стратегии параллельного сближения в случае равенства скоростей игроков |
| title_full |
Максимальное время преследования для стратегии параллельного сближения в случае равенства скоростей игроков |
| title_fullStr |
Максимальное время преследования для стратегии параллельного сближения в случае равенства скоростей игроков |
| title_full_unstemmed |
Максимальное время преследования для стратегии параллельного сближения в случае равенства скоростей игроков |
| title_sort |
максимальное время преследования для стратегии параллельного сближения в случае равенства скоростей игроков |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2014 |
| topic_facet |
Теория и методы оптимизации |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84819 |
| citation_txt |
Максимальное время преследования для стратегии параллельного сближения в случае равенства скоростей игроков / С.В. Пашко // Компьютерная математика. — 2014. — № 1. — С. 140-149. — Бібліогр.: 3 назв. — рос. |
| series |
Компьютерная математика |
| work_keys_str_mv |
AT paškosv maksimalʹnoevremâpresledovaniâdlâstrategiiparallelʹnogosbliženiâvslučaeravenstvaskorostejigrokov AT paškosv maksimalʹnijčaspereslíduvannâdlâstrategííparalelʹnogozbližennâuvipadkurívnostíšvidkostejgravcív AT paškosv maximumtimeofpursuitforthestrategyofparallelapproachinthecaseofequalspeedsoftheplayers |
| first_indexed |
2025-11-25T11:49:47Z |
| last_indexed |
2025-11-25T11:49:47Z |
| _version_ |
1849762923286626304 |
| fulltext |
140 Компьютерная математика. 2014, № 1
Работа посвящена дифференци-
альным играм преследования, в
которых несколько игроков дого-
няют одного, применяя стра-
тегию параллельного сближения.
Сформулировано и доказано необ-
ходимое условие оптимальности,
позволяющее эффективно рас-
считывать оптимальные стра-
тегии уклонения.
С.В. Пашко, 2014
УДК 518.9
C.B. ПАШКО
МАКСИМАЛЬНОЕ ВРЕМЯ
ПРЕСЛЕДОВАНИЯ ДЛЯ
СТРАТЕГИИ ПАРАЛЛЕЛЬНОГО
СБЛИЖЕНИЯ
В СЛУЧАЕ РАВЕНСТВА
СКОРОСТЕЙ ИГРОКОВ
Введение. Задачи преследования – уклоне-
ния занимают одно из центральных мест в
теории динамических игр. В данной работе
рассматривается задача оптимального укло-
нения одного убегающего от нескольких
преследователей. Предполагается, что каж-
дый преследователь использует стратегию
параллельного сближения [1]. В качестве
критерия выступает время захвата цели, ко-
торое убегающий игрок стремится максими-
зировать.
Стратегия параллельного сближения со-
стоит в следующем. Каждый преследователь,
зная скорость преследуемого в данный мо-
мент времени, считает эту скорость постоян-
ной и вычисляет на линии движения убе-
гающего игрока точку захвата, в которой он
может догнать его, двигаясь с постоянной
максимальной скоростью. В текущий момент
времени вектор скорости преследователя на-
правлен на точку захвата, а величина скоро-
сти максимальна. Если максимальные скоро-
сти преследователя и убегающего равны, а
точка захвата отсутствует, преследователь
двигается параллельно убегающему игроку.
В данной работе изучается случай равен-
ства максимальных скоростей всех участни-
ков игры. Сформулировано и доказано необ-
ходимое условие оптимальности стратегии
уклонения, позволяющее эффективно произ-
водить расчеты. Более общая задача, в кото-
рой скорость убегающего игрока не превос-
Компьютерная математика. 2014, № 1 141
ходит скоростей преследова-
телей, рассмотрена в работе
[2].
МАКСИМАЛЬНОЕ ВРЕМЯ ПРЕСЛЕДОВАНИЯ ДЛЯ СТРАТЕГИИ ...
Компьютерная математика. 2014, № 1 141
Стратегии уклонения и максимальное время преследования. Пусть
в точке )(00 tXX = n-мерного действительного евклидового пространства nE
расположен преследуемый игрок E, а в точках )(tXX ii = находятся преследо-
ватели iP , mi ,...,2,1= . Векторы )(tVV ii = размерности n, mi ,...,1,0= , обо-
значают скорости игроков (нулевое значение индекса i относится к игроку E).
Пространство nE состоит из n-мерных векторов ),...,,( 21 nxxxX = c веще-
ственными компонентами, ∞<≤ n2 . Норма вектора X задается формулой
2/1
, XXX = , где ∑ =
= n
i ii yxYX
1
, – скалярное произведение векторов
),...,,( 21 nxxxX = и ),...,,( 21 nyyyY = .
Игра начинается в момент времени 0=t . Уравнения движения игроков
имеют вид
ii VX =& , mi ,...,1,0= .
Считаем, что выполняются ограничения wtVi ≤≤ )(0 , 0≥t , 0,1, ..., ,i m=
где 0 w< < ∞ – максимальная величина скорости.
Движение игроков предполагается простым. В каждый момент времени иг-
рок может выбрать произвольный вектор скорости движения, норма которого не
превосходит заданной величины.
Скорость )(0 tV считается кусочно-непрерывной функцией от времени. Это
значит, что в каждом ограниченном временном интервале существует не больше
конечного числа точек разрыва первого рода. Поскольку каждый преследователь
применяет стратегию параллельного сближения, то функции )(tVi , 1,2,..., ,i m=
также являются кусочно-непрерывными.
Игрок E управляет своими координатами, выбирая в каждый момент време-
ни вектор скорости 0V , являющийся функцией от времени и от точек
)(),...,(),( 10 tXtXtX m . Функцию ),(0 tV 0,t ≥ будем называть стратегией убе-
гающего игрока и обозначать S.
Временем окончания игры назовем величину
}0))()((min:inf{)( 0
,...,1
<−−=
= ii
mi
ltXtXtST ,
где 0>il – заданные числа. Игрок E стремится максимизировать величину
)(ST . Максимальным временем преследования назовем число )(sup STT
S
=∗ .
Стратегию S, для которой справедливо равенство ( ) ,T S T ∗= назовем опти-
мальной стратегией уклонения. Считаем, что выполняются неравенства
ii lXX >− )0()0( 0 , 1,2,..., .i m=
С.В. ПАШКО
Компьютерная математика. 2014, № 1 142
Обозначим conv },...,,{ 21 mXXX выпуклую оболочку точек mXXX ,...,, 21 .
Пусть int X – внутренность множества .X Считаем, что точка расположения
убегающего )0(0X принадлежит внутренности выпуклой оболочки точек
)0(),...,0(),0( 21 mXXX , т. е. выполняется условие
∈)0(0X int conv 1 2{ (0), (0),..., (0)}.mX X X (1)
Очевидно, если условие (1) не выполнено, то игрок E может избежать захвата.
Обозначим )0()0(/))0()0(( 00 XXXXN iii −−= , 1,2,..., .i m= Согласно
лемме 1 работы [2], величины скоростей сближения )(tuu ii = объектов E и iP
вычисляются по формулам
22 2
0 0 0, , ,i i iu N V w v N V= + − + 1,2,..., .i m= (2)
Здесь )()( 000 tVtvv == , значение квадратного корня считается неотри-
цательным.
Задачу поиска оптимальной стратегии уклонения запишем в виде
max,T →
∫ −≤
T
iii lddttu
0
)( , 1,2,..., ,i m=
где id – расстояние между игроками E и iP в момент 0=t .
Важно заметить следующее. Углы между векторами
→
iXX 0 и
→
jXX 0 на
протяжении игры остаются постоянными, поскольку прямые )()(0 tXtX q
и )0()0(0 qXX параллельны при каждом 0≥t ; mq ,...,2,1= [3]. Скорости
сближения )(tui неотрицательны. Поскольку используется стратегия парал-
лельного сближения, то из условия (1) вытекает соотношение
∈)(0 tX int conv )}(),...,(),({ 21 tXtXtX m , )](,0[ STt ∈ .
Лемма 4 работы [2] утверждает, что время окончания игры для произволь-
ной стратегии уклонения не превосходит некоторую константу ∞<T .
Из теоремы 1 работы [2] вытекает существование оптимальной стратегии
уклонения ),...,,,,...,,( **
2
*
1
**
2
*
1
*
mm ZZZtttS = , где величины ** , ii Zt обозначают
следующее. Представим временной промежуток ),0[ ∗T , где ( )T T S∗ ∗= =
*
1
,
m
ii
t
=
=∑ в виде объединения m непрерывных непересекающихся промежутков,
(1) (2)
1[0, ) [ , ).m
i i iT ∗
== τ τU Длина промежутка (1) (2)[ , )i iτ τ равна * ,it а вектор скоро-
сти оптимальной стратегии уклонения на промежутке (1) (2)[ , )i iτ τ равен * ,iwZ
причем 1* =iZ , 1,2,..., .i m=
МАКСИМАЛЬНОЕ ВРЕМЯ ПРЕСЛЕДОВАНИЯ ДЛЯ СТРАТЕГИИ ...
Компьютерная математика. 2014, № 1 143
Теорема 2 работы [2] утверждает, что в каждый момент времени ),0( *Tt ∈
такой, что оптимальная стратегия )(*
0 tV непрерывна, справедливо равенство
wtV =)(*
0 .
Необходимое условие оптимальности. Пусть *T – момент окончания игры
для оптимальной стратегии )(*
0 tV . Справедлива теорема.
Теорема. В каждый момент времени ),0( *Tt ∈ , в который стратегия )(*
0 tV
непрерывна, существует набор чисел 121 ,...,, −niii , принадлежащих множеству
},...,2,1{ m , такой, что система векторов },...,,{
121 −niii NNN линейно независима
и выполняются равенства
0)(, *
0 =tVN
ji , 1,...,2,1 −= nj .
Доказательство. Пусть ),0( *Tt ∈′ и стратегия )(*
0 tV непрерывна в момент
времени t′ . Согласно теореме 2 работы [2], 0)(*
0 >=′ wtV .
Пусть 1
0
−nE – )1( −n -мерное подпространство пространства nE , такое, что
вектор )(*
0 tV ′ ортогонален 1
0
−nE . Из условия (1) следует, что во множестве
},...,,{ 21 mNNNQ = имеется n линейно независимых векторов. Предположим,
утверждение теоремы не верно, т. е. никакие )1( −n линейно независимых век-
торов из множества Q не принадлежат подпространству 1
0
−nE . Покажем, что это
предположение противоречит условию оптимальности стратегии )(*
0 tV .
Пусть },...,,{
210 qiii NNNQ = – такое подмножество множества Q, что
1
0
−∈ n
i EN
j
, qj ,...,2,1= . Всевозможные линейные комбинации
1
,
j
q
j ij
N
=
α∑
где jα – вещественные числа, а векторы
jiN принадлежат множеству 0Q , обра-
зуют линейное подпространство rE1 размерности r, такое, что 1
01
−⊂ nr EE ,
1−< nr . Очевидно, вектор )(*
0 tV ′ ортогонален подпространству rE1 .
Обозначим rnE −
2 подпространство размерности rn − , являющееся орто-
гональным дополнением подпространства rE1 . Очевидно, rnEtV −∈′ 2
*
0 )( .
Поскольку 2≥− rn , то в подпространстве rnE −
2 существует двумерное подпро-
странство 2
3 ,E такое, что 2
3
*
0 )( EtV ∈′ . Подпространства rE1 и 2
3E ортогональны.
С.В. ПАШКО
Компьютерная математика. 2014, № 1 144
Обозначим },...,2,1{ mI = , }0)(,,:{ *
00 =′∈= tVNIiiI i , ,:{1 IiiI ∈=
}0)(, *
0 >′tVN i , }0)(,,:{ *
01 <′∈=− tVNIiiI i . Пусть
2/,min 0
}\{ 0
∗
∈
= NNa i
IIi
, 21 ,b a= − (3)
где wtVN /)(*
00 ′=∗ . Справедливы неравенства 0 1/ 2a< ≤ , 12/1 <≤ b .
Обозначим ∆ отрезок [ , ]t t′ ′− δ + δ , на котором функция )(*
0 tV непрерыв-
на, здесь 0δ > . Число 0δ > выберем настолько малым, чтобы выполнялось
соотношение ),0( *T⊂∆ .
Определим стратегию )(0̂ tV следующим образом:
0
*
0 0
*
0
( ), [0, ] \ ,
ˆ ( ) ( ) , [ , ],
( ) , ( , ].
V t t T
V t bV t aY t t t
bV t aY t t t
∗ ∗ ∈ ∆
′ ′ ′= − ∈ − δ
′ ′ ′+ ∈ + δ
(4)
Здесь Y – вектор, принадлежащий подпространству 2
3E , такой, что
0)(, *
0 =′tVY и wY = . Легко видеть, что wtV =)(0̂ для тех значений 0≥t ,
в которых функция )(0̂ tV непрерывна.
При условии wV =0 из соотношений (2) следует
≥
<
=
,0,,,2
,0,,0
00
0
VNVN
VN
u
ii
i
i 1,2,..., .i m= (5)
Пусть 1Ii ∈ . Из соотношений (3) вытекает неравенство
*
0, ( ) 0.iN bV t aY′ − ≥ Поэтому средняя скорость сближения iû между точками
0X и iX на временном отрезке ∆ для стратегии )(0̂ tV согласно (5) определяет-
ся по формулам:
=+′+−′= 2/))(,2)(,2(ˆ *
0
*
0 aYtbVNaYtbVNu iii
)(,2 *
0 tVNb i ′= , 1Ii ∈ . (6)
Скорость сближения )(tui ′∗ между точками 0X и іХ в момент t′ для стратегии
)(*
0 tV согласно (5) определяется по формулам:
)(,2)( *
0 tVNtu ii ′=′∗ , 1.i I∈ (7)
МАКСИМАЛЬНОЕ ВРЕМЯ ПРЕСЛЕДОВАНИЯ ДЛЯ СТРАТЕГИИ ...
Компьютерная математика. 2014, № 1 145
Поскольку 1<b , то из (6) и (7) следуют неравенства ii utu ˆ)( >′∗ , 1Ii ∈ . Из этих
соотношений вытекает, что величина )ˆ)((min
1
1 ii
Ii
utu −′= ∗
∈
ε положительна.
Имеем
1ˆ ( )i iu u t∗ ′≤ − ε , 1Ii ∈ , (8)
где 1 0.ε >
Если 0Ii ∈ , то из ортогональности подпространств rE1 , 2
3E и соотношений
rEQ 10 ∈ , 2
3
*
0 }),({ EYtV ∈′ следует, что на временном отрезке ∆ справедливо
соотношение 0ˆ =iu .
Пусть 1−∈ Ii . В этом случае, как и в предыдущем, на временном отрезке ∆
справедливо равенство 0ˆ =iu . Действительно, пусть wtVN /)(ˆˆ
00 = , ∆∈t .
Из соотношений (4) следует соотношение waYbNN /ˆ *
00 m= , где 1
0
−∈ nEY .
Вектор iN можно представить в виде: wYbNaN iiii /*
0 +−= . Здесь aai ≥ ,
122 =+ ii ba , 1
0
−∈ n
i EY , wYi = . Имеем 0
ˆ,i i iN N a b a b≤ − + =
= 2 21 1 0.i ia a a a− − + − ≤ Последнее неравенство вытекает из соотношений
0>≥ aai . Из неравенства 0ˆ, 0 ≤NN i и соотношения (5) следует равенство
0ˆ =iu .
Обозначим ii ss ˆ,∗ величины уменьшения расстояния между точками 0X и
iX на временном отрезке ∆ для функций )(*
0 tV и )(0̂ tV соответственно.
Скорости сближения ∗
iu , iû неотрицательны и в случае 01 IIi U−∈ справедливо
равенство 0ˆ =iu . Поэтому
0ˆ ≥−∗
ii ss , 01 IIi U−∈ . (9)
Пусть 1Ii ∈ . Используя (8), выводим
1ˆ ˆ2 2 ( ( ) )i i is u u t∗ ′= δ ≤ δ − ε , 1Ii ∈ . (10)
Величина ∗
is удовлетворяет соотношениям
( ) ( ( ) ( ) ( )) 2 ( ) ( ) ( ) .i i i i i i i is u t dt u t u t u t dt u t u t u t dt∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗
∆ ∆ ∆
′ ′ ′ ′= = − + ≥ δ − −∫ ∫ ∫
С.В. ПАШКО
Компьютерная математика. 2014, № 1 146
Поскольку функция )(tui
∗ непрерывна на отрезке ∆ , то число 0δ > можно вы-
брать таким образом, чтобы выполнялось неравенство 1( ) ( ) / 2i iu t u t∗ ∗ ′− ≤ ε ,
∆∈t . Поэтому справедливо неравенство 12 ( ( ) / 2)i is u t∗ ∗ ′≥ δ − ε . Из этого нера-
венства и (10) вытекает 1 1 1ˆ 2 ( ( ) / 2 ( ) ) .i i i is s u t u t∗ ∗ ∗′ ′− ≥ δ − ε − + ε = δε Таким об-
разом, справедливы соотношения
1ˆi is s∗ − ≥ δε , 1Ii ∈ . (11)
Из соотношений (9) и (11) следует, что в момент *T расстояние между точ-
ками 0X и iX при условии 01 IIi U−∈ не меньше числа il , а при условии
1Ii ∈ не меньше числа 1il + δε , причем 1 0δε > . Поэтому существует число
0τ > такое, что на временном отрезке * *[ , ]T T + τ игрок E может избежать за-
хвата, если будет двигаться со скоростью )(*
0 tV ′ . Это противоречит предполо-
жению об оптимальности стратегии )(*
0 tV .
Теорема доказана.
Следствие. Пусть 2=n . В каждый момент времени ),0( *Tt ∈ , в который
стратегия )(*
0 tV непрерывна, существует такое число {1,2,..., },i m∈ что спра-
ведливо равенство 0)(, *
0 =tVN i .
Расчет оптимальной стратегии. Сформулируем задачу линейного програ-
ммирования, решение которой определяет оптимальную стратегию уклонения.
Пусть },...,,{ 121 −= niiiI – подмножество множества },...,2,1{ m такое, что систе-
ма векторов },...,,{
121 −
=
niii NNNH линейно независима, }{ I – множество всех
таких подмножеств. Пусть 21, II NN – векторы единичной длины, ортогональ-
ные каждому вектору из системы H, причем 21 II NN −= . Из доказанной теоре-
мы и теорем 1, 2 работы [2] вытекает существование оптимальной кусочно-
постоянной стратегии уклонения )(*
0 tV такой, что на каждом промежутке
постоянства вектор )(*
0 tV равен некоторому вектору IkwN , где }{ II ∈ ,
{1,2}k ∈ . Обозначим Ikt время, на протяжении которого игрок E имеет ско-
рость IkwN . Необходимо решить задачу линейного программирования
2
{ } 1
max,IkI I k
t
∈ =
→∑ ∑
iiII k IkiIk ldtu −≤∑ ∑∈ =}{
2
1
, 1,2,..., ,i m=
0≥Ikt , }{ II ∈ , 1,2.k =
МАКСИМАЛЬНОЕ ВРЕМЯ ПРЕСЛЕДОВАНИЯ ДЛЯ СТРАТЕГИИ ...
Компьютерная математика. 2014, № 1 147
Здесь iIku – скорость сближения игроков E и iP при условии, что вектор скорос-
ти убегающего равен IkwN . В соответствии с (2), величины iIku вычисляются по
формулам:
≥
<
=
,0,,,2
,0,,0
IkiIki
Iki
iIk NNNNw
NN
u mi ,...,2,1= , }{ II ∈ , 2,1=k .
Пример. Пусть три игрока преследуют одного на плоскости, т. е. 3=m ,
2=n (рисунок).
РИСУНОК. Преследование в случае равенства скоростей
Начала векторов IkN находятся в точке 0X (рисунок). Символами , ,α β γ
обозначим углы 302 ,, XXX , 103 ,, XXX , 201 ,, XXX соответственно. Имеем
2 .α + β + γ = π Считаем, что .γ ≤ β ≤ α Из условия (1) следуют неравенства
0,γ > ,β + γ > π / 2,β > π .α < π Предположим, / 2,γ ≥ π а направления век-
торов IkN выбраны таким образом, что справедливы равенства
0121 =u , 0132 =u , 0212 =u , 0231 =u , 0311 =u , 0322 =u . (12)
Имеем
122 2 cos( / 2) 2 sin ,u w w= γ − π = γ
131 2 cos( / 2) 2 sin ,u w w= β − π = β
211 2 cos( / 2) 2 sin ,u w w= γ − π = γ
232 2 cos( / 2) 2 sin ,u w w= α − π = α
X3
X2
X1
α
β
γ
N22
N31
N11
N32
N12
N21
X0
С.В. ПАШКО
Компьютерная математика. 2014, № 1 148
312 2 cos( / 2) 2 sin ,u w w= β − π = β
321 2 cos( / 2) 2 sin .u w w= α − π = α
Нужно решить задачу линейного программирования
11 12 21 22 31 32 max,t t t t t t+ + + + + →
22 31 1 1(sin ) (sin ) ( ) / (2 ),t t d l wγ + β ≤ −
11 32 2 2(sin ) (sin ) ( ) / (2 ),t t d l wγ + α ≤ −
12 21 3 3(sin ) (sin ) ( ) / (2 ),t t d l wβ + α ≤ −
0≥jkt , 3,2,1=j , 1,2.k =
Пусть ),,,,,( 323122211211
∗∗∗∗∗∗ tttttt – оптимальное решение этой задачи, =∗T
∗∗∗∗∗∗ +++++= 323122211211 tttttt – максимальное время преследования.
Поскольку / 2 ,π ≤ γ ≤ β ≤ α < π то выполняются неравенства sinγ ≥
sin sin ,≥ β ≥ α поэтому можно выбрать 0221211 === ∗∗∗ ttt , 1 1
31 ,
2 sin
d l
t
w
∗ −=
β
2 2
32 ,
2 sin
d l
t
w
∗ −=
α
3 3
21 .
2 sin
d l
t
w
∗ −=
α
Максимальное время преследования ∗T вычис-
ляется по формуле
1 1 2 3 2 31
.
2 sin sin
d l d d l l
T
w
∗ − + − −= + β α
(13)
Последнее соотношение выведено при условиях, что / 2,γ ≥ π а векторы IkN
выбраны таким образом, что выполняются равенства (12). Но легко проверить
справедливость (13) для всех , ,α β γ таких, что 0 < γ ≤ β ≤ α < π и для всех
допустимих векторов .IkN
Заключение. В работе рассмотрена задача оптимального уклонения одного
убегающего от нескольких преследователей в случае, когда каждый преследова-
тель независимо от других использует стратегию параллельного сближения, а
убегающий игрок стремится максимизировать время захвата. Считается, что
убегающий игрок находится внутри выпуклой оболочки точек расположения
преследователей и максимальные скорости всех участников игры равны. Сфор-
мулировано и доказано необходимое условие оптимальности, позволяющее эф-
фективно рассчитывать оптимальные стратегии.
МАКСИМАЛЬНОЕ ВРЕМЯ ПРЕСЛЕДОВАНИЯ ДЛЯ СТРАТЕГИИ ...
Компьютерная математика. 2014, № 1 149
С.В. Пашко
МАКСИМАЛЬНИЙ ЧАС ПЕРЕСЛІДУВАННЯ ДЛЯ СТРАТЕГІЇ
ПАРАЛЕЛЬНОГО ЗБЛИЖЕННЯ У ВИПАДКУ РІВНОСТІ ШВИДКОСТЕЙ ГРАВЦІВ
Робота присвячена диференційним іграм переслідування, в яких кілька гравців доганяють
одного, застосовуючи стратегію паралельного зближення. Сформу-льована та доведена необ-
хідна умова оптимальності, що дозволяє ефективно розраховувати оптимальні стратегії втечі.
S.V. Pashko
MAXIMUM TIME OF PURSUIT FOR THE STRATEGY OF PARALLEL APPROACH
IN THE CASE OF EQUAL SPEEDS OF THE PLAYERS
The paper deals with differential pursuit-evasion games with several players using the strategy of
parallel approach. Necessary optimality condition is formulated and proved. This condition allows
us to calculate effectively the optimal evading strategies.
1. Петросян Л.А., Томский Г.В. Геометрия простого преследования. – Новосибирск: Наука,
1983. – 140 с.
2. Пашко С.В., Яловец А.Л. Максимальное время преследования для стратегии параллель-
ного сближения // Проблеми програмування. – 2014. – № 4. – С. 91 – 105.
3. Рихсиев Б.Б. Дифференциальные игры с простыми движениями. – Ташкент: ФАН, 1989.
– 232 с.
Получено 08.01.2014
Об авторе:
Пашко Сергей Владимирович,
старший научный сотрудник
Института программных систем НАН Украины.
|