ПРИЛОЖЕНИЕ. Обзор некоторых результатов по теории дифференциальных игр

М. И. Зеликин, Э. Н. Симакова

Теория дифференциальных игр — это новое математическое направление, возникшее всего лишь несколько лет назад. Она тесно связана с теорией оптимального синтеза, адаптивными процессами и управлением случайными процессами; некоторые ее аспекты переплетаются с такими классическими направлениями, как многошаговые (дискретные) игры, дифференциальные уравнения, вариационное исчисление. Теория дифференциальных игр, интенсивно развивающаяся в настоящее время, весьма далека от завершения. В этом обзоре мы попытаемся осветить современное состояние и наиболее существенные продвижения в теории дифференциальных игр, не затронутые в книге Айзекса.

Первые работы, посвященные дифференциальным играм, появились 10—15 лет назад. Толчком к изучению дифференциальных игр послужили задачи из различных практических областей. Одним из первых интересные результаты в этой области получил Р. Айзеке. Вопросы существования решения дифференциальной игры и вопросы сходимости решения многошаговой игры к решению дифференциальной исследовал в 1957-1964 гг. В. Флеминг [1-З]1). Л. Берковиц [4, 5], используя подходы вариационного исчисления, получил в 1964 г. необходимые условия оптимальности и некоторые достаточные условия, сформулированные в терминах поля. Достаточные условия в более общих предположениях, а именно когда решение уравнения Беллмана может иметь ветвление, получены Л. С. Понтрягиным [6, 7] в 1964 г. Практический метод решения некоторых дифференциальных игр был предложен в 1965 г. Н. Н. Красовским и др. [8, 9]. Исследованию различных аспектов теории и решению конкретных задач посвящены появившиеся в последнее время работы [10—24, 27—35].

Мы будем использовать принятые в советской литературе обозначения, которые несколько отличаются от обозначений, применяемых Айзексом.

Игра задается системой дифференциальных уравнений

где компактные множества в евклидовых пространствах соответственно. Игра считается оконченной, когда точка z достигает заданного многообразия Кроме того, задается функционал (плата)

где момент первого достижения точкой z терминального многообразия

Стратегиями называются вектор-функции принимающие значения в соответственно; некоторые пространства допустимых функций.

Эта игра будет в дальнейшем обозначаться

1. Вопросы сходимости и существования. Вопрос о существовании цены игры и оптимальных стратегий игроков в общей задаче дифференциальных игр очень сложен. Оптимальные стратегии по определению являются функциями, которые сопоставляют состоянию игры z определенные значения управлений; таким образом, задача об отыскании оптимальных стратегий есть общая задача синтеза, осложненная наличием игровой ситуации.

Известно, что всякая многошаговая игра с полной информацией имеет седловую точку в чистых стратегиях (см., например, [25, теорема 6.1]). Поэтому естественный подход к проблеме существования в дифференциальных играх — исследовать их как предельный случай многошаговых игр, когда число шагов неограниченно возрастает. Такой подход в настоящее время разработан Флемингом получившим в этом направлении интересные результаты.

Флеминг рассматривает дифференциальную игру оканчивающуюся в момент Предполагается, что функции непрерывны на и удовлетворяют условию Липшица по z, т. е.

где С — константа, не зависящая от Дискретный аналог игры — многошаговая игра, описываемая разностными уравнениями

где есть состояние игры, интервал времени между двумя последовательными ходами, управления

выбираются одновременно из выпуклых компактных множеств начальным состоянием игры является а конечным Обозначим где целое). Тогда плата, соответствующая некоторой фиксированной партии, равна

где непрерывная функция, удовлетворяющая условию Липшица; определяет значение платы, соответствующее конечному состоянию Условия (3) гарантируют ограниченность последовательности Обозначим сформулированную многошаговую игру через

Индукцией по легко показать, что цена игры которую мы будем обозначать через удовлетворяет функциональному уравнению (см., например, [39])

Здесь цена одношаговой игры, определенной на множестве с платой, задаваемой выражением, стоящим в квадратных скобках.

