=Paper=
{{Paper
|id=Vol-1662/opt6
|storemode=property
|title=Существование функции цены в игре быстродействия с линией жизни(Existence of value function in time-optimal game with life line)
|pdfUrl=https://ceur-ws.org/Vol-1662/opt6.pdf
|volume=Vol-1662
|authors=Nataly V. Munts,Sergey S. Kumkov
}}
==Существование функции цены в игре быстродействия с линией жизни(Existence of value function in time-optimal game with life line)==
https://ceur-ws.org/Vol-1662/opt6.pdf
Существование функции цены в игре быстродействия
с линией жизни
Н.В. Мунц С.С. Кумков
natalymunts@gmail.com sskumk@gmail.com
ИММ УрО РАН (Екатеринбург) УрФУ (Екатеринбург)
Аннотация
В статье рассматриваются дифференциальные игры быстродей-
ствия с линией жизни. В таких играх цель первого игрока — как
можно быстрее привести систему на замкнутое целевое множество
так, чтобы траектория в каждый момент времени принадлежала
некоторому открытому множеству, на котором и происходит игра.
Второй игрок препятствует этому, причем, как только траектория
системы покидает множество игры, второй игрок немедленно вы-
игрывает. Многие практические задачи преследования-уклонения
могут быть поставлены и решены в рамках этого класса игр. В
данной статье представлено доказательство существования функ-
ции цены.
1 Постановка задачи
По всей видимости, первым задачи с линией жизни сформулировал Р. Айзекс в своей книге [1, 2]. В его
формулировках под линией жизни понималось множество, достигнув которое, второй игрок безусловно
выигрывал. Значительный вклад в исследование игр с линией жизни сделал Л.А. Петросян (см., напри-
мер, [3, 4, 5, 6]). Однако авторам неизвестны работы, в которых исчерпывающе рассматривались бы игры
такого типа: Л.А. Петросян в основном исследовал задачи, где игроки имели динамику простых движений.
В данной статье решается вопрос о существовании функции цены игры быстродействия с линией жизни.
При доказательстве существования функции цены авторы опираются на подход, предложенный Н.Н.
Красовским и А.И. Субботиным [9, 10] и основанный на изучении пучков конструктивных движений.
Соответствующие определения вкратце будут даны ниже.
Рассмотрим задачу быстродействия:
ẋ = f (x, u, v), t > 0, x(0) = x0 , u ∈ P, v ∈ Q. (1)
Здесь x ∈ Rn — фазовый вектор, u и v — управления первого и второго игроков соответственно; компакт-
ные множества P и Q — геометрические ограничения на управления игроков. Функция f правой части
динамики непрерывна по совокупности переменных x, u, v и глобально липшицева по переменной x. Также
считаем, что выполнено условие седловой точки в маленькой игре (условие Айзекса):
∀x, p ∈ Rn min max p, f (x, u, v) = max min p, f (x, u, v) .
u∈P v∈Q v∈Q u∈P
Copyright c by the paper’s authors. Copying permitted for private and academic purposes.
In: A.A. Makhnev, S.F. Pravdin (eds.): Proceedings of the 47th International Youth School-conference “Modern Problems in
Mathematics and its Applications”, Yekaterinburg, Russia, 02-Feb-2016, published at http://ceur-ws.org
94
Здесь символ h· , ·i означает скалярное произведение.
Игра происходит на открытом ограниченном множестве G. Компактное множество T является терми-
нальным, T ⊂ G. Обозначим F = Rn \ G (рис. 1). Начальное положение системы x0 ∈ cl G. (Здесь и далее
символ cl обозначает замыкание множества.) Первый игрок, использующий управление u, стремится при-
вести систему на множество T , не выводя движение из G. Второй игрок, использующий управление v,
старается либо вообще этого избежать, бесконечно долго сохраняя движение системы на G или выводя
его на F, либо как можно сильнее отдалить момент попадания системы на целевое множество, если это
неизбежно.
Рис. 1: множества T , F и G
Формализовать такие цели игроков в виде функции платы можно следующим образом. Для заданных
управлений игроков u(·) и v(·), определим величины
t∗ x0 , u(·), v(·) = min t : x t; x0 , u(·), v(·) ∈ F .
t∗ x0 , u(·), v(·) = min t : x t; x0 , u(·), v(·) ∈ T ,
Если траектория не приходит на множество T (F), тогда величина t∗ (t∗ ) полагается равной +∞. Опре-
делим результат игры как
(
+∞, если t∗ = +∞ или t∗ < t∗ ,
T x0 , u(·), v(·) = (2)
t∗ , иначе.
Такую игру можно называть игрой с линией жизни: граница ∂F множества F — это линия жизни, т.е.
область, где второй игрок безоговорочно выигрывает.
Некоторое неудобство для численного исследования игры (1), (2) представляет неограниченность зна-
чений функций платы и цены. Поэтому часто с помощью замены Кружкова от неограниченной функции
платы переходят к ограниченной:
(
1 − exp − T x0 , u(·), v(·) , если T x0 , u(·), v(·) < +∞,
J x0 , u(·), v(·) = (3)
1, иначе.
При этом функция цены также становится ограниченной, и ее значения лежат в диапазоне от нуля до
единицы.
Постановка игры без линии жизни (то есть когда множество G совпадает со всем фазовым простран-
ством Rn ) аналитически исследовалась в книге Р. Айзекса [1, 2]. Методика, предложенная им, основана
на разделении пространства игры сингулярными поверхностями на области, в которых функция цены
регулярна и в классическом смысле удовлетворяет соответствующему уравнению Гамильтона – Якоби. Од-
нако практическое применение этой методики наталкивается на существенные трудности, связанные с
обнаружением и классификацией сингулярных поверхностей, особенно в случае размерности фазового
вектора 3 или более. Численные методы построения функции цены игр быстродействия были предложены
В.С. Пацко и В.Л. Туровой [17, 18, 15]. Эти методы имеют геометрический характер и ориентированы на
решение задач на плоскости (с двумерным фазовым вектором). Более универсальный сеточный алгоритм
построения функции цены игр быстродействия был предложен итальянскими математиками М. Барди и
М. Фальконе [7, 8]. Он вычисляет функцию цены как вязкостное решение [11, 12] соответствующего уравне-
ния Гамильтона – Якоби. Однако данный метод обладает одним существенным недостатком с точки зрения
95
его практического применения. А именно, корректность его работы обоснована в случае использования бес-
конечных сеток, покрывающих все игровое пространство Rn , в то время как при компьютерной реализации
можно использовать лишь конечные сетки. Это приводит к необходимости задавать краевые условия для
функции цены на внешней границе сетки, где ее обычно полагают равной бесконечности (единице по-
сле замены Кружкова). Таким образом, компьютерная реализация метода Барди – Фальконе фактически
решает задачу быстродействия (1), (3), происходящую на открытом множестве, с линией жизни, совпадаю-
щей с внешней границей области, покрытой сеткой. Этот факт дополнительно стимулирует необходимость
всестороннего исследования таких задач.
2 Существование функции цены
Существование функции цены следует из результатов книг [9, 10], а именно, из разделов «Игра на
минимакс-максимин времени до встречи» на стр. 79–86 в первой из них и «Differential Games of Pursuit-
Evasion» на стр. 106–112 второй.
В указанных разделах рассматривается задача быстродействия с динамикой (1). Заданы замкнутое
терминальное множество M∗ и замкнутое множество N ∗ , на котором и происходит игра. Считается, что
M∗ ⊂ N ∗ . Плата на траектории x(·) определяется как
τ 0 x(·) = min t : x(t) ∈ M∗ , ∀ϑ ∈ [0, t] x(ϑ) ∈ N ∗ .
(4)
∗ ∗ ∗
никогда не приходит на M или же до попадания на M покидает множество N ,
Если траектория x(·)
0
то полагаем τ x(·) = +∞.
Пусть заданы автономная стратегия первого игрока U : Rn → P и начальная позиция x0 ∈ N ∗ . Выберем
разбиение времени
∆ = {0 = t0 < t1 < . . . }.
Обозначим за X1 (x0 , U, ∆) множество пошаговых движений системы
u(t) ≡ U x(ti ) , ti 6 t < ti+1 , i = 0, 1, 2, . . . , (5)
ẋ(t) ∈ f t, x(t), u(t), v : v ∈ Q . (6)
Элементами этого множества являются абсолютно-непрерывные функции x(·) : [0, ∞) → Rn , удовлетворя-
ющие начальному условию x(0) = x0 и дифференциальному включению (6) для почти всех t ∈ [0, ∞), где
управление u(t) формируется по правилу (5). Определим величину
diam ∆ = sup (ti+1 − ti ).
i=1,2,...
Пусть xl ∈ X1 (x0 , U, ∆l ) (l = 1, 2, . . . ) — последовательность пошаговых движений. Если xl (·) сходится к
x∗ (·) и diam ∆l → 0 при l → ∞, то предельная функция x∗ (·) называется конструктивным движением,
порожденным стратегией U [10, стр.107]. Пучок всех конструктивных движений обозначается X1 (x0 , U ).
Множество X1 (x0 , U ) непусто и секвенциально компактно в C [0, ∞) → Rn , т.е. из любой последова-
тельности xk (·) ∈ X1 (x0 , U ) (k = 1, 2, . . . ) можно выделить подпоследовательность xkl (·) (l = 1, 2, . . . ),
сходящуюся к предельной функции x∗ (·), принадлежащей множеству X1 (x0 , U ). Здесь сходимость понима-
ется в смысле компактно-открытой топологии (а не в смысле обычной метрики пространства C, поскольку
промежуток времени неограничен).
Аналогично вводится множество конструктивных движений X2 (x0 , V ), порожденное позиционной стра-
тегией V : Rn → Q убегающего. Длялюбой стратегии V множество X2 (x0 , V ) будет непустым и секвенци-
ально компактным в C [0, ∞) → Rn (в компактно-открытой топологии).
Гарантированные результаты, обеспечиваемые позиционными стратегиями U : R × Rn → P и V : R×
×Rn → Q первого и второго игрока, находятся из соотношений
Γ1 (x0 , U ) = sup τ 0 x(·) : x(·) ∈ X1 (x0 , U ) ,
Γ2 (x0 , V ) = min τ 0 x(·) : x(·) ∈ X2 (x0 , V ) .
В книгах [9, 10] доказана следующая
96
Теорема 1. Для любой начальной позиции x ∈ Rn в дифференциальной игре преследования существует
момент ω 0 ∈ [0, ∞] такой, что
min Γ1 (x0 , U ) = sup Γ2 (x0 , V ) = ω 0 .
U V
Однако этот результат нельзя напрямую применить к играм (1), (2) и (1), (3), так как они происходят
на незамкнутом множестве G. Для определения цены игры подменим открытое множество G, на котором
происходит игра, некоторым замкнутым.
Пусть Bε — замкнутый шар радиуса ε с центром в начале координат. Обозначим Tε = T , Fε = F + Bε ,
Gε = Rn \ (Fε ∪ Tε ). Здесь знак «+» для операндов-множеств обозначает алгебраическую сумму (сумму
Минковского). Используя Tε как целевое множество, а cl Gε — как множество фазовых ограничений, введем
функцию платы аналогично (4):
τeε x(·) = min t : x(t) ∈ Tε , ∀ϑ ∈ [0, t] x(ϑ) ∈ cl Gε .
(7)
Гарантированные результаты игроков определяются сходным образом:
e ε (x0 , U ) = sup τeε x(·) : x(·) ∈ X1 (x0 , U ) ,
Γ 1
e ε2 (x0 , V ) = min τeε x(·) : x(·) ∈ X2 (x0 , V ) .
Γ
Стало быть, можно рассмотреть семейство игр быстродействия (1), (7), параметризованных величиной ε:
M∗ = Tε , N ∗ = cl Gε . При любом достаточно малом ε > 0 из теоремы 1 следует
Теорема 2. Для любой начальной позиции x0 ∈ Rn и для любого достаточно малого ε > 0 в дифферен-
циальной игре преследования (1), (7) существует момент ω ε ∈ [0, ∞] такой, что
e ε1 (x0 , U ) = sup Γ
inf Γ e ε2 (x0 , V ) = ω ε .
U V
Рассмотрим пределы гарантированных результатов по ε:
Γ e ε1 (x0 , U ),
e ε1 (x0 ) = inf Γ e ε2 (x0 ) = sup Γ
Γ e ε2 (x0 , V ),
U V
e 01 (x0 ) = lim Γ
Γ e ε1 (x0 ), e 02 (x0 ) = lim Γ
Γ e ε2 (x0 ).
ε→0 ε→0
Пусть x0 — такая точка, что для некоторого ε > 0 первый игрок может привести систему на терминаль-
ное множество Tε = T , удерживая ее в множестве cl Gε . Тогда для любых ε1 , ε2 таких, что 0 < ε1 < ε2 6 ε,
имеем Γ e ε1 (x0 ) 6 Γ
e ε2 (x0 ). Если же точка x0 такова, что для любой стратегии U первого игрока траектории
1 1
из пучка X1 (x0 , U ) или приходят на F до попадания на T , или навсегда остаются в G, не попадая на T ,
ε
e ε (x0 ) = +∞ для любого ε. Следовательно, значения функций из семейства Γ
то Γ e (·) в любой точке x
1 1 ε
порождают числовое семейство, либо монотонное по ε, либо стационарное. Из этого следует, что существу-
ет поточечный предел Γ e ε (·) → Γ
e 0 (·) при ε → 0. Поскольку для любого ε функции Γ
e ε (·) и Γ
e ε (·) совпадают,
1 1 1 2
0 ε e 0 (·). Этот
то при ε → 0 также существует и поточечный предел Γ2 (·) функций Γ2 (·), который совпадает с Γ
e e
1
общий предел является ε-седловой точкой Val игры (1), (2). Термин ε-седловая точка понимается в том
смысле, что каждый из игроков может указать свою стратегию, гарантирующую результат, сколь угодно
близкий к значению Val. Отсюда следует, что игра (1), (3) также имеет цену V (как ε-седловую точку) и
для всех x ∈ G выполняется соотношение V(x) = 1 − exp − Val(x) .
3 Заключение
Важным классом дифференциальных игр являются игры с линией жизни, где под линией жизни пони-
мается такое множество, при попадании системы на которое второй игрок немедленно выигрывает. Будучи
предложенными еще в 1950-60 годы Р. Айзексом, они были исследованы лишь в весьма несложных поста-
новках: в случае простой динамики системы или простой формы линии жизни. Кроме того, этот класс
игр интересен тем, что практическая реализация численного метода решения игр быстродействия, предло-
женного итальянскими учеными М. Барди и М. Фальконе, фактически строит решение некоторой игры с
линией жизни. В данной статье, с использованием идеологии конструктивных движений Н.Н. Красовского,
доказано существование функции цены игры с линией жизни в весьма общей постановке.
В дальнейшем, авторы планируют обосновать существование обобщенного решения (минимаксного или
вязкостного) для краевой задачи уравнения типа Гамильтона – Якоби, соответствующей игре с линией
жизни. Также планируется доказать совпадение цены игры и обобщенного решения.
97
Благодарности
Данное исследование финансово поддержано Российским фондом фундаментальных исследований, про-
ект № 15-01-07909.
Список литературы
[1] R. Isaacs. Differential Games. John Wiley and Sons, New York, 1965.
[2] R. Isaacs. Differential Games. Mir, Moscow, 1967 (in Russian). = Р. Айзекс. Диффиренциальные игры.
М.: Мир, 1967.
[3] L.A. Petrosjan. A family of differential survival games in the space Rn . Soviet Math. Dokl., 6:377–380, 1965.
[4] L.A. Petrosjan. Dispersive surfaces in one family of pursuit games. Doklady Akademii nauk Armjanskoj
SSR, 43(4):193–197, 1966 (in Russian). = Л.А. Петросян. Дисперсионные поверхности в одном семействе
игр преследования. Доклады Академии наук Армянской ССР, 43(4):193–197, 1966.
[5] Yu.G. Dutkevich, L.A. Petrosjan. Game with a ”life line”. Case of l-capture. Vestn. Leningr. un-ta, 13:31–38,
1969 (in Russian). = Ю.Г. Дуткевич, Л.А. Петросян. Игра с «линией жизни». Случай l-захвата. Вестн.
Ленингр. ун-та, 13:31–38, 1969.
[6] L.A. Petrosjan. Differential games of pursuit. LSU, Leningrad, 1977 (in Russian). = Л.А. Петросян.
Дифференциальные игры преследования. Ленинград: ЛГУ, 1977.
[7] M. Bardi, I. Capuzzo-Dolcetta. Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman
Equations. Birkhäuser, Boston, 1997.
[8] M. Bardi, M. Falcone, P. Soravia. Numerical Methods for Pursuit-Evasion Games via Viscosity Solutions.
Annals of the International Society of Dynamic Games, Vol. 6: Stochastic and Differential Games, edited
by M. Bardi, T. Parthasarathy and T.E.S. Raghavan, Birkhäuser, Boston, 105–175, 1999.
[9] N.N. Krasovskii, A.I. Subbotin. Positional differential games. Nauka, Moscow, 1974 (in Russian). =
Н.Н. Красовский, А.И. Субботин. Позиционные дифференциальные игры. М.: Наука, 1974.
[10] N.N. Krasovskii, A.I. Subbotin. Game-Theoretical Control Problems. Springer-Verlag, New York, 1988.
[11] M.G. Crandall, L.C. Evans, P.-L Lions. Viscosity solutions of Hamilton-Jacobi equations. Transactions of
the American Mathematical Society, 277(1):1–42, 1983.
[12] M.G. Crandall, L.C. Evans, P.-L Lions. Some properties of viscosity solutions of Hamilton-Jacobi equations.
Transactions of the American Mathematical Society, 282(2):487–502, 1984.
[13] A.I. Subbotin. Generalized Solutions of First Order PDEs: the Dynamical Optimization Perspective.
Birkhäuser, Boston, 1995.
[14] A.I. Subbotin. Generalized solutions of first order PDEs. The dynamical optimization perspective. Moskva-
Izhevsk, Institut komp’juternyh issledovanij, 2003 (in Russian). = А.И. Субботин. Обобщенные решения
уравнений в частных производных первого порядка. Перспективы динамической оптимизации. М.-
Ижевск: Институт компьютерных исследований, 2003.
[15] V.S. Patsko, V.L. Turova. Level sets of the value function in differential games with the homicidal chauffeur
dynamics. International Game Theory Review, 3(1):67–112, 2001.
[16] V.S. Patsko, V.L. Turova. Numerical Solution of Two-Dimensional Differential Games. UrO RAN. Institute
of Mathematics and Mechanics, Ekaterinburg, 78 p., 1995.
[17] V.S. Patsko, V.L. Turova. Numerical solution of differential games on the plane. Preprint. IMM UrO RAN,
Ekaterinburg, 1995 (in Russian). = В.С. Пацко, В.Л. Турова. Численное решение дифференциальных
игр на плоскости. Препринт. Екатеринбург: ИММ УрО РАН, 1995.
[18] V.S. Patsko, V.L. Turova. Numerical solutions to the minimum-time problem for linear second-order conflict-
controlled systems, edited by D. Bainov. Proceedings of the Seventh International Colloquium on Differential
Equations, Plovdiv, Bulgaria, August 18–23, 1996, 329–338, 1997.
98
Existence of value function in time-optimal game with life line
Nataly V. Munts, Sergey S. Kumkov
Krasovskii Institute of Mathematics and Mechanics (Yekaterinburg, Russia)
Ural Federal University (Yekaterinburg, Russia)
Keywords: time-optimal differential games, life line, value function, constructive motions, epsilon-
equilibrium.
This paper deals with time-optimal differential games with a life line. In such games, the first player tries to
lead a system to a prescribed closed target set as soon as possible while keeping the trajectory of the system in
some open set where the game takes place. The second one counteracts this. Once the system leaves the set, the
second player wins immediately. In the framework of this class of games, many practical pursuit-evasion problems
can be formalized and solved. The paper presents a result on the existence of the value function in games of this
class.
99