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

На правах рукописи

АЛГОРИТМЫ ПОСТРОЕНИЯ

ЭПСИЛОН-ОПТИМАЛЬНЫХ СТРАТЕГИЙ

В НЕЛИНЕЙНЫХ ДИФФЕРЕНЦИАЛЬНЫХ ИГРАХ НА ПЛОСКОСТИ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

ДИССЕРТАЦИИ НА СОИСКАНИЕ УЧЕНОЙ СТЕПЕНИ КАНДИДАТА ФИЗИКО-МАТЕМАТИЧЕСКИХ НАУК

2 8 НОЯ 2013

Москва — 2013

005539807

005539807

Работа выполнена на кафедре высшей математики Московского физико-технического института (государственного университета)

Научный руководитель: Доктор физико-математических наук,

профессор

Иванов Григорий Евгеньевич

Официальные оппоненты: Доктор физико-математических наук,

профессор

Бекларян Лёва Андреевич,

Центральный экономико-математический институт РАН, лаборатория 01 - Экспериментальная экономика, главный научный сотрудник.

Кандидат физико-математических наук Камзолкин Дмитрий Владимирович,

Московский государственный университет имени М. В. Ломоносова, кафедра оптимального управления факультета вычислительной математики и кибернетики, ассистент.

Ведущая организация: Институт проблем управления

им. В.А. Трапезникова РАН

Защита состоится № XX 2013 г. в №_часов на

заседании диссертационного совета Д 212.156.05 при Московском физико-техническом институте (государственном университете) по адресу 141700, Московская обл., г. Долгопрудный, Институтский пер., д. 9, ауд. 903 КПМ

С диссертацией можно ознакомиться в библиотеке Московского физико-технического института (государственного университета).

Автореферат разослан _2013 г.

Ученый секретарь / ^

диссертационного совета Фсдько Ольга Сергеевна

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Управление динамическими системами на практике как равило происходит в условиях неопределенности, помех и конфликтов. Математиче-кой теорией, в рамках которой изучаются такие задачи, является теория дифферен-иальных игр. В данной работе рассматриваются антагонистические дифференциаль-ые игры, в которых участвуют два игрока с противоположными интересами. Термин дифференциальная игра» был введен Р. Айзексом, проводившим первые теоретиче-кие исследования в этой области на основе разработанного им метода сингулярных по-ерхностей. Им также впервые рассмотрена дифференциальная игра «шофер-убийца» частично получено ее аналитическое решение.

Классические работы по теории дифференциальных игр в СССР принадлежат .С. Понтрягину, H.H. Красовскому, А.И. Субботину, Б.Н. Пшеничному. JI.C. Понтря-иным предложен метод альтернированного интеграла для решения линейных задач, тот метод использует в своем построении понятия суммы и разности множеств по инковскому. В отличие от этого метода, операторные конструкции, предложенные .Н. Пшеничным, применимы и для нелинейных дифференциальных игр, но требу-т разработки алгоритмов, которые позволили бы приближенно вычислять образы тих операторов. H.H. Красовский и А.И. Субботин исследовали дифференциальные гры в довольно общей постановке. Ими доказана теорема об альтернативе, введе-ю понятие стабильного моста и предложен метод экстремального прицеливания для остроения оптимальных стратегий. Позднее были предложены и получили распро-транение методы, использующие для построения стратегий уравнение Гамильтона-коби-Беллмана-Айзекса.

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

К сожалению, далеко не все типы задач теории дифференциальных игр удается ешить аналитически. Поэтому актуальной становится задача разработки численных етодов поиска оптимальных стратегий в дифференциальных играх. Основные набавления исследований, посвященных численным методам, в целом повторяют на-равления теоретических исследований и основаны на аппроксимационных схемах по-троения используемых теоретических конструкций (уравнения Гамильтона-Якоби-Челлмана-Айзекса, альтернированного интеграла Понтрягина, стабильного моста).

ри этом важно не только приближенно построить мост или альтернированный интеграл, но и вычислить оптимальные стратегии.

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

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

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

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

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

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

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

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

Теоретическая и практическая ценность. В диссертации предложен новый одход к построению и исследованию алгоритмов поиска эпсилон-оптимальных стра-егий в нелинейных дифференциальных играх с целевым множеством, основанный а использовании операторов Минковского. Изучены топологические, геометрические 1 экстремальные свойства операторов Минковского, обобщающих понятия суммы и тзности множеств по Минковскому. Разработаны конструктивные алгоритмы приближенного вычисления значений операторов Минковского, использующие методы омпыотерной геометрии. Полученные явные оценки погрешностей алгоритмов позво-яют по заданной точности определять значения параметров дискретизации, которые тужно использовать для получения стратегий, обеспечивающих эту точность. Теоретические оценки и результаты численных экспериментов показали, что предложенный лгоритм является более эффективным, чем известные аналоги. Эффективность ал-оритма на практике подтверждена численными экспериментами.

Апробация работы. Результаты, изложенные в диссертации, в разное время до-ладывались и обсуждались на

• Четвертой международной конференции «Системный анализ и информационные технологии» САИТ-2011, пос. Новоабзаково, 2011;

• Четвертой традиционной молодежной школе «Управление, информация, оптимизация», Звенигород, 2012;

• 55-й научной конференции МФТИ - Всероссийской научной конференции «Современные проблемы фундаментальных и прикладных, естественных и технических наук в современном информационном обществе», Москва - Долгопрудный, 2012;

• Научных семинарах кафедры высшей математики МФТИ, Москва - Долгопрудный, 2010 - 2013;

• Научном семинаре «Теория автоматического управления» лаборатории 7 ИПУ РАН, Москва, 2013;

