Введение к работе
Актуальность темы. Управление динамическими системами на практике как правило происходит в условиях неопределенности, помех и конфликтов. Математической теорией, в рамках которой изучаются такие задачи, является теория дифференциальных игр. В данной работе рассматриваются антагонистические дифференциальные игры, в которых участвуют два игрока с противоположными интересами. Термин «дифференциальная игра» был введен Р. Айзексом, проводившим первые теоретические исследования в этой области на основе разработанного им метода сингулярных поверхностей. Им также впервые рассмотрена дифференциальная игра «шофер-убийца» и частично получено ее аналитическое решение.
Классические работы по теории дифференциальных игр в СССР принадлежат Л.С. Понтрягину, Н.Н. Красовскому, А.И. Субботину, Б.Н. Пшеничному. Л.С. Понтря-гиным предложен метод альтернированного интеграла для решения линейных задач. Этот метод использует в своем построении понятия суммы и разности множеств по Минковскому. В отличие от этого метода, операторные конструкции, предложенные Б.Н. Пшеничным, применимы и для нелинейных дифференциальных игр, но требуют разработки алгоритмов, которые позволили бы приближенно вычислять образы этих операторов. Н.Н. Красовский и А.И. Субботин исследовали дифференциальные игры в довольно общей постановке. Ими доказана теорема об альтернативе, введено понятие стабильного моста и предложен метод экстремального прицеливания для построения оптимальных стратегий. Позднее были предложены и получили распространение методы, использующие для построения стратегий уравнение Гамильтона-Якоби-Беллмана-Айзекса.
Важные результаты по дифференциальным играм были получены в работах А. Б. Куржанского, А. В. Кряжимского, Ю. С. Осипова, А. И. Субботина, А. Г. Ченцова, А. А. Чикрия, Ю. И. Онопчука, В. В. Остапенко, Ф. Л. Черноусько, А. А. Меликяна, Е.Ф. Мищенко. Существенные результаты были получены Э. Г. Альбрехтом, В. Д. Батухтиным, Н.Д. Боткиным, И. Л. Григоренко, В.И. Жуковским, М.И. Зеликиным, Г.Е.Ивановым, Д.В. Камзолкиным, А.Ф. Клейменовым, А.Н. Красовским, СИ. Кум-ковым, С.С. Кумковым, Ю.С. Ледяевым, Н.Ю. Лукояновым, В.И. Максимовым, М.С. Никольским, О.И. Никоновым, B.C. Пацко, И. Н. Петровым, Л. А. Петросяном, Е.С. Половинкиным, А.П. Пономаревым, Н.Н.Субботиной, A.M. Тарасьевым, В.Е. Третьяковым, В.Л. Туровой, А.А. Успенским, В.И. Ухоботовым, В.И. Ушаковым, СВ. Чистяковым и другими.
К сожалению, далеко не все типы задач теории дифференциальных игр удается решить аналитически. Поэтому актуальной становится задача разработки численных методов поиска оптимальных стратегий в дифференциальных играх. Основные направления исследований, посвященных численным методам, в целом повторяют направления теоретических исследований и основаны на аппроксимационных схемах построения используемых теоретических конструкций (уравнения Гамильтона-Якоби-Беллмана-Айзекса, альтернированного интеграла Понтрягина, стабильного моста). При этом важно не только приближенно построить мост или альтернированный интеграл, но и вычислить оптимальные стратегии.
В задачах приведения фазового вектора на целевое множество часто возникают геометрические подзадачи, которые также необходимо решать алгоритмически. Для выпуклых задач при вычислении суммы и разности множеств по Минковскому используется аппарат опорных функций. Также известна техника эллипсоидального исчисления, позволяющая исследовать линейные дифференциальные игры, для которых целевое множество и множества допустимых управлений представляют собой эллипсоиды. К сожалению, аппарат опорных функций и эллипсоидальная техника неприменимы для игр с нелинейной динамикой или с невыпуклым целевым множеством.
С другой стороны, в связи с решением различных задач робототехники, например, планирования движения роботов (motion planning), развиваются методы компьютерной геометрии и создается библиотека программ (см. ), используемых для решения таких задач. В частности, в данной библиотеке реализованы эффективные алгоритмы вычисления суммы Минковского двух невыпуклых многоугольников. Несмотря на то, что в компьютерной геометрии и теории дифференциальных игр имеются общие задачи, эти два раздела математики, насколько известно автору, до сих пор существовали абсолютно независимо.
Чрезвычайно высокая вычислительная сложность алгоритмов, используемых в теории дифференциальных игр, делает актуальной задачу анализа эффективности предлагаемых алгоритмов. Теоретический анализ эффективности алгоритмов состоит в оценках их погрешностей, а следовательно, и скоростей сходимости. Работ на эту тему сравнительно мало, и в большинстве из них рассматриваются лишь линейные дифференциальные игры или делаются предположения о выпуклости целевого множества. Часть работ ограничивается оценкой погрешности, связанной с дискретизацией по времени, но важно учитывать также и погрешность, вызванную дискретизацией по пространству фазовой переменной. Для полного исследования эффективности алгоритмов следует не ограничиваться оценкой погрешности построения моста или альтернированного интеграла, но и оценить погрешность построенных стратегий.
Все это делает актуальной задачу разработки алгоритмов для построения оптимальных стратегий в нелинейных дифференциальных играх и оценки их погрешности, учитывающей как дискретизацию по времени, так и дискретизацию по пространствам фазовой переменной и управлений.
Цель работы. Разработать алгоритмы поиска эпсилон-оптимальных стратегий в нелинейных дифференциальных играх с целевым множеством как с фиксированным временем окончания, так и с нефиксированным временем окончания. Оценить погрешность предложенных алгоритмов в зависимости от параметров дискретизации как по времени, так и по пространствам фазовой переменной и управлений. Доказать сходимость и эффективность этих алгоритмов. Провести численные эксперименты и сравнить реализующуюся на практике погрешность предложенных алгоритмов с ее теоретической оценкой.
Методы исследования. Аппарат выпуклого и многозначного анализа, попятные конструкции дифференциальных игр, методы компьютерной геометрии.
Научная новизна. Разработаны новые алгоритмы поиска эпсилон-оптимальных стратегий в нелинейных дифференциальных играх с целевым множеством. Рассмот-
рены как игры с фиксированным временем окончания, так и нефиксированным временем окончания. Для вычисления одношаговых множеств достижимости, используемых в попятной конструкции, на основании которой строится алгоритм, введены операторы Минковского, обобщающие понятия суммы и разности множеств по Мин-ковскому. Обобщен известный в области компьютерной геометрии алгоритм поиска суммы Минковского двух многоугольников на плоскости. Предложенный алгоритм позволяет эффективно вычислять аппроксимации значений операторов Минковского в плоском случае. Получена оценка погрешности таких аппроксимаций и общая оценка погрешности алгоритмов поиска эпсилон-оптимальных стратегий в рассматриваемых дифференциальных играх на плоскости.
Теоретическая и практическая ценность. В диссертации предложен новый подход к построению и исследованию алгоритмов поиска эпсилон-оптимальных стратегий в нелинейных дифференциальных играх с целевым множеством, основанный на использовании операторов Минковского. Изучены топологические, геометрические и экстремальные свойства операторов Минковского, обобщающих понятия суммы и разности множеств по Минковскому. Разработаны конструктивные алгоритмы приближенного вычисления значений операторов Минковского, использующие методы компьютерной геометрии. Полученные явные оценки погрешностей алгоритмов позволяют по заданной точности определять значения параметров дискретизации, которые нужно использовать для получения стратегий, обеспечивающих эту точность. Теоретические оценки и результаты численных экспериментов показали, что предложенный алгоритм является более эффективным, чем известные аналоги. Эффективность алгоритма на практике подтверждена численными экспериментами.
Апробация работы. Результаты, изложенные в диссертации, в разное время докладывались и обсуждались на
Четвертой международной конференции «Системный анализ и информационные технологии» САИТ-2011, пос. Новоабзаково, 2011;
Четвертой традиционной молодежной школе «Управление, информация, оптимизация», Звенигород, 2012;
55-й научной конференции МФТИ - Всероссийской научной конференции «Современные проблемы фундаментальных и прикладных, естественных и технических наук в современном информационном обществе», Москва - Долгопрудный, 2012;
Научных семинарах кафедры высшей математики МФТИ, Москва - Долгопрудный, 2010 - 2013;
Научном семинаре «Теория автоматического управления» лаборатории 7 ИПУ РАН, Москва, 2013;
Научном семинаре «Оптимальное управление: математическая теория и прикладные задачи» кафедры оптимального управления факультета вычислительной математики и кибернетики МГУ, Москва, 2013;
VI Международной конференции «Динамические системы: устойчивость, управление, оптимизация», посвященной 95-летию со дня рождения Е.А. Барбашина, Минск, 2013.
Также на основе материалов диссертации автором был прочитан факультативный курс «Нелинейные дифференциальные игры на плоскости» для студентов МФТИ.
Публикации. По теме диссертации опубликовано 8 работ, в том числе две [1,2] - в изданиях из списка, рекомендованного ВАК РФ. Основные результаты диссертации отражают личный вклад соискателя в опубликованные по теме диссертации работы с соавторами.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и списка иллюстраций. Общий объем диссертации составляет 122 страницы. Список литературы содержит 76 наименований. Список иллюстраций содержит 20 наименований.
Похожие диссертации на Алгоритмы построения эпсилон-оптимальных стратегий в нелинейных дифференциальных играх на плоскости
