Алгоритмы построения эпсилон-оптимальных стратегий в нелинейных дифференциальных играх на плоскости тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Двуреченский, Павел Евгеньевич

• Двуреченский, Павел Евгеньевич
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Двуреченский, Павел Евгеньевич

Оглавление

Введение

1 Алгоритм вычисления значений операторов Минковского

1.1 Определение и свойства операторов Минковского

1.2 Алгоритм вычисления суммы Минковского

1.3 Конволюта многоугольника и многозначного отображения на плоскости

1.4 Вспомогательные оценки

1.5 Доказательство теоремы 1.3.1

1.6 Алгоритм вычисления значений операторов Минковского

1.7 Модифицированные операторы Минковского

2 Дифференциальная игра с фиксированным временем окончания

2.1 Постановка задачи

2.2 Стратегии и законы управления

2.3 Алгоритм вычисления стратегий управления

2.4 Доказательство теорем 2.3.1-2.3.4

2.5 Применение алгоритмов главы 1 для построения стратегий

3 Дифференциальная игра быстродействия

3.1 Постановка задачи

3.2 Стратегии и законы управления

3.3 Алгоритм вычисления стратегий управления

3.4 Доказательство теорем 3.3.1-3.3.4

3.5 Применение алгоритмов главы 1 для построения стратегий

4 Результаты численных расчетов

4.1 Игра для нелинейного маятника с фиксированным временем окончания

4.2 Игра для нелинейного маятника с нефиксированным временем

окончания и ее модификация

4.3 Игра «шофер-убийца» и ее модификации

Заключение

Литература

Список иллюстраций

Введение диссертации (часть автореферата) на тему «Алгоритмы построения эпсилон-оптимальных стратегий в нелинейных дифференциальных играх на плоскости»

Введение

В современной математике задачи оптимального управления динамическими системами в условиях неопределенности, помех и конфликтов изучаются в рамках теории дифференциальных игр. В данной работе рассматриваются антагонистические дифференциальные игры (игры с нулевой суммой), в которых участвуют два игрока с противоположными интересами. Исследования по теории антагонистических дифференциальных игр насчитывают более чем полувековую историю. Термин «дифференциальная игра» был введен Р. Айзексом. Его первые работы [58], [59], [60], [61] относятся к 50-м годам XX века. В его книге [62] проводится теоретическое рассмотрение различных дифференциальных игр на основе разработанного им метода сингулярных поверхностей.

В 60-ые годы XX века теория дифференциальных игр получила существенное развитие в работах советских математиков. Среди них следует отметить работы Л.С. Понтрягина по линейным дифференциальным играм [25], [26], [27], [28], работы H.H. Красовского [15], [16], Б.Н. Пшеничного [30], [31], [32]. В работе [28] предложен известный метод альтернированного интеграла для решения линейных задач. Этот метод использует в своем построении понятия суммы и разности множеств по Минковскому. В отличие от этого метода, операторные конструкции, предложенные Б.Н. Пшеничным, применимы и для нелинейных дифференциальных игр, но требуют разработки алгоритмов, которые позволили бы приближенно вычислять образы этих операторов. В 70-е годы исследования по дифференциальным играм активно продолжались. В 1974 году была издана классическая книга [17], в которой исследуются дифференциальные игры в довольно общей постановке. В этой книге доказана теорема об альтернативе, введено понятие стабильного моста и предложен метод экстремального прицеливания для построения оптимальных стратегий. Стоит отметить также, что в этой книге особое внимание уделяется переходу от теоретических рассмотрений к конструктивным, позволяющим создавать алгоритмы построения стабильных мостов и оптимальных стратегий.

В работах зарубежных авторов [48], [50], относящихся к этому периоду, развивался

метод сингулярных поверхностей, предложенный Р. Айзексом. В диссертации [64] дано полное аналитическое решение игры «шофер-убийца», поставленной Р. Айзексом. Отметим также работы [55], [56], в которых рассматривается дискретная схема построения верхней и нижней цены игры с помощью пошагового минимакса или максимина соответственно и доказывается сходимость предлагаемых аппроксимаций и книгу [49], подводящую некоторые итоги теоретических исследований по дифференциальным играм в 50-е - 60-е годы прошлого столетия.

Позднее были предложены и получили распространение методы, использующие для построения стратегий уравнение Гамильтона-Якоби-Беллмана-Айзекса. Здесь можно отметить работы [35], [36], [37], [46], [52]. В последние десятилетия при теоретическом исследовании дифференциальных игр активно используются методы выпуклого и многозначного анализа. Примером могут служить работы [10], [12], [51].

Важные результаты по дифференциальным играм были получены в работах А. Б. Куржанского, А. В. Кряжимского, Ю. С. Осипова, А. И. Субботина, А. Г. Ченцова, А. А. Чикрия, Ю. Н. Онопчука, В. В. Остапенко, Ф. Л. Черноусько, А. А. Меликяна, Е.Ф. Мищенко. Существенные результаты были получены Э. Г. Альбрехтом, В. Д. Батухтиным, Н.Д. Боткиным, Н. J1. Григоренко, В.И. Жуковским, М.И. Зеликиным, Г.Е.Ивановым, Д.В. Камзолкиным, А.Ф. Клейменовым, А.Н. Красовским, С.И. Кумковым, С.С. Кумковым, Ю.С. Ледяевым, Н.Ю. Лукояновым, В.И. Максимовым, М.С. Никольским, О.И. Никоновым, B.C. Пацко, Н. Н. Петровым, Л. А. Петросяном, Е.С. Половинкиным, А.П. Пономаревым, Н.Н.Субботиной, A.M. Тарасьевым, В.Е. Третьяковым, В.Л. Туровой, A.A. Успенским, В.И. Ухоботовым, В.Н. Ушаковым, С.В. Чистяковым и другими.