Назовем минорантой игру, совпадающую с игрой но с той лишь разницей, что на шаге игрок при выборе своего управления уже знает управление противника Мажорантной назовем игру, когда при выборе игрок знает управление Соответствующие значения цены обозначим через и Тогда для имеют место уравнения

Легко видеть, что

Определенные таким образом минорантная и мажорантная игры представляют собой многошаговые игры с полной информацией, для которых доказано существование решения в чистых стратегиях (см., например, [25]).

В работах [1, 2] устанавливается, что если в многошаговой игре функции удовлетворяют условию Липшица (3) и линейны относительно выпукла по и, вогнута по и представима в виде

то справедливы соотношения

В статье [10] получен более слабый результат для общего случая игр на выживание, а именно, там показано, что предел функции удовлетворяющей уравнению Беллмана (6) для многошаговой игры, подчиняется неравенствам

где значения цены для соответствующим образом определенных минорантной и мажорантной игр.

В работе [3], посвященной проблеме сходимости, с помощью интересного построения доказано более сильное утверждение:

Если в многошаговой игре функции непрерывны и удовлетворяют условию Липшица (3), то существует при этом имеет место равномерная сходимость на каждом ограниченном множестве пространства состояний

Остановимся коротко на основных этапах доказательства этого утверждения. Наряду с детерминированной игрой рассмотрим вспомогательную многошаговую стохастическую игру, описываемую стохастическими разностными уравнениями

где взаимно независимые случайные величины, принимающие значения 1 и —1; математическое ожидание и дисперсия равны соответственно а — положительный малый параметр; платой является математическое ожидание (5). Цена этой игры V% для каждого удовлетворяет функциональному уравнению (см., например, [39])

Эта стохастическая игра имеет решение в смешанных стратегиях которые каждому состоянию сопоставляют вероятностные меры, сосредоточенные соответственно на

Рассмотрим теперь нелинейное параболическое уравнение

где - оператор Лапласа. Существование классического решения этого уравнения установлено в [35, 36].

Тогда (см., например, [3]) для каждого найдутся такие константы и такое что

для каждого состояния и

Использование некоторых вероятностных соображений позволяет оценить разность между ценой детерминированной многошаговой игры и ценой стохастической многошаговой игры и установить, что

где К — положительная константа.

Теперь из (11) и (12) легко следует доказываемое утверждение. В самом деле,

и так как произвольны, то существует.

Формальный переход к пределу при в функциональном уравнении (6) дает следующее уравнение в частных производных первого порядка:

Это уравнение было, по-видимому, впервые получено Айзексом. Заметим, что вывод этого уравнения предполагает дифференцируемость функции

Уравнение (13) для дифференциальных игр является аналогом уравнения Гамильтона — Якоби для задач вариационного исчисления. В классических работах по вариационному исчислению существование решения уравнения Гамильтона — Якоби показано в предположении существования гладкого поля экстремалей.

В ряде работ по уравнениям в частных производных [29—33] при значительно менее жестких условиях доказано существование решения уравнения Гамильтона — Якоби, правда в некотором обобщенном смысле. Остановимся несколько подробнее на аналогичных результатах, полученных в [29] для уравнений типа (13).

Рассматривается задача Коши для уравнения в частных производных первого порядка:

где функция равномерно по удовлетворяет условию Гельдера с показателем

ограничена и удовлетворяет условию Липшица. Под обобщенным решением уравнения (14) будем понимать функцию удовлетворяющую условию Липшица, для которой (14) выполняется для почти всех

Основной результат работы [29] — это установление существования обобщенного решения уравнения (14). Методы доказательства этого результата аналогичны методам работы [3] и основаны на несколько более общих конструкциях, представляющих самостоятельный интерес.

Рассмотрим вспомогательную стохастическую игру с полной информацией, описываемую системой стохастических дифференциальных уравнений в векторной форме:

где есть -мерный винеровский процесс; положительно определенная матрица. В

