Гарантированное время преследования для стратегии параллельного сближения
Данная работа посвящена дифференциальным играм преследования, в которых несколько игроков догоняют одного, применяя стратегию параллельного сближения. Построена стратегия уклонения и доказана ее оптимальность. Исследованы свойства оптимальных стратегий уклонения. Сформулированы задачи линейного про...
Збережено в:
| Опубліковано в: : | Доповіді НАН України |
|---|---|
| Дата: | 2014 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Видавничий дім "Академперіодика" НАН України
2014
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/87593 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Гарантированное время преследования для стратегии параллельного сближения / С.В. Пашко // Доповiдi Нацiональної академiї наук України. — 2014. — № 4. — С. 43-48. — Бібліогр.: 6 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859636605789143040 |
|---|---|
| author | Пашко, С.В. |
| author_facet | Пашко, С.В. |
| citation_txt | Гарантированное время преследования для стратегии параллельного сближения / С.В. Пашко // Доповiдi Нацiональної академiї наук України. — 2014. — № 4. — С. 43-48. — Бібліогр.: 6 назв. — рос. |
| collection | DSpace DC |
| container_title | Доповіді НАН України |
| description | Данная работа посвящена дифференциальным играм преследования, в которых несколько игроков догоняют одного, применяя стратегию параллельного сближения. Построена
стратегия уклонения и доказана ее оптимальность. Исследованы свойства оптимальных стратегий уклонения. Сформулированы задачи линейного программирования, позволяющие строить такие стратегии.
Дана робота присвячена диференцiальним iграм переслiдування, в яких кiлька гравцiв доганяють одного, застосовуючи стратегiю паралельного зближення. Побудовано стратегiю
втечi та доведено її оптимальнiсть. Вивчено властивостi оптимальних стратегiй втечi.
Сформульовано задачi лiнiйного програмування, що дозволяють будувати такi стратегiї.
This paper is concerned with differential pursuit-evasion games, in which several players chase one,
using the strategy of parallel approach. The strategy of evasion is constructed, and its optimality is
proved. Optimal strategies of evasion are investigated. Linear programming problems, which specify
the optimal strategies of evasion, are stated.
|
| first_indexed | 2025-12-07T13:16:15Z |
| format | Article |
| fulltext |
УДК 518.9
С.В. Пашко
Гарантированное время преследования для стратегии
параллельного сближения
(Представлено академиком НАН Украины Ф.И. Андоном)
Данная работа посвящена дифференциальным играм преследования, в которых несколь-
ко игроков догоняют одного, применяя стратегию параллельного сближения. Построена
стратегия уклонения и доказана ее оптимальность. Исследованы свойства оптималь-
ных стратегий уклонения. Сформулированы задачи линейного программирования, по-
зволяющие строить такие стратегии.
Задачи преследования–уклонения занимают одно из центральных мест в теории динамичес-
ких игр. В данной работе рассматривается задача оптимального уклонения одного убегаю-
щего от нескольких преследователей. Предполагается, что каждый преследователь исполь-
зует стратегию параллельного сближения [1]. В качестве критерия выступает время захвата
цели, которое убегающий игрок стремится максимизировать.
В последнее время проявляется интерес к созданию многоагентных роботизированных
систем преследователей [2], поэтому рассматриваемая задача является актуальной.
Движение игроков считается простым. Это значит, что в каждый момент времени игрок
может выбрать произвольный вектор скорости движения, норма которого не превосходит
заданную величину. Скорости считаются кусочно-непрерывными функциями от времени.
Стратегия параллельного сближения состоит в следующем. Каждый преследователь,
зная скорость преследуемого в данный момент времени, считает эту скорость постоянной
и вычисляет на линии движения убегающего игрока точку захвата, в которой он может
догнать его, двигаясь с постоянной максимальной скоростью. В текущий момент времени
вектор скорости преследователя направлен на точку захвата, а величина скорости макси-
мальна. Если максимальные скорости преследователя и убегающего равны, а точка захвата
отсутствует, преследователь двигается параллельно убегающему игроку.
Ниже построены стратегии уклонения, каждая из которых определяется пределом по-
следовательности оптимальных решений задач линейного программирования. Приведена
теорема об оптимальности таких стратегий. Построенные оптимальные стратегии являю-
тся кусочно-постоянными функциями от времени, причем число промежутков постоянства
не превосходит число преследователей.
В случае, когда максимальные скорости всех игроков равны, выведено дополнительное
необходимое условие оптимальности. Оно состоит в том, что вектор скорости убегающего
игрока должен быть ортогонален прямой, проходящей через точки расположения убегаю-
щего и одного из преследователей.
Описаны задачи линейного программирования, решения которых позволяют строить
оптимальные или близкие к ним стратегии уклонения. Приведена теорема о величине по-
грешности получаемых таким образом стратегий.
© С. В. Пашко, 2014
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2014, №4 43
Хотя изложенные в данной работе утверждения могут быть обобщены на случай n-мер-
ного пространства, ниже задачи оптимального уклонения рассмотрены для евклидовой
плоскости.
Оптимальные стратегии уклонения и гарантированное время преследования.
Пусть на плоскости в точке X0 = X0(t) расположен преследуемый игрок E, а в точках
Xi = Xi(t) находятся преследователи Pi, i = 1, 2, . . . ,m. Двухмерные векторы Vi = Vi(t),
i = 0, 1, . . . ,m, обозначают скорости игроков (нулевое значение индекса i относится к игро-
ку E).
Уравнения движения игроков имеют вид Ẋi = Vi, i = 0, 1, . . . ,m. Считаем, что выполня-
ются ограничения 0 6 ‖Vi‖ 6 wi, i = 0, 1, . . . ,m, где 0 < wi < ∞ — максимальная величина
скорости; ‖X‖ =
√
x2 + y2 — длина вектора X = (x, y). Пусть выполняются неравенства
w0 6 wi, i = 1, 2, . . . ,m.
Скорость V0(t) считается кусочно-непрерывной функцией от времени. Это значит, что
в каждом ограниченном временном интервале существует не больше конечного числа точек
разрыва первого рода. Поскольку каждый преследователь применяет стратегию параллель-
ного сближения, то функции Vi(t), i = 1, 2, . . . ,m, также являются кусочно-непрерывными.
Игрок E управляет своими координатами, выбирая в каждый момент времени вектор
скорости V0, являющийся функцией от времени и от точек X0(t), X1(t), . . ., Xm(t). Функцию
V0(t), t > 0, будем называть стратегией убегающего игрока и обозначать S.
Пусть di(t) = ‖Xi(t) − X0(t)‖, li > 0 — заданные числа, i = 1, 2, . . . ,m. Определим
функцию d(t) следующим образом: d(t) = 0, если для некоторого значения i ∈ {1, 2, . . . ,m}
справедливо равенство di(t) = 0 или выполняется неравенство di(t) < li; d(t) = 1 в про-
тивном случае.
Игра начинается в момент времени t = 0. Временем окончания игры назовем величину
T (S) = inf {t : d(t) = 0, t > 0}. Игрок E стремится максимизировать величину T (S). Га-
рантированным временем преследования назовем число T ∗ = sup
S
T (S). Стратегию S, для
которой справедливо равенство T (S) = T ∗, назовем оптимальной стратегией уклонения.
Считаем, что выполняются условия
di(0) > li, i = 1, 2, . . . ,m. (1)
Для таких значений i, что wi = w0, дополнительно потребуем выполнения неравенства
li > 0. Это условие обеспечивает существование оптимальных стратегий уклонения.
Свойства оптимальных стратегий уклонения. Обозначим conv{X1,X2, . . . ,Xm}
выпуклую оболочку точек X1, X2, . . . ,Xm. Пусть intX — внутренность множества X.
Рассмотрим случай, когда точка расположения убегающего X0 принадлежит внутрен-
ности выпуклой оболочки точек X1, X2, . . . ,Xm, т. е. выполняется условие
X0 ∈ int conv{X1,X2, . . . ,Xm}. (2)
Известно [3], что стратегия параллельного сближения обладает следующим свойством.
Прямая, проходящая через точки X0(t) и Xi(t), в которых находятся игроки E и Pi, при
каждом t > 0 параллельна прямой, проходящей через точки X0(0) и Xi(0). Используя это,
легко вывести формулы для величин скоростей сближения ui = ui(t) объектов E и Pi:
ui = v0 cos θi +
√
w2
i − v20 sin
2 θi, i = 1, 2, . . . ,m. (3)
44 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2014, №4
Здесь v0 = v0(t) = ‖V0(t)‖, θi = θi(t) — угол, образованный векторами V0 и
−→
X0(0)Xi(0)
в момент t (при условии ‖V0(t)‖ = 0 считаем θi = 0).
Задачу поиска оптимальной стратегии уклонения запишем в виде
T −→ max, (4)
T
∫
0
ui(t) dt 6 di − li, i = 1, 2, . . . ,m. (5)
Здесь и далее di = di(0) — расстояние между игроками E и Pi в момент t = 0.
Важно заметить следующее. Углы между векторами
−→
X0Xi и
−→
X0Xj на протяжении игры
остаются постоянными, поскольку прямые X0(t)Xk(t) и X0(0)Xk(0) параллельны при каж-
дом t > 0; k = 1, 2, . . . ,m. Скорости сближения ui(t) неотрицательны. Стратегия уклоне-
ния V0(t) обладает следующим свойством. Поменяем местами скорости на отрезках [t1, t2]
и [t3, t4], где 0 < t1 < t2 < t3 < t4 < T (V0), t2 − t1 = t4 − t3. Образуем новую стратегию
уклонения V 1
0 (t), где V 1
0 (t) = V0(t), если t /∈ [t1, t2] и t /∈ [t3, t4]; V
1
0 (t) = V0(t+ t3 − t1), если
t ∈ [t1, t2]; V
1
0 (t) = V0(t+ t1 − t3), если t ∈ [t3, t4]. В момент времени t4 координаты игроков
не зависят от того, которая из двух стратегий применяется.
Сформулируем задачу линейного программирования, являющуюся приближением за-
дачи (4), (5). Выберем величину угла δ по формуле δ = π/(2n), где n — натуральное число.
Пусть в каждый момент времени вектор V0 лежит на одном из лучей, выходящих из начала
координат и образующих углы jδ с осью абсцисс, j = 1, 2, . . . , 4n, и V0 = w0. Угол между
вектором Xi − X0 и лучом jδ обозначим θij.
В соответствии с соотношениями (3), скорости сближения uij игроков E и Pi вычисля-
ются по формулам
uij = w0 cos θij +
√
w2
i −w2
0 sin
2 θij, i = 1, 2, . . . ,m, j = 1, 2, . . . , 4n. (6)
Обозначим tj время, в течение которого вектор скорости игрока E лежит на луче jδ. Рас-
смотрим задачу линейного программирования
4n
∑
j=1
tj −→ max, (7)
4n
∑
j=1
uijtj 6 di − li, i = 1, 2, . . . ,m, (8)
tj > 0, j = 1, 2, . . . , 4n. (9)
Легко доказать, что для любой стратегии уклонения время окончания игры не превос-
ходит некоторую константу T < ∞. Величину T нетрудно выписать в явном виде как функ-
цию от параметров игры. Из этого следует, что целевая функция (6) на множестве (7), (8)
ограничена сверху константой T . Поэтому оптимальное решение задачи (6)–(8) сущест-
вует, причем одно из оптимальных решений находится в угловой точке [4]. Но решение,
соответствующее угловой точке, содержит не больше, чем m положительных компонент.
Значит, оптимальное решение S∗
n = (t
∗(n)
1 , t
∗(n)
2 , . . . , t
∗(n)
4n ) задачи (6)–(8) можно представить
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2014, №4 45
в виде S∗
n = (t
∗(n)
j
(n)
1
, t
∗(n)
j
(n)
2
, . . . , t
∗(n)
j
(n)
m
, j
(n)
1 , j
(n)
2 , . . . , j(n)m ), где j
(n)
k ∈ {1, 2, . . . , 4n} и t
∗(n)
j = 0, если
j ∈ {1, 2, . . . , 4n} \ {j
(n)
1 , j
(n)
2 , . . . , j(n)m }.
Очевидно, вместо последнего представления S∗
n можно использовать S∗
n = (t
(n)
1 , t
(n)
2 , . . .,
. . . t(n)m , ϕ
(n)
1 , ϕ
(n)
2 , . . . , ϕ(n)
m ), где t
(n)
k = t
∗(n)
j
(n)
k
— время, в течение которого вектор скорости
игрока E лежит на луче, образующем угол ϕ
(n)
k = j
(n)
k δ с осью абсцисс, k = 1, 2, . . . ,m. Пос-
кольку t
(n)
k ∈ [0, T ], ϕ
(n)
k ∈ [0, 2π], k = 1, 2, . . . ,m, можно считать, что точки S∗
n принадлежат
замкнутому ограниченному множеству Q, которое является подмножеством 2m-мерного
евклидового пространства.
Множество Q является компактным, поэтому последовательность S∗
n, n = 1, 2, 3, . . . ,
имеет предельную точку S∗ = (t∗1, t
∗
2, . . . , t
∗
m, ϕ∗
1, ϕ
∗
2, . . . , ϕ
∗
m), причем S∗ ∈ Q [5]. Точка S∗
определяет стратегию уклонения (которая также обозначается S∗), состоящую в том, что на
непрерывном промежутке времени длиной t∗k вектор скорости V0 образует угол ϕ∗
k с осью
абсцисс, причем ‖V0‖ = w0.
Теорема 1. Стратегия S∗ является оптимальной стратегией уклонения.
Теорема 1 утверждает, что время окончания игры
m
∑
i=1
t∗i стратегии S∗ не меньше, чем
время окончания игры любой другой стратегии уклонения. Количество промежутков по-
стоянства построенной оптимальной стратегии S∗ не превосходит число преследователей m.
Пусть V ∗
0 (t), t > 0, — некоторая оптимальная стратегия уклонения; T ∗ — соответствую-
щее время окончания игры.
Теорема 2. В каждый момент времени t ∈ (0, T ∗), в который оптимальная стратегия
V ∗
0 (t) непрерывна, справедливо равенство ‖V ∗
0 (t)‖ = w0.
Теорема 2 утверждает, что с целью максимизации времени окончания игры убегающий
должен двигаться с максимальной скоростью.
Приведем оценку погрешности стратегии, соответствующей оптимальному решению за-
дачи (6)–(8). Обозначим g = min
i=1,...,m
(di − li), hn = g/(g + πw0T/n). Очевидно, hn −→ 1, если
n −→ ∞. Пусть T ∗
n — оптимальное значение целевой функции задачи (6)–(8), соответству-
ющее оптимальному решению S∗
n.
Теорема 3. Оптимальное значение целевой функции T ∗
n удовлетворяет неравенствам
hnT
∗
6 T ∗
n 6 T ∗, n = 1, 2, 3, . . . .
Пример. Предположим, три игрока преследуют одного. Исходные данные заданы ра-
венствами m = 3, X0 = (0, 0), X1 = (300, 200), X2 = (−300, 150), X3 = (0,−400), l1 = l2 =
= l3 = 30, w0 = 5,0, w1 = 5,5, w2 = 6,0, w3 = 6,5. Для получения близкой к оптимальной
стратегии уклонения решена задача линейного программирования (6)–(8) при условиях
n = 90, d1 = ‖X1‖ = 360, 6, d2 = ‖X2‖ = 335, 4, d3 = ‖X3‖ = 400.
Оптимальное решение этой задачи: t
∗(n)
66 = 15,8, t
∗(n)
118 = 23,7, t
∗(n)
316 = 33,6. Время оконча-
ния игры t
∗(n)
66 + t
∗(n)
118 + t
∗(n)
316 равно 73,1. На рис. 1 изображены траектории игроков E, P1,
P2, P3 от момента начала игры до момента ее окончания.
В случае X0 /∈ int conv{X1,X2, . . . ,Xm} из результатов работ [3, 6] легко вывести сле-
дующее. При выполнении условий wi > w0, li = 0, i = 1, 2, . . . ,m, существует точка X∗
такая, что стратегия уклонения игрока E, заключающаяся в прямолинейном движении
с максимальной скоростью по направлению к точке X∗, оптимальна. Гарантированное вре-
мя преследования равно ‖X∗ − X0‖/w0.
46 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2014, №4
Рис. 1. Траектории преследования и уклонения
Предположим, справедливы равенства w0 = w1 = · · · = wm. В этом случае захват
гарантируется только при условии (2), поэтому считаем, что оно выполняется. Ниже 〈·, ·〉
обозначает скалярное произведение.
Теорема 4. В каждый момент времени t ∈ (0, T ∗), в который оптимальная страте-
гия V ∗
0 (t) непрерывна, найдется такое число i ∈ {1, 2, . . . ,m}, что справедливо равенство
〈Xi(0) − X0(0), V
∗
0 (t)〉 = 0.
Теорема 4 позволяет сформулировать задачу линейного программирования, содержа-
щую m ограничений и 2m переменных, решение которой определяет оптимальную страте-
гию уклонения.
1. Петросян Л.А., Томский Г.В. Геометрия простого преследования. – Новосибирск: Наука, 1983. –
140 с.
2. Vieira Marcos A.M., Govindan R., Sukhatme G. S. Scalable and practical pursuit-evasion with networked
robots // J. of Intelligent Service Robotics. Special Iss. on Networked Robots. – 2009. – 2. – P. 247–263.
3. Рихсиев Б. Б. Дифференциальные игры с простыми движениями. – Ташкент: ФАН, 1989. – 232 с.
4. Карманов В. Г. Математическое программирование. – Москва: ФИЗМАТЛИТ, 2004. – 264 с.
5. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. – Москва:
Наука, 1972. – 496 с.
6. Пашко С.В. Квазиоптимальные стратегии в дифференциальных играх преследования на плоскос-
ти // Пробл. управления и информатики. – 2012. – № 6. – С. 30–43.
Поступило в редакцию 17.09.2013Институт программных систем НАН Украины, Киев
С.В. Пашко
Гарантований час переслiдування для стратегiї паралельного
зближення
Дана робота присвячена диференцiальним iграм переслiдування, в яких кiлька гравцiв до-
ганяють одного, застосовуючи стратегiю паралельного зближення. Побудовано стратегiю
втечi та доведено її оптимальнiсть. Вивчено властивостi оптимальних стратегiй втечi.
Сформульовано задачi лiнiйного програмування, що дозволяють будувати такi стратегiї.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2014, №4 47
S.V. Pashko
Guaranteed time of pursuit for the strategy of parallel approach
This paper is concerned with differential pursuit-evasion games, in which several players chase one,
using the strategy of parallel approach. The strategy of evasion is constructed, and its optimality is
proved. Optimal strategies of evasion are investigated. Linear programming problems, which specify
the optimal strategies of evasion, are stated.
48 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2014, №4
|
| id | nasplib_isofts_kiev_ua-123456789-87593 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | Russian |
| last_indexed | 2025-12-07T13:16:15Z |
| publishDate | 2014 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| record_format | dspace |
| spelling | Пашко, С.В. 2015-10-21T17:15:35Z 2015-10-21T17:15:35Z 2014 Гарантированное время преследования для стратегии параллельного сближения / С.В. Пашко // Доповiдi Нацiональної академiї наук України. — 2014. — № 4. — С. 43-48. — Бібліогр.: 6 назв. — рос. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/87593 518.9 Данная работа посвящена дифференциальным играм преследования, в которых несколько игроков догоняют одного, применяя стратегию параллельного сближения. Построена стратегия уклонения и доказана ее оптимальность. Исследованы свойства оптимальных стратегий уклонения. Сформулированы задачи линейного программирования, позволяющие строить такие стратегии. Дана робота присвячена диференцiальним iграм переслiдування, в яких кiлька гравцiв доганяють одного, застосовуючи стратегiю паралельного зближення. Побудовано стратегiю втечi та доведено її оптимальнiсть. Вивчено властивостi оптимальних стратегiй втечi. Сформульовано задачi лiнiйного програмування, що дозволяють будувати такi стратегiї. This paper is concerned with differential pursuit-evasion games, in which several players chase one, using the strategy of parallel approach. The strategy of evasion is constructed, and its optimality is proved. Optimal strategies of evasion are investigated. Linear programming problems, which specify the optimal strategies of evasion, are stated. ru Видавничий дім "Академперіодика" НАН України Доповіді НАН України Інформатика та кібернетика Гарантированное время преследования для стратегии параллельного сближения Гарантований час переслiдування для стратегiї паралельного зближення Guaranteed time of pursuit for the strategy of parallel approach Article published earlier |
| spellingShingle | Гарантированное время преследования для стратегии параллельного сближения Пашко, С.В. Інформатика та кібернетика |
| title | Гарантированное время преследования для стратегии параллельного сближения |
| title_alt | Гарантований час переслiдування для стратегiї паралельного зближення Guaranteed time of pursuit for the strategy of parallel approach |
| title_full | Гарантированное время преследования для стратегии параллельного сближения |
| title_fullStr | Гарантированное время преследования для стратегии параллельного сближения |
| title_full_unstemmed | Гарантированное время преследования для стратегии параллельного сближения |
| title_short | Гарантированное время преследования для стратегии параллельного сближения |
| title_sort | гарантированное время преследования для стратегии параллельного сближения |
| topic | Інформатика та кібернетика |
| topic_facet | Інформатика та кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/87593 |
| work_keys_str_mv | AT paškosv garantirovannoevremâpresledovaniâdlâstrategiiparallelʹnogosbliženiâ AT paškosv garantovaniičasperesliduvannâdlâstrategiíparalelʹnogozbližennâ AT paškosv guaranteedtimeofpursuitforthestrategyofparallelapproach |