Помимо теоретических исследований огромный практический интерес представляют численные методы поиска оптимальных стратегий в дифференциальных играх. Пожалуй, наиболее изученной с точки зрения вычислительных методов задачей является линейно-квадратичная задача, в которой динамика задается линейным дифференциальным уравнением, а функционал качества является квадратичным. Такой задаче посвящены, например, работы [34], [53]. Некоторые классы игр [10] удается свести к задаче оптимального управления и применить принцип максимума Понтрягина.

Основные направления исследований, посвященных численным методам, в целом повторяют направления теоретических исследований и основаны на аппроксимационных схемах построения используемых теоретических конструкций. Так, предложены алгоритмы численного решения уравнения Гамильтона-Якоби-Беллмана-Айзекса [38], [47]. В работах [9], [23] рассматриваются численные методы

приближенного построения альтернированного интеграла Понтрягина. Большое количество работ основывается на методе стабильного моста и предлагает различные алгоритмы для его приближенного вычисления [13], [14], [40]. При этом важно не только приближенно построить мост или альтернированный интеграл, но и вычислить оптимальные стратегии, как это сделано, например, в [5], [19], [39].

С алгоритмической точки зрения наиболее изученным является класс задач с линейной динамикой [2], [41], [67]. Работ, в которых предложены алгоритмы для нелинейных игр меньше. Среди них отметим работы [14], [66]. В работе [14] рассматривается игра с целевым множеством и фиксированным временем окончания, доказана сходимость в метрике Хаусдорфа построенной на основе пиксельного метода аппроксимации сечений максимального стабильного моста к истинным сечениям максимального стабильного моста. При этом вопрос о построении стратегий остается в стороне. В работе [66] рассмотрена нелинейная игра с нефиксированным временем окончания «шофер-убийца» и ее модификации, предложен алгоритм для численного построения множеств уровня цены игры, но не даны оценки погрешности этого алгоритма.

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

С другой стороны, в связи с решением различных задач робототехники, например, планирования движения роботов (motion planning), развиваются методы компьютерной геометрии [54], [57], [68] и создается библиотека программ (см. www.cgal.org), используемых для решения таких задач. В частности, в данной библиотеке реализованы эффективные алгоритмы вычисления суммы Минковского двух невыпуклых многоугольников. Несмотря на то, что в компьютерной геометрии и теории дифференциальных игр имеются общие задачи, эти два раздела математики, насколько известно автору, до сих пор существовали абсолютно независимо.

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

теории дифференциальных игр, делает актуальной задачу анализа эффективности и скорости сходимости этих алгоритмов. Для анализа скорости сходимости алгоритмов важно оценить их погрешности. Оценкам погрешностей алгоритмов и скорости их сходимости в теории дифференциальных игр посвящены работы [4], [24], [22], [39]. В работе [4] исследованы игры с линейной динамикой и фиксированным временем окончания и получена оценка близости в метрике Хаусдорфа между сечениями множеств позиционного поглощения в исходной игре и в ее аппроксимации. В работе [24] рассмотрены линейные дифференциальные игры с выпуклым целевым множеством и фиксированным временем окончания, а также выпуклыми ограничениями на управления, доказана оценка близости альтернированных сумм и альтернированного интеграла Понтрягина. При этом не учитывается дискретизация по пространству фазовой переменной. Работа [22] посвящена той же задаче, но использует аппарат опорных функций для приближенного вычисления суммы и разности множеств по Минковскому и учитывает связанную с таким приближением погрешность. В ней также предложен способ построения стратегий. В работе [39] предложен алгоритм для линейной дифференциальной игры на плоскости и нефиксированным временем окончания. Алгоритм использует разбиение временного отрезка игры на интервалы одинаковой длины г и пошагово строит множества уровня функции платы, которой является время перевода системы на целевое множество, а также позволяет приближенно найти оптимальные стратегии. Оценка погрешности алгоритма при этом получается порядка у/т.

Часть работ ограничивается оценкой погрешности, связанной с дискретизацией по времени, но важно учитывать также и погрешность, вызванную дискретизацией по пространству фазовой переменной, как это сделано, например, в [7], [8]. В работе [7] предлагается алгоритм для поиска эпсилон-оптимальных стратегий в нелинейной игре быстродействия с целевым множеством в многомерном пространстве. Полученная оценка погрешности этого алгоритма имеет вид с\т + Сг/г/т + сз^, где сг,с2,сз -константы зависящие только от задачи, т - параметр дискретизации по времени, Н - параметр дискретизации по пространству фазовой переменной, 6 - параметр дискретизации по пространствам управлений. В работе [8] предлагается алгоритм для поиска эпсилон-оптимальных стратегий в нелинейной игре с липшицевой финитной платой в многомерном пространстве и показано, что этот алгоритм может быть использован для поиска эпсилон-оптимальных стратегий в нелинейной игре с целевым множеством и фиксированным временем окончания. Полученная оценка погрешности этого алгоритма имеет тот же характер зависимости от параметров дискретизации, что ив [7].

Диссертация включает в себя четыре главы.