качестве платы возьмем условное математическое ожидание (при условии, что

функционала (2).

Главная причина рассмотрения такого рода конструкций заключается в том, что функция

при некоторых ограничениях гладкости на удовлетворяет параболическому дифференциальному уравнению (см. [34])

где

Детерминированный аналог уравнения имеет место лишь при очень сильном дополнительном предположении о гладкости функции при любых управлениях В работе [29] рассматривается уравнение Беллмана для игры (15), (16) вида

где

здесь коэффициент обрыва диффузионного процесса (15). Как уже упоминалось, существование классического решения квазилинейного параболического уравнения (18) при невырожденной матрице доказано в [35] и при более ослабленных предположениях — в [36]. Однако наибольший интерес для дифференциальных игр представляет случай вырожденных операторов в частности, если то мы имеем дело с обычной дифференциальной игрой.

Доказательство существования обобщенного решения (в смысле Соболева) уравнения (18) для вырожденного оператора проводится по следующей схеме.

Рассматривается невырожденное параболическое уравнение, зависящее от малого параметра

где оператор Лапласа. Далее, пусть цена стохастической многошаговой игры, описываемой разностным аналогом системы (18), с матрицей диффузии где единичная матрица, цена соответствующей игры при Показывается, что при равномерно по и В то же время при Таким образом, является обобщенным решением задачи Коши для уравнения (18). Применительно к детерминированному случаю по той же схеме доказано, что функция -= является обобщенным решением уравнения (13).

Рассмотренные выше стохастические дифференциальные игры, которые использовались в качестве вспомогательных конструкций в проблемах сходимости и существования, тесно связаны с теорией управляемых диффузионных процессов (см. [40, 41]) и представляют самостоятельный интерес.

В работе [12] рассматривалась стохастическая дифференциальная игра типа (15), (16), где в качестве терминального многообразия взята граница некоторой области в расширенном пространстве состояний Предполагается, что управления игроков входят линейно в правые части уравнений (15) и при фиксированном множества значений управлений обоих игроков представляют собой невырожденные эллипсоиды в пространствах зависящие, вообще говоря, от

На основании результатов, связанных с существованием решений квазилинейных параболических уравнений, в работе [12] показано, что цена игры удовлетворяет уравнению (13) и достигается на чистых стратегиях.

Кроме рассмотренных выше работ, вопросы существования решения дифференциальных игр затронуты в [13, 14]. В частности, в [13] дифференциальная игра рассматривается в рамках общей теории непрерывных игр, формулируемых следующим образом. Стратегии игроков являются элементами некоторых абстрактных множеств Пусть задано отображение множества в некоторое топологическое пространство Тогда можно определить игру в нормальной форме

где действительная функция, определенная на Очевидно, что такая постановка формально охватывает дифференциальные игры. Для такого рода игр при некоторых ограничениях топологического характера на сформулирован ряд теорем существования. Однако проверка этих условий в конкретных ситуациях наталкивается на существенные трудности, а в дифференциальных играх эти условия, как правило, не выполняются. Для заданных таким образом непрерывных игр в работе [13] рассматриваются также их многошаговые аналоги и обсуждаются вопросы аппроксимации непрерывных игр многошаговыми.

2. Необходимые условия оптимальности. Предположим, что сформулированная выше дифференциальная игра имеет седловую точку Рассмотрим вектор-функцию удовлетворяющую сопряженной системе дифференциальных уравнений

и положим

Имеет место следующее необходимое условие оптимальности в форме, аналогичной принципу максимума Понтрягина (см. [37]).

Пусть оптимальные стратегии игроков соответствующая им оптимальная траектория, исходящая из начального положения в момент и оканчивающаяся на терминальном множестве в момент Тогда существует такая ненулевая непрерывная вектор-функция которая вместе с удовлетворяет уравнениям (18), (19), прием для всех

Это условие было получено в работе [15] для случая гладкого синтеза. Аналогичные необходимые условия получены Л. Берковицем [5] для случая, когда любой допустимый синтез приводит к так называемому регулярному разложению области

Предположим, что синтез разбивает область X на непересекающиеся подобласти, разделенные кусочно-гладкими многообразиями и заполняющими всю область на этих многообразиях стратегии могут иметь особенности определенного характера, а внутри каждой подобласти они являются гладкими функциями. Кроме того, предполагается, что если точка находится на этих многообразиях, то скорость, соответствующая паре функций не касается многообразия в этой точке (последнее предположение особенно сильное и редко выполняется в реальных ситуациях). Такое разбиение Берковиц называет регулярным разложением области X, порожденным парой стратегий В работе [5] рассматривается случай синтеза, порождающего регулярное разложение области ограничения на управления игроков предполагаются гладкими. Необходимые условия оптимальности в этом случае можно записать в форме, аналогичной принципу максимума.

3. Достаточные условия оптимальности. Если найдена гладкая функция удовлетворяющая уравнению (13), то эта функция является ценой игры, а функции обеспечивающие соответственно минимум и максимум определяют оптимальные стратегии

Берковицем в работе [5] сформулированы достаточные условия в терминах поля: если стратегии допускающие регулярное разбиение области X и удовлетворяющие необходимым условиям оптимальности, таковы, что соответствующие им функции образуют кусочно-гладкое поле, то эти стратегии оптимальны, если допустимыми стратегиями считать только те пары функций которые в совокупности образуют регулярный синтез. Отметим, что для получения результатов, содержащихся в [5], использованы подходы вариационного исчисления.

Дальнейшее продвижение в проблеме достаточных условий было сделано Л. С. Понтрягиным в [6, 7]. Для формулировки основного результата нам потребуется ввести некоторые обозначения и понятия.

Рассмотрим дифференциальную игру преследования, описываемую уравнением

где

Окончанием игры считается достижение точкой z многообразия М. Введем функцию

где гладкие многообразия. Рассмотрим систему дифференциальных уравнений

где время со знаком минус, отсчитываемое от момента окончания, т. е. от терминального многообразия Найдем функции доставляющие соответственно максимум и минимум Пусть решение системы (21), соответствующее этим функциям, имеет вид

Обозначим где вектор, ортогональный к в точке Тогда соотношение (22) задает отображение многообразия 5 в фазовое пространство

Рассмотрим случай, когда обратное отображение пространства на неоднозначно, а именно, прообразами точки z служат точки где Мы будем говорить, что точка являющаяся прообразом точки z, принадлежит верхнему слою, если

Для удобства формулировки обозначим теперь Пусть произвольная функция переменных Заменив в ней переменные их выражениями через из (22), мы получим функцию заменив все аргументы выражениями из (22), получим функцию

Рассмотрим следующие условия:

1. Векторы линейно независимы в каждой точке многообразия

2. Если в некоторой точке многообразия функция обращается в нуль, то градиент ее в этой точке отличен от нуля.

3. Функция переменного достигает своего максимума в единственной точке многосбр Точно

так же функция переменного достигает своего минимума в единственной точке многообразия

4. Квадратичные формы, соответствующие максимуму функции и минимуму функции невырождены.

5. В каждой точке принадлежащей верхнему слою,

6. Уравнение

всегда разрешимо относительно и для всех При этом если то это решение можно выбрать так, что градиент по и функции будет в этой точке отличен от нуля.

7. Многообразия являются аналитическими; функции аналитические.

8. Для всякой точки а пространства и положительного числа найдутся настолько малое положительное число и настолько большое положительное число что, каковы бы ни были управления и начальное значение удовлетворяющее условию решение уравнения

с начальным значением удовлетворяет неравенству

9. Оба многообразия компактны.

Сформулированная ниже теорема доказана в двух вариантах: при выполнении условий 1, 2, 3, 4, 6, 8, 9 или условий 1, 2, 3, 4, 5, 7, 8, 9.

Теорема. Пусть Рассматриваемая игра на множестве А может быть закончена за время

Заметим, что существуют примеры, где нарушение условия 1 приводит к такому положению дел, когда выбор управления соответствующего некоторому другому (не верхнему) слою, приводит к захвату за время большее, чем

4. Методы решения дифференциальных игр, не затронутые в книге Айзекса. Сущнвсть метода, предложенного в работах [8, 9], состоит в том, что нахождение оптимальных управлений игроков сводится к задаче нахождения управлений,

позволяющих перевести игру в некоторую точку фазового пространства, определяемую областями достижимости и Если эти области — выпуклые замкнутые множества, то такой точкой будет точка касания этих множеств в «момент поглощения», т. е. в первый момент времени, когда Очевидно, что искомая точка зависит от положения игроков в начальный момент — от состояния z. Поэтому управления игроков, «нацеливающие» движение их в эту точку, также являются функциями от z, т. е. они осуществляют синтез. Ограничением к применению этого метода является требование существования и единственности «точки прицеливания». В работе [9] обсуждаются трудности применения метода и намечены пути их преодоления.

Наконец, следует упомянуть так называемый «геометрический» метод, используемый в основном при решении игр преследования. Исходя из различных геометрических построений, можно получить «области достижимости» игроков и находить решение. Особенно успешно этот метод применяется при рассмотрении так называемых «простых игр преследования» — игр, где скорости игроков постоянны, а управлениями являются направления этих скоростей. Задачи этого типа рассмотрены в [19, 20].

5. Некоторые конкретные задачи. Трудности, возникающие при решении конкретных дифференциальных игр, весьма существенны. Прежде всего остается открытым вопрос о существовании цены игры в общем случае игр на выживание. Рассмотренный Берковицем [38] пример показывает, что для довольно простой дифференциальной игры цена игры в чистых стратегиях не существует. Далее, во многих случаях оказывается, что цена игры существует не во всей области X, а лишь в некоторой ее подобласти; задача выделения этой подобласти представляет собой некоторую игру качества. Как уже отмечалось, решение дифференциальной игры есть задача синтеза; определение оптимальных стратегий связано с выявлением и нахождением большого числа сингулярных многообразий. Поэтому решение конкретных задач представляет наряду с практическим большой теоретический интерес, помогая выявить трудности проблемы и наметить пути их преодоления. Приведем некоторые результаты, связанные с решением конкретных задач.

Хорошими моделями дифференциальных игр, к тому же поддающимися геометрическим методам решения, являются так называемые простые игры преследования. В таких играх скорости игроков постоянны, а управлениями служат направления скоростей; платой, как правило, выбирается время захвата. Если имеет превосходство в скорости, а игра происходит во всем

пространстве то цена игры существует (см. [21]). В работе [20] рассмотрены некоторые варианты плоской простой игры двух точек, а также задача погони двух точек за третьей. Различные варианты плоской игры преследования в а также игры с «линией жизни» и «линией смерти» и некоторые групповые игры рассмотрены в [16—18]; при этом предполагается, что игроку в каждый момент известно не только состояние игры, но и управление своего противника

В работах [8, 9] рассматриваются игры преследования, описываемые линейными дифференциальными уравнениями с постоянными коэффициентами; платой является время захвата. На управления наложены ограничения интегрального типа. Игра преследования между однотипными объектами рассмотрена в [22]. Автор сводит задачу преследования к некоторой задаче об оптимальном быстродействии и находит аналитическое выражение оптимальных управлений игроков через оптимальные управления, полученные для последней задачи.

В работе [23] наряду с некоторыми другими оптимальными задачами рассматривается игра преследования спутников, движущихся по круговой орбите радиуса вокруг Земли в поле силы тяжести. Управлениями игроков являются направления постоянного по величине ускорения, развиваемого двигателями; в качестве платы выбрано время захвата. Показано, что при оптимальном движении спутников направления их ускорений должны совпадать.

В [44] рассмотрена плоская игра преследования между объектами, скорости и радиусы кривизны которых ограничены, в качестве платы выбирается время захвата, и захватом считается сближение игроков на заданное расстояние. Постановка этой задачи приведена Айзексом, а в работе [44] найдены оптимальные стратегии и определена цена игры в области, где начальное расстояние между объектами больше радиуса кривизны их траекторий.

Постановка задачи в линейной игре преследования с фиксированным временем содержится в [24]; платой выбирается функционал, определяющий энергетические затраты игроков; необходимые условия получены формальным применением вариационного исчисления.

ЛИТЕРАТУРА

(см. скан)

(см. скан)

(см. скан)