Антагонистические дифференциальные игры
Антагонисти́ческие дифференциа́льные и́гры, дифференциальные игры с двумя игроками противоположных интересов. Например, первый игрок минимизирует некоторый скалярный показатель, а второй старается его максимизировать.
Возникновение теории и начальные понятия
Обычно считают, что динамика системы описывается соотношениемЗдесь – время, – фазовый вектор, – производная по , – векторное управляющее воздействие первого игрока, – второго игрока. Относительно функции предполагают её непрерывность и выполнение глобального условия Липшица по . Последнее означает существование положительной константы такой, что при любых Принципиальным является вопрос о характере ограничений, накладываемых на управления игроков. Выделим два класса ограничений: геометрические и интегральные.
При геометрическом ограничении реализуемое во времени управление первого игрока (аналогично управление второго) стеснено включением где множество в конечномерном пространстве является ограниченным и замкнутым. Примером интегральных ограничений являются ограничения видагде – некоторая скалярная неотрицательная функция. Подсчитываемый при помощи этой функции расход управлений и на промежутке не должен превышать значений и , оговорённых в начальный момент
Далее будем считать, что управления игроков подчинены геометрическим ограничениям.
К основным задачам теории дифференциальных игр можно отнести задачи сближения – уклонения на конечном промежутке времени и задачи преследования – убегания.
Первые результаты по дифференциальным играм были получены американским математиком Р. Айзексом в начале 1950-х гг. в его отчётах для RAND Corporation (Isaacs. 1951). Он же первым начал использовать термин «дифференциальная игра». В основу своего метода Айзекс положил уравнение в частных производных (УЧП) первого порядка. Разработанный им подход ориентирован на разбиение пространства игры на области, в каждой из которых решение некоторой граничной задачи для такого уравнения было бы гладким. Последовательное (в обратном времени) обнаружение и описание клеток с гладким решением составляет основу (и главную трудность) метода Айзекса. Первые теоремы существования функции цены в дифференциальных играх были доказаны У. Х. Флемингом (США). Наилучшие гарантии игроков рассматривались им как пределы мажорантных и минорантных многошаговых игр (Fleming. 1961).
Независимо от этих работ, в Советском Союзе теория дифференциальных игр, выросшая из теории оптимального управления, была предметом внимания и исследований Л. С. Понтрягина, Н. Н. Красовского и их сотрудников. Интенсивно работали коллективы, возглавляемые Ф. Л. Черноусько, Б. Н. Пшеничным и Л. А. Петросяном.
Нестрогое определение наилучших гарантированных результатов
При рассмотрении дифференциальных игр прежде всего вводится функционал платы который (для определённости) минимизирует первый игрок и максимизирует второй. Такой показатель определяется на движениях системы порождаемых допустимыми программными управлениями и в качестве которых используются измеримые функции, удовлетворяющие заданным ограничениям. Измеримость нужна для получения замкнутых пучков движений. При приближённых вычислениях можно вместо измеримых функций рассматривать кусочно-непрерывные по функции.
Типичным и наиболее простым является функционал задаваемый при помощи терминальной функции платы подсчитываемой в заранее заданный момент окончания При начальной позиции где – начальный момент, а – начальное состояние, программные управления порождают движение системы и, соответственно, положение в момент окончания, что позволяет подсчитать значение Первый игрок старается минимизировать значение платы, а второй – максимизировать.
Можно было бы поставить игровую задачу в программных управлениях и исследовать наилучший, с точки зрения первого игрока, гарантированный результата с точки зрения второго игрока – наилучший гарантированный результатЕсть задачи, в которых это имеет смысл. Но это далеко не главные задачи, ради которых возникла теория дифференциальных игр.
Основными являются задачи, где при постановке за первого игрока его управление строится по принципу обратной связи при помощи управлений вида со значениями в множестве Используя какое-либо управление обратной связи, первый игрок может столкнуться с любой реализацией программного управления второго игрока со значениями в множестве . Таким образом, мы могли бы задать наилучший гарантированный результат первого игрока в видеа при постановке за второго игрока – в видеОднако, опираясь на теорию дифференциальных уравнений, очень трудно аккуратно определить, что такое движение порождённое из начальной позиции разрывным по управлением обратной связи и программным управлением В то же время (и это было известно давно) наилучшим (минимизирующим) управлением часто является разрывная функция Аналогичная ситуация относительно наилучшего управления второго игрока. Более того, имеются примеры, показывающие, что оптимальное разрывное по управление обратной связи нельзя (без существенной потери в результате) приблизить непрерывным по управлением (Барабанова. 1970).
В связи с этим возникает вопрос о строгой постановке задачи за первого игрока (соответственно, и второго) в классе управлений обратной связи.
Постановка задачи о наилучших гарантиях
Вполне разумный и понятный для инженеров вариант постановки связан с введением дискретных схем управления.
Рассмотрим постановку за первого игрока. Пусть зафиксирована начальная позиция и выбрано управление обратной связи (стратегия) Будем считать, что первый игрок реализует своё управление по времени с шагом Это означает, что в начальной позиции он берёт управление и держит его постоянным на промежутке При этом второй игрок реализует какое-то своё допустимое программное управление Тогда в момент получим состояние Здесь нет проблем с применением теории дифференциальных уравнений для описания возникающего движения и доведения его до момента На промежутке будет действовать постоянное управление где а – состояние системы, полученное в конце первого промежутка. Повторяя такой процесс, доведём движение до момента и получим результат Введём величинуТрактуем её как наилучшую гарантию первого игрока для начальной позиции при выбранной стратегии и произвольном шаге дискретной схемы Далее полагаеми, наконец,Получаем наилучшую гарантию первого игрока. Если при рассмотрении минимум достигается, то имеем оптимальную стратегию первого игрока для начальной позиции Подчеркнём, что при смене начальной позиции оптимальная стратегия, ей соответствующая, может измениться.
Аналогично с понятной заменой операций и на и вводим величину наилучшего гарантированного результата второго игрока для позиции .
Рассматривая зависимости и можем говорить о функциях наилучшего гарантированного результата первого и второго игроков. В теории дифференциальных игр выделены широкие классы задач, когда для любой начальной позиции В этом случае функция называется функцией цены игры в чистых позиционных стратегиях и .
Как правило, существование функции цены в чистых позиционных стратегиях и доказывается в предположениикоторое должно быть выполнено для любого вектора при всех Условие называют условием Айзекса. Другое название – условие седловой точки в маленькой игре (Красовский. 1974). Долгое время без ответа был вопрос о теоретическом и численном анализе задач, для которых условие не выполнено. Но в дальнейшем был найден подход к исследованию и таких задач (Красовский. 1974; Субботин. 1981).
Стабильный мост. Экстремальный сдвиг
Формулы – относятся к проблеме постановки дифференциальных игр в позиционных стратегиях. Отдельным является вопрос о том, как можно строить оптимальные (или близкие к ним по результату) стратегии.
В теории дифференциальных игр на начальном этапе её развития (да и ныне) использовались постановки, в которых при рассмотрении задачи за первого игрока предполагалась дискриминация второго (в постановке за второго, наоборот, дискриминация первого). Дискриминация означает, что в каждый текущий момент времени второй игрок показывает своё управление вперёд на некоторый интервал Зная такое управление, первый игрок выбирает своё управление на этот промежуток. С точки зрения инженерной практики подобные предположения казались неприемлемыми, но были оправданы с математической точки зрения. Используя свойство дискриминации, Понтрягин для задач с линейной динамикой описал способы управления первого игрока, которые можно использовать для эффективного решения линейных по динамике задач (Понтрягин. О линейных дифференциальных играх. 1. 1967; О линейных дифференциальных играх. 2. 1967). При этом Понтрягин в качестве самостоятельной стал рассматривать задачу о приведении конфликтно-управляемой системы на целевое множество
Пусть, например, первый игрок заинтересован в приведении фазового вектора системы в заданный момент на целевое множество а второй препятствует этому. Требуется описать множество начальных позиций из которых такое возможно при дискриминации второго игрока. Понтрягин для линейных задач обосновал конструкции, позволяющие находить указанное множество. Красовский также сформулировал условие (случай однотипных объектов), при котором такое множество может быть построено (Красовский. 1970). Несколько позже Красовский, анализируя общие нелинейные постановки, пришёл к идее рассматривать задачи с дискриминацией противника как вспомогательные, на основе решения которых могут быть построены позиционные стратегии.
В рамках задачи наведения на множество в фиксированный момент введём понятие стабильного моста. Чтобы избежать сложных обозначений, будем считать замкнутым пучок движений системы порождаемый допустимыми программными управлениями первого игрока при любом заданном программном управлении второго игрока. Стабильным мостом назовём замкнутое множество в пространстве где для которого сечение совпадает с и для любой позиции а также для любого удовлетворяющего неравенству справедливо следующее свойство: по любому постоянному управлению второго игрока, заданному на промежутке найдётся программное управление первого игрока такое, что движение в момент будет находиться в сечении множества Содержательно это означает, что при управлении с дискриминацией первый игрок осуществляет перевод на множество в момент Максимальным стабильным мостом назовём максимальное (по включению) множество, обладающее свойством стабильности.
В монографии «Позиционные дифференциальные игры» (Красовский. 1974) указан способ построения чистой позиционной стратегии обеспечивающей удержание движения в сколь угодно малой окрестности стабильного множества, если начальная позиция принадлежит этому множеству. Эту стратегию стали называть экстремальной. Её содержательный смысл состоит в следующем. Если то управление выбирается произвольным из множества Если то в сечении определяется точка ближайшая к точке и управление выбирается экстремальным по вектору а именно доставляющим внешний максимум выражения Такое определение введено для случая правой части динамики, удовлетворяющей условию Но соответствующие модификации сделаны и для общего случая При применении описанной стратегии экстремального сдвига в дискретной схеме управления с шагом за счёт выбора достаточно малого шага движение системы приводится в сколь угодно малую окрестность множества в момент
Правило экстремального сдвига, возникшее в теории дифференциальных игр, оказалось полезным и применимым ко многим задачам теории управления, а также к другим задачам математики (Osipov. 1995; Kurzhanski. 2014).
Теорема об альтернативе
С понятиями максимального стабильного моста и экстремальной стратегии к нему тесно связана теорема об альтернативе, которая является центральной в монографии «Позиционные дифференциальные игры» (Красовский. 1974). Содержательный смысл теоремы состоит в следующем.
Пусть выполнено условие Тогда для любой начальной позиции имеет место одно из двух утверждений: а) существует чистая позиционная стратегия первого игрока, которая обеспечивает перевод на множество в момент (в том смысле, что был описан выше, т. е. попадание в любую сколь угодно малую окрестность множества за счёт выбора шага ); б) существуют чистая позиционная стратегия второго игрока и число такие, что второй игрок гарантирует уклонение движения от попадания в открытую окрестность множества в момент (в рамках дискретной схемы управления второго игрока это означает перевод движения в момент в любую сколь угодно малую окрестность дополнения окрестности множества до всего пространства ).
Теорема об альтернативе является глубоким математическим результатом и служит основой, на базе которой доказываются утверждения, связанные, например, с дифференциальной игрой минимизации-максимизации непрерывной функции платы в фиксированный момент окончания . Поясним это. Рассмотрим множество уровня функции платы. Выделим максимальный стабильный мост обрывающийся на множестве в момент . Если то существует позиционная стратегия первого игрока, приводящая систему на множество в момент [вариант а) альтернативы]. Стало быть, для такой начальной позиции в игре с фиксированным моментом окончания и функцией платы первый игрок гарантирует себе результат меньший или равный Пусть Тогда вариант а) альтернативы не выполнен и, стало быть, реализуется вариант б): существуют стратегия и число такие, что второй игрок гарантирует уклонение от открытой окрестности множества в момент Отсюда следует, что множество является максимальным множеством, где значение функции цены антагонистической дифференциальной игры не превышает числа Для точек на границе множества имеем
Принципиальное продвижение теории экстремального сдвига получено (Krasovskii. 1995) для антагонистических дифференциальных игр с «позиционным функционалом». Так были названы задачи, в которых оптимальные стратегии игроков можно строить в виде позиционных, т. е. только на основе состояния системы в текущий момент времени. В частности, широко используются линейные по динамике задачи с фиксированным моментом окончания, в которых показатель (функционал платы) зависит от квадрата отклонения системы от оговорённого положения в момент окончания, а также от квадратов расстояний от заданных точек в некоторые заданные промежуточные моменты времени. Обзор задач с позиционным функционалом сделан в статье Н. Ю. Лукоянова и М. И. Гомоюнова (Lukoyanov. 2019).
Программные итерации
В середине 1970-х гг. А. Г. Ченцов предложил метод программных итераций для определённых классов дифференциальных игр. Применительно к нахождению максимального стабильного моста на промежутке в игре с фиксированным моментом окончания и целевым множеством итерационная процедура спуска к (при некоторых предположениях) выглядит следующим образом (Субботин. 1981). Итерации начинаются с множества где – фазовое пространство динамической системы. Затем определяется максимальное замкнутое подмножество для любой точки которого по любому постоянному управлению второго игрока на промежутке первый игрок может так выбрать своё программное управление что движение генерируемое управлениями и приходит на множество в момент Имеем На второй итерации находим максимальное замкнутое множество такое, что для любой позиции по любому заданному найдётся что соответствующее движение системы сохраняется в фазовом ограничении вплоть до момента Затем переходим к нахождению с соблюдением фазового ограничения и т. д. Доказано, что последовательность множеств определённая на сходится при к множеству в метрике Хаусдорфа.
Численное построение максимальных стабильных мостов
Ключевая роль стабильных мостов в исследовании дифференциальных игр и сложность их аналитического описания определяют важность развития численных методов построения стабильных мостов.
В этом направлении много сделано для линейных и нелинейных задач с фиксированным моментом окончания. Разработаны попятные процедуры построения таких множеств. Эти процедуры можно трактовать как специфические процедуры динамического программирования применительно к дифференциальным играм (Алгоритмы и программы ... 1984; Тарасьев. 1992).
Кратко поясним смысл попятной процедуры. Вводим разбиение с шагом оси слева от момента Находим для момента максимальную совокупность состояний для каждой точки которой по любому постоянному управлению второго игрока найдётся управление первого игрока, переводящее систему из точки на множество в момент Аналогично, заменяя множество на множество строим множество и т. д. Для некоторых классов дифференциальных игр теоретически обоснована сходимость попятной процедуры при к множеству при любом из заданного промежутка В случае линейных по динамике задач с выпуклым целевым множеством получаемые на каждом шаге множества в пространстве являются выпуклыми и их нахождение эффективно реализуется при помощи операции алгебраической суммы множеств и операции пересечения.
Прямые методы Л. С. Понтрягина
В 1967 г. Понтрягин в статьях «О линейных дифференциальных играх. 1» и «О линейных дифференциальных играх. 2» ввёл в теорию линейных дифференциальных игр операцию геометрической разности двух множеств (разность Минковского) (Понтрягин. О линейных дифференциальных играх. 1. 1967; О линейных дифференциальных играх. 2. 1967). Разность Минковского может быть определена двумя эквивалентными способами:В статье «О линейных дифференциальных играх. 1» эта операция использована для описания преимущества первого игрока над вторым в подынтегральном выражении формулы Коши, где учитываются действия первого и второго игроков (Понтрягин. О линейных дифференциальных играх. 1. 1967). Возникший метод стали называть «первым прямым методом Понтрягина» решения линейных дифференциальных игр. Подробное изложение метода содержится в работе М. С. Никольского «О применении первого прямого метода Понтрягина в играх преследования».
При помощи операций алгебраической суммы и геометрической разности в работе Понтрягина «О линейных дифференциальных играх. 2» определена попятная процедура (и её предел – «альтернированный интеграл») построения максимального стабильного моста в задаче приведения на множество в момент («второй прямой метод Понтрягина») (Понтрягин. О линейных дифференциальных играх. 2. 1967). Подчеркнём, что при этом рассмотрен важный для практики случай, когда выпуклое множество определяется лишь частью координат вектора Такой случай позволяет исходную линейную динамику видазаменить динамикойс целевым множеством которое лежит в подпространстве размерности выделенных координат вектора Здесь – соответствующая подматрица фундаментальной матрицы Коши определяемой матрицей исходной системы. Вектор имеет смысл вектора прогноза на момент выделенных координат полного вектора состояния исходной системы в момент при свободном движении системы (т. е. при , ) на промежутке Максимальные стабильные мосты при этом строятся в рамках системы При численных построениях терминальное выпуклое множество а также выпуклые множества и подменяются многогранниками. Операция вычисления геометрической разности двух множеств эквивалентна операции построения выпуклой оболочки разности двух опорных функций. Для случая разработанные процедуры просты и наглядны (Алгоритмы и программы ... 1984). Они применимы в задачах, где и эти задачи важны для практики.
Однотипные объекты
В работах Красовского, выполненных в 1960-х гг., было введено понятие «однотипных объектов». Так были названы задачи, где динамика двух управляемых объектов описывается соотношениямиВводя разностные координаты приходим к системеЗдесь динамическое преимущество первого игрока над вторым задано в виде
Системе сопоставляется управляемая системаи максимальный стабильный мост для может быть построен как множество разрешимости для задачи управления системой при наведении её на множество в момент К этому множеству может быть добавлена экстремальная стратегия первого игрока, работающая в рамках системы Таким способом эффективно решаются для однотипных объектов игровые задачи с фиксированным моментом окончания и выпуклой функцией платы.
Говоря об утверждениях, приведённых в монографии Н. Н. Красовского «Игровые задачи о встрече движений», отметим результаты, связанные с рассмотрением множеств достижимости и первого и второго игроков (Красовский. 1970).
Множеством достижимости управляемого объекта в заданный момент времени (при оговорённом начальном моменте и начальном фазовом состоянии) называют совокупность всех его фазовых состояний, которые можно получить в этот момент при переборе всех допустимых программных управлений. Аналогично можно рассматривать множество достижимости в подпространстве некоторых координат фазового вектора, например, в подпространстве координат геометрического положения.
Для дифференциальных игр с фиксированным моментом окончания и выпуклой функцией платы в монографии «Игровые задачи о встрече движений» выделены задачи, для которых сформулировано условие регулярности (автоматически выполненное в случае однотипных объектов) (Красовский. 1970). Рассматривая взаимное расположение двух множеств достижимости в соответствующих подпространствах, можно говорить о «выпирании» множества достижимости второго игрока из множества достижимости первого игрока. При выполнении условия регулярности величина «выпирания» определяет цену игры в виде значения функции . Но даже если условие регулярности не выполнено, то рассмотрение такого «гипотетического» промаха позволяет весьма эффективно исследовать многие инженерные задачи, ибо сам метод Красовского, основанный на рассмотрении множеств достижимости, применим и без предположения о выполнении условия регулярности. Более того, он применим и к ситуациям, когда имеется, например, один убегающий и несколько преследователей (Чикрий. 1992). Важные прикладные задачи, которые удалось решить на основе метода Н. Н. Красовского, описаны в книге О. А. Толпегина (Толпегин. 2021).
Унификация дифференциальных игр
Рассматривая дифференциальную игру с геометрическими ограничениями, мы прежде всего выписываем уравнения динамики и ограничения на управление. В середине 1970-х гг. актуальным был вопрос о том, какие варианты такого описания являются эквивалентными, т. е. приводят к одному и тому же результату при подсчёте функции цены. Другими словами: насколько важна конкретность выписывания уравнения динамики и геометрических ограничений? Красовский дал ответ в статье «К задаче унификации дифференциальных игр» (Красовский. 1976).
Составляем скалярное произведение где – единичная сфера с центром в нуле в а – правая часть системы Вычисляем гамильтонианВ силу предположения о седловой точке в маленькой игре операции и в последнем выражении можно переставлять. В качестве унифицированной модели возьмём динамикуЗдесь – минимизирующее управление, – максимизирующее управление. Константа выбирается достаточно большой так, чтобы для всех из некоторого ограниченного множества в в котором может проходить решение системы при заданной начальной позиции гамильтонианы исходной динамики и унифицированной совпадали. Это всегда можно сделать.
В статье Красовского показано, в частности, что цена игры в задаче с фиксированным моментом окончания и терминальной непрерывной функцией платы совпадает с ценой игры в задаче, где исходная динамика заменена унифицированной (Красовский. 1976). Поскольку формула задаёт гамильтониан, то две дифференциальные игры эквивалентны, если их гамильтонианы совпадают.
Уравнение Айзекса – Беллмана
Рассмотрим дифференциальную игру с динамикой фиксированным моментом окончания и непрерывной терминальной функцией платы Функция цены в такой игре является непрерывной (Красовский. 1974). Если бы дополнительно она была непрерывно дифференцируемой, то мы могли бы найти производную вдоль движения системы Здесь – реализующиеся в момент управления первого и второго игроков. Символ означает частную производную по скалярной переменной а – частную производную по векторной переменной Последнюю записываем как матрицу-строку с элементами в виде обычных частных производных по компонентам вектора Поскольку первый игрок стремится уменьшить значение цены вдоль движения, а второй – увеличить, то естественно рассмотреть выражениеравное (в силу условия седловой точки в маленькой игре) выражениюТак как в рассматриваемой задаче функция цены игры вдоль оптимальных движений является постоянной, то получаем соотношениепри краевом условии
Поэтому можем сказать, что функция цены (если она непрерывно дифференцируема) удовлетворяет УЧП первого порядка с заданным краевым условием:Такое уравнение стали называть уравнением Айзекса – Беллмана. Оно является частным случаем классического уравнения Гамильтона – ЯкобиОднако функция цены в дифференциальных играх, как правило, не является дифференцируемой во всём пространстве игры. Типичными являются задачи, в которых дифференцируемость есть в конечном (или бесконечном) числе областей, стыкующихся друг с другом по некоторым поверхностям. Кроме того, классическая теория уравнений Гамильтона – Якоби в своих достаточных условиях говорит о существовании гладкого решения лишь в малой окрестности терминальной поверхности.
Функцию в называют гамильтонианом. В случае гамильтониан имеет видЧтобы подчеркнуть наличие операции часто говорят о минимаксном гамильтониане.
Производные по направлению. Необходимые и достаточные условия для функции цены игры
К началу 1980-х гг. в Советском Союзе практически было закончено формирование теории антагонистических дифференциальных игр как самостоятельной математической дисциплины. Принципиальное значение при этом имели работы Красовского по унификации дифференциальных игр. Развитие теории антагонистических дифференциальных игр обострило вопрос об определении и поиске обобщённых (вообще говоря, негладких) решений УЧП. Отметим также, что в 1970-х гг. в Московской школе по теории УЧП велись интенсивные работы (инициированные современными физическими задачами) по созданию теории УЧП с негладкими решениями. Здесь важное значение имели пионерские работы С. Н. Кружкова и В. П. Маслова [например, (Кружков. 1975; Маслов. 1987)]. Всё это сподвигло А. И. Субботина к созданию теории обобщённых решений УЧП первого порядка.
Чтобы пояснить теорию обобщённых решений, вначале опишем результат А. И. Субботина и Н. Н. Субботиной о необходимых и достаточных условиях существования функции цены в дифференциальных играх с фиксированным моментом окончания и непрерывной функцией платы Предположим, что непрерывная функция цены является дифференцируемой по любому направлению в каждой позиции Как правило, такое условие выполнено в конкретных дифференциальных играх.
Под производной по направлению понимаем величинуСправедлива следующая теорема (Субботин. 1978). В игре с фиксированным моментом окончания и терминальной непрерывной функцией платы непрерывная функция удовлетворяющая терминальному условию является функцией цены игры тогда и только тогда, когда при всех выполнены неравенстваЗдесьСледовательно, необходимые и достаточные условия существования функции цены имеют вид двух неравенств, а не одного соотношения в виде равенства, как это было в классической теории УЧП первого порядка, и в частности в теории уравнений Гамильтона – Якоби. Содержательно левое неравенство в означает выполнение свойства стабильности при дискриминации второго игрока первым, а правое неравенство, наоборот, первого вторым (Красовский. 1974; Krasovskii. 1988). Такие свойства стабильности рассматриваются теперь с учётом значений функции В точках непрерывной дифференцируемости функции неравенства обращаются в равенства, и мы получаем выполнение соотношения
Пусть при исследовании конкретной задачи с фиксированным моментом окончания и терминальной непрерывной функцией платы мы получили некоторую функцию при обладающую свойствами: 1) функция непрерывна и 2) удовлетворяет терминальному условию кроме того, 3) множество разбито на области, во внутренности каждой из которых функция непрерывно дифференцируема и удовлетворяет равенству вида а в любой точке на границе каждой из областей – двум неравенствам Тогда функция является ценой игры.
Обобщённые минимаксные решения УЧП
Сформулированная в предыдущем пункте теорема и тщательный анализ классического метода характеристик для УЧП первого порядка (Курант. 1964; Меликян. 2014) позволили А. И. Субботину ввести понятие обобщённого «минимаксного» решения УЧП. Тем самым было открыто новое направление в изучении не только дифференциальных игр, но и в математической теории уравнений в частных производных. Следуя теории А. И. Субботина, рассмотрим УЧП первого порядка (Субботин. 2003)Здесь – открытое множество, – скалярная функция, – вектор, совпадающий с вектором градиента функции в точке если она дифференцируема в этой точке. Скалярная функция непрерывна, удовлетворяет условию Липшица по третьему аргументу и не возрастает по второму аргументу. Непрерывная функция называется минимаксным решением уравнения если для любой точки на графике функции и любого вектора существуют интервал и липшицева функция на нём, которая является решением дифференциального уравнения с начальным условием и удовлетворяет при всех равенству
Подчеркнём, что представляет собой УЧП весьма общего вида. В определении решения проверка свойств, связанных с вектором напоминает проверку стабильности (инвариантности) функции цены в дифференциальных играх.
Используя понятие минимаксного решения, Субботин доказал теоремы существования и единственности решения для различных задач, в том числе для уравнений Гамильтона – Якоби с краевым условием в виде непрерывной по функции, заданной в некоторый фиксированный момент времени При этом был охвачен случай, когда гамильтониан зависит от значений искомой функции.
Обобщённые вязкостные решения
В это же время (начало 1980-х гг.) в работах М. Г. Крэндалла и П.-Л. Лионса было введено понятие обобщённого «вязкостного» решения УЧП (Crandall. 1983). Непрерывная функция называется вязкостным решением УЧП в области , если выполнено следующее условие: для любой точки и для любой непрерывно дифференцируемой функции такой, что разность достигает в точке локального минимума (максимума), имеет место неравенство Здесь функции играют роль тест-функций. В целом два неравенства в напоминают условия стабильности (инвариантности) функции цены в дифференциальных играх.
В рамках понятия вязкостного решения (так же как и минимаксного) были доказаны теоремы существования и единственности для широкого класса задач УЧП. Для некоторых классов УЧП А. И. Субботиным и А. М. Тарасьевым была обоснована эквивалентность минимаксного и вязкостного решений (Subbotin. 1986). Доказательство эквивалентности понятий минимаксного и вязкостного решений приведено также в книге Субботина (Субботин. 2003).
Теория обобщённых решений УЧП открывает новые возможности для разработки численных методов нахождения функции цены антагонистических дифференциальных игр. Новые методы могут базироваться не только на попятных по времени процедурах динамического программирования, но и на сеточных аппроксимациях функции цены, рассматриваемых во всём пространстве игры [см., например, (Bardi. 1999. P. 105–175)].
Задачи игрового быстродействия
До сих пор, поясняя методы решения дифференциальных игр, мы говорили об играх с фиксированным моментом окончания.
Другим важным классом являются задачи с нефиксированным моментом окончания. Из них наиболее распространёнными являются задачи быстродействия, в которых платой является время перевода системы на заданное множество. Для таких задач также вводится понятие стабильного (и максимального стабильного) моста. Однако здесь понятие стабильности предусматривает попадание на целевое множество заданное уже в пространстве Численные процедуры построения стабильных мостов при этом существенно усложняются, но они также разработаны и продолжают развиваться ныне. Главное отличие игровых задач быстродействия от задач с фиксированным моментом окончания и непрерывной терминальной функцией платы в том, что в типичных примерах функция цены не является непрерывной.
Сингулярные многообразия
Айзекс описал типы возможных сингулярных многообразий размерности в автономных [функция в не зависит от ] дифференциальных играх (Айзекс. 1967). Рассеивающей была названа поверхность, из каждой точки которой в прямом времени выходят два оптимальных движения в разные стороны от поверхности. Универсальной называется поверхность, на которую оптимальные движения приходят с её обеих сторон и затем идут по ней. Полупроницаемая – это поверхность, в каждой точке которой первый игрок не допускает сход системы в одну из сторон, а второй игрок предотвращает переход в противоположную сторону.
На полупроницаемых поверхностях в задачах быстродействия происходит потеря непрерывности функции цены – времени оптимального быстродействия. Поэтому Айзекс для задач быстродействия назвал такие поверхности барьерными.
Особой заслугой Айзекса является обнаружение и описание экивокальной сингулярной поверхности. Оптимальные движения приходят на такую поверхность с одной из её сторон, затем продолжение идёт по поверхности и в каждый момент может давать ветвь, переходящую на другую сторону. Айзекс показал, что экивокальные поверхности – это специфика дифференциальных игр: сингулярных экивокальных поверхностей не может быть в задачах управления с одним игроком.
Сингулярные поверхности создают «скелет» решения дифференциальной игры. Вне сингулярных поверхностей функция цены является непрерывно дифференцируемой.
В книге Й. Левина, а также в книге Т. Башара и Г. Олсдера содержится большое число примеров дифференциальных игр с пояснением возникающих в них сингулярных поверхностей (Lewin. 1994; Başar. 1998). Существенное продвижение теоретического исследования сингулярных поверхностей было сделано А. А. Меликяном (Меликян. 2014).
Игра «шофёр-убийца»
Пожалуй, наиболее известной задачей игрового быстродействия является игра «шофёр-убийца», предложенная Айзексом (Айзекс. 1967). В этой задаче автомобиль («машина Дубинса», по современной терминологии) преследует безынерционного пешехода и пытается как можно скорее захватить его в заданную замкнутую окрестность своего текущего положения. Айзекс использовал замену переменных, после которой фазовый вектор становится двумерным и все построения проводятся на двумерной плоскости. Однако он сумел получить решение лишь в некоторой начальной части попятных построений. Полностью задача исследована в диссертации Э. Мерца (Merz. 1971). При этом были обнаружены новые типы сингулярных линий (или, лучше сказать, уточнены определения сингулярных линий, предложенные Айзексом). Полученные Мерцем результаты подтверждены численным исследованием задачи, представленным в работе «Игра шофёр-убийца: история и современные исследования» (Пацко. 2009). Отличающиеся от задачи «шофёр-убийца» постановки задач игрового быстродействия, где один из объектов – машина Дубинса, а другой является безынерционным объектом, исследованы в работах Й. Левина, Г. Олсдера; П. Кардальяге, М. Кинкампуа, П. Сен-Пьера (Lewin. 1979; Cardaliaguet. 1999. P. 177–247).
Дифференциальные игры с интегральными ограничениями
Типичными интегральными ограничениями на управления первого и второго игроков являются квадратичные ограниченияЗдесь функции и предполагаются непрерывно дифференцируемыми.
Если на промежутке где реализовалось управление первого игрока, то естественно считать, что его интегральный ресурс уменьшился иВ предположении о непрерывности функции имеем Аналогично за второго игрока. Поэтому к основной системе можем добавить соотношенияс начальными условиями Тем самым формально избавляемся от интегральных ограничений, но при этом увеличиваем фазовый вектор рассматриваемой системы, вводя в него компоненты и
После указанных преобразований можно изучать задачи и рассматривать конструкции, описанные ранее, учитывая при этом, что уравнения нелинейные, значения и могут быть сколь угодно большими, должны соблюдаться условия и Эти обстоятельства выделяют класс дифференциальных игр с интегральными ограничениями как самостоятельный и весьма трудный.
В качестве примера рассмотрим игровую задачу быстродействия (задачу преследования) для автономных однотипных объектовна промежутке с интегральными ограничениями Добавляя к уравнениям соотношения получим объекты с фазовыми векторами и При начальных условиях и первый игрок стремится минимизировать время до момента первого совпадения векторов и а второй – максимизировать. В текущий момент каждому из игроков известен объединённый фазовый вектор
Для поиска оптимальной позиционной стратегии первого игрока используем свойство однотипности расширенной системы Полагая и вводим вспомогательную задачу управленияс начальным состоянием Считаем, что управляющее воздействие стеснено ограничениемПусть – момент оптимального быстродействия в такой задаче и – соответствующее оптимальное программное управление.
Рассмотрим теперь в рамках игровой задачи объединённый фазовый вектор в некоторый момент и предположим, что Приняв за начальный момент во вспомогательной задаче, определим программное управление В книге Н. Н. Красовского «Теория управления движением» доказано, что оптимальное позиционное управление первого игрока в системе задаётся равенством (Красовский. 1968)Таким образом, оптимальное позиционное управление первого игрока в текущей позиции в момент определяется в виде начального значения программного управления при Показано, что если первый игрок придерживается стратегии начиная с момента то вплоть до первого момента совпадения положений первого и второго игроков, т. е. до момента окончания игры.
Оптимальное (минимаксное) время совпадает с и является моментом первого поглощения множества достижимости второго игрока множеством достижимости первого из начальных состояний и (Красовский. 1968).
Важно, что стратегия является универсальной: её оптимальность не зависит от начальных позиций объектов [из области состояний, где задача быстродействия разрешима].
Множества достижимости первого и второго игроков в рассматриваемой задаче [как и множество достижимости разностной системы ] – эллипсоиды, т. е. имеют гладкую границу. Вырабатываемое в текущий момент управление первого игрока «прицеливает» его движение на единственную точку соприкосновения границ множеств достижимости в момент первого поглощения, рассчитываемого по текущим состояниям.
Момент первого поглощения для задач с линейной динамикой и квадратичными интегральными ограничениями помогает исследовать задачи преследования и в случае, когда условие однотипности нарушено. Применение множеств достижимости разумно также и для линейных задач с фиксированным моментом окончания и выпуклой непрерывной терминальной функцией платы.
В целом, однако, следует отметить, что в отличие от геометрических ограничений теория дифференциальных игр с интегральными ограничениями развита намного хуже. Мало́ также и количество публикаций.
Интенсивно изучаемые классы антагонистических дифференциальных игр
Приведём перечень классов антагонистических дифференциальных игр с геометрическими ограничениями на управления, которые не были упомянуты выше, но в теоретическом исследовании которых достигнуто существенное продвижение.
Задачи с фазовыми ограничениями. Обычно фазовые ограничения являются замкнутыми. Оговаривается, какой игрок (первый или второй) обязан их соблюдать.
Задачи с неполной информацией. Пусть, например, в процессе движения первый игрок получает неточную информацию о фазовом состоянии системы Это приводит к тому, что при постановке дифференциальной игры за первого игрока состоянием системы в момент для него является не точка в конечномерном пространстве, а множество, согласованное с информацией о процессе наблюдения-управления, полученной до этого момента. Аналогично, если второй игрок имеет неточную информацию.
Задачи с неопределёнными ограничениями на управление. Во многих прикладных задачах геометрическое ограничение на управление противника трудно задать точно. Например, в задаче о посадке самолёта в условиях ветрового возмущения (ветер – второй игрок) мы, как правило, не знаем точно, в каких пределах изменяется скорость ветра. Теория дифференциальных игр позволяет в таком случае строить адаптивное управление обратной связи первого игрока.
Задачи для систем с последействием. В таких задачах движение управляемой системы описывается не формулой а формулой, где скорость в момент зависит от состояний системы в прошлом (или от управления системы в прошлом). Здесь под позицией системы в текущий момент обычно понимают историю движения на некотором промежутке примыкающем к моменту слева.
Задачи для систем с дробными производными. Вместо обычной производной в можно рассматривать дробную производную.
Задачи с группами объектов. Пусть одна группа движущихся объектов противодействует другой группе. Выписывая объединённый фазовый вектор, получаем очень большую его размерность, что делает невозможным эффективное исследование задачи в общей постановке. Поэтому в таких задачах изучаются частные случаи, в рамках которых удаётся дать ответ об исходе игры.
Задачи для систем с распределёнными параметрами. Самостоятельными и очень трудными являются задачи, в которых описание поведения конфликтно-управляемого объекта использует частные производные. Например, объект – стержень, и нас интересует температура в его различных частях. Распределение температуры по стержню зависит от управлений первого и второго игроков.