В первой главе вводится понятие операторов Минковского, обобщающих понятия суммы и разности множеств по Минковскому, и рассматриваются их свойства. Для приближенного вычисления их образов в двумерном случае предлагается алгоритм, состоящий из двух этапов: построение конволюты и извлечение из нее границы многоугольника, являющегося аппроксимацией образа соответствующего оператора. Алгоритм построения конволюты обобщает алгоритм построения конволюты двух многоугольников при вычислении суммы Минковского этих многоугольников [68]. Следует отметить, что операторы Минковского в общем случае не сводятся к сумме Минковского. Поэтому в диссертации даны независимые описания и обоснования алгоритмов построения значений операторов Минковского, использующие некоторые идеи алгоритмов построения суммы Минковского двух невыпуклых многоугольников. Далее доказывается оценка близости конволюты и границы образа оператора Минковского. После этого приводятся алгоритмы, позволяющие по конволюте вычислить границу многоугольника, аппроксимирующего образ соответствующего оператора Минковского и доказывается теорема об оценке близости построенной аппроксимации и образа оператора Минковского в метрике Хаусдорфа. Затем вводится понятие модифицированных операторов Минковского, рассматриваются их свойства и доказывается, что их образы близки к образам операторов Минковского, а также доказывается теорема о близости алгоритмических аппроксимаций образов операторов Минковского и образов модифицированных операторов Минковского. Модифицированные операторы Минковского используются далее для построения эпсилон-оптимальных стратегий в дифференциальных играх.

Вторая глава посвящена алгоритму построения эпсилон-оптимальных стратегий для нелинейной дифференциальной игры с целевым множеством и фиксированным моментом окончания. Алгоритм использует одношаговые операторы достижимости, конструкция которых близка к операторной конструкции Б.Н.Пшеничного [33]. Показано, что одношаговые операторы достижимости являются модифицированными операторами Минковского. В предположении, что существуют алгоритмы, позволяющие с заданной точностью вычислять аппроксимацию одношаговых операторов достижимости, предложен алгоритм для вычисления эпсилон-оптимальных стратегий и доказана теорема о погрешности этого алгоритма. В двумерном случае для приближенного вычисления образов одношаговых операторов достижимости используются алгоритмы первой главы и выводится общая оценка погрешности предлагаемого алгоритма в зависимости от параметров дискретизации по времени и по пространствам управлений и фазовой переменной.

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

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

Основные результаты, отражающие личный вклад автора в работы, опубликованные по теме диссертации и выносимые на защиту:

1. Доказаны теоремы об оценке близости истинных значений операторов Минковского и их численных аппроксимаций в двумерном случае.

2. Получены новые топологические, геометрические и экстремальные свойства операторов Минковского.

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

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

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

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

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

Глава 1

Алгоритм вычисления значений операторов Минковского

В данной главе введены операторы Минковского, обобщающие понятия суммы и разности по Минковскому, предложены алгоритмы, позволяющие вычислять значения этих операторов и дана оценка погрешности предложенных алгоритмов. В параграфе 1.1 дано определение указанных операторов и рассмотрены их свойства. Так леммы 1.1.2-1.1.4 посвящены топологическим свойствам операторов Минковского, леммы 1.1.5-1.1.7 - свойствам устойчивости и непрерывности этих операторов, леммы 1.1.8, 1.1.9 - геометрическим и экстремальным свойствам значений операторов Минковского. В параграфе 1.2 приведено краткое описание известного алгоритма вычисления суммы Минковского двух многоугольников на плоскости. Этот алгоритм состоит из двух этапов: построение конволюты двух многоугольников и извлечение суммы Минковского из построенной конволюты. В параграфе 1.3 алгоритм построения конволюты двух многоугольников обобщен для целей построения конволюты многоугольника и многозначного отображения, образами которого являются многоугольники. В параграфах 1.3 - 1.5 сформулированы и доказаны теоремы об оценке расстояния в метрике Хаусдорфа между границами образов операторов Минковского и конволютой многоугольника и многозначного отображения. В параграфе 1.6 предложен алгоритм, позволяющий извлечь из конволюты многоугольника и многозначного отображения множества, близкие в метрике Хаусдорфа к образам операторов Минковского и выведена оценка для расстояния между образами операторов Минковского и их вычисляемыми приближениями. В параграфе 1.7 введены модифицированные операторы Минковского, показана близость их образов к образам операторов Минковского, а также предложен алгоритм, позволяющий вычислять образы модифицированных операторов Минковского и

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

1.1 Определение и свойства операторов Минковского

Пусть Е - линейное пространство. Суммой и разностью Минковского множеств X С Е и Y С Е называются соответственно множества

X + Y={x + y\xeX, yeY}, X ^Y = {х е Е \ х + Y с X} .

Операторами Минковского многозначного отображения G : Е —> 2е называются операторы Ас : 2е —> 2е и BG 2Е —> 2е, заданные формулами

AgS= UOs + ОД), (1-1-1)

xeS

BgS = E\(Ag(E\S)) (1.1.2)

для любого множества S С Е.

Заметим, что в случае, когда многозначное отображение G постоянно, т.е. G(x) — Gq при всех х £ S, значения операторов Минковского совпадают соответственно с суммой и разностью Минковского:

AgS = S + G0, BGS = S± (-Go).

Таким образом, понятие операторов Минковского представляет собой естественное обобщение понятий суммы и разности Минковского. Известно, что сумма Минковского и алгоритмы ее вычисления широко применяются во многих разделах прикладной математики, таких как вычислительная геометрия (см. www.cgal.org), системы числового программного управления (numerical control), планирование движения роботов (motion planning), теория оптимального управления (optimal control theory) и ДР-

Изучим свойства введенных операторов Минковского (1.1.1), (1.1.2). Очевидно, операторы Минковского являются монотонными по включению, то есть для любых двух множеств Si, ¿2, таких, что Si С 5*2 справедливо

AgSi С AgS2, BgSI С BGS2.

Далее будем считать, что Е = К". Будем также предполагать, что отображение С(х) принимает непустые значения. Через 5 и дв будем обозначать

соответственно внутренность, замыкание и границу множества Пусть в введена некоторая норма ||ж||. Будем говорить, что функция / : Мп —» Мт удовлетворяет условию Липшица с константой Ь, если

Ц/(Х!) - /(х2)|| < - х2\\ Ухъх2 € Мп.

Через будем обозначать замкнутый шар вМпс центром в нуле и радиусом г:

05г = {х е Мп : ||ж|| < г}.

Уклонением множества X С Шп от множества У С Мп называется величина

И+(Х, У) = т£{г > О I X с К + <ВГ}. (1.1.3)

Хаусдорфовым расстоянием между множествами I С М" и У С называется

Ь.(Х, У) = тах{/*+(Х, У), /г+(У, X)}.

Заметим, что если множество X С Мп ограничено, а множество У С Мп замкнуто, то инфимум в формуле (1.1.3) достигается. В этом случае при г > У)

справедливо включение X С У +

Будем говорить, что многозначное отображение С : Мп —> 2К™ удовлетворяет условию Липшица с константой Ьс в смысле метрики Хаусдорфа, если

/г(С(ж!), С{х2)) < Ьс\\х1 - х2\\ Vж1, х2 е Мп. (1.1.4)

В дальнейшем нам понадобится следующая

Лемма 1.1.1. Пусть многозначное отображение С : —> принимает замкнутые значения и удовлетворяет условию Липшица с константой Ьс < 1 в смысле метрики Хаусдорфа (1.1.4). Пусть хо £ Мп, х\ £ С(хо). Тогда существует тючка х € С (ж) такая, что

Ьс

\\х ~ хг\\ < --=—||Ж1 - ж0||.

1 — Ьс

Доказательство. Пусть при некотором к £ N определены точки Хк-\ 6 Мп и € С(хь-\). Тогда в силу липшицевости многозначного отображения С и замкнутости его значений существует точка Е С(ж^) такая, что

Ц^+1 - ж*|| < Ьс\\хк - Хк-х]]. (1.1.5)

Таким образом, построим последовательность {хкоторая для каждого к Е N удовлетворяет неравенству (1.1.5). Следовательно, \\xk+i — хк\\ < Vq\\x\ — xq\\. Поэтому при п > к имеем

71—1 j^fc

\\ХП ~ Хк\\ < \\Х1 ~ Х0\\ V VG < zr-^-Wxi - Х0\\. (1.1.6)

и 1 — LG

Итак, последовательность {ж^} фундаментальна, а значит, имеет предел х Е Rn. Переходя к пределу во включении Xk+i Е G{xk), учитывая липшицевость многозначного отображения G и замкнутость его значений, получаем включение х Е G{x). Переходя к пределу в неравенстве (1.1.6) при к = 1, п —» сю, получаем доказываемое неравенство. □

Лемма 1.1.2. Пусть многозначное отображение G : Rn —> 2R™ принимает замкнутые значения и удовлетворяет условию Липшица с константой Lg < 1 в смысле метрики Хаусдорфа (1.1.4). Пусть задано множество S С Rn и точки хо £ intS1, уо Е хо + G(xo). Тогда для множества AqS, определенного соотношением (1.1.1), справедливо включение уо £ int^cS1.

Доказательство. Так как xq Е int S, то существует число 6 > 0 такое, что 93¿(жо) С S. Положим = (1 — Lg)S и покажем, что 93^ (у0) С AqS. Пусть У\ £ 93^ (г/о)- Применяя лемму 1.1.1 к многозначному отображению F(a) = у\ — С(а), точке хо и точке х\ — xq — уо + у\ Е F(xо), получаем существование точки х Е F(x) такой, что \\х — xi\\ < H^i — жо||- Следовательно,

и - и ^ и- ..........и ^ ИЖ1 ~ жо|| . ¿1 ,

If _ жо|| < if - xi\\ + ifi - жо|| < —;—-т— < -—— = о.

1 — Lg 1 — LG

Поэтому х Е *Bs(xo) С 5, а значит, у\ Е х + G{x) С AqS. Тем самым доказано включение 93^ (г/о) С AcS, а значит, г/о Е int AqS. □

Заметим, что требование Lg < 1 в лемме 1.1.2 существенно. Действительно, рассмотрим отображение G : R —> 2К, заданное формулой G(x) = {Lc|a;|}, х Е R, множество S = [—1,1] и точки ж0 = Уо = 0. Тогда хо Е int 5", уо Е хо + G(xо), однако при Lg > 1 включение уо е int AqS не справедливо.

Лемма 1.1.3. Пусть многозначное отображение G : Rn —> 2®" принимает замкнутые значения и непрерывно в смысле метрики Хаусдорфа (1.1.4). Пусть множество S с R™ замкнут,о и

sup sup \\и\\ < +оо.

xes ueG(x)

Тогда множество AqS замкнуто.

Доказательство. Пусть последовательность {у/.} С AgS сходится к точке уо G Мп. Тогда существует последовательность {хk} С S такая, что ук — Xk G G(xk) для любого к Е N. Поскольку последовательности {у¿J и {у^ — } ограничены, то последовательность {} также ограничена. Выделяя сходящуюся подпоследовательность, без потери общности будем считать, что {ж*;} сходится к некоторой точке xq G Rn. Поскольку множество S замкнуто, то xq G S. В силу непрерывности многозначного отображения G и замкнутости его значений справедливо включение уо — xq G G(xо). Следовательно, уо G AqS. □

Лемма 1.1.4. Пусть многозначное отображение G : Rn —> 2Rn принимает замкнутые значения и непрерывно в смысле метрики Хаусдорфа (1.1.4). Пусть задано множество S с W1 и

sup sup |Н| < +оо.

xeS ueG(x)

Тогда для множества AqS, определенного соотношением (1.1.1); справедливо равенство AqS = AqS и, следовательно dAgS = dAcS.

Доказательство. Так как S С S и оператор Ас монотонный по включению, то AqS С AqS. Отсюда, используя лемму 1.1.3 получаем AqS с AqS = AgS. Пусть теперь Zq G AqS. Тогда существует последовательность {xk} С 5, такая, что Xk —+ xq при к —> оо и выполнено включение zq G xq + G(xо). В силу непрерывности многозначного отображения G и замкнутости его значений при каждом к G N существует такая точка щ G g(xk), что справедливо неравенство \\щ — zq + жо|| < tk, где tk —5- 0 при к —> оо. Обозначим Zk = Xk + Щ- Тогда при всех к G N выполнены включения Zk G Xk + G(xk) С ^g-S" и справедливы неравенства \\zk — ¿о|| < \\xk — жо|| + 11uk — zq + £о|| < iiхк — ^о|| + tk, а ЗНаЧИТ Zk —» zq При к —► ОО. ПОЭТОМУ Zo G .Д<25* и утверждение леммы справедливо. □

Лемма 1.1.5. Пусть многозначное отображение G : Rn —> 2Ж™ принимает замкнутые значения и удовлетворяет условию Липшица с константой Lc < 1 в смысле метрики Хаусдорфа (1.1.4). Тогда для любого множества S с Rn и любого числа 5 > 0 операторы Минковского (1.1.1) и (1.1.2) удовлетворяют включениям

Ag {S + Ъз/а+ьс)) С + С Ag (S + ®J/(i_Lo)) , (1.1.7)

Ло ± »¿/(1-ьс)) с ^ ^ (1.1.8)

ВСБ + Ш{СВС(5 + ®*/(1-£с)) , (1.1.9)