• Научном семинаре «Оптимальное управление: математическая теория и прикладные задачи» кафедры оптимального управления факультета вычислительной математики и кибернетики МГУ, Москва, 2013;

• VI Международной конференции «Динамические системы: устойчивость, упра ление, оптимизация», посвященной 95-летию со дня рождения Е.А. Барбашин Минск, 2013.

Также на основе материалов диссертации автором был прочитан факультативный ку «Нелинейные дифференциальные игры на плоскости» для студентов МФТИ.

Публикации. По теме диссертации опубликовано 8 работ, в том числе две [1, - в изданиях из списка, рекомендованного ВАК РФ. Основные результаты диссерт ции отражают личный вклад соискателя в опубликованные по теме диссертащ работы с соавторами.

Структура и объем работы. Диссертация состоит из введения, четырех гла заключения, списка литературы и списка иллюстраций. Общий объем диссертац составляет 122 страницы. Список литературы содержит 76 наименований. Список и люстрации содержит 20 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

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

В первом параграфе первой главы вводится следующее определение опер торов Минковского. Пусть Е - линейное пространство. Операторами Минковско многозначного отображения G : Е —> 2е называются операторы Ад : 2Е —» 2е Bg : 2е —> 2е, заданные формулами

AgS = U (х + G(x)), BgS = E\ (Ag(E \S)) (1

xes

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

Суммой и разностью Минковского множеств X С Е и У С Е называю ся соответственно множества X + Y = {х + у \ х £ X, у £ У} , X — Y {х £ Е | x + Y С X).

Оставшаяся часть параграфа посвящена изучению свойств этих операторов в сл чае Е = R". Через int S, S и dS обозначены соответственно внутренность, замыкан и граница множества S. Предполагается, что в Мп введена некоторая норма || • ||. Ч рез обозначен замкнутый шар в!"с центром в нуле и радиусом г: ®г = {х R" : ||а:|| < г}. Уклонением множествах С К" от множества У СК" называете величина h+(X,Y) = inf{r > 0 | X С Y + ЯЗГ}- Хауедорфовым расстоянием межд множествами X С 1R" и Y С R" называется h{X, Y) = тах{/г+(Х, У), /г+(У, X)}. Мно гозначное отображение G : R" —> 2К" удовлетворяет условию Липшица с констапто Lq в смысле метрики Хаусдорфа, если h(G(xi), G(Х2)) < — жг|| Vxj, Х2 € М"

Приведем некоторые свойства операторов Минковского.

емма 1. Пусть многозначное отображение G : К™ —> 2К" принимает замкнутые пачения и удовлетворяет условию Липшица с константой Lg < 1 е смысле метри-и Хаусдорфа. Пусть задано множество S С Rn и точки хо € int S, уо G Xq + G(xo). огда для множества AqS, определенного первым соотношением (1), справедливо ключение уо £ int AgS.

'емма 2. Пусть многозначное отображение G : R" —> 2К" принимает замкнутые пачения и непрерывно в смысле метрики Хаусдорфа. Пусть множество S С R" замкнуто и supie5supueG^j ||u|| < +оо. Тогда множество AqS замкнуто.

.емма 3. Пусть многозначное отображение G : R™ —> 2К" принимает замкнутые значения и удовлетворяет условию Липшица с константой Lg < 1 е смысле метри-и Хаусдорфа. Тогда для любого мпоэюества ScK" и любого числа 5 > 0 операторы Iинковского (1) удовлетворяют включениям

Ag (S + tBi/(1+La)) с + <3icAG(S + Bi/(1 _Lc}) ,

AG (S ± Ъ5/(!_£С)) С AGS ± Ъ5, BC,S + с BG (S + Ъб/ц-Ьс)) , BG (S ± »5/(1 -La)) с BGS i В, С Вс (S — В,/(1+Ьо)) .

Во втором параграфе первой главы вводятся необходимые для работы с плос-ими многоугольниками определения, состоящие в следующем. Пусть задан набор очек cik € К2, к = 1,тп, причем а^г ф ак Для любого к € l,m — 1. Упорядоченный ;абор отрезков {[ai, 02], [аг, аз],..., [am_i, ат]} называется ломаной Г(й1, ..., ат), точи ajt называются вершинами, а отрезки [а^, - звеньями этой ломаной. Ломаная (ai,..., am) называется замкнутой, если ат = Ломаная T(ai,..., ат) называется ростой замкнутой, если т > 1, ат = ai и из того, что г £ [aj,aJ+i] П [а^, < j < к < т следует, что к = j + 1 и z = Ofc. Простым многоугольником называ-тся ограниченное замкнутое множество 5cR2 такое, что его границей dS является ростая замкнутая ломаная. Вершинами простого многоугольника S называются вер-ины ломаной 8S. Запись d+S и d~S обозначает границу простого многоугольника S, риентированную соответственно против часовой стрелки и по часовой стрелке. Выпуклым лтогоугольником называется выпуклая оболочка конечного числа точек bR2.

ерез (а, Ь) обозначено скалярное произведение векторов а е К" и b € R™. Нормальным конусом выпуклого множества X С R" в точке xq £ X называется множество = {р 6 I" | (р,х) < {р,х0) Ух G X}. Для любого ненулевого вектора е R2 через (0,z ■ оо) обозначен луч {tz \ t G (0,+оо)}. Для любых двух ненулевых екторов а € R2 и b 6 R2 через Z(a, b) обозначено множество всех ненулевых векто-ов, лежащих на лучах, полученных путем вращения луча (0, а - оо) против часовой трелки до луча (0,6 • оо). Правым перпендикуляром для вектора а = (ах,ау)Т G R2 называется вектор а1 = (ау, —ах)т.

В третьем параграфе первой главы вводится понятие конволюты многоугольника и многозначного отображения на плоскости, состоящее в следующем. Пусть многозначное отображение G каждому вектору х е R2 ставит в соответствие выпуклый

многоугольник Пусть Го = Г(а;1,..., - замкнутая ломаная. Для л

бого j £ 1 , п обозначим р^ — \ — хположим ро — рп. Для каждого j € 1, рассмотрим д\, ■ ■ ■ ,д]т. ~ пронумерованные против часовой стрелки все вершины мн гоуголышка С"(:г;) такие, что

т е (2

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

ко, то будем выбирать вершину д{ как любую, удовлетворяющую еще и услови < (х^ — Xj—l^ д) для всех вершин д многоугольника С(х^), удовлетворя1 щих условию £ №(д, Сг(ху)). Пусть при этом д последняя против часовой стрелк вершина многоугольника С(х^), не совпадающая с Если р^ € М(д, .,•)), то буде полагать д3т. = д, иначе будем полагать д^ = д{.

Коиволютой для многозначного отображения (3 и замкнутой ломаной Го назыв ется замкнутая ломаная

Сс(Г0) = Г(хг + д\,... ,хг+ д1П1,х2 + д^, ■ ■ ■ ,х2+ д1г2, ■ ■. ,хп + д",... ,хп + д^п,хх+ д\

(3

Будем рассматривать тагг-норму вектора х 6 К": ||ж||оо = тах^-р^ где хк к-ая компонента вектора х.

При получении оценок расстояния между границей образов операторов Минко ского (1) и коиволютой, а также между образами операторов Минковского и извл чепными из конволюты их аппроксимациями считаются выполненными следующ предположения:

А1: 5 простой (вообще говоря невыпуклый) многоугольник, длины (относительн таж-нормы) сторон которого не превосходят числа /г;

А2: значением многозначного отображения (3 является отрезок, т.е. (3(х)

АЗ: функции д\,д2 '■ К2 у ®2 удовлетворяют условию Липшица (относительн тах-нормы) с константой Ьс <

А4: выполнены неравенства ИшС2-) — <72(3^) ||оо £ <

тах-{(д?)||оо) НйМЦоо} < Са < +оо Ух е М2.

Параметры /г, Ьд, ¿с и Сд считаются малыми и определяют точность работ алгоритмов. Методы обоснования предложенных алгоритмов применимы и к боле общему случаю, когда значением многозначного отображения <3 является выпуклы многоугольник, вершины которого удовлетворяют условию Липшица как функции о точки х.. Однако в силу значительной технической сложности доказательств данна работа ограничивается наиболее важным частным случаем, когда множество С(х является отрезком.

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

_емма 4. Пусть в пространстве R2 введена некоторая норма || ■ ||. Пусть мно-означное отображение G : К2 —> 2r2 принимает выпуклые компактные значения удовлетворяет условию Липшица с константой Lq относительно нормы || • || в мысле метрики Хаусдорфа. Пусть длины звеньев (в смысле нормы || • Ц,) замкну-пой ломаной Г С К2 не превосходят числа h. Тогда относительно нормы || ■ || для онволюты (3) и первого из операторов Минковского (1) справедливо неравенство

!г+(Сс(Г),АсГ) <LGh.

Пусть границей множества S СК2 является простая замкнутая ломаная Г. Будем оворить, что ломаная Г ориентирована положительно относительно множества S \ писать Г = d+S, если при обходе ломаной Г в направлении ее ориентации множество остается слева.

'еорема 1. Пусть границей множества S С М2 является простая замкнутая ло-анаяд^Б, ориентированная положительно относительно множестваБ, длины (в смысле тах-нормы) звеньев ломаной d+S не превосходят числа h. Пусть выполнены предположения А2-А4. Тогда (в смысле тах-нормы)

h+{OAGS, CG(d+S)) < (16dG + 7h)La.

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

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

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

Для любой замкнутой ломаной 7 С К2 ее дополнение М2 \ 7 состоит из конечного числа непересекающихся областей, одна из которых неограничена. Дополнение к этой неограниченной области называется доменом 7 и обозначается Domain 7. Граница домена замкнутой ломаной 7 называется внешним контуром 7 и обозначается ExtC7: ExtC7 = 9(Domain7).

Пусть заданы замкнутая ломаная 7 С R2 и точка G (Domain 7) \ 7. Замыкание множества всех точек х £ К2, которые можно соединить с точкой хо ломаной, не пересекающейся с 7, называется внутренним (относительно точки Xq) доменом 7 и обозначается IntDom^ 7. Граница внутреннего домена замкнутой ломаной 7 называется внутренним контуром 7 и обозначается IntCl07: IntCXo7 = <9(IntDoml0 7).

Многоугольники AgS и BGS, аппроксимирующие множества AGS, BGS, определяются следующим образом:

AgS = Domain (CG{d+S)), BGS = IntDomX0(CG(5_5)).

Приведенные в этом параграфе алгоритмы вычисления внешнего и внутреннего относительно T04j<H хо контуров замкнутой ломаной позволяют вычислить границы многоугольников AqS и BgS. В качестве Хд берется любая точка, удовлетворяющая включению х0е (S ± ^(iGdc+sh^c+Cc) nDomain(CG(d"S)).

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

Теорема 2. Пусть в пространстве М2 введена тах-норма. Пусть выполнены предп ложения А1-А4. Пусть ¿1 = Ь^Н, ¿2 = {16йс + 1Н)Ьс- Под 23г будем понимат замкнутый шар радиуса г в тах-норме. Пусть множества

£с5±а341, Вс3±<352, М2\(Ас5 + 03г1), М2 \ (АСБ + В*)

связны. Тогда справедливы включения

Лс5 С Аа3 + ®&, с + ®г,, А с ± с

Лемма 5. Пусть выполнены условия теоремы 2. Пусть множества АсБ, ВсБ опр делены следующим образом:

Лс5 = АсБ + ОЗг2, =

Тогда при £ = справе()ливы включения

Лс5 С АсЭ сЛс(5 + ®е), ®£) С С

Седьмой параграф первой главы посвящен модифицированным оператора Минковекого Ас ■ 2В —> 2е, Вс ■ 2Е —»• 2я, определяемым равенствами

Я \ = АС(Е \ 5) (

для любого множества Б с Е. При этом ВдБ = {х Е | х — С(ж) С 5} \/Б С Е.

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

Теорема 3. Пусть выполнены условия леммы 5. Тогда справедливы включения

Ас (Б ^ <В£_) С АСБ С Ас (Б + , Вс (Б ^ <В£+) с ВСБ С Вс (5 + Ве_)

где

ЬсСс Т „ 5\ + 5г _ _ , (№ + 8/1)Ьс

= Т^' = ЬсСс + Т^ = ЬсСс + —1-ьс •

Таким образом, для любого простого многоугольника 5 описанные в первой гла ве алгоритмы вычисляют множества АсБ, ВсБ, которые являются аппроксимациям значений модифицированных операторов Минковекого. Эти алгоритмы использован

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

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

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

x{t) = a{t,x(t),u{t)) + b(t,x{t),v(t)), fe x(í)eE",

u(t) eP CP, v(t) eQcR® Vf G [0,1?]

редполагается, что функции а : [0,1?] х Г х РГ и 6 : [0, т9] х Ж" х Q ->■ Rn 1епрерывны, а также, что вектограммы a(t,x,P) = {a(t,x,u) : и G Р}, b(t,x,Q) = b(t,x,v) : v G Q} выпуклы при всех f € [0, tf], x G Rn. Также предполагается задан-1ым целевое компактное множество M С Мп.

Если выполняется x(i9) G M, то в игре имеет место поимка. Если выполняется (â) ф M, то в игре имеет место уклонение. Цель первого игрока состоит в поимке, дель второго игрока - в уклонении.

Пусть в К" задана некоторая норма || ■ ||. Расстоянием от точки x G M" до ножества У С К" называется величина g(x,Y) = infygy ||ж — у||. Неравенство (х(г9),М) < е означает, что в конечный момент времени имеет место е-поимка.

Предполагается, что функции а: [0, i9] x R" x Р -> R" и Ь : [0, Щ х К" x Q Мп довлетворяют следующим условиям Липшица:

\\a(ti,xï,ul)-a(t2,x2,u2)\\ < L'Jfj - t2\ + L*\\xi - x2\\ + Ьиа\\щ - u2\\

Vfbf2 G [0,7?], ib^eK", иъи2еР;

(5)

||b(ib II,«!) - b{t2,X2, U2)|| < L\|Í! - f2| + L%lin - x2|| + Ll\\Vl - v2\\

Vfi,í2 e [0, xi, x2 G K.", vuv2 gQ;

(6)

||a(f, x, и) Il < Ca Vf € [0,0], геГ, и € P; (7)

||6(f, x, u)|| < Сь Vé e [o,i?], ieP, veQ. (8)

Обозначим

C = Ca + Cb, L = Lxa + Ll (9)

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

Пусть задан отрезок [fo,fi] С [0,79]. Множеством £Y[fo,fi] допустимых реализаций управления первого игрока называется множество всех измеримых функций и : [í0líl] —> Р. Аналогично задастся множество V[fo,fi] допустимых реализаций управления второго игрока.

Пусть заданы число ¿o £ [0, и начальное состояние x(to) = Хо- Пусть Т = {r¿}[= - разбиение отрезка [ío>i?] • ^о = то < Ti < ■■• < tj = "д. Кусочно-постоянно стратегией первого игрока, соответствующей разбиению Т, называется набор фун ций uf = {uf : R™ —> P}¿=q. Движением, соответствующим начальному состояни x(tо) = Хо, разбиению Т, стратегии первого игрока и допустимой реализаци управления v G V[fo,$], называется функция х : [fo, $] —> К", определяемая из пош гового уравнения

x(t) = a{t,x(t),us¿T(x(Ti))) + b(t,x(t),v(t)),

которое должно выполняться при почти всех t G [r¿, r¿+j] и всех i G О, I — 1. При это начальная позиция для отрезка [то, tí] равна Хо, а начальная позиция x(t¿) для отрезк [t¿,t¿+i] совпадает с конечной позицией x(r¿) отрезка [t¿_i,t¿].

Обозначим движение следующим образом: x™ot(t,to,xo,T,Uj;T,v). Аналоги1 по определяются кусочно-постоянная стратегия второго игрока u|ír и движени x™\t,t0,xQ,T,u,vf).

Кусочно-постоянная стратегия гарантирует, е-поимку для начального сост яния хо, если для любой реализации управления v G V[0,i9] выполняется неравег ство £) (х™о1(г9,0,хо,Г,u^,v),M) < е. Кусочно-постоянная стратегия гарант рует уклонение для начального состояния хо, если для любой реализации управл ния и G Ы\0,-¡5] выполняется соотношение x™ot($, 0, Хо, Т, и, М. Пара кусочн

постоянных стратегий (iiyr,i>yr) называется е-оптимальной, если для любого начал ного состояния хо G Кп выполняется хотя бы одно из условий:

1) стратегия и^Т гарантирует е-поимку или

2) стратегия ufí1 гарантирует уклонение.

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

Пусть зафиксировано натуральное число I и произведено равномерное разбиени Т = {t¿}[=0 отрезка [0,1?], где r¿ = ir, i G 0,1. Шаг т = i9/I разбиения Т называете параметром дискретизации по времени.

Для любого множества 5с1"и любого индекса г G 0,1 — 1 определяются мно жества

Afí = {x е W: 3uG Р: x + ra(r¿, х, и) G S}, BiS={x 6Г: Vu G Q : х + тЬ(тих,у) G 5}.

Таким образом, определены одношаговые операторы достиэ/симости Ai, Bi.

Для любого г G 0,1 рассматриваются выпуклозначные многозначные отображени G", G¡, заданные формулами

G1{x) = -та(тих,Р), Gbi(x) = -тЪ{тих,Ц) Vi € бJ Vx G К2. Из определений модифицированных операторов Минковского (4) следуют равенств

Ai = ÁGa, Bi = BGb Vz G Ü7-

Из соотношений (5) - (8) следует, что Ьа? = тЬ^, Со» = тСа, = 2тСа, Ь^« = тЬга, Ьсь = тЬхь, Ссь = тСь, сгсь = 2тСь, Щ = тЬ[.

Пусть Е - класс множеств в Ип, с которым работают алгоритмы. Все используемые для построения стратегий множества аппроксимируются множествами из этого класса.

В данном параграфе часть алгоритмов, являющихся внутренними по отношению к алгоритму поиска оптимальных стратегий, не конкретизируются, а лишь предполагается, что они существуют и имеются оценки их погрешностей. Так, предполагается, что реально для каждого множества 5 Е £ и индекса г 6 0, / вычисляются множества ¿¿5 класса Е, удовлетворяющие условиям

В£-) сЛ;5с Д(5 + ®£+), С АЯ С -Ь <В£-), (10)

где числа е^. £д определяют погрешности этих алгоритмов.

Также предполагается существование алгоритма, который для любых множества 5 С Е, индекса г Е 0, / — 1 и вектора х Е позволяет определить вектор щ = щ{х,В) € Р такой, что

х + та(т,, х, щ) Е 5 + ®£и, (11)

и алгоритма, который для любых множества 5 С £, индекса г е 0, / — 1 и вектора х € Мп\ (-Вг>5) позволяет определить вектор г^ = {¡¿(х, в) Е С} такой, что

Х + Г6(Ч,1,Й;)6(Г\5) + <8е„. (12)

Здесь числа еи и £„ определяют погрешности соответствующих алгоритмов.

Зафиксируем некоторые векторы и, Е Р, V* € (5 и положим щ(х, 5) = и« при х {¡¿(х, 5) = и» при х Е •Вгй'. Тем самым при всех г 6 0,1 — 1 определены

функции

й, : Кп х Е Р, ^ : К" х Е <5. (13)

Обозначим

= г2 + ¿с + ь?с„) , д? = г2 + ьс + ед) ,

Ди = Д° + £-в + (1 + тЬ1)еи, Д„ = Д£ + е~а + (1 + т1£)е„.

Предполагается, что имеются алгоритмы, которые для любого множества 5 Е Е вычисляют множества Д¡Э Е Е, С Е такие, что

5 ^ <вйи+ео с £>„5 с 5 ^ <ВДи, 5 + <ВД„ с с 5 + ®д„+£о, (14)

где число ££) определяет погрешность этих алгоритмов.

Пусть зафиксировано положительное число е. Начальные множества М" Е Е, М] € Е попятной конструкции определяются следующим образом:

М + ®£_г„ с Щ С М + <В£, М с Щ С М + ®£д,. (15)

Здесь число ем € (0, е) определяет погрешность начальной аппроксимации.

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

{мпи, {МУ}£о1:

М1 = д-д , м^ = в^вЖм

Для любых г £ 0, / — 1 их £ Мп, с использованием функций (13) и игровы множеств достижимости М", М", определяются стратегии игроков

щ{х) = щ(х, ВгОиМ?+1), (16

ц(х)=ъ(х,АО„М?+1). (17)

Перечислим основные результаты третьего параграфа второй главы.

Теорема 4. Пусть х$ € Мд, стратегия и= {«г}(=о определена соотношение.

(16). Тогда стратегия гарантирует е-поимку на отрезке [0, ■г?] для начальног состояния х(0) = хо-

Теорема 5. Пусть Хо Е Кп\Мд, стратегия = {«¿}£Го определена соотношение.

(17). Тогда стратегия гарантирует уклонение на отрезке [0,?9] для начальног состояния х(0) = Хо.

Определим числа

4 4

До = Д„ + Д„ + 2еП + + £2 + -£+ +£-в + г2Ь1ь,

£0 = тСь + 2ем + Аи + £о + (тСь + А01)ем. Теорема 6. Пусть е > £о, тЩ < Тогда

М0" с Щ. (18)

Теорема 7. Пусть е > ед/ и справедливо включение (18). Тогда пара кусочно-постоянных стратегий является е-оптимальной.

Четвертый параграф второй главы посвящен доказательству теорем 4-7. Наконец, в пятом параграфе второй главы для игр на плоскости конкретизируются алгоритмы, существование которых предполагалось в третьем параграфе. Предполагается, что каждая из вектограмм а(£, х, Р) = х, и) | и € Р} и х, (5) = {&(£, х, у) | V £ <5} либо является отрезком, либо не зависит отх. В этом параграфе используется тах-норма. Алгоритмы строятся следующим образом. Зафиксируем натуральное число I > 10$ таЩ} и рассмотрим равномерное разбиение Т = о отрезка [0,?9], где г,- = гт, г е 0,1, т = чЭ/1. Зафиксируем число /г > 0. Игровые множества достижимости будем аппроксимировать простыми многоугольниками, длины сторон которых не превосходят числа/г. Пусть Р и <5 - сетки на множествах Р и <3 с мелкостями Нр и /гд соответственно, т.е. множества Р С Р и <3 С (3

состоят из конечного числа элементов Р = {гР}^, Q = {û-7'}^ и hp = h+(P,P),

Iiq = h+(Q,Q), где h+ - уклонение множеств.

Зафиксируем произвольное число £ > 0. Приблизим множества М + !В£иМ соответственно простыми многоугольниками Mf и MJ с точностью ем G (0, е) так, чтобы выполнялись включения (15).

В качестве операторов приближенного вычисления образов одношаговых операторов достижимости будем использовать операторы Aq?, Всь введенные в лемме 5. Таким образом, в соотношениях (10) можно положить Л; = А&>, Bi = BGt> \/i S 0,7.

Выбор вектора ûi(x,S) G P, для которого справедливо включение (11) производится следующим образом. Пусть задан помер i G 0, / — 1 и точка х G Вычислим с помощью алгоритма второго параграфа первой главы множество S + 23f++T£u/jp — я и перебором по j G 1 ,Jp найдем такой вектор й>, что выполняется включение та(т{, х, iP) G S + — х. Вектор гР и будет искомым. Аналогичный алгоритм

позволяет пайти вектор щ(х, S) G Q, для которого справедливо включение (12).

Использование шах-нормы позволяет использовать алгоритм поиска суммы Мин-ковского двух многоугольников из второго параграфа первой главы для вычисления без погрешности суммы и разности Минковского многоугольника S и шара в этой норме. Это означает, что в соотношениях (14) можно положитьед = 0, DUS = S — 93ди, DVS = S + 93 д„.

Используя теорему 3, получаем следующую оценку сверху для числа ео: £0 < 2ем + т2 + 3LC + 40Lxac}j + ШЬхак + 2rLuahP+

+ г [С4(1 + VéL) + (3(4 + L\) + 3LC + 94(LxaCa + ЦСа))] + + 2MedbLh + 2 де^1{Ьиа1гР + LvbhQ). (19)

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

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

x(t) = a(x(t), u(t)) + b(x(t), v{t)),

где t G [0,i?] - время, число d определяет максимальную продолжительность игры. Остальные предположения совпадают с предположениями второй главы. Если существует момент времени t G [io, ¿i] такой, что x(t) G M, то на отрезке [¿о, h] имеет место поимка. Иначе, то есть если ж(£) ^ M при всех t G [iojii]> то на отрезке [fo,ii] имеет место уклонение. Цель первого игрока состоит в минимизации числа^о G [0, такого, что на отрезке [0,i?o] обеспечена поимка. Цель второго игрока - обеспечить уклонение на отрезке [0,1?] или, если это невозможно, максимизировать время г?о S [0,

такое, что на отрезке [0, $о] обеспечено уклонение. Будем говорить, что на отрезк [£о, £1] С [0,1?] имеет место Е-поимка, если существует такой момент времени £ е [¿о, £1] что М) < е.

Во втором параграфе третьей главы описано в каком классе стратегий ищут ся оптимальные стратегии и какие реализации действий противника предполагаю ся возможными. Допустимыми реализациями управлений игроков считаются те ж< что и во второй главе. Позиционной стратегией первого игрока называется произ вольная функция иви : К" —» Р. Пусть Т = {тг}[=0 - разбиение отрезка [£о,£1] [О, : £о = то < т\ < ■ ■ ■ < 77 = £1. Пара (и^т,Т) называется законом управлени первого игрока на отрезке [£о,£1]- Движением, соответствующим начальному состо янию ^(¿о) = зго, закону управления (и^т, Т) и допустимой реализации управлени V £ ^ 1]5 называется абсолютно непрерывная функция х : [¿0,^1] ► К", определяе мая из пошагового уравнения ±(£) = а{х{Ь), иБЬг(х(т{))) + «(£)), которое должн

выполняться при почти всех £ £ [т;,тг+1] и всех г £ 0,7 — 1. При этом начальная по зиция для отрезка [70,71] равна хо, а начальная позиция х{т{) для отрезка [т*,т,-+1 совпадает с конечной позицией а;(т¿) отрезка [тг_1,Гг]. Обозначим движение следую щим образом: £о, хо, Т, у) = х(£) \/£ £ [¿о, ¿1]- Аналогично определяютс

позиционная стратегия второго игрока г;Б1г и движение £о, Хо, Т, и, у^1).

Закон управления (и8'г, Т) гарантирует е-поимку на отрезке [£о, £1] для начальног состояния Хо, если для любой реализации управления г; £ У[£о,£;|] существует момен времени £ 6 [£о,£1] такой, что выполняется неравенство д £о, х$,Т, у), М)

е. Закон управления (у^т,Т) гарантирует уклонение на отрезке [¿о> ^ 1] Для началь ного состояния хо, если для любой реализации управления и € £^[£0,^1] выполняете соотношение £™о1(£, £0, х0, Т, и, у^1) <£ М \/£ е [£о, £1]-

Пусть задано число г > 0 и законы управления (и^,Ти), (уА<:,Ту) первого второго игроков на отрезке [0,?9]. Пара законов ((и5*1, Ти), (и5и, Ту)) называется е оптимальной, если для любого начального положения хо £ К™ такого, что д(хо, М) е выполняется альтернатива:

1) существует момент времени до £ [0, г9] такой, что закон управления (гг541", Ти) га рантирует £>поимку на отрезке [0, а закон управления (г/51г,Т„) гарантирует укло нение на отрезке [0,а?о], либо

2) закон управления , Ту) гарантирует уклонение на отрезке [0,1?].

В третьем параграфе третьей главы введены одношаговые операторы дости жимости для игры с нефиксированным временем, описан алгоритм построения страте гий и сформулированы теоремы о его погрешности без конкретизации способа постро ения образов одношаговых операторов достижимости. Как и ранее рассматривает» равномерное разбиение отрезка [0,$] с шагом т = д/1. Одношаговые операторы до стижимости А я В задаются равенствами

Л5 = {£ е К" : Зи£ Р : х + та(х, и) £ Б}, (20)

В5={хбГ: х + тЬ(х, у) £ 5}, (21)

для любого множества 5 С Кп.

Для игры с нефиксированным временем окончания рассматриваются выпуклознач-ные многозначные отображения С", С?6 с замкнутыми значениями, заданные формулами Са(х) = —та(х,Р), Сь(х) = —тЪ(х,0) Ух £ К2. Из определений модифицированных операторов Минковского(4) следует, что А. — Л, В — .

Справедливы следующие равенства Ьс = тЬ*, Сд* = тСа, с/с» = 2тСа, Ьсь — тЩ, Сдь = тСь, <1сь = 2тСь-

Как и ранее предполагается, что алгоритмы работают с множествами класса Е. Предполагается, что реально для каждого множества 5 € Е вычисляются множества Л5, ВБ класса Е, удовлетворяющие условиям

А(Б * В£-) СЛ5С Л(5 + ®Е+), В(5 ± 03£+) с с + «8е->,

где числа определяют погрешности этих алгоритмов.

Также предполагается существование алгоритма, который для любых множества 5 С Е и вектора х £ Лб1 позволяет определить вектор й = ¿(ж, Б) £ Р такой, что ж + та(х, й) £ 5 + 23е„, и алгоритма, который для любых множества й С Е и вектора х £ К" \ (ВБ) позволяет определить вектор v = у(х, 5) е (5 такой, что ж + тЬ(х, Ъ) £ (К™ \ 5) + Я3£<). Здесь числа еи и еу определяют погрешности соответствующих алгоритмов.

Если зафиксировать некоторые векторы и* £ Р, г>* £ <5 и положить ) = и»

при х ^ Л5, 5(х, 5) = г», при х 6 ¿?,5, то будут определены функции

й : К" х Е Р, Ъ : Ж" х Е -><5. (22)

Аналогично второй главе определяются числа Аи, Д„ и предполагается,

что имеются алгоритмы, которые для любого множества 5 6 Е вычисляют множества Д^ £ Е, Иув £ Е такие, что справедливы включения (14). Также предполагается монотонность по включению операторов Ии и

Пусть зафиксировано положительное число £ и начальные множества Мд ё Е, Мд € Е попятной конструкции задаются включениями

м + <в£_Ел, С М0" С м + в£) м + озтС см;с! + <вгС+£м■

Здесь число £м £ (0,е) определяет погрешность начальной аппроксимации. Двигаясь в сторону увеличения индекса г и используя алгоритмы, существование которых мы предположили, вычисляются наборы игровых множеств достижимости {М"}/=0,

{мпи

м;1+1 = (.АВВиМи = (ВАО„М?) и М?, г £ О, I - 1.

С использованием функций (22) и игровых множеств достижимости, следующим образом определяются позиционные стратегии управления. Для любого векторах £ Ж" \ М0" положим г(х) = тах{г е 0,7-1 : х £ Мги}, а для любого х £ Мп \ обозначим j(x) = тах{^' е О, I — 1 : х £ Теперь для любого х £ К" определим

Гм», х 6 Мд ,

ийг(х) = ^ /' . ч 0' (23)

4 ' I „~. / ~ о п л /Г" I „/- та>п \ л/ги ^ /

¿(г, ВБиМ^ , х € К" \ Мц,

К, хемг,

У^т(х) = < / ~ \ (24

^ \у(х, АПьМ]{х)) , х£Г\ Щ. К

Основными результатами этого параграфа являются следующие теоремы.

Теорема 8. Пусть г € О, I, х^ е М", стратегия определена соотношением (23) Тогда закон управления (и8'г, Т) гарантирует е-поимку на отрезке [0, т;] для началь ного состояния х(0) = Хо-

Теорема 9. Пусть г € 0, / — 1, Хо £ М", стратегия определена соотношение (24). Тогда закон управления гарантирует уклонение на отрезке [0,т;+1] дл

начального состояния х(0) = Хр-

Определим числа

4

До = Аи + Ау + 2ел +е~а+еа + + е'в,

го = т(С + Сь) + 2ем + Аи + ев + (тСь + Д0(/ -

Теорема 10. Пусть е > ео, число т выбрано так, что < Тогда

М^СМ? Уг € 0, / — 1. (25

Теорема 11. Пусть стратегии определены соотношениями (23), (24)

Пусть число е > тС + 2ем выбрано так, что выполняется условие (25). Тогда пар законов управления {(у?1т, Ти), (и84г,Ти)) является £-оптимальной.

Четвертый параграф третьей главы посвящен доказательству теорем 8-11.

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

£0 < 2ем + т2 (3ТС + 40ЦСа) + 10тЬхак + 2тЬиаНР+

+ т[С + Сь{ 1 + + 0е«ь (ЗТС + 94(ЬхаСа + ЬхьСа))] +

+ 23 де^ЬН + 2де*\ЬиаНР + ЦИЯ). (26)

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

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

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

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

' Заключительный, третий параграф четвертой главы посвящен игре «шофер-убийца» и ее модификациям. В классическом варианте этой игры динамика управляемой системы в редуцированном двумерном пространстве описывается нели-ейной системой дифференциальных уравнений

Г x{t) = -y{t)u(t) + vx{t), , „

\y(t) = x(t)u(t)-l+vv{t),

Тервый игрок выбирает управление u(t), второй — управление v(t) = (vx(t),vy(t)) € l2. Управления игроков подчинены ограничениям

| К«)1<1, \jMtY + М*)2 <" V* е [О5«9],

где V - скалярный параметр.

На рис. 1 изображены результаты расчетов с использованием упрощенной пошаговой конструкции

М?+1 = (А&. ВсьМ") и М", г £ 0,1 - 1.

Рис. 1: Результаты расчета упрощенной пошаговой конструкции при и = 0.1. Целевое множество - круг радиуса 1 с центром в точке (2, 0). Вычисления проведены до момента времени г9 = 4.7, изображено каждое 100-ое сечение.

Эти и другие приведенные в этом параграфе результаты свидетельствуют о той что для приближенного расчета игровых множеств достижимости можно использс) вать упрощенную пошаговую конструкцию. Помимо этого, в третьем параграфе при ведены результаты расчета игровых множеств достижимости и графики зависимост; теоретической и практической погрешности от различных параметров дискретизации Обе зависимости оказываются близки к линейным. Так, на рис. 2 показаны граф!-ки практической погрешности алгоритма и его теоретической погрешности, умножен ной на коэффициент 0.23, в зависимости от параметра т при условии, что к = 5т| 1гр = И с] = 2.5 т.

Рис. 2: Теоретическая и практическая погрешности алгоритма в зависимости от пара метра т при линейной зависимости остальных параметров дискретизации от т.

В заключении приводятся основные результаты диссертации и проводится срав нение предложенных алгоритмов с известными аналогами. В работах1,2 предложень; алгоритмы построения ^-оптимальных стратегий для нелинейных дифференциальны^ игр и получены оценки погрешностей этих алгоритмов. В отличие от указанных ра бот, в которых оценки погрешностей (19), (26) предлагаемых алгоритмов имеют ви] С\Т + сгЛ,/т + С36, где с\, С2, сз - константы зависящие только от задачи, г - параметр дискретизации по времени, /г - параметр дискретизации по пространству фазовой пе ременной, 5 - параметр дискретизации по пространствам управлений, предложенны( в данной работе алгоритм имеет оценку погрешности видас^т-ЬсгЛ+сз^, что позволяем для получения лучшей точности уменьшать параметр Н со скоростью, пропорциональной т, а не г2.

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

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

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

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

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

т.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

*Patsko V.S., Turova V.I,. 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.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

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

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

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

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

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

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

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

8. Двуреченский П.Е. Программный комплекс для построения оптимальных стра тегий в дифференциальных играх. // Современные проблемы фундаментальны и прикладных наук. Часть VII. Управление и прикладная математика. - Т.1

Труды ХЫП научной конференции. /Моск. физ. - техн. ин-т. - М. - Долгопрудный, 2010. - С. 17.

уо

Двуреченский Павел Евгеньевич

АЛГОРИТМЫ ПОСТРОЕНИЯ ЭПСИЛОН-ОПТИМАЛЬНЫХ СТРАТЕГИЙ В НЕЛИНЕЙНЫХ ДИФФЕРЕНЦИАЛЬНЫХ ИГРАХ НА ПЛОСКОСТИ

АВТОРЕФЕРАТ

Подписано в печать 10.10.2013. Формат 60 х 84 1/16 . Усл. печ. л. 1,0.

Тираж 100 экз. Заказ №318 Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Московский физико-технический институт (государственный университет)» Отдел оперативной полиграфии «Физтех-полиграф» 141700, Московская обл., г. Долгопрудный, Институтский пер., 9

МОСКОВСКИЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ (ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ) _КАФЕДРА ВЫСШЕЙ МАТЕМАТИКИ_

На правах рукописи УДК 517.977.8

04201450115

ДВУРЕЧЕНСКИЙ ПАВЕЛ ЕВГЕНЬЕВИЧ

АЛГОРИТМЫ ПОСТРОЕНИЯ ЭПСИЛОН-ОПТИМАЛЬНЫХ СТРАТЕГИЙ В НЕЛИНЕЙНЫХ ДИФФЕРЕНЦИАЛЬНЫХ ИГРАХ НА ПЛОСКОСТИ

01.01.09. — Дискретная математика и математическая кибернетика

ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук

Научный руководитель:

доктор физико-математических наук, профессор

Иванов Григорий Евгеньевич

Москва - 2013

Оглавление

Введение 4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение 111

Литература 113

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

Введение

В современной математике задачи оптимального управления динамическими системами в условиях неопределенности, помех и конфликтов изучаются в рамках теории дифференциальных игр. В данной работе рассматриваются антагонистические дифференциальные игры (игры с нулевой суммой), в которых участвуют два игрока с противоположными интересами. Исследования по теории антагонистических дифференциальных игр насчитывают более чем полувековую историю. Термин «дифференциальная игра» был введен Р. Айзексом. Его первые работы [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. Показано, что полученные в численных экспериментах реальные погрешности предложенных алгоритмов имеют близкий к линейному характер зависимости от параметров дискретизации, что соответствует теоретическим результатам работы.

Автор выражает глубокую благодарность своему научному руководителю доктору фи