В статье рассматриваются дифференциальные игры быстродействия с линией жизни. В таких играх цель первого игрока как можно быстрее привести систему на замкнутое целевое множество так, чтобы траектория в каждый момент времени принадлежала некоторому открытому множеству, на котором и происходит игра. Второй игрок препятствует этому, причем, как только траектория системы покидает множество игры, второй игрок немедленно выигрывает. Многие практические задачи преследования-уклонения могут быть поставлены и решены в рамках этого класса игр. В данной статье представлено доказательство существования функции цены.
x_ = f (x; u; v); t > 0; x(0) = x0; u 2 P; v 2 Q:
(
u2P v2Q v2Q u2P Здесь символ h ; i означает скалярное произведение.
Игра происходит на открытом ограниченном множестве G. Компактное множество T является терминальным, T G. Обозначим F = Rn n G (рис. 1). Начальное положение системы x0 2 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( ) 2 T ; t x0; u( ); v( ) = min t : x t; x0; u( ); v( ) 2 F : Если траектория не приходит на множество T (F ), тогда величина t (t ) полагается равной +1. Определим результат игры как
T x0; u( ); v( ) = (+1; если t = +1 или t < t ;
t ; иначе: Такую игру можно называть игрой с линией жизни: граница @F множества F это линия жизни, т.е. область, где второй игрок безоговорочно выигрывает.
Некоторое неудобство для численного исследования игры (
J x0; u( ); v( ) = (1 1; exp
T x0; u( ); v( ) ; если T x0; u( ); v( ) < +1;
иначе:
(
Постановка игры без линии жизни (то есть когда множество G совпадает со всем фазовым
пространством Rn) аналитически исследовалась в книге Р. Айзекса [1, 2]. Методика, предложенная им, основана
на разделении пространства игры сингулярными поверхностями на области, в которых функция цены
регулярна и в классическом смысле удовлетворяет соответствующему уравнению Гамильтона – Якоби.
Однако практическое применение этой методики наталкивается на существенные трудности, связанные с
обнаружением и классификацией сингулярных поверхностей, особенно в случае размерности фазового
вектора 3 или более. Численные методы построения функции цены игр быстродействия были предложены
В.С. Пацко и В.Л. Туровой [17, 18, 15]. Эти методы имеют геометрический характер и ориентированы на
решение задач на плоскости (с двумерным фазовым вектором). Более универсальный сеточный алгоритм
построения функции цены игр быстродействия был предложен итальянскими математиками М. Барди и
М. Фальконе [7, 8]. Он вычисляет функцию цены как вязкостное решение [11, 12] соответствующего
уравнения Гамильтона – Якоби. Однако данный метод обладает одним существенным недостатком с точки зрения
его практического применения. А именно, корректность его работы обоснована в случае использования
бесконечных сеток, покрывающих все игровое пространство Rn, в то время как при компьютерной реализации
можно использовать лишь конечные сетки. Это приводит к необходимости задавать краевые условия для
функции цены на внешней границе сетки, где ее обычно полагают равной бесконечности (единице
после замены Кружкова). Таким образом, компьютерная реализация метода Барди – Фальконе фактически
решает задачу быстродействия (
Существование функции цены Существование функции цены следует из результатов книг [9, 10], а именно, из разделов ¾Игра на минимакс-максимин времени до встречи¿ на стр. 79–86 в первой из них и ¾Differential Games of PursuitEvasion¿ на стр. 106–112 второй.
В указанных разделах рассматривается задача быстродействия с динамикой (
Пусть заданы автономная стратегия первого игрока U : Rn ! P и начальная позиция x0 2 N . Выберем разбиение времени
= f0 = t0 < t1 < : : : g: Обозначим за X1(x0; U; ) множество пошаговых движений системы u(t)
U x(ti) ; ti 6 t < ti+1; i = 0; 1; 2; : : : ;
x_ (t) 2 f t; x(t); u(t); v : v 2 Q :
Элементами этого множества являются абсолютно-непрерывные функции x( ) : [0; 1) ! Rn,
удовлетворяющие начальному условию x(0) = x0 и дифференциальному включению (
Аналогично вводится множество конструктивных движений X2(x0; V ), порожденное позиционной стратегией V : Rn ! Q убегающего. Для любой стратегии V множество X2(x0; V ) будет непустым и секвенциально компактным в C [0; 1) ! Rn (в компактно-открытой топологии).
Гарантированные результаты, обеспечиваемые позиционными стратегиями U : R Rn ! P и V : R Rn ! Q первого и второго игрока, находятся из соотношений 1(x0; U ) = sup 2(x0; V ) = min 0 x( ) : x( ) 2 X1(x0; U ) ; 0 x( ) : x( ) 2 X2(x0; V ) : В книгах [9, 10] доказана следующая Теорема 1. Для любой начальной позиции x 2 Rn в дифференциальной игре преследования существует момент !0 2 [0; 1] такой, что min 1(x0; U ) = sup 2(x0; V ) = !0:
U V
Однако этот результат нельзя напрямую применить к играм (
Пусть B" замкнутый шар радиуса " с центром в начале координат. Обозначим T" = T , F" = F + B",
G" = Rn n (F" [ T"). Здесь знак ¾+¿ для операндов-множеств обозначает алгебраическую сумму (сумму
Минковского). Используя T" как целевое множество, а cl G" как множество фазовых ограничений, введем
функцию платы аналогично (
e" x( ) = min t : x(t) 2 T"; 8# 2 [0; t] x(#) 2 cl G" :
Гарантированные результаты игроков определяются сходным образом:
(
V e"1(x0) = inUf e"1(x0; U ); e10(x0) = "li!m0 e"1(x0); e"2(x0) = sup e"2(x0; V );
V e20(x0) = "li!m0 e"2(x0): Пусть x0
такая точка, что для некоторого " > 0 первый игрок может привести систему на
терминальиномеееммноeж"11е(сxт0в)о6T"e="12 (Tx0,)у.дЕесрлжиижваеятеоечвкамxн0ожтаексотввае,cчl тGо".дТлоягдлаюдболйя слтюрбаытехги"1и, U"2птеарквиохг,очитгор0ок<а "т1ра<ек"т2о6ри"и,
из пучка X1(x0; U ) или приходят на F до попадания на T , или навсегда остаются в G, не попадая на T ,
то e"1(x0) = +1 для любого ". Следовательно, значения функций из семейства e"1( ) " в любой точке x
порождают числовое семейство, либо монотонное по ", либо стационарное. Из этого следует, что
существует поточечный предел e"1( ) ! e10( ) при " ! 0. Поскольку для любого " функции e"1( ) и e"2( ) совпадают,
то при " ! 0 также существует и поточечный предел e20( ) функций e"2( ), который совпадает с e10( ). Этот
общий предел является "-седловой точкой Val игры (
Заключение Важным классом дифференциальных игр являются игры с линией жизни, где под линией жизни понимается такое множество, при попадании системы на которое второй игрок немедленно выигрывает. Будучи предложенными еще в 1950-60 годы Р. Айзексом, они были исследованы лишь в весьма несложных постановках: в случае простой динамики системы или простой формы линии жизни. Кроме того, этот класс игр интересен тем, что практическая реализация численного метода решения игр быстродействия, предложенного итальянскими учеными М. Барди и М. Фальконе, фактически строит решение некоторой игры с линией жизни. В данной статье, с использованием идеологии конструктивных движений Н.Н. Красовского, доказано существование функции цены игры с линией жизни в весьма общей постановке.
В дальнейшем, авторы планируют обосновать существование обобщенного решения (минимаксного или вязкостного) для краевой задачи уравнения типа Гамильтона – Якоби, соответствующей игре с линией жизни. Также планируется доказать совпадение цены игры и обобщенного решения. Список литературы
Данное исследование финансово поддержано Российским фондом фундаментальных исследований, проект № 15-01-07909. 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, epsilonequilibrium.
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.