Вс (5 ± »«/(1_ьс)) С ± с (5 ± »¿/(1+ьс)) • (1.1.10)

Доказательство. Докажем левое включение (1.1.7). Пусть ж Е Ас (5 + ®$/(1+ьс)). Тогда найдутся такие у Е 5, и Е ®а/(1+Ьс), V Е С {у + и), что ж = ?/ + + г>. В силу липшицевости многозначного отображения С и замкнутости его значений существует точка т Е С (у) такая, что Цг; — ги|| < ¿сЦиЦ < 6Ьс/{ 1 + Ьс) и у + ги Е А<з5. При этом ||ж — у — ги|| = \\и + у — и)\\ < 6/(1 + Ьс) + (1 + Ьс) = а значит ж Е А? 5 + 93$.

Докажем правое включение (1.1.7). Пусть х Е + 93$. Тогда найдется вектор у Е Аз»? такой, что \\х — у|| < 5. В силу равенства (1.1.1) существует вектор и) Е Б такой, что у Е ги+С(ги). Получаем, что ии Е у—С(г^). Применяя лемму 1.1.1 к векторам хо = т, х\ = т + ж — у и отображению -Р(а) = х — С(а), получаем существование вектора Е ж — С(г<)), удовлетворяющего неравенству ||ги + ж — г/ — ги|| < ||ж — г/|| <

Отсюда получаем цепочку неравенств ||ги —ги|| < \\w-\-x — у — г&|| + ||ж — у\\ < Значит, так как ъи Е 5, то ги Е 5" + 93<$/(1_£с). Используя включение ж Е и) + С^ги) и равенство (1.1.1), получаем включение правое (1.1.7).

Докажем включение (1.1.8). Пусть ж Е Ас (¿> — Тогда, в силу равенства

(1.1.1), найдется вектор у Е 5 — такой, что ж Е у + С (у). Зафиксируем

произвольный вектор 2 Е 93,5. Применяя лемму 1.1.1 к векторам жо = у, х\ = г + у и отображению Я(а) = ж + г —С(а), получаем существование вектора ъи Е ж + г — С(и/), удовлетворяющего неравенству ||го — г — у\\ < < Т-П^- Отсюда получаем

цепочку неравенств Цги — у\\ < \\w-y — г\\ + \\г\\ < Значит, и) Е У + *8д/{1-ьс) с ^

и х+г Е ги + С(к;) С АсБ. Используя равенство (1.1.1), в силу произвольности вектора г Е язй, получаем включение (1.1.8).

Докажем включение (1.1.9). Используя включение (1.1.8) для множества Е \ Б и равенство (1.1.2), получаем следующую цепочку включений

Е \ Вс (Б _Ьо)) = Ас (Е\ (Б + Ът-ьа))) = Ло {Е \ 5 ± ®г/(1_Ьс)) С

С Лг (Я \ 5) ± «г = (Я \ Яс^) - 03^ = Я \ + ЗД .

Отсюда следует включение (1.1.9).

Докажем левое включение (1.1.10). Используя правое включение (1.1.7) для множества £\5и равенство (1.1.2), получаем следующую цепочку включений

Список литературы диссертационного исследования кандидат наук Двуреченский, Павел Евгеньевич, 2013 год

Литература

[1] Айзеке Р. Дифференциальные игры. М.: Мир, 1967.

[2] Боткин Н.Д., Рязанцева Е.А. Алгоритм построения множества разрешимости в линейной дифференциальной игре высокой размерности. // Тр. ин-та мат. и мех. УрО РАН, №2, 1992. - С. 128-134.

[3] Боткин Н.Д. Оценка погрешности численных построений в дифференциальной игре с фиксированным моментом окончания. // Пробл. управл. и теории информ, Т. 11, №4, 1982. - С.283-295.

[4] Боткин Н.Д. Численное решение линейных дифференциальных игр. Диссертация на соискание ученой степени кандидата физико-математических наук. Свердловск, 1983.

[5] Ганебный С.А., Красов А.И.. Пацко B.C., Смольникова М.А. Преодоление самолетом препятствий по высоте в условиях ветрового возмущения // Труды института математики и механики УрО РАН, Екатеринбург, Т. 15, №4, 2009. - С. 69-81.

[6] Иванов Г.Е., Казеев В.А. Минимаксный алгоритм построения оптимальной стратегии управления в дифференциальной игре с липшицевой платой // Ж. выч. мат. и мат. физ, Т. 51, №4, 2011. - С.594-619.

[7] Иванов P.E. Алгоритм решения нелинейной игровой задачи быстродействия // Фундаментальные задачи и проблемы современной математики: Сб. науч. трудов / - М. МФТИ: 2011. - С. 49-76.

[8] Иванов P.E. Алгоритм построения оптимальной стратегии управления в нелинейной дифференциальной игре с липшицевой финитной платой / / Дифференциальные уравнения, Т. 48, №4, 2012. - С.551-564.

[9] Иванов Г.Е. Квадратичная оценка сходимости алгоритма вычисления альтернированного интеграла Понтрягина. // Численные методы интегральных уравнений в прикладных задачах.: Научно-метод. матер. ВВИА им. Н.Е. Жуковского. М. 1994. - С.91-111.

10] Иванов Г.Е. Седловая точка для дифференциальных игр с сильно выпукло-вогнутым интегрантом. // Мат. заметки, Т. 62, №5, 1997. - С.725-743.

11] Иванов Г. Е., Половинкин Е. С. Второй порядок сходимости алгоритма вычисления цены линейной дифференциальной игры. // Доклады РАН, Т. 340, №2, 1995. -С.151-154.

12] Иванов Т.Е., Половинкин Е.С. О сильно выпуклых линейных дифференциальных играх. // Дифференц. уравнения, Т. 31, №10, 1995. - С. 1641-1648.

13] Исакова Е.А., Логунова Г.В., Пацко B.C. Построение стабильных мостов в линейной дифференциальной игре с фиксированным моментом окончания // Алгоритмы и программы решения линейных дифференциальных игр/ Ред. Субботин А.И., Пацко B.C. Свердловск: УНЦ АН СССР, 1984. - С.127-158.

14] Камзолкин Д.В. О построении максимальных стабильных мостов для одного класса нелинейных дифференциальных игр сближения // Дифференциальные уравнения, Т. 42, №3, 2006. - С.338-346.

15] Красовский Н. П. Об одной задаче преследования // Прикл. математика и механика, Т. 26, Вып. 2, 1962. - С.218-232.

16] Красовский Н. П. Об одной задаче преследования // Прикл. математика и механика, Т. 27, Вып. 3, 1963. - С.244-254.

17] Красовский H.H., Субботин А.И. Позиционные дифференциальные игры. - М.: Наука, 1974. - 455 с.

18] Красовский Н. Н. Управление динамической системой. М.: Наука, 1985.

19] Кумков С.И., Пацко B.C. Оптимальные стратегии в задаче преследования с неполной информацией // Прикладная математика и механика, Т. 59, Вып. 1, 1995. - С.82-95.

[20] Никольский М.С. О приближенном вычислении геометрической разности множеств // Вестник Московского университета, Сер. 15, вычислительная математика и кибернетика, 1, 2003. - С.49-54.

[21] Пацко B.C.. Турова В.Л. Игра шофер-убийца: история и современные исследования. Научные доклады. Екатеринбург: УрО РАН, 2009.

[22] Половинкин Е.С., Иванов Г.Е., Балашов М.В., Константинов Р.В., Хорее A.B. Алгоритмы численного решения линейных дифференциальных игр // Математический сборник, Т. 192, №10, 2001. - С.95-122.

[23] Пономарев А.П. Оценка погрешности численного метода построения альтернированного интеграла Понтрягина. // Вести. Моск. ун-та. сер. 15, вычисл. матем. и киберн, №4, 1978. - С.37-43.

[24] Пономарев А.П. Улучшенная оценка сходимости альтернированных сумм к альтернированному интегралу Понтрягина. // Мат. заметки, Т. 35, №1, 1984. -С.83-92.

[25] Понтрягин Л. С. О некоторых дифференциальных играх // Докл. АН СССР, Т. 156, №4, 1964. - С.738-741.

[26] Понтрягин Л. С. К теории дифференциальных игр. // Успехи мат. наук, Т. 21, №4, 1966 - С.193-246.

[27] Понтрягин Л. С. О линейных дифференциальных играх 1. // Докл. АН СССР, Т. 174, №6, 1967. - С. 1278-1280.

[28] Понтрягин Л. С. О линейных дифференциальных играх 2. // Докл. АН СССР, Т. 175. т, 1967. - С.764-766.

[29] Понтрягин Л. С. Линейные дифференциальные игры преследования // Матем. сборник, Т. 112, № 3, 1980. - С. 307-330.

[30] Пшеничный Б.Н. Линейные дифференциальные игры. // Авт. и телемех, №1, 1968. - С.65-78.

[31] Пшеничный Б.Н. Структура дифференциальных игр. // Докл. АН СССР, Т. 184, №2, 1969. - С.285-287.

[32] Пшеничный Б.Н., Сагайдак М.И. О дифференциальных играх с фиксированным временем. // Кибернетика, №2, 1970. - С.54-63.

[33] Пшеничный Б.Н., Остапенко В.В. Дифференциальные игры. Киев: Наукова думка, 1992.

[34] Розоноэр Л.И. О линейно-квадратичной оптимизации и линейно-квадратичных дифференциальных играх. // Автомат, и телемех., №5, 1999. - С.170-186.

[35] Субботин А.И. Обобщение основного уравнения теории дифференциальных игр // Докл. АН СССР, Т. 254, №2, 1980. - С.293-297.

[36] Субботин А.И. Минимаксные неравенства и уравнение Гамильтона-Якоби. - М.: Наука, 1991.

[37] Субботин А.И., Ченцов А.Г. Итерационная процедура построения минимаксных и вязкостных решений уравнений Гамильтона-Якоби и ее обобщения. // Тр. Мат. ин-та РАН, Т. 224, 1999. - С.311-334.

[38] Тарасьев A.M., Успенский A.A., Ушаков В.П. Аппроксимационные схемы и конечно-разностные операторы для построения обобщенных решений уравнений Гамильтона-Якоби // Изв. РАН. Техн. кибернетика, №3, 1994. - С. 173-185.

[39] Турова В.Л. Построение множеств позиционного поглощения в линейной дифференциальной игре второго порядка с нефиксированным временем окончания. // Управление с гарантированным результатом, Свердловск, 1987. -С.92-112.

[40] Ушаков В.П. К задаче построения стабильных мостов в дифференциальной игре сближения уклонения. // Изв. АН СССР. Сер. техн. кибернетика, №4, 1980. -С.29-36.

[41] Алгоритмы и программы решения линейных дифференциальных игр/ Ред. А.И. Субботин, B.C. Пацко. Свердловск: УНЦ АН СССР. 1984.

[42] Синтез оптимального управления в игровых системах. Сборник научных трудов. Свердловск: УНЦ АН СССР. 1986.

[43] Управление с гарантированным результатом. Сборник научных трудов. Свердловск: УНЦ АН СССР. 1987.

[44] Позиционное управление с гарантированным результатом. Сборник научных трудов. Свердловск: УО АН СССР. 1988.

[45] Управление в динамических системах. Сборник научных трудов. Свердловск: УО АН СССР. 1990.

[46] Bardi М., Capuzzo-Dolcetta I. Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equation. - Birkhauser, Boston, 1997. - 570 p.

[47] Bardi M., Falcone M.. Soravia P. Numerical methods for pursuit-evasion games via viscosity solutions // Stochastic and Differential Games: Theory and Numerical Methods: Annals Intern. Soc. Dynamic Games, Vol. 4. Birkhauser, Boston, 1999. - pp. 105-175.

[48] Bernhard P. Singular surfaces in differential games: an introduction // Differential Games and Applications. - Springer-Verlag, Berlin, 1977. - pp. 1-33.

[49] Blaquiere A., Gerard F., Leitmann G. Quantitive and Qualitative Games. - Acad. Press., New York, London, 1969. - 172 p.

[50] Breakwell J.V., Merz A.W. Towards a complete solution of the homicidal chauffeur game // Proc. 1st Intern. Conf. Theory and Appl. of Differential Games, Amherst, Mass., 1969. - pp. III-1-III-5.

[51] Cardaliaguet P., Quincampoix M., Saint-Pierre P. Set-valued numerical analysis for optimal control and differential games // Stocahastic and Differential Games: Theory and Numerical Methods: Annals Intern. Soc. Dynamic Games, Vol. 4. Birkhauser, Boston, 1999. - pp. 177-247.

[52] Crandall M. G.. Lions P.L. Viscosity solutions of Hamilton - Jacobi equations // Trans. Amer. Math. Soc., V. 277, №1, 1983. - pp. 1-42.

[53] Dragusin C. On differential linear games with quadratic performance criteria. // Sci. Bull. A. Politehn. Univ. Bucharest, Vol. 56, №3-4, 1994. - pp. 19-26.

[54] Flato E.. Robust and efficient construction of planar Minkowski sums // Master's thesis. School of Computer Science, Tel-Aviv University, 2000.

[55] Fleming W.H. The convergence problem for differential games. // J.Math.Anal, and Appl., №, 1961. - pp.102-116.

Fleming W.H. The convergence problem for differential games, 2. // Adv. in Game Theory. Ann. Math. Studies, №52, 1964. - pp. 195-210.

Guibas L. J., Ramshaw L., Stolfi J.. A kinetic framework for computational geometry // Proc. of the 24th Annual IEEE Symposium on Foundations of Computer Science (FOCS'83). Tucson, Arizona, 1983. - pp. 100-111.

Isaacs R. Games of pursuit, Paper P-257. - RAND Corporation, Santa Monica, California. - 1951.

Isaacs R. Differential Games, I: Introduction. Research Memorandum RM-1391. -RAND Corporation, Santa Monica, California. - 1954.

Isaacs R. Differential Games, II: The Defnition and Formulation. Research Memorandum RM-1399. - RAND Corporation, Santa Monica, California. - 1954.

Isaacs R. Differential Games, III: The Basic Principles of the Solution Process. Research Memorandum RM-1411. - RAND Corporation, Santa Monica, California. -1954.

Isaacs R. Differential games NY: John Wiley, 1965.

Kurzhanski A.B., Valyi I. The problem of control synthesis for uncertain systems: Ellipsoidal techniques. / G.B. Di Masi, A. Gombani, A.B. Kurzhanski Eds. Modeling, Estimation and Control of Systems with Uncertainty, Progress in Systems and Control Theory. 10. Boston: Birkhauser, 1991. - pp.260-283.

Merz A. W. The Homicidal Chauffeur - A Differential Game // PhD Thesis, Stanford University, 1971.

Needham T. Visual Complex Analysis. Oxford University Press, Oxford, UK, 1997.

Patsko V.S., Turova V.L. Level Sets of the Value Function in Differential Games with the Homicidal Chauffeur Dynamics // International Game Theory Review, V. 3, №1, 2001. - pp. 67-112.

[67] Tarns''ev A.M., Uspenskii A.A., Ushakov V. N. On construction of solving procedures in a linear control problem // IMACS. The Lyapunov functions method and applications, 1990. - pp. 111-115.

[68] Wein R.. Exact and efficient construction of planar Minkowski sums using the convolution method // Proc. 14th European Symposium on Algorithms (ESA), LNCS, V. 4186, 2006. - pp. 829-840.

Публикации автора по теме диссертации

[69] Двуреченский П.Е., Иванов Г.Е. Алгоритм построения оптимальной стратегии в нелинейной дифференциальной игре с использованием конволюты // Труды МФТИ - 2011. - Т. 3, №1 - С. 61-67.

[70] Двуреченский П.Е., Иванов Г.Е. Алгоритм построения оптимальной стратегии в нелинейной дифференциальной игре с нефиксированным временем окончания // Труды МФТИ - 2012. - Т. 4, №4 - С. 51-61.

[71] Двуреченский П.Е. Алгоритм поиска оптимальных стратегий для дифференциальной игры с целевым множеством на нефиксированном интервале времени. // Теория и практика системного анализа: Труды II Всероссийской научной конференции молодых ученых с международным участием. - Т.П. /Рыбинск: РГАТУ имени П. А. Соловьева, 2012. - С. 14-24.

[72] Двуреченский П.Е. Алгоритм построения оптимальных стратегий для дифференциальной игры быстродействия с целевым множеством. // Современные проблемы фундаментальных и прикладных наук. Управление и прикладная математика. - Т.1: Труды XLV научной конференции. /Моск. физ. - техн. ин-т. -М. - Долгопрудный, 2012. - С. 19 - 20.

[73] Двуреченский П.Е. Программный комплекс для построения оптимальных стратегий в дифференциальных играх. // Материалы XIX научно-технической конференции молодых ученых и специалистов. 14-18 ноября 2011 г. Часть 2. / Под ред. доктора технических наук В.В. Синявского; Ракетно-космическая корпорация «Энергия» им. С.П.Королева. - XII №3. /г. Королев: Типография РКК «Энергия» им. С.П.Королева, 2012. - С. 38-42.

[74] Двуреченский П.Е. Об одном алгоритме построения оптимальной стратегии в нелинейной дифференциальной игре на плоскости с использованием конволюты. // Системный анализ и информационные технологии: Труды Четвертой международной конференции. - Т.1. /Челябинск: Изд-во Челяб. гос. ун-та, 2011. - С. 179-181.

[75] Двуреченский U.E. О построении оптимальной стратегии в нелинейной дифференциальной игре на плоскости. // Сборник трудов Всероссийской молодежной конференции «Перспективы развития фундаментальных наук», проводимой в рамках Второй международной научной школы для молодежи «Прикладные математика и физика: от фундаментальных исследований к инновациям»: сб. науч. тр. - М.: МФТИ, 2011. - С. 5-6.

[76] Двуреченский U.E. Программный комплекс для построения оптимальных стратегий в дифференциальных играх. / / Современные проблемы фундаментальных и прикладных наук. Часть VII. Управление и прикладная математика. - Т.1: Труды XLIII научной конференции. /Моск. физ. - техн. ин-т. - М. - Долгопрудный, 2010. - С. 17.

Список иллюстраций

1 Пример вычисленной конволюты двух многоугольников.......... 22

2 К примеру 1.3.1..................................................................28

3 К примеру 1.3.2................................. 29

4 Конволюта и значение оператора Минковского, пример 1.6.1........ 57

5 Игровые множества достижимости для нелинейного маятника и фиксированного времени окончания...................... 99

6 Теоретическая и практическая погрешности для нелинейного маятника

и фиксированного времени окончания.....................100

7 Игровые множества достижимости для нелинейного маятника и нефиксированного времени окончания....................101

8 Игровые множества достижимости для модификации игры «нелинейный маятник».....................................102

9 Результаты расчета упрощенной пошаговой конструкции для задачи «шофер-убийца» при у = 0.3, г = 0.3.....................103

10 Результаты расчета упрощенной пошаговой конструкции для задачи «шофер-убийца» при у = 0.3, г = 0.0075................... 104

11 Результаты расчета упрощенной пошаговой конструкции для задачи «шофер-убийца» при у = 0.7, г = 0.3.....................105

12 Результаты расчета упрощенной пошаговой конструкции для задачи «шофер-убийца» с измененной динамикой..................106

13 Результаты расчета упрощенной пошаговой конструкции для задачи «шофер-убийца» с параметрами у = 0.1, г = 0.5...............107

14 Результаты расчета упрощенной пошаговой конструкции для задачи «шофер-убийца» с параметрами г/ = 0.1, г = 1................108

15 Игровые множества достижимости для задачи «шофер-убийца» с параметрами у = 0.1, г = 0.3..........................108

16 Теоретическая и практическая погрешности алгоритма в зависимости от параметра г...................................109

17 Теоретическая и практическая погрешности алгоритма в зависимости от параметра к...................................109

18 Теоретическая и практическая погрешности алгоритма в зависимости от параметра кр = кд...............................109

19 Теоретическая и практическая погрешности алгоритма в зависимости от параметра г...................................110

20 Зависимость времени счета в секундах от полученной практической погрешности...................................110