close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
На правах рукописи
ДВУРЕЧЕНСКИЙ ПАВЕЛ ЕВГЕНЬЕВИЧ
АЛГОРИТМЫ ПОСТРОЕНИЯ
ЭПСИЛОН-ОПТИМАЛЬНЫХ СТРАТЕГИЙ
В НЕЛИНЕЙНЫХ ДИФФЕРЕНЦИАЛЬНЫХ
ИГРАХ НА ПЛОСКОСТИ
01.01.09 дискретная математика и математическая кибернетика
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата физико-математических наук
Москва 2013
Работа выполнена на кафедре высшей математики Московского
физико-технического института (государственного университета)
Научный руководитель:
Доктор физико-математических наук,
профессор
Иванов Григорий Евгеньевич
Официальные оппоненты:
Доктор физико-математических наук,
профессор
Бекларян Лева Андреевич,
Центральный экономико-математический
институт РАН, лаборатория
01 Экспериментальная экономика,
главный научный сотрудник.
Кандидат физико-математических наук
Камзолкин Дмитрий Владимирович,
Московский государственный университет
имени М. В. Ломоносова, кафедра
оптимального управления факультета
вычислительной математики и кибернетики,
ассистент.
Ведущая организация:
Институт проблем управления
им. В.А. Трапезникова РАН
Защита состоится
2013 г. в
часов на
заседании диссертационного совета Д 212.156.05 при Московском физикотехническом институте (государственном университете) по адресу 141700,
Московская обл., г. Долгопрудный, Институтский пер., д. 9, ауд. 903 КПМ.
С диссертацией можно ознакомиться в библиотеке Московского физикотехнического института (государственного университета).
Автореферат разослан
Ученый секретарь
диссертационного совета
2013 г.
Федько Ольга Сергеевна
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Управление динамическими системами на практике как
правило происходит в условиях неопределенности, помех и конфликтов. Математической теорией, в рамках которой изучаются такие задачи, является теория дифференциальных игр. В данной работе рассматриваются антагонистические дифференциальные игры, в которых участвуют два игрока с противоположными интересами. Термин
ѕдифференциальная играї был введен Р. Айзексом, проводившим первые теоретические исследования в этой области на основе разработанного им метода сингулярных поверхностей. Им также впервые рассмотрена дифференциальная игра ѕшофер-убийцаї
и частично получено ее аналитическое решение.
Классические работы по теории дифференциальных игр в СССР принадлежат
Л.С. Понтрягину, Н.Н. Красовскому, А.И. Субботину, Б.Н. Пшеничному. Л.С. Понтрягиным предложен метод альтернированного интеграла для решения линейных задач.
Этот метод использует в своем построении понятия суммы и разности множеств по
Минковскому. В отличие от этого метода, операторные конструкции, предложенные
Б.Н. Пшеничным, применимы и для нелинейных дифференциальных игр, но требуют разработки алгоритмов, которые позволили бы приближенно вычислять образы
этих операторов. Н.Н. Красовский и А.И. Субботин исследовали дифференциальные
игры в довольно общей постановке. Ими доказана теорема об альтернативе, введено понятие стабильного моста и предложен метод экстремального прицеливания для
построения оптимальных стратегий. Позднее были предложены и получили распространение методы, использующие для построения стратегий уравнение Гамильтона
ЯкобиБеллманаАйзекса.
Важные результаты по дифференциальным играм были получены в работах А. Б.
Куржанского, А. В. Кряжимского, Ю. С. Осипова, А. И. Субботина, А. Г. Ченцова,
А. А. Чикрия, Ю. Н. Онопчука, В. В. Остапенко, Ф. Л. Черноусько, А. А. Меликяна,
Е.Ф. Мищенко. Существенные результаты были получены Э. Г. Альбрехтом, В. Д.
Батухтиным, Н.Д. Боткиным, Н. Л. Григоренко, В.И. Жуковским, М.И. Зеликиным,
Г.Е.Ивановым, Д.В. Камзолкиным, А.Ф. Клейменовым, А.Н. Красовским, С.И. Кумковым, С.С. Кумковым, Ю.С. Ледяевым, Н.Ю. Лукояновым, В.И. Максимовым, М.С.
Никольским, О.И. Никоновым, В.С. Пацко, Н. Н. Петровым, Л. А. Петросяном, Е.С.
Половинкиным, А.П. Пономаревым, Н.Н.Субботиной, А.М. Тарасьевым, В.Е. Третьяковым, В.Л. Туровой, А.А. Успенским, В.И. Ухоботовым, В.Н. Ушаковым, С.В. Чистяковым и другими.
К сожалению, далеко не все типы задач теории дифференциальных игр удается
решить аналитически. Поэтому актуальной становится задача разработки численных
методов поиска оптимальных стратегий в дифференциальных играх. Основные направления исследований, посвященных численным методам, в целом повторяют направления теоретических исследований и основаны на аппроксимационных схемах построения используемых теоретических конструкций (уравнения ГамильтонаЯкоби
БеллманаАйзекса, альтернированного интеграла Понтрягина, стабильного моста).
При этом важно не только приближенно построить мост или альтернированный интеграл, но и вычислить оптимальные стратегии.
3
В задачах приведения фазового вектора на целевое множество часто возникают
геометрические подзадачи, которые также необходимо решать алгоритмически. Для
выпуклых задач при вычислении суммы и разности множеств по Минковскому используется аппарат опорных функций. Также известна техника эллипсоидального исчисления, позволяющая исследовать линейные дифференциальные игры, для которых целевое множество и множества допустимых управлений представляют собой эллипсоиды.
К сожалению, аппарат опорных функций и эллипсоидальная техника неприменимы
для игр с нелинейной динамикой или с невыпуклым целевым множеством.
С другой стороны, в связи с решением различных задач робототехники, например,
планирования движения роботов (motion planning), развиваются методы компьютерной геометрии и создается библиотека программ (см. www.cgal.org), используемых
для решения таких задач. В частности, в данной библиотеке реализованы эффективные алгоритмы вычисления суммы Минковского двух невыпуклых многоугольников.
Несмотря на то, что в компьютерной геометрии и теории дифференциальных игр имеются общие задачи, эти два раздела математики, насколько известно автору, до сих
пор существовали абсолютно независимо.
Чрезвычайно высокая вычислительная сложность алгоритмов, используемых в
теории дифференциальных игр, делает актуальной задачу анализа эффективности
предлагаемых алгоритмов. Теоретический анализ эффективности алгоритмов состоит
в оценках их погрешностей, а следовательно, и скоростей сходимости. Работ на эту
тему сравнительно мало, и в большинстве из них рассматриваются лишь линейные
дифференциальные игры или делаются предположения о выпуклости целевого множества. Часть работ ограничивается оценкой погрешности, связанной с дискретизацией по времени, но важно учитывать также и погрешность, вызванную дискретизацией по пространству фазовой переменной. Для полного исследования эффективности
алгоритмов следует не ограничиваться оценкой погрешности построения моста или
альтернированного интеграла, но и оценить погрешность построенных стратегий.
Все это делает актуальной задачу разработки алгоритмов для построения оптимальных стратегий в нелинейных дифференциальных играх и оценки их погрешности,
учитывающей как дискретизацию по времени, так и дискретизацию по пространствам
фазовой переменной и управлений.
Цель работы. Разработать алгоритмы поиска эпсилон-оптимальных стратегий
в нелинейных дифференциальных играх с целевым множеством как с фиксированным временем окончания, так и с нефиксированным временем окончания. Оценить
погрешность предложенных алгоритмов в зависимости от параметров дискретизации
как по времени, так и по пространствам фазовой переменной и управлений. Доказать
сходимость и эффективность этих алгоритмов. Провести численные эксперименты и
сравнить реализующуюся на практике погрешность предложенных алгоритмов с ее
теоретической оценкой.
Методы исследования. Аппарат выпуклого и многозначного анализа, попятные
конструкции дифференциальных игр, методы компьютерной геометрии.
Научная новизна. Разработаны новые алгоритмы поиска эпсилон-оптимальных
стратегий в нелинейных дифференциальных играх с целевым множеством. Рассмот4
рены как игры с фиксированным временем окончания, так и нефиксированным временем окончания. Для вычисления одношаговых множеств достижимости, используемых в попятной конструкции, на основании которой строится алгоритм, введены
операторы Минковского, обобщающие понятия суммы и разности множеств по Минковскому. Обобщен известный в области компьютерной геометрии алгоритм поиска
суммы Минковского двух многоугольников на плоскости. Предложенный алгоритм
позволяет эффективно вычислять аппроксимации значений операторов Минковского
в плоском случае. Получена оценка погрешности таких аппроксимаций и общая оценка
погрешности алгоритмов поиска эпсилон-оптимальных стратегий в рассматриваемых
дифференциальных играх на плоскости.
Теоретическая и практическая ценность. В диссертации предложен новый
подход к построению и исследованию алгоритмов поиска эпсилон-оптимальных стратегий в нелинейных дифференциальных играх с целевым множеством, основанный
на использовании операторов Минковского. Изучены топологические, геометрические
и экстремальные свойства операторов Минковского, обобщающих понятия суммы и
разности множеств по Минковскому. Разработаны конструктивные алгоритмы приближенного вычисления значений операторов Минковского, использующие методы
компьютерной геометрии. Полученные явные оценки погрешностей алгоритмов позволяют по заданной точности определять значения параметров дискретизации, которые
нужно использовать для получения стратегий, обеспечивающих эту точность. Теоретические оценки и результаты численных экспериментов показали, что предложенный
алгоритм является более эффективным, чем известные аналоги. Эффективность алгоритма на практике подтверждена численными экспериментами.
Апробация работы. Результаты, изложенные в диссертации, в разное время докладывались и обсуждались на
? Четвертой международной конференции ѕСистемный анализ и информационные
технологииї САИТ-2011, пос. Новоабзаково, 2011;
? Четвертой традиционной молодежной школе ѕУправление, информация, оптимизацияї, Звенигород, 2012;
? 55-й научной конференции МФТИ - Всероссийской научной конференции ѕСовременные проблемы фундаментальных и прикладных, естественных и технических наук в современном информационном обществеї, Москва Долгопрудный,
2012;
? Научных семинарах кафедры высшей математики МФТИ, Москва Долгопрудный, 2010 2013;
? Научном семинаре ѕТеория автоматического управленияї лаборатории 7 ИПУ
РАН, Москва, 2013;
? Научном семинаре ѕОптимальное управление: математическая теория и прикладные задачиї кафедры оптимального управления факультета вычислительной математики и кибернетики МГУ, Москва, 2013;
5
? VI Международной конференции ѕДинамические системы: устойчивость, управление, оптимизацияї, посвященной 95-летию со дня рождения Е.А. Барбашина,
Минск, 2013.
Также на основе материалов диссертации автором был прочитан факультативный курс
ѕНелинейные дифференциальные игры на плоскостиї для студентов МФТИ.
Публикации. По теме диссертации опубликовано 8 работ, в том числе две [1,2]
в изданиях из списка, рекомендованного ВАК РФ. Основные результаты диссертации отражают личный вклад соискателя в опубликованные по теме диссертации
работы с соавторами.
Структура и объем работы. Диссертация состоит из введения, четырех глав,
заключения, списка литературы и списка иллюстраций. Общий объем диссертации
составляет 122 страницы. Список литературы содержит 76 наименований. Список иллюстраций содержит 20 наименований.
СОДЕРЖАНИЕ РАБОТЫ
Во введении дается краткий обзор публикаций по дифференциальным играм,
краткое содержание диссертации, перечисляются основные результаты работы.
В первой главе вводятся понятия операторов Минковского, обобщающих понятия
суммы и разности множеств по Минковскому, и рассматриваются их свойства, а также
предлагается алгоритм для приближенного вычисления их образов на плоскости и
доказывается оценка погрешности этой аппроксимации.
В первом параграфе первой главы вводится следующее определение операторов Минковского. Пусть E линейное пространство. Операторами Минковского
многозначного отображения G : E ? 2E называются операторы AG : 2E ? 2E и
BG : 2E ? 2E , заданные формулами
AG S =
[
(x + G(x)),
BG S = E \ (AG (E \ S))
(1)
x?S
для любого множества S ? E .
Суммой и разностью Минковского множеств
X ? E и Y ? E называют
? Y =
ся соответственно
множества
X + Y = x + y x ? X, y ? Y ,
X ?
x?E x+Y ?X .
Оставшаяся часть параграфа посвящена изучению свойств этих операторов в случае E = Rn . Через int S , S и ?S обозначены соответственно внутренность, замыкание
и граница множества S . Предполагается, что в Rn введена некоторая норма k · k. Через Br обозначен замкнутый шар в Rn с центром в нуле и радиусом r: Br = {x ?
Rn : kxk ? r}. Уклонением множества X ? Rn от множества Y ? Rn называется
величина h+ (X, Y ) = inf{r ? 0 | X ? Y + Br }. Хаусдорфовым расстоянием между
множествами X ? Rn и Y ? Rn называется h(X, Y ) = max{h+ (X, Y ), h+ (Y, X)}. Мноn
гозначное отображение G : Rn ? 2R удовлетворяет условию Липшица с константой
LG в смысле метрики Хаусдорфа, если h(G(x1 ), G(x2 )) ? LG kx1 ?x2 k
?x1 , x2 ? Rn .
Приведем некоторые свойства операторов Минковского.
6
Лемма 1. Пусть многозначное отображение G : Rn ? 2R принимает замкнутые
n
значения и удовлетворяет условию Липшица с константой LG < 1 в смысле метрики Хаусдорфа. Пусть задано множество S ? Rn и точки x0 ? int S , y0 ? x0 + G(x0 ).
Тогда для множества AG S , определенного первым соотношением (1), справедливо
включение y0 ? int AG S .
Лемма 2. Пусть многозначное отображение G : Rn ? 2R принимает замкнутые
n
значения и непрерывно в смысле метрики Хаусдорфа. Пусть множество S ? Rn
замкнуто и supx?S supu?G(x) kuk < +?. Тогда множество AG S замкнуто.
Лемма 3. Пусть многозначное отображение G : Rn ? 2R принимает замкнутые
n
значения и удовлетворяет условию Липшица с константой LG < 1 в смысле метрики Хаусдорфа. Тогда для любого множества S ? Rn и любого числа ? > 0 операторы
Минковского (1) удовлетворяют включениям
AG S + B?/(1+LG ) ? AG S + B? ? AG S + B?/(1?LG ) ,
? B
? B , B S+B ?B S+B
AG S ?
?
A
S
?
G
?
G
?
G
?/(1?LG )
?/(1?LG ) ,
? B
? B ?B S?
? B
.
?B S?
B S?
G
?/(1?LG )
G
?
G
?/(1+LG )
Во втором параграфе первой главы вводятся необходимые для работы с плоскими многоугольниками определения, состоящие в следующем. Пусть задан набор
точек ak ? R2 , k = 1, m, причем ak+1 6= ak для любого k ? 1, m ? 1. Упорядоченный
набор отрезков {[a1 , a2 ], [a2 , a3 ], . . . , [am?1 , am ]} называется ломаной ?(a1 , . . . , am ), точки ak называются вершинами, а отрезки [ak , ak+1 ] звеньями этой ломаной. Ломаная
?(a1 , . . . , am ) называется замкнутой, если am = a1 . Ломаная ?(a1 , . . . , am ) называется
простой замкнутой, если m > 1, am = a1 и из того, что z ? [aj , aj+1 ] ? [ak , ak+1 ],
1 ? j < k < m следует, что k = j + 1 и z = ak . Простым многоугольником называется ограниченное замкнутое множество S ? R2 такое, что его границей ?S является
простая замкнутая ломаная. Вершинами простого многоугольника S называются вершины ломаной ?S . Запись ? + S и ? ? S обозначает границу простого многоугольника S ,
ориентированную соответственно против часовой стрелки и по часовой стрелке. Выпуклым многоугольником называется выпуклая оболочка конечного числа точек в R2 .
Через ha, bi обозначено скалярное произведение векторов a ? Rn и b ? Rn . Нормальным конусом выпуклого множества X ? Rn в точке x0 ? X называется множество
N (x0 , X) = {p ? Rn | hp, xi ? hp, x0 i ?x ? X}. Для любого ненулевого вектора
z ? R2 через (0, z · ?) обозначен луч {tz | t ? (0, +?)}. Для любых двух ненулевых
векторов a ? R2 и b ? R2 через ?(a, b) обозначено множество всех ненулевых векторов, лежащих на лучах, полученных путем вращения луча (0, a · ?) против часовой
стрелки до луча (0, b · ?). Правым перпендикуляром для вектора a = (ax , ay )T ? R2
называется вектор a? = (ay , ?ax )T .
В третьем параграфе первой главы вводится понятие конволюты многоугольника и многозначного отображения на плоскости, состоящее в следующем. Пусть многозначное отображение G каждому вектору x ? R2 ставит в соответствие выпуклый
7
многоугольник G(x). Пусть ?0 = ?(x1 , . . . , xn , xn+1 ) замкнутая ломаная. Для любого j ? 1, n обозначим pj = (xj+1 ? xj )? , положим p0 = pn . Для каждого j ? 1, n
j
j
рассмотрим g1 , . . . , gm
пронумерованные против часовой стрелки все вершины мноj
гоугольника G(xj ) такие, что
j
N (gm
, G(xj )) ? ?pj?1 pj 6= ?,
m ? 1, mj .
(2)
j
Если условию (2) удовлетворяют все вершины многоугольника G(xj ), то вершину g1
j
будем определять из условия pj?1 ? N (g1 , G(xj )) (если таких точек окажется нескольj
ко, то будем выбирать вершину g1 как любую, удовлетворяющую еще и условию
hxj ?xj?1 , g1j i ? hxj ?xj?1 , gi для всех вершин g многоугольника G(xj ), удовлетворяющих условию pj?1 ? N (g, G(xj )). Пусть при этом g? последняя против часовой стрелки
j
вершина многоугольника G(xj ), не совпадающая с g1 . Если pj ? N (g?, G(xj )), то будем
j
j
= g1j .
= g? , иначе будем полагать gm
полагать gm
j
j
Конволютой для многозначного отображения G и замкнутой ломаной ?0 называется замкнутая ломаная
1
2
n
CG (?0 ) = ?(x1 + g11 , . . . , x1 + gm
, x2 + g12 , . . . , x2 + gm
, . . . , xn + g1n , . . . , xn + gm
, x1 + g11 ).
1
2
n
(3)
n
Будем рассматривать max-норму вектора x ? R : kxk? = maxk?1,n |xk |, где xk k -ая компонента вектора x.
При получении оценок расстояния между границей образов операторов Минковского (1) и конволютой, а также между образами операторов Минковского и извлеченными из конволюты их аппроксимациями считаются выполненными следующие
предположения:
A1: S простой (вообще говоря невыпуклый) многоугольник, длины (относительно
max-нормы) сторон которого не превосходят числа h;
A2: значением многозначного отображения G является отрезок, т.е. G(x) =
[g1 (x), g2 (x)];
A3: функции g1 , g2 : R2 ? R2 удовлетворяют условию Липшица (относительно
1
max-нормы) с константой LG ? 10
;
A4: выполнены неравенства kg1 (x) ? g2 (x)k?
?
dG
<
+?,
2
max{kg1 (x)k? , kg2 (x)k? } ? CG < +? ?x ? R .
Параметры h, LG , dG и CG считаются малыми и определяют точность работы
алгоритмов. Методы обоснования предложенных алгоритмов применимы и к более
общему случаю, когда значением многозначного отображения G является выпуклый
многоугольник, вершины которого удовлетворяют условию Липшица как функции от
точки x. Однако в силу значительной технической сложности доказательств данная
работа ограничивается наиболее важным частным случаем, когда множество G(x)
является отрезком.
Близость конволюты и границ образов операторов Минковского выражается в следующих лемме и теореме.
8
Лемма 4. Пусть в пространстве R2 введена некоторая норма k · k. Пусть мно2
гозначное отображение G : R2 ? 2R принимает выпуклые компактные значения
и удовлетворяет условию Липшица с константой LG относительно нормы k · k в
смысле метрики Хаусдорфа. Пусть длины звеньев (в смысле нормы k · k) замкнутой ломаной ? ? R2 не превосходят числа h. Тогда относительно нормы k · k для
конволюты (3) и первого из операторов Минковского (1) справедливо неравенство
h+ (CG (?), AG ?) < LG h.
Пусть границей множества S ? R2 является простая замкнутая ломаная ?. Будем
говорить, что ломаная ? ориентирована положительно относительно множества S
и писать ? = ? + S , если при обходе ломаной ? в направлении ее ориентации множество
S остается слева.
Теорема 1. Пусть границей множества S ? R2 является простая замкнутая ломаная ? + S , ориентированная положительно относительно множества S , длины (в
смысле max-нормы) звеньев ломаной ? + S не превосходят числа h. Пусть выполнены
предположения A2A4. Тогда (в смысле max-нормы)
h+ (?AG S, CG (? + S)) < (16dG + 7h)LG .
В третьем параграфе также приведены примеры, показывающие точность оценки
в теореме 1 и показывающие сложность получения этой оценки.
Пятый параграф первой главы целиком посвящен доказательству теоремы 1
с использованием вспомогательных утверждений четвертого параграфа.
В шестом параграфе первой главы приводятся необходимые определения и
алгоритмы, позволяющие извлечь из конволюты границы множеств, являющихся аппроксимациями образов операторов Минковского.
Для любой замкнутой ломаной ? ? R2 ее дополнение R2 \ ? состоит из конечного
числа непересекающихся областей, одна из которых неограничена. Дополнение к этой
неограниченной области называется доменом ? и обозначается Domain ? . Граница домена замкнутой ломаной ? называется внешним контуром ? и обозначается ExtC ? :
ExtC ? = ?(Domain ?).
Пусть заданы замкнутая ломаная ? ? R2 и точка x0 ? (Domain ?) \ ? . Замыкание множества всех точек x ? R2 , которые можно соединить с точкой x0 ломаной, не
пересекающейся с ? , называется внутренним (относительно точки x0 ) доменом ? и
обозначается IntDomx0 ? . Граница внутреннего домена замкнутой ломаной ? называется внутренним контуром ? и обозначается IntCx0 ? : IntCx0 ? = ?(IntDomx0 ?).
bG S и B
bG S , аппроксимирующие множества AG S , BG S , опредеМногоугольники A
ляются следующим образом:
bG S = IntDomx (CG (? ? S)).
B
0
bG S = Domain(CG (? + S)),
A
Приведенные в этом параграфе алгоритмы вычисления внешнего и внутреннего относительно точки x0 контуров замкнутой ломаной позволяют вычислить границы многоbG S и B
bG S . В качестве x0 берется любая точка, удовлетворяющая вклюугольников A
?
? B
чению x0 ? S ?
(16dG +8h)LG +CG ? Domain(CG (? S)).
9
Главными результатами шестого параграфа являются следующие теорема и лемма.
Теорема 2. Пусть в пространстве R2 введена max-норма. Пусть выполнены предположения A1A4. Пусть ?1 = LG h,
?2 = (16dG + 7h)LG . Под Br будем понимать
замкнутый шар радиуса r в max-норме. Пусть множества
? B ,
BG S ?
?1
? B ,
bG S ?
B
?2
2
R \ (AG S + B?1 ) ,
2
bG S + B?
R \ A
2
связны. Тогда справедливы включения
bG S + B? ,
AG S ? A
2
bG S ? AG S + B? ,
A
1
? B ?B
bG S,
BG S ?
?1
? B ? B S.
bG S ?
B
?2
G
Лемма 5. Пусть выполнены условия теоремы 2. Пусть множества A?G S, B?G S опре-
делены следующим образом:
bG S + B? ,
A?G S = A
2
Тогда при ? =
LG (16dG +8h)
1?LG
? B .
bG S ?
B?G S = B
?2
справедливы включения
AG S ? A?G S ? AG (S + B? ) ,
? B ? B? S ? B S.
BG S ?
G
G
?
Седьмой параграф первой главы посвящен модифицированным операторам
Минковского A?G : 2E ? 2E , B?G : 2E ? 2E , определяемым равенствами
A?G S = {x ? E | (x ? G(x)) ? S 6= ?},
E \ B?G S = A?G (E \ S)
(4)
для любого множества S ? E . При этом B?G S = {x ? E | x ? G(x) ? S} ?S ? E .
Далее доказывается несколько свойств модифицированных операторов, аналогичных свойствам операторов Минковского (1), приведенным в первом параграфе, и теорема о том, что алгоритмы шестого параграфа могут быть использованы для приближенного вычисления также и образов модифицированных операторов Минковского.
Теорема 3. Пусть выполнены условия леммы 5. Тогда справедливы включения
? B ? A? S ? A? S + B ,
A?G S ?
??
G
G
?+
?
B?G S ? B?+ ? B?G S ? B?G S + B??
где
?? =
LG CG
,
1 ? LG
?+ = LG CG +
?1 + ?2
(16dG + 8h)LG
= LG CG +
.
1 ? LG
1 ? LG
Таким образом, для любого простого многоугольника S описанные в первой главе алгоритмы вычисляют множества A?G S , B?G S , которые являются аппроксимациями
значений модифицированных операторов Минковского. Эти алгоритмы использованы
10
в следующих главах для построения эпсилон-оптимальных гарантированных стратегий управления в нелинейных дифференциальных играх. С использованием оценок
теоремы 3 получены общие оценки погрешностей рассматриваемых в третьей и четвертой главах алгоритмов.
Во второй главе рассматривается нелинейная дифференциальная игра с целевым
множеством и фиксированным временем окончания и предлагается алгоритм для построения эпсилон-оптимальных стратегий в такой игре.
Первый параграф второй главы посвящен постановке задачи и перечислению
принятых предположений. Рассматривается дифференциальная игра
x(t) ? Rn ,
x?(t) = a(t, x(t), u(t)) + b(t, x(t), v(t)), t ? [0, ?],
u(t) ? P ? Rp , v(t) ? Q ? Rq ?t ? [0, ?]
Предполагается, что функции a : [0, ?] Ч Rn Ч P ? Rn и b : [0, ?] Ч Rn Ч Q ? Rn
непрерывны, а также, что вектограммы a(t, x, P ) = {a(t, x, u) : u ? P }, b(t, x, Q) =
{b(t, x, v) : v ? Q} выпуклы при всех t ? [0, ?], x ? Rn . Также предполагается заданным целевое компактное множество M ? Rn .
Если выполняется x(?) ? M , то в игре имеет место поимка. Если выполняется
x(?) ?
/ M , то в игре имеет место уклонение. Цель первого игрока состоит в поимке,
цель второго игрока в уклонении.
Пусть в Rn задана некоторая норма k · k. Расстоянием от точки x ? Rn до
множества Y ? Rn называется величина %(x, Y ) = inf y?Y kx ? yk. Неравенство
%(x(?), M ) ? ? означает, что в конечный момент времени имеет место ?-поимка.
Предполагается, что функции a : [0, ?] Ч Rn Ч P ? Rn и b : [0, ?] Ч Rn Ч Q ? Rn
удовлетворяют следующим условиям Липшица:
ka(t1 , x1 , u1 ) ? a(t2 , x2 , u2 )k ? Lta |t1 ? t2 | + Lxa kx1 ? x2 k + Lua ku1 ? u2 k
?t1 , t2 ? [0, ?], x1 , x2 ? Rn , u1 , u2 ? P ;
kb(t1 , x1 , v1 ) ? b(t2 , x2 , v2 )k ?
Ltb |t1
? t2 | +
Lxb kx1
Lvb kv1
? x2 k +
? v2 k
?t1 , t2 ? [0, ?], x1 , x2 ? Rn ,
v1 , v2 ? Q;
(5)
ka(t, x, u)k ? Ca
?t ? [0, ?],
x?R ,
u ? P;
(6)
(7)
kb(t, x, v)k ? Cb
?t ? [0, ?],
x ? Rn ,
v ? Q.
(8)
Обозначим
C = Ca + Cb ,
n
L = Lxa + Lxb .
(9)
Во втором параграфе второй главы описано в каком классе стратегий ищутся оптимальные стратегии и какие реализации действий противника предполагаются
возможными.
Пусть задан отрезок [t0 , t1 ] ? [0, ?]. Множеством U[t0 , t1 ] допустимых реализаций управления первого игрока называется множество всех измеримых функций
u : [t0 , t1 ] ? P . Аналогично задается множество V[t0 , t1 ] допустимых реализаций
управления второго игрока.
11
I
Пусть заданы число t0 ? [0, ?) и начальное состояние x(t0 ) = x0 . Пусть T = {?i }i=0
разбиение отрезка [t0 , ?] : t0 = ?0 < ?1 < · · · < ?I = ?. Кусочно-постоянной
стратегией первого игрока, соответствующей разбиению T , называется набор функI?1
str
n
ций ustr
T = {ui : R ? P }i=0 . Движением, соответствующим начальному состоянию
x(t0 ) = x0 , разбиению T , стратегии первого игрока ustr
T и допустимой реализации
управления v ? V[t0 , ?], называется функция x : [t0 , ?] ? Rn , определяемая из пошагового уравнения
x?(t) = a(t, x(t), ustr
T (x(?i ))) + b(t, x(t), v(t)),
которое должно выполняться при почти всех t ? [?i , ?i+1 ] и всех i ? 0, I ? 1. При этом
начальная позиция для отрезка [?0 , ?1 ] равна x0 , а начальная позиция x(?i ) для отрезка
[?i , ?i+1 ] совпадает с конечной позицией x(?i ) отрезка [?i?1 , ?i ].
str
Обозначим движение следующим образом: xmot
u (t, t0 , x0 , T, uT , v). Аналогично определяются кусочно-постоянная стратегия второго игрока vTstr и движение
str
xmot
v (t, t0 , x0 , T, u, vT ).
Кусочно-постоянная стратегия ustr
T гарантирует ?-поимку для начального состояния x0 , если для любой реализации управления v ? V[0, ?] выполняется неравенstr
str
ство % (xmot
u (?, 0, x0 , T, uT , v), M ) ? ?. Кусочно-постоянная стратегия vT гарантирует уклонение для начального состояния x0 , если для любой реализации управлеstr
/ M . Пара кусочнония u ? U[0, ?] выполняется соотношение xmot
v (?, 0, x0 , T, u, vT ) ?
str str
постоянных стратегий (uT , vT ) называется ?-оптимальной, если для любого начального состояния x0 ? Rn выполняется хотя бы одно из условий:
1) стратегия ustr
T гарантирует ?-поимку или
str
2) стратегия vT гарантирует уклонение.
В третьем параграфе второй главы введены одношаговые операторы достижимости, описан алгоритм построения стратегий и сформулированы теоремы о его
погрешности без конкретизации способа построения образов одношаговых операторов
достижимости.
Пусть зафиксировано натуральное число I и произведено равномерное разбиение
T = {?i }Ii=0 отрезка [0, ?], где ?i = i? , i ? 0, I . Шаг ? = ?/I разбиения T называется
параметром дискретизации по времени.
Для любого множества S ? Rn и любого индекса i ? 0, I ? 1 определяются множества
Ai S = {x ? Rn :
Bi S = {x ? Rn :
?u ? P :
?v ? Q :
x + ? a(?i , x, u) ? S},
x + ? b(?i , x, v) ? S}.
Таким образом, определены одношаговые операторы достижимости Ai , Bi .
Для любого i ? 0, I рассматриваются выпуклозначные многозначные отображения
a
Gi , Gbi , заданные формулами
Gai (x) = ?? a(?i , x, P ),
Gbi (x) = ?? b(?i , x, Q) ?i ? 0, I
?x ? R2 .
Из определений модифицированных операторов Минковского (4) следуют равенства
Ai = A?Gai , Bi = B?Gbi ?i ? 0, I .
12
Из соотношений (5) (8) следует, что LGai = ? Lxa , CGai = ? Ca , dGai = 2? Ca , LtGai =
? Lta , LGbi = ? Lxb , CGbi = ? Cb , dGbi = 2? Cb , LtGb = ? Ltb .
i
Пусть ? класс множеств в Rn , с которым работают алгоритмы. Все используемые для построения стратегий множества аппроксимируются множествами из этого
класса.
В данном параграфе часть алгоритмов, являющихся внутренними по отношению
к алгоритму поиска оптимальных стратегий, не конкретизируются, а лишь предполагается, что они существуют и имеются оценки их погрешностей. Так, предполагается,
что реально для каждого множества S ? ? и индекса i ? 0, I вычисляются множества
A?i S , B?i S класса ?, удовлетворяющие условиям
? B ? ) ? A? S ? A (S + B + ),
Ai (S ?
i
i
?A
?A
? B + ) ? B? S ? B (S + B ? ),
Bi (S ?
i
i
?B
?B
(10)
+
?
+
где числа ??
A , ?A , ?B , ?B определяют погрешности этих алгоритмов.
Также предполагается существование алгоритма, который для любых множества
S ? ?, индекса i ? 0, I ? 1 и вектора x ? A?i S позволяет определить вектор u?i =
u?i (x, S) ? P такой, что
x + ? a(?i , x, u?i ) ? S + B?u ,
(11)
и алгоритма, который для любых множества S ? ?, индекса i ? 0, I ? 1 и вектора
x ? Rn \ (B?i S) позволяет определить вектор v?i = v?i (x, S) ? Q такой, что
x + ? b(?i , x, v?i ) ? (Rn \ S) + B?v .
(12)
Здесь числа ?u и ?v определяют погрешности соответствующих алгоритмов.
Зафиксируем некоторые векторы u? ? P , v? ? Q и положим u?i (x, S) = u? при
x 6? A?i S , v?i (x, S) = v? при x ? B?i S . Тем самым при всех i ? 0, I ? 1 определены
функции
u?i : Rn Ч ? ? P,
v?i : Rn Ч ? ? Q.
(13)
Обозначим
?0u = ? 2
Lta + Ltb
+ LC + Lxb Ca ,
2
x
?u = ?0u + ??
B + (1 + ? Lb )?u ,
?0v = ? 2
Lta + Ltb
+ LC + Lxa Cb ,
2
x
?v = ?0v + ??
A + (1 + ? La )?v .
Предполагается, что имеются алгоритмы, которые для любого множества S ? ? вычисляют множества Du S ? ?, Dv S ? ? такие, что
? B
?
S?
?u +?D ? Du S ? S ? B?u ,
S + B?v ? Dv S ? S + B?v +?D ,
(14)
где число ?D определяет погрешность этих алгоритмов.
Пусть зафиксировано положительное число ?. Начальные множества MIu ? ?,
MIv ? ? попятной конструкции определяются следующим образом:
M + B???M ? MIu ? M + B? ,
13
M ? MIv ? M + B?M .
(15)
Здесь число ?M ? (0, ?) определяет погрешность начальной аппроксимации.
Двигаясь в сторону уменьшения индекса i и используя алгоритмы, существование
которых мы предположили, вычисляются наборы игровых множеств достижимости
v I?1
{Miu }I?1
i=0 , {Mi }i=0 :
u
Miu = A?i B?i Du Mi+1
,
v
Miv = B?i A?i Dv Mi+1
Для любых i ? 0, I ? 1 и x ? Rn , с использованием функций (13) и игровых
множеств достижимости Miu , Miv , определяются стратегии игроков
u
ui (x) = u?i (x, B?i Du Mi+1
),
(16)
v
vi (x) = v?i (x, A?i Dv Mi+1
).
(17)
Перечислим основные результаты третьего параграфа второй главы.
I?1
Теорема 4. Пусть x0 ? M0u , стратегия ustr
T = {ui }i=0 определена соотношением
(16). Тогда стратегия ustr
T гарантирует ?-поимку на отрезке [0, ?] для начального
состояния x(0) = x0 .
Теорема 5. Пусть x0 ? Rn \ M0v , стратегия vTstr = {vi }I?1
i=0 определена соотношением
(17). Тогда стратегия vTstr гарантирует уклонение на отрезке [0, ?] для начального
состояния x(0) = x0 .
Определим числа
4 +
4 2 t
?
?
?0 = ?u + ?v + 2?D + ?+
+
?
+
?
? Lb ,
+
?
+
A
A
B
3 B
3
?0 = ? Cb + 2?M + ?u + ?D + (? Cb + ?0 I)e?L .
Теорема 6. Пусть ? ? ?0 , ? Lxb < 21 . Тогда
M0v ? M0u .
(18)
Теорема 7. Пусть ? ? ?M и справедливо включение (18). Тогда пара кусочноstr
постоянных стратегий (ustr
T , vT ) является ?-оптимальной.
Четвертый параграф второй главы посвящен доказательству теорем 47.
Наконец, в пятом параграфе второй главы для игр на плоскости конкре-
тизируются алгоритмы, существование которых предполагалось в третьем параграфе. Предполагается, что каждая из вектограмм a(t, x, P ) = {a(t, x, u) | u ? P } и
b(t, x, Q) = {b(t, x, v) | v ? Q} либо является отрезком, либо не зависит от x. В этом параграфе используется max-норма. Алгоритмы строятся следующим образом. Зафиксируем натуральное число I ? 10? max{Lxa , Lxb } и рассмотрим равномерное разбиение
T = {?i }Ii=0 отрезка [0, ?], где ?i = i? , i ? 0, I , ? = ?/I . Зафиксируем число h > 0.
Игровые множества достижимости будем аппроксимировать простыми многоугольниками, длины сторон которых не превосходят числа h. Пусть P? и Q? сетки на множествах P и Q с мелкостями hP и hQ соответственно, т.е. множества P? ? P и Q? ? Q
14
состоят из конечного числа элементов P? =
j JP
JQ
u? j=1 , Q? = v? j j=1
и hP = h+ (P, P? ),
hQ = h+ (Q, Q?), где h+ уклонение множеств.
Зафиксируем произвольное число ? > 0. Приблизим множества M + B? и M соответственно простыми многоугольниками MIu и MIv с точностью ?M ? (0, ?) так, чтобы
выполнялись включения (15).
В качестве операторов приближенного вычисления образов одношаговых операторов достижимости будем использовать операторы A?Gai , B?Gbi введенные в лемме 5.
Таким образом, в соотношениях (10) можно положить A?i = A?Gai , B?i = B?Gbi ?i ? 0, I .
Выбор вектора u?i (x, S) ? P , для которого справедливо включение (11) производится следующим образом. Пусть задан номер i ? 0, I ? 1 и точка x ? A?i S . Вычислим
с помощью алгоритма второго параграфа первой главы множество S + B?+A +? Lua hP ? x
и перебором по j ? 1, JP найдем такой вектор u?j , что выполняется включение
? a(?i , x, u?j ) ? S + B?+A +? Lua hP ? x. Вектор u?j и будет искомым. Аналогичный алгоритм
позволяет найти вектор v?i (x, S) ? Q, для которого справедливо включение (12).
Использование max-нормы позволяет использовать алгоритм поиска суммы Минковского двух многоугольников из второго параграфа первой главы для вычисления
без погрешности суммы и разности Минковского многоугольника S и шара в этой нор? B ,
ме. Это означает, что в соотношениях (14) можно положить ?D = 0, Du S = S ?
?u
Dv S = S + B?v .
Используя теорему 3, получаем следующую оценку сверху для числа ?0 :
t
t
x
2 La + Lb
+ 3LC + 40La Ca + 10? Lxa h + 2? Lua hP +
?0 < 2?M + ?
2
+ ? Cb (1 + ?e?L ) + ?e?L 3(Lta + Ltb ) + 3LC + 94(Lxa Ca + Lxb Ca ) +
+ 23?e?L Lh + 2?e?L (Lua hP + Lvb hQ ).
(19)
В третьей главе рассматривается нелинейная дифференциальная игра с целевым множеством и нефиксированным временем окончания и предлагается алгоритм
для построения эпсилон-оптимальных стратегий в такой игре. Структура и содержание третьей главы аналогичны структуре и содержанию второй главы. Поэтому
ограничимся перечислением отличий в содержании.
В первом параграфе третьей главы приводится постановка задачи и перечисляются принятые предположения. Рассматривается динамическая система, описываемая автономным дифференциальным уравнением
x?(t) = a(x(t), u(t)) + b(x(t), v(t)),
где t ? [0, ?] время, число ? определяет максимальную продолжительность игры.
Остальные предположения совпадают с предположениями второй главы. Если существует момент времени t ? [t0 , t1 ] такой, что x(t) ? M , то на отрезке [t0 , t1 ] имеет место
поимка. Иначе, то есть если x(t) ?
/ M при всех t ? [t0 , t1 ], то на отрезке [t0 , t1 ] имеет
место уклонение. Цель первого игрока состоит в минимизации числа ?0 ? [0, ?] такого,
что на отрезке [0, ?0 ] обеспечена поимка. Цель второго игрока обеспечить уклонение на отрезке [0, ?] или, если это невозможно, максимизировать время ?0 ? [0, ?]
15
такое, что на отрезке [0, ?0 ] обеспечено уклонение. Будем говорить, что на отрезке
[t0 , t1 ] ? [0, ?] имеет место ?-поимка, если существует такой момент времени t ? [t0 , t1 ],
что %(x(t), M ) ? ?.
Во втором параграфе третьей главы описано в каком классе стратегий ищутся оптимальные стратегии и какие реализации действий противника предполагаются возможными. Допустимыми реализациями управлений игроков считаются те же,
что и во второй главе. Позиционной стратегией первого игрока называется произI
вольная функция ustr : Rn ? P . Пусть T = {?i }i=0 разбиение отрезка [t0 , t1 ] ?
[0, ?] : t0 = ?0 < ?1 < · · · < ?I = t1 . Пара (ustr , T ) называется законом управления
первого игрока на отрезке [t0 , t1 ]. Движением, соответствующим начальному состоянию x(t0 ) = x0 , закону управления (ustr , T ) и допустимой реализации управления
v ? V[t0 , t1 ], называется абсолютно непрерывная функция x : [t0 , t1 ] ? Rn , определяемая из пошагового уравнения x?(t) = a(x(t), ustr (x(?i ))) + b(x(t), v(t)), которое должно
выполняться при почти всех t ? [?i , ?i+1 ] и всех i ? 0, I ? 1. При этом начальная позиция для отрезка [?0 , ?1 ] равна x0 , а начальная позиция x(?i ) для отрезка [?i , ?i+1 ]
совпадает с конечной позицией x(?i ) отрезка [?i?1 , ?i ]. Обозначим движение следуюstr
щим образом: xmot
u (t, t0 , x0 , T, u , v) = x(t) ?t ? [t0 , t1 ]. Аналогично определяются
str
позиционная стратегия второго игрока v str и движение xmot
v (t, t0 , x0 , T, u, v ).
Закон управления (ustr , T ) гарантирует ?-поимку на отрезке [t0 , t1 ] для начального
состояния x0 , если для любой реализации управления v ? V[t0 , t1 ] существует момент
str
времени t ? [t0 , t1 ] такой, что выполняется неравенство % (xmot
u (t, t0 , x0 , T, u , v), M ) ?
?. Закон управления (v str , T ) гарантирует уклонение на отрезке [t0 , t1 ] для начального состояния x0 , если для любой реализации управления u ? U[t0 , t1 ] выполняется
str
/M
?t ? [t0 , t1 ].
соотношение xmot
v (t, t0 , x0 , T, u, v ) ?
Пусть задано число ? > 0 и законы управления (ustr , Tu ), (v str , Tv ) первого и
второго игроков на отрезке [0, ?]. Пара законов ((ustr , Tu ), (v str , Tv )) называется ?оптимальной, если для любого начального положения x0 ? Rn такого, что %(x0 , M ) >
? выполняется альтернатива:
1) существует момент времени ?0 ? [0, ?] такой, что закон управления (ustr , Tu ) гарантирует ?-поимку на отрезке [0, ?0 ], а закон управления (v str , Tv ) гарантирует уклонение на отрезке [0, ?0 ], либо
2) закон управления (v str , Tv ) гарантирует уклонение на отрезке [0, ?].
В третьем параграфе третьей главы введены одношаговые операторы достижимости для игры с нефиксированным временем, описан алгоритм построения стратегий и сформулированы теоремы о его погрешности без конкретизации способа построения образов одношаговых операторов достижимости. Как и ранее рассматривается
равномерное разбиение отрезка [0, ?] с шагом ? = ?/I . Одношаговые операторы достижимости A и B задаются равенствами
AS = {x ? Rn :
BS = {x ? Rn :
?u ? P :
?v ? Q :
для любого множества S ? Rn .
16
x + ? a(x, u) ? S},
x + ? b(x, v) ? S},
(20)
(21)
Для игры с нефиксированным временем окончания рассматриваются выпуклозначные многозначные отображения Ga , Gb с замкнутыми значениями, заданные формулами Ga (x) = ?? a(x, P ), Gb (x) = ?? b(x, Q) ?x ? R2 . Из определений модифицированных операторов Минковского (4) следует, что A = A?Ga , B = B?Gb .
Справедливы следующие равенства LGa = ? Lxa , CGa = ? Ca , dGa = 2? Ca , LGb = ? Lxb ,
CGb = ? Cb , dGb = 2? Cb .
Как и ранее предполагается, что алгоритмы работают с множествами класса ?.
Предполагается, что реально для каждого множества S ? ? вычисляются множества
A?S , B?S класса ?, удовлетворяющие условиям
? B ? ) ? A?S ? A(S + B + ),
A(S ?
?A
?A
? B + ) ? B?S ? B(S + B ? ),
B(S ?
?B
?B
+
?
+
где числа ??
A , ?A , ?B , ?B определяют погрешности этих алгоритмов.
Также предполагается существование алгоритма, который для любых множества
S ? ? и вектора x ? A?S позволяет определить вектор u? = u?(x, S) ? P такой, что x +
? a(x, u?) ? S + B?u , и алгоритма, который для любых множества S ? ? и вектора x ?
Rn \ (B?S) позволяет определить вектор v? = v?(x, S) ? Q такой, что x + ? b(x, v?) ? (Rn \
S) + B?v . Здесь числа ?u и ?v определяют погрешности соответствующих алгоритмов.
Если зафиксировать некоторые векторы u? ? P , v? ? Q и положить u?(x, S) = u?
при x 6? A?S , v?(x, S) = v? при x ? B?S , то будут определены функции
u? : Rn Ч ? ? P,
(22)
v? : Rn Ч ? ? Q.
Аналогично второй главе определяются числа ?0u , ?0v , ?u , ?v и предполагается,
что имеются алгоритмы, которые для любого множества S ? ? вычисляют множества
Du S ? ?, Dv S ? ? такие, что справедливы включения (14). Также предполагается
монотонность по включению операторов Du и Dv .
Пусть зафиксировано положительное число ? и начальные множества M0u ? ?,
M0v ? ? попятной конструкции задаются включениями
M + B???M ? M0u ? M + B? ,
M + B? C ? M0v ? M + B? C+?M .
Здесь число ?M ? (0, ?) определяет погрешность начальной аппроксимации. Двигаясь
в сторону увеличения индекса i и используя алгоритмы, существование которых мы
предположили, вычисляются наборы игровых множеств достижимости {Miu }Ii=0 ,
{Miv }Ii=0 :
u
Mi+1
= (A?B?Du Miu ) ? Miu ,
v
Mi+1
= (B? A?Dv Miv ) ? Miv ,
i ? 0, I ? 1.
С использованием функций (22) и игровых множеств достижимости, следующим
образом определяются позиционные стратегии управления. Для любого вектора x ?
Rn \ M0u положим i(x) = max{i ? 0, I ? 1 : x 6? Miu }, а для любого x ? Rn \ M1v
v
обозначим j(x) = max{j ? 0, I ? 1 : x 6? Mj+1
}. Теперь для любого x ? Rn определим
(
u
x ? M0u ,
?,
str
u (x) =
u
u? x, B?Du Mi(x)
, x ? Rn \ M0u ,
17
(23)
str
v (x) =
(
v?,
x ? M1v ,
v
v? x, A?Dv Mj(x)
, x ? Rn \ M1v .
(24)
Основными результатами этого параграфа являются следующие теоремы.
Теорема 8. Пусть i ? 0, I , x0 ? Miu , стратегия ustr определена соотношением (23).
Тогда закон управления (ustr , T ) гарантирует ?-поимку на отрезке [0, ?i ] для начального состояния x(0) = x0 .
/ Miv , стратегия v str определена соотношением
Теорема 9. Пусть i ? 0, I ? 1, x0 ?
(24). Тогда закон управления (v str , T ) гарантирует уклонение на отрезке [0, ?i+1 ] для
начального состояния x(0) = x0 .
Определим числа
4 +
?
?
?0 = ?u + ?v + 2?D + ?+
A + ?A + ?B + ?B ,
3
?0 = ? (C + Cb ) + 2?M + ?u + ?D + (? Cb + ?0 (I ? 1))e(??? )L .
Теорема 10. Пусть ? ? ?0 , число ? выбрано так, что ? Lxb < 21 . Тогда
Miv ? Miu
?i ? 0, I ? 1.
(25)
Теорема 11. Пусть стратегии ustr , v str определены соотношениями (23), (24).
Пусть число ? ? ? C + 2?M выбрано так, что выполняется условие (25). Тогда пара
законов управления ((ustr , Tu ), (v str , Tv )) является ?-оптимальной.
Четвертый параграф третьей главы посвящен доказательству теорем 811.
В пятом параграфе третьей главы для игр на плоскости конкретизируются
алгоритмы, существование которых предполагалось в третьем параграфе. При тех
же предположениях, что и в пятом параграфе второй главы, с использованием тех
же алгоритмов получается алгоритм для построения эпсилон-оптимальных стратегий
для игры с нефиксированным временем окончания на плоскости. Суммарная оценка
погрешности этого алгоритма имеет следующую оценку сверху
?0 < 2?M + ? 2 (3LC + 40Lxa Ca ) + 10? Lxa h + 2? Lua hP +
+ ? C + Cb (1 + ?e?L ) + ?e?L (3LC + 94(Lxa Ca + Lxb Ca )) +
+ 23?e?L Lh + 2?e?L (Lua hP + Lvb hQ ).
(26)
В последней, четвертой главе рассматриваются результаты численных экспериментов.
В первом параграфе четвертой главы рассмотрена дифференциальная игра
с фиксированным временем окончания и динамикой нелинейного маятника. Приведены результаты расчета игровых множеств достижимости и графики зависимости
теоретической оценки погрешности и погрешности, реализовавшейся на практике, от
18
параметра дискретизации по времени при условии, что остальные параметры дискретизации линейно зависят от него. Эти графики свидетельствуют о том, что на практике
погрешность хорошо согласуется с теоретической оценкой.
Во втором параграфе четвертой главы рассмотрена дифференциальная игра
с динамикой нелинейного маятника, но уже с нефиксированным временем окончания,
а также ее модификация, в которой в правой части дифференциального уравнения динамики системы стоит недифференцируемая функция. Для этих двух игр приведены
результаты расчета игровых множеств достижимости.
Заключительный, третий параграф четвертой главы посвящен игре
ѕшофер-убийцаї и ее модификациям. В классическом варианте этой игры динамика
управляемой системы в редуцированном двумерном пространстве описывается нелинейной системой дифференциальных уравнений
x?(t) = ?y(t)u(t) + vx (t),
y?(t) = x(t)u(t) ? 1 + vy (t),
t ? [0, ?].
Первый игрок выбирает управление u(t), второй управление v(t) = (vx (t), vy (t)) ?
R2 . Управления игроков подчинены ограничениям
|u(t)| ? 1,
q
vx (t)2 + vy (t)2 ? ?
?t ? [0, ?],
где ? скалярный параметр.
На рис. 1 изображены результаты расчетов с использованием упрощенной пошаговой конструкции
u
bGa B
bGb Miu ) ? Miu ,
Mi+1
= (A
i ? 0, I ? 1.
Рис. 1: Результаты расчета упрощенной пошаговой конструкции при ? = 0.1. Целевое множество круг радиуса 1 с центром в точке (2, 0). Вычисления проведены до
момента времени ? = 4.7, изображено каждое 100-ое сечение.
19
Эти и другие приведенные в этом параграфе результаты свидетельствуют о том,
что для приближенного расчета игровых множеств достижимости можно использовать упрощенную пошаговую конструкцию. Помимо этого, в третьем параграфе приведены результаты расчета игровых множеств достижимости и графики зависимости
теоретической и практической погрешности от различных параметров дискретизации.
Обе зависимости оказываются близки к линейным. Так, на рис. 2 показаны графики практической погрешности алгоритма и его теоретической погрешности, умноженной на коэффициент 0.23, в зависимости от параметра ? при условии, что h = 5? ,
hP = hQ = 2.5? .
Рис. 2: Теоретическая и практическая погрешности алгоритма в зависимости от параметра ? при линейной зависимости остальных параметров дискретизации от ? .
В заключении приводятся основные результаты диссертации и проводится сравнение предложенных алгоритмов с известными аналогами. В работах1 , 2 предложены
алгоритмы построения ?-оптимальных стратегий для нелинейных дифференциальных
игр и получены оценки погрешностей этих алгоритмов. В отличие от указанных работ, в которых оценки погрешностей (19), (26) предлагаемых алгоритмов имеют вид
c1 ? + c2 h/? + c3 ? , где c1 , c2 , c3 константы зависящие только от задачи, ? параметр
дискретизации по времени, h параметр дискретизации по пространству фазовой переменной, ? параметр дискретизации по пространствам управлений, предложенный
в данной работе алгоритм имеет оценку погрешности вида c1 ? +c2 h+c3 ? , что позволяет
для получения лучшей точности уменьшать параметр h со скоростью, пропорциональной ? , а не ? 2 .
Проведенные численные эксперименты показывают, что на практике погрешность
хорошо согласуется с теоретической оценкой. Также численные результаты по построению множеств уровня цены игры в игре ѕшофер-убийцаї и одной из ее модификаций
1 Иванов
Г.Е. Алгоритм решения нелинейной игровой задачи быстродействия // Фундаментальные задачи и проблемы современной математики: Сб. науч. трудов / М. МФТИ: 2011. С. 4976.
2 Иванов Г.Е. Алгоритм построения оптимальной стратегии управления в нелинейной дифференциальной игре с
липшицевой финитной платой // Дифференциальные уравнения, Т. 48, ќ4, 2012. C.551564.
20
хорошо согласуются с полученными в работе3 с использованием алгоритма из4 . В отличие от этого алгоритма, предложенный в данной работе алгоритм может также
вычислять оптимальные стратегии и для него в данной работе получены детальные
оценки погрешности.
Предложенный в данной работе алгоритм для игры с нефиксированным временем
окончания может быть также использован для построения множеств уровня функции
цены в линейных дифференциальных играх с нефиксированным временем окончания,
5
рассмотренных в работе
? . Алгоритм, предложенный в указанной статье имеет оценку
погрешности порядка ? , где ? параметр дискретизации по времени. Предложенный
в данной работе алгоритм имеет для указанных линейных игр погрешность порядка
?.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
1. Доказаны теоремы об оценке близости истинных значений операторов Минковского и их численных аппроксимаций в двумерном случае.
2. Получены новые топологические, геометрические и экстремальные свойства операторов Минковского.
3. Предложены алгоритмы построения эпсилон-оптимальных стратегий для нелинейных дифференциальных игр с целевым множеством как с фиксированным
временем окончания, так и с нефиксированным временем окончания, использующие модифицированные операторы Минковского.
4. Доказаны теоремы о том, что построенные стратегии игрока-преследователя и
игрока-убегающего для любой начальной позиции гарантируют, соответственно,
эпсилон-поимку или уклонение.
5. Получены оценки погрешностей предложенных алгоритмов, линейно зависящие
как от параметра дискретизации по времени, так и от параметра дискретизации
по фазовому пространству.
6. Показано, что полученные в численных экспериментах реальные погрешности
предложенных алгоритмов имеют близкий к линейному характер зависимости
от параметров дискретизации, что соответствует теоретическим результатам работы.
3 Пацко
В.С., Турова В.Л.
ринбург: УрО РАН, 2009.
Игра шофер-убийца: история и современные исследования. Научные доклады. Екате-
4 Patsko
V.S., Turova V.L. Level Sets of the Value Function in Dierential Games with the Homicidal Chaueur Dynamics
// International Game Theory Review, V. 3, ќ1, 2001. pp. 67112.
5 Турова В.Л. Построение множеств позиционного поглощения в линейной дифференциальной игре второго порядка
с нефиксированным временем окончания. // Управление с гарантированным результатом, Свердловск, 1987. С.92
112.
21
ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ
1. Двуреченский П.Е., Иванов Г.Е. Алгоритм построения оптимальной стратегии
в нелинейной дифференциальной игре с использованием конволюты // Труды
МФТИ 2011. Т. 3, ќ1 С. 6167.
2. Двуреченский П.Е., Иванов Г.Е. Алгоритм построения оптимальной стратегии
в нелинейной дифференциальной игре c нефиксированным временем окончания
// Труды МФТИ 2012. Т. 4, ќ4 C. 5161.
3. Двуреченский П.Е. Алгоритм поиска оптимальных стратегий для дифференциальной игры с целевым множеством на нефиксированном интервале времени. //
Теория и практика системного анализа: Труды II Всероссийской научной конференции молодых ученых с международным участием. Т.II. /Рыбинск: РГАТУ
имени П. А. Соловьева, 2012. С. 1424.
4. Двуреченский П.Е. Алгоритм построения оптимальных стратегий для дифференциальной игры быстродействия с целевым множеством. // Современные проблемы фундаментальных и прикладных наук. Управление и прикладная математика. Т.1: Труды XLV научной конференции. /Моск. физ. техн. ин-т. М.
Долгопрудный, 2012. С. 1920.
5. Двуреченский П.Е. Программный комплекс для построения оптимальных стратегий в дифференциальных играх. // Материалы XIX научно-технической конференции молодых ученых и специалистов. 1418 ноября 2011 г. Часть 2. / Под
ред. доктора технических наук В.В. Синявского; Ракетно-космическая корпорация ѕЭнергияї им. С.П.Королева. XII ќ3. /г. Королев: Типография РКК
ѕЭнергияї им. С.П.Королева, 2012. С. 3842.
6. Двуреченский П.Е. Об одном алгоритме построения оптимальной стратегии в
нелинейной дифференциальной игре на плоскости с использованием конволюты.
// Системный анализ и информационные технологии: Труды Четвертой международной конференции. Т.1. /Челябинск: Изд-во Челяб. гос. ун-та, 2011. С.
179181.
7. Двуреченский П.Е. О построении оптимальной стратегии в нелинейной дифференциальной игре на плоскости. // Сборник трудов Всероссийской молодежной
конференции ѕПерспективы развития фундаментальных наукї, проводимой в
рамках Второй международной научной школы для молодежи ѕПрикладные математика и физика: от фундаментальных исследований к инновациямї: сб. науч.
тр. М.: МФТИ, 2011. С. 56.
8. Двуреченский П.Е. Программный комплекс для построения оптимальных стратегий в дифференциальных играх. // Современные проблемы фундаментальных
и прикладных наук. Часть VII. Управление и прикладная математика. Т.1:
22
Труды XLIII научной конференции. /Моск. физ. техн. ин-т. М. Долгопрудный, 2010. С. 17.
23
Двуреченский Павел Евгеньевич
АЛГОРИТМЫ ПОСТРОЕНИЯ ЭПСИЛОН-ОПТИМАЛЬНЫХ СТРАТЕГИЙ В
НЕЛИНЕЙНЫХ ДИФФЕРЕНЦИАЛЬНЫХ ИГРАХ НА ПЛОСКОСТИ
АВТОРЕФЕРАТ
Подписано в печать 10.10.2013. Формат 60 Ч 84 1/16 . Усл. печ. л. 1,0.
Тираж 100 экз. Заказ ќ318
Федеральное государственное автономное образовательное учреждение
высшего профессионального образования ѕМосковский физико-технический
институт (государственный университет)ї
Отдел оперативной полиграфии ѕФизтех-полиграфї
141700, Московская обл., г. Долгопрудный, Институтский пер., 9
?вается h(X, Y ) = max{h+ (X, Y ), h+ (Y, X)}. Мноn
гозначное отображение G : Rn ? 2R удовлетворяет условию Липшица с константой
LG в смысле метрики Хаусдорфа, если h(G(x1 ), G(x2 )) ? LG kx1 ?x2 k
?x1 , x2 ? Rn .
Приведем некоторые свойства операторов Минковского.
6
Лемма 1. Пусть многозначное отображение G : Rn ? 2R принимает замкнутые
n
значения и удовлетворяет условию Липшица с константой LG < 1 в смысле метрики Хаусдорфа. Пусть задано множество S ? Rn и точки x0 ? int S , y0 ? x0 + G(x0 ).
Тогда для множества AG S , определенного первым соотношением (1), справедливо
включение y0 ? int AG S .
Лемма 2. Пусть многозначное отображение G : Rn ? 2R принимает замкнутые
n
значения и непрерывно в смысле метрики Хаусдорфа. Пусть множество S ? Rn
замкнуто и supx?S supu?G(x) kuk < +?. Тогда множество AG S замкнуто.
Лемма 3. Пусть многозначное отображение G : Rn ? 2R принимает замкнутые
n
значения и удовлетворяет условию Липшица с константой LG < 1 в смысле метрики Хаусдорфа. Тогда для любого множества S ? Rn и любого числа ? > 0 операторы
Минковского (1) удовлетворяют включениям
AG S + B?/(1+LG ) ? AG S + B? ? AG S + B?/(1?LG ) ,
? B
? B , B S+B ?B S+B
AG S ?
?
A
S
?
G
?
G
?
G
?/(1?LG )
?/(1?LG ) ,
? B
? B ?B S?
? B
.
?B S?
B S?
G
?/(1?LG )
G
?
G
?/(1+LG )
Во втором параграфе первой главы вводятся необходимые для работы с плоскими многоугольниками определения, состоящие в следующем. Пусть задан набор
точек ak ? R2 , k = 1, m, причем ak+1 6= ak для любого k ? 1, m ? 1. Упорядоченный
набор отрезков {[a1 , a2 ], [a2 , a3 ], . . . , [am?1 , am ]} называется ломаной ?(a1 , . . . , am ), точки ak называются вершинами, а отрезки [ak , ak+1 ] звеньями этой ломаной. Ломаная
?(a1 , . . . , am ) называется замкнутой, если am = a1 . Ломаная ?(a1 , . . . , am ) называется
простой замкнутой, если m > 1, am = a1 и из того, что z ? [aj , aj+1 ] ? [ak , ak+1 ],
1 ? j < k < m следует, что k = j + 1 и z = ak . Простым многоугольником называется ограниченное замкнутое множество S ? R2 такое, что его границей ?S является
простая замкнутая ломаная. Вершинами простого многоугольника S называются вершины ломаной ?S . Запись ? + S и ? ? S обозначает границу простого многоугольника S ,
ориентированную соответственно против часовой стрелки и по часовой стрелке. Выпуклым многоугольником называется выпуклая оболочка конечного числа точек в R2 .
Через ha, bi обозначено скалярное произведение векторов a ? Rn и b ? Rn . Нормальным конусом выпуклого множества X ? Rn в точке x0 ? X называется множество
N (x0 , X) = {p ? Rn | hp, xi ? hp, x0 i ?x ? X}. Для любого ненулевого вектора
z ? R2 через (0, z · ?) обозначен луч {tz | t ? (0, +?)}. Для любых двух ненулевых
векторов a ? R2 и b ? R2 через ?(a, b) обозначено множество всех ненулевых векторов, лежащих на лучах, полученных путем вращения луча (0, a · ?) против часовой
стрелки до луча (0, b · ?). Правым перпендикуляром для вектора a = (ax , ay )T ? R2
называется вектор a? = (ay , ?ax )T .
В третьем параграфе первой главы вводится понятие конволюты многоугольника и многозначного отображения на плоскости, состоящее в следующем. Пусть многозначное отображение G каждому вектору x ? R2 ставит в соответствие выпуклый
7
многоугольник G(x). Пусть ?0 = ?(x1 , . . . , xn , xn+1 ) замкнутая ломаная. Для любого j ? 1, n обозначим pj = (xj+1 ? xj )? , положим p0 = pn . Для каждого j ? 1, n
j
j
рассмотрим g1 , . . . , gm
пронумерованные против часовой стрелки все вершины мноj
гоугольника G(xj ) такие, что
j
N (gm
, G(xj )) ? ?pj?1 pj 6= ?,
m ? 1, mj .
(2)
j
Если условию (2) удовлетворяют все вершины многоугольника G(xj ), то вершину g1
j
будем определять из условия pj?1 ? N (g1 , G(xj )) (если таких точек окажется нескольj
ко, то будем выбирать вершину g1 как любую, удовлетворяющую еще и условию
hxj ?xj?1 , g1j i ? hxj ?xj?1 , gi для всех вершин g многоугольника G(xj ), удовлетворяющих условию pj?1 ? N (g, G(xj )). Пусть при этом g? последняя против часовой стрелки
j
вершина многоугольника G(xj ), не совпадающая с g1 . Если pj ? N (g?, G(xj )), то будем
j
j
= g1j .
= g? , иначе будем полагать gm
полагать gm
j
j
Конволютой для многозначного отображения G и замкнутой ломаной ?0 называется замкнутая ломаная
1
2
n
CG (?0 ) = ?(x1 + g11 , . . . , x1 + gm
, x2 + g12 , . . . , x2 + gm
, . . . , xn + g1n , . . . , xn + gm
, x1 + g11 ).
1
2
n
(3)
n
Будем рассматривать max-норму вектора x ? R : kxk? = maxk?1,n |xk |, где xk k -ая компонента вектора x.
При получении оценок расстояния между границей образов операторов Минковского (1) и конволютой, а также между образами операторов Минковского и извлеченными из конволюты их аппроксимациями считаются выполненными следующие
предположения:
A1: S простой (вообще говоря невыпуклый) многоугольник, длины (относительно
max-нормы) сторон которого не превосходят числа h;
A2: значением многозначного отображения G является отрезок, т.е. G(x) =
[g1 (x), g2 (x)];
A3: функции g1 , g2 : R2 ? R2 удовлетворяют условию Липшица (относительно
1
max-нормы) с константой LG ? 10
;
A4: выполнены неравенства kg1 (x) ? g2 (x)k?
?
dG
<
+?,
2
max{kg1 (x)k? , kg2 (x)k? } ? CG < +? ?x ? R .
Параметры h, LG , dG и CG считаются малыми и определяют точность работы
алгоритмов. Методы обоснования предложенных алгоритмов применимы и к более
общему случаю, когда значением многозначного отображения G является выпуклый
многоугольник, вершины которого удовлетворяют условию Липшица как функции от
точки x. Однако в силу значительной технической сложности доказательств данная
работа ограничивается наиболее важным частным случаем, когда множество G(x)
является отрезком.
Близость конволюты и границ образов операторов Минковского выражается в следующих лемме и теореме.
8
Лемма 4. Пусть в пространстве R2 введена некоторая норма k · k. Пусть мно2
гозначное отображение G : R2 ? 2R принимает выпуклые компактные значения
и удовлетворяет условию Липшица с константой LG относительно нормы k · k в
смысле метрики Хаусдорфа. Пусть длины звеньев (в смысле нормы k · k) замкнутой ломаной ? ? R2 не превосходят числа h. Тогда относительно нормы k · k для
конволюты (3) и первого из операторов Минковского (1) справедливо неравенство
h+ (CG (?), AG ?) < LG h.
Пусть границей множества S ? R2 является простая замкнутая ломаная ?. Будем
говорить, что ломаная ? ориентирована положительно относительно множества S
и писать ? = ? + S , если при обходе ломаной ? в направлении ее ориентации множество
S остается слева.
Теорема 1. Пусть границей множества S ? R2 является простая замкнутая ломаная ? + S , ориентированная положительно относительно множества S , длины (в
смысле max-нормы) звеньев ломаной ? + S не превосходят числа h. Пусть выполнены
предположения A2A4. Тогда (в смысле max-нормы)
h+ (?AG S, CG (? + S)) < (16dG + 7h)LG .
В третьем параграфе также приведены примеры, показывающие точность оценки
в теореме 1 и показывающие сложность получения этой оценки.
Пятый параграф первой главы целиком посвящен доказательству теоремы 1
с использованием вспомогательных утверждений четвертого параграфа.
В шестом параграфе первой главы приводятся необходимые определения и
алгоритмы, позволяющие извлечь из конволюты границы множеств, являющихся аппроксимациями образов операторов Минковского.
Для любой замкнутой ломаной ? ? R2 ее дополнение R2 \ ? состоит из конечного
числа непересекающихся областей, одна из которых неограничена. Дополнение к этой
неограниченной области называется доменом ? и обозначается Domain ? . Граница домена замкнутой ломаной ? называется внешним контуром ? и обозначается ExtC ? :
ExtC ? = ?(Domain ?).
Пусть заданы замкнутая ломаная ? ? R2 и точка x0 ? (Domain ?) \ ? . Замыкание множества всех точек x ? R2 , которые можно соединить с точкой x0 ломаной, не
пересекающейся с ? , называется внутренним (относительно точки x0 ) доменом ? и
обозначается IntDomx0 ? . Граница внутреннего домена замкнутой ломаной ? называется внутренним контуром ? и обозначается IntCx0 ? : IntCx0 ? = ?(IntDomx0 ?).
bG S и B
bG S , аппроксимирующие множества AG S , BG S , опредеМногоугольники A
ляются следующим образом:
bG S = IntDomx (CG (? ? S)).
B
0
bG S = Domain(CG (? + S)),
A
Приведенные в этом параграфе алгоритмы вычисления внешнего и внутреннего относительно точки x0 контуров замкнутой ломаной позволяют вычислить границы многоbG S и B
bG S . В качестве x0 берется любая точка, удовлетворяющая вклюугольников A
?
? B
чению x0 ? S ?
(16dG +8h)LG +CG ? Domain(CG (? S)).
9
Главными результатами шестого параграфа являются следующие теорема и лемма.
Теорема 2. Пусть в пространстве R2 введена max-норма. Пусть выполнены предположения A1A4. Пусть ?1 = LG h,
?2 = (16dG + 7h)LG . Под Br будем понимать
замкнутый шар радиуса r в max-норме. Пусть множества
? B ,
BG S ?
?1
? B ,
bG S ?
B
?2
2
R \ (AG S + B?1 ) ,
2
bG S + B?
R \ A
2
связны. Тогда справедливы включения
bG S + B? ,
AG S ? A
2
bG S ? AG S + B? ,
A
1
? B ?B
bG S,
BG S ?
?1
? B ? B S.
bG S ?
B
?2
G
Лемма 5. Пусть выполнены условия теоремы 2. Пусть множества A?G S, B?G S опре-
делены следующим образом:
bG S + B? ,
A?G S = A
2
Тогда при ? =
LG (16dG +8h)
1?LG
? B .
bG S ?
B?G S = B
?2
справедливы включения
AG S ? A?G S ? AG (S + B? ) ,
? B ? B? S ? B S.
BG S ?
G
G
?
Седьмой параграф первой главы посвящен модифицированным операторам
Минковского A?G : 2E ? 2E , B?G : 2E ? 2E , определяемым равенствами
A?G S = {x ? E | (x ? G(x)) ? S 6= ?},
E \ B?G S = A?G (E \ S)
(4)
для любого множества S ? E . При этом B?G S = {x ? E | x ? G(x) ? S} ?S ? E .
Далее доказывается несколько свойств модифицированных операторов, аналогичных свойствам операторов Минковского (1), приведенным в первом параграфе, и теорема о том, что алгоритмы шестого параграфа могут быть использованы для приближенного вычисления также и образов модифицированных операторов Минковского.
Теорема 3. Пусть выполнены условия леммы 5. Тогда справедливы включения
? B ? A? S ? A? S + B ,
A?G S ?
??
G
G
?+
?
B?G S ? B?+ ? B?G S ? B?G S + B??
где
?? =
LG CG
,
1 ? LG
?+ = LG CG +
?1 + ?2
(16dG + 8h)LG
= LG CG +
.
1 ? LG
1 ? LG
Таким образом, для любого простого многоугольника S описанные в первой главе алгоритмы вычисляют множества A?G S , B?G S , которые являются аппроксимациями
значений модифицированных операторов Минковского. Эти алгоритмы использованы
10
в следующих главах для построения эпсилон-оптимальных гарантированных стратегий управления в нелинейных дифференциальных играх. С использованием оценок
теоремы 3 получены общие оценки погрешностей рассматриваемых в третьей и четвертой главах алгоритмов.
Во второй главе рассматривается нелинейная дифференциальная игра с целевым
множеством и фиксированным временем окончания и предлагается алгоритм для построения эпсилон-оптимальных стратегий в такой игре.
Первый параграф второй главы посвящен постановке задачи и перечислению
принятых предположений. Рассматривается дифференциальная игра
x(t) ? Rn ,
x?(t) = a(t, x(t), u(t)) + b(t, x(t), v(t)), t ? [0, ?],
u(t) ? P ? Rp , v(t) ? Q ? Rq ?t ? [0, ?]
Предполагается, что функции a : [0, ?] Ч Rn Ч P ? Rn и b : [0, ?] Ч Rn Ч Q ? Rn
непрерывны, а также, что вектограммы a(t, x, P ) = {a(t, x, u) : u ? P }, b(t, x, Q) =
{b(t, x, v) : v ? Q} выпуклы при всех t ? [0, ?], x ? Rn . Также предполагается заданным целевое компактное множество M ? Rn .
Если выполняется x(?) ? M , то в игре имеет место поимка. Если выполняется
x(?) ?
/ M , то в игре имеет место уклонение. Цель первого игрока состоит в поимке,
цель второго игрока в уклонении.
Пусть в Rn задана некоторая норма k · k. Расстоянием от точки x ? Rn до
множества Y ? Rn называется величина %(x, Y ) = inf y?Y kx ? yk. Неравенство
%(x(?), M ) ? ? означает, что в конечный момент времени имеет место ?-поимка.
Предполагается, что функции a : [0, ?] Ч Rn Ч P ? Rn и b : [0, ?] Ч Rn Ч Q ? Rn
удовлетворяют следующим условиям Липшица:
ka(t1 , x1 , u1 ) ? a(t2 , x2 , u2 )k ? Lta |t1 ? t2 | + Lxa kx1 ? x2 k + Lua ku1 ? u2 k
?t1 , t2 ? [0, ?], x1 , x2 ? Rn , u1 , u2 ? P ;
kb(t1 , x1 , v1 ) ? b(t2 , x2 , v2 )k ?
Ltb |t1
? t2 | +
Lxb kx1
Lvb kv1
? x2 k +
? v2 k
?t1 , t2 ? [0, ?], x1 , x2 ? Rn ,
v1 , v2 ? Q;
(5)
ka(t, x, u)k ? Ca
?t ? [0, ?],
x?R ,
u ? P;
(6)
(7)
kb(t, x, v)k ? Cb
?t ? [0, ?],
x ? Rn ,
v ? Q.
(8)
Обозначим
C = Ca + Cb ,
n
L = Lxa + Lxb .
(9)
Во втором параграфе второй главы описано в каком классе стратегий ищутся оптимальные стратегии и какие реализации действий противника предполагаются
возможными.
Пусть задан отрезок [t0 , t1 ] ? [0, ?]. Множеством U[t0 , t1 ] допустимых реализаций управления первого игрока называется множество всех измеримых функций
u : [t0 , t1 ] ? P . Аналогично задается множество V[t0 , t1 ] допустимых реализаций
управления второго игрока.
11
I
Пусть заданы число t0 ? [0, ?) и начальное состояние x(t0 ) = x0 . Пусть T = {?i }i=0
разбиение отрезка [t0 , ?] : t0 = ?0 < ?1 < · · · < ?I = ?. Кусочно-постоянной
стратегией первого игрока, соответствующей разбиению T , называется набор функI?1
str
n
ций ustr
T = {ui : R ? P }i=0 . Движением, соответствующим начальному состоянию
x(t0 ) = x0 , разбиению T , стратегии первого игрока ustr
T и допустимой реализации
управления v ? V[t0 , ?], называется функция x : [t0 , ?] ? Rn , определяемая из пошагового уравнения
x?(t) = a(t, x(t), ustr
T (x(?i ))) + b(t, x(t), v(t)),
которое должно выполняться при почти всех t ? [?i , ?i+1 ] и всех i ? 0, I ? 1. При этом
начальная позиция для отрезка [?0 , ?1 ] равна x0 , а начальная позиция x(?i ) для отрезка
[?i , ?i+1 ] совпадает с конечной позицией x(?i ) отрезка [?i?1 , ?i ].
str
Обозначим движение следующим образом: xmot
u (t, t0 , x0 , T, uT , v). Аналогично определяются кусочно-постоянная стратегия второго игрока vTstr и движение
str
xmot
v (t, t0 , x0 , T, u, vT ).
Кусочно-постоянная стратегия ustr
T гарантирует ?-поимку для начального состояния x0 , если для любой реализации управления v ? V[0, ?] выполняется неравенstr
str
ство % (xmot
u (?, 0, x0 , T, uT , v), M ) ? ?. Кусочно-постоянная стратегия vT гарантирует уклонение для начального состояния x0 , если для любой реализации управлеstr
/ M . Пара кусочнония u ? U[0, ?] выполняется соотношение xmot
v (?, 0, x0 , T, u, vT ) ?
str str
постоянных стратегий (uT , vT ) называется ?-оптимальной, если для любого начального состояния x0 ? Rn выполняется хотя бы одно из условий:
1) стратегия ustr
T гарантирует ?-поимку или
str
2) стратегия vT гарантирует уклонение.
В третьем параграфе второй главы введены одношаговые операторы достижимости, описан алгоритм построения стратегий и сформулированы теоремы о его
погрешности без конкретизации способа построения образов одношаговых операторов
достижимости.
Пусть зафиксировано натуральное число I и произведено равномерное разбиение
T = {?i }Ii=0 отрезка [0, ?], где ?i = i? , i ? 0, I . Шаг ? = ?/I разбиения T называется
параметром дискретизации по времени.
Для любого множества S ? Rn и любого индекса i ? 0, I ? 1 определяются множества
Ai S = {x ? Rn :
Bi S = {x ? Rn :
?u ? P :
?v ? Q :
x + ? a(?i , x, u) ? S},
x + ? b(?i , x, v) ? S}.
Таким образом, определены одношаговые операторы достижимости Ai , Bi .
Для любого i ? 0, I рассматриваются выпуклозначные многозначные отображения
a
Gi , Gbi , заданные формулами
Gai (x) = ?? a(?i , x, P ),
Gbi (x) = ?? b(?i , x, Q) ?i ? 0, I
?x ? R2 .
Из определений модифицированных операторов Минковского (4) следуют равенства
Ai = A?Gai , Bi = B?Gbi ?i ? 0, I .
12
Из соотношений (5) (8) следует, что LGai = ? Lxa , CGai = ? Ca , dGai = 2? Ca , LtGai =
? Lta , LGbi = ? Lxb , CGbi = ? Cb , dGbi = 2? Cb , LtGb = ? Ltb .
i
Пусть ? класс множеств в Rn , с которым работают алгоритмы. Все используемые для построения стратегий множества аппроксимируются множествами из этого
класса.
В данном параграфе часть алгоритмов, являющихся внутренними по отношению
к алгоритму поиска оптимальных стратегий, не конкретизируются, а лишь предполагается, что они существуют и имеются оценки их погрешностей. Так, предполагается,
что реально для каждого множества S ? ? и индекса i ? 0, I вычисляются множества
A?i S , B?i S класса ?, удовлетворяющие условиям
? B ? ) ? A? S ? A (S + B + ),
Ai (S ?
i
i
?A
?A
? B + ) ? B? S ? B (S + B ? ),
Bi (S ?
i
i
?B
?B
(10)
+
?
+
где числа ??
A , ?A , ?B , ?B определяют погрешности этих алгоритмов.
Также предполагается существование алгоритма, который для любых множества
S ? ?, индекса i ? 0, I ? 1 и вектора x ? A?i S позволяет определить вектор u?i =
u?i (x, S) ? P такой, что
x + ? a(?i , x, u?i ) ? S + B?u ,
(11)
и алгоритма, который для любых множества S ? ?, индекса i ? 0, I ? 1 и вектора
x ? Rn \ (B?i S) позволяет определить вектор v?i = v?i (x, S) ? Q такой, что
x + ? b(?i , x, v?i ) ? (Rn \ S) + B?v .
(12)
Здесь числа ?u и ?v определяют погрешности соответствующих алгоритмов.
Зафиксируем некоторые векторы u? ? P , v? ? Q и положим u?i (x, S) = u? при
x 6? A?i S , v?i (x, S) = v? при x ? B?i S . Тем самым при всех i ? 0, I ? 1 определены
функции
u?i : Rn Ч ? ? P,
v?i : Rn Ч ? ? Q.
(13)
Обозначим
?0u = ? 2
Lta + Ltb
+ LC + Lxb Ca ,
2
x
?u = ?0u + ??
B + (1 + ? Lb )?u ,
?0v = ? 2
Lta + Ltb
+ LC + Lxa Cb ,
2
x
?v = ?0v + ??
A + (1 + ? La )?v .
Предполагается, что имеются алгоритмы, которые для любого множества S ? ? вычисляют множества Du S ? ?, Dv S ? ? такие, что
? B
?
S?
?u +?D ? Du S ? S ? B?u ,
S + B?v ? Dv S ? S + B?v +?D ,
(14)
где число ?D определяет погрешность этих алгоритмов.
Пусть зафиксировано положительное число ?. Начальные множества MIu ? ?,
MIv ? ? попятной конструкции определяются следующим образом:
M + B???M ? MIu ? M + B? ,
13
M ? MIv ? M + B?M .
(15)
Здесь число ?M ? (0, ?) определяет погрешность начальной аппроксимации.
Двигаясь в сторону уменьшения индекса i и используя алгоритмы, существование
которых мы предположили, вычисляются наборы игровых множеств достижимости
v I?1
{Miu }I?1
i=0 , {Mi }i=0 :
u
Miu = A?i B?i Du Mi+1
,
v
Miv = B?i A?i Dv Mi+1
Для любых i ? 0, I ? 1 и x ? Rn , с использованием функций (13) и игровых
множеств достижимости Miu , Miv , определяются стратегии игроков
u
ui (x) = u?i (x, B?i Du Mi+1
),
(16)
v
vi (x) = v?i (x, A?i Dv Mi+1
).
(17)
Перечислим основные результаты третьего параграфа второй главы.
I?1
Теорема 4. Пусть x0 ? M0u , стратегия ustr
T = {ui }i=0 определена соотношением
(16). Тогда стратегия ustr
T гарантирует ?-поимку на отрезке [0, ?] для начального
состояния x(0) = x0 .
Теорема 5. Пусть x0 ? Rn \ M0v , стратегия vTstr = {vi }I?1
i=0 определена соотношением
(17). Тогда стратегия vTstr гарантирует уклонение на отрезке [0, ?] для начального
состояния x(0) = x0 .
Определим числа
4 +
4 2 t
?
?
?0 = ?u + ?v + 2?D + ?+
+
?
+
?
? Lb ,
+
?
+
A
A
B
3 B
3
?0 = ? Cb + 2?M + ?u + ?D + (? Cb + ?0 I)e?L .
Теорема 6. Пусть ? ? ?0 , ? Lxb < 21 . Тогда
M0v ? M0u .
(18)
Теорема 7. Пусть ? ? ?M и справедливо включение (18). Тогда пара кусочноstr
постоянных стратегий (ustr
T , vT ) является ?-оптимальной.
Четвертый параграф второй главы посвящен доказательству теорем 47.
Наконец, в пятом параграфе второй главы для игр на плоскости конкре-
тизируются алгоритмы, существование которых предполагалось в третьем параграфе. Предполагается, что каждая из вектограмм a(t, x, P ) = {a(t, x, u) | u ? P } и
b(t, x, Q) = {b(t, x, v) | v ? Q} либо является отрезком, либо не зависит от x. В этом параграфе используется max-норма. Алгоритмы строятся следующим образом. Зафиксируем натуральное число I ? 10? max{Lxa , Lxb } и рассмотрим равномерное разбиение
T = {?i }Ii=0 отрезка [0, ?], где ?i = i? , i ? 0, I , ? = ?/I . Зафиксируем число h > 0.
Игровые множества достижимости будем аппроксимировать простыми многоугольниками, длины сторон которых не превосходят числа h. Пусть P? и Q? сетки на множествах P и Q с мелкостями hP и hQ соответственно, т.е. множества P? ? P и Q? ? Q
14
состоят из конечного числа элементов P? =
j JP
JQ
u? j=1 , Q? = v? j j=1
и hP = h+ (P, P? ),
hQ = h+ (Q, Q?), где h+ уклонение множеств.
Зафиксируем произвольное число ? > 0. Приблизим множества M + B? и M соответственно простыми многоугольниками MIu и MIv с точностью ?M ? (0, ?) так, чтобы
выполнялись включения (15).
В качестве операторов приближенного вычисления образов одношаговых операторов достижимости будем использовать операторы A?Gai , B?Gbi введенные в лемме 5.
Таким образом, в соотношениях (10) можно положить A?i = A?Gai , B?i = B?Gbi ?i ? 0, I .
Выбор вектора u?i (x, S) ? P , для которого справедливо включение (11) производится следующим образом. Пусть задан номер i ? 0, I ? 1 и точка x ? A?i S . Вычислим
с помощью алгоритма второго параграфа первой главы множество S + B?+A +? Lua hP ? x
и перебором по j ? 1, JP найдем такой вектор u?j , что выполняется включение
? a(?i , x, u?j ) ? S + B?+A +? Lua hP ? x. Вектор u?j и будет искомым. Аналогичный алгоритм
позволяет найти вектор v?i (x, S) ? Q, для которого справедливо включение (12).
Использование max-нормы позволяет использовать алгоритм поиска суммы Минковского двух многоугольников из второго параграфа первой главы для вычисления
без погрешности суммы и разности Минковского многоугольника S и шара в этой нор? B ,
ме. Это означает, что в соотношениях (14) можно положить ?D = 0, Du S = S ?
?u
Dv S = S + B?v .
Используя теорему 3, получаем следующую оценку сверху для числа ?0 :
t
t
x
2 La + Lb
+ 3LC + 40La Ca + 10? Lxa h + 2? Lua hP +
?0 < 2?M + ?
2
+ ? Cb (1 + ?e?L ) + ?e?L 3(Lta + Ltb ) + 3LC + 94(Lxa Ca + Lxb Ca ) +
+ 23?e?L Lh + 2?e?L (Lua hP + Lvb hQ ).
(19)
В третьей главе рассматривается нелинейная дифференциальная игра с целевым множеством и нефиксированным временем окончания и предлагается алгоритм
для построения эпсилон-оптимальных стратегий в такой игре. Структура и содержание третьей главы аналогичны структуре и содержанию второй главы. Поэтому
ограничимся перечислением отличий в содержании.
В первом параграфе третьей главы приводится постановка задачи и перечисляются принятые предположения. Рассматривается динамическая система, описываемая автономным дифференциальным уравнением
x?(t) = a(x(t), u(t)) + b(x(t), v(t)),
где t ? [0, ?] время, число ? определяет максимальную продолжительность игры.
Остальные предположения совпадают с предположениями второй главы. Если существует момент времени t ? [t0 , t1 ] такой, что x(t) ? M , то на отрезке [t0 , t1 ] имеет место
поимка. Иначе, то есть если x(t) ?
/ M при всех t ? [t0 , t1 ], то на отрезке [t0 , t1 ] имеет
место уклонение. Цель первого игрока состоит в минимизации числа ?0 ? [0, ?] такого,
что на отрезке [0, ?0 ] обеспечена поимка. Цель второго игрока обеспечить уклонение на отрезке [0, ?] или, если это невозможно, максимизировать время ?0 ? [0, ?]
15
такое, что на отрезке [0, ?0 ] обеспечено уклонение. Будем говорить, что на отрезке
[t0 , t1 ] ? [0, ?] имеет место ?-поимка, если существует такой момент времени t ? [t0 , t1 ],
что %(x(t), M ) ? ?.
Во втором параграфе третьей главы описано в каком классе стратегий ищутся оптимальные стратегии и какие реализации действий противника предполагаются возможными. Допустимыми реализациями управлений игроков считаются те же,
что и во второй главе. Позиционной стратегией первого игрока называется произI
вольная функция ustr : Rn ? P . Пусть T = {?i }i=0 разбиение отрезка [t0 , t1 ] ?
[0, ?] : t0 = ?0 < ?1 < · · · < ?I = t1 . Пара (ustr , T ) называется законом управления
первого игрока на отрезке [t0 , t1 ]. Движением, соответствующим начальному состоянию x(t0 ) = x0 , закону управления (ustr , T ) и допустимой реализации управления
v ? V[t0 , t1 ], называется абсолютно непрерывная функция x : [t0 , t1 ] ? Rn , определяемая из пошагового уравнения x?(t) = a(x(t), ustr (x(?i ))) + b(x(t), v(t)), которое должно
выполняться при почти всех t ? [?i , ?i+1 ] и всех i ? 0, I ? 1. При этом начальная позиция для отрезка [?0 , ?1 ] равна x0 , а начальная позиция x(?i ) для отрезка [?i , ?i+1 ]
совпадает с конечной позицией x(?i ) отрезка [?i?1 , ?i ]. Обозначим движение следуюstr
щим образом: xmot
u (t, t0 , x0 , T, u , v) = x(t) ?t ? [t0 , t1 ]. Аналогично определяются
str
позиционная стратегия второго игрока v str и движение xmot
v (t, t0 , x0 , T, u, v ).
Закон управления (ustr , T ) гарантирует ?-поимку на отрезке [t0 , t1 ] для начального
состояния x0 , если для любой реализации управления v ? V[t0 , t1 ] существует момент
str
времени t ? [t0 , t1 ] такой, что выполняется неравенство % (xmot
u (t, t0 , x0 , T, u , v), M ) ?
?. Закон управления (v str , T ) гарантирует уклонение на отрезке [t0 , t1 ] для начального состояния x0 , если для любой реализации управления u ? U[t0 , t1 ] выполняется
str
/M
?t ? [t0 , t1 ].
соотношение xmot
v (t, t0 , x0 , T, u, v ) ?
Пусть задано число ? > 0 и законы управления (ustr , Tu ), (v str , Tv ) первого и
второго игроков на отрезке [0, ?]. Пара законов ((ustr , Tu ), (v str , Tv )) называется ?оптимальной, если для любого начального положения x0 ? Rn такого, что %(x0 , M ) >
? выполняется альтернатива:
1) существует момент времени ?0 ? [0, ?] такой, что закон управления (ustr , Tu ) гарантирует ?-поимку на отрезке [0, ?0 ], а закон управления (v str , Tv ) гарантирует уклонение на отрезке [0, ?0 ], либо
2) закон управления (v str , Tv ) гарантирует уклонение на отрезке [0, ?].
В третьем параграфе третьей главы введены одношаговые операторы достижимости для игры с нефиксированным временем, описан алгоритм построения стратегий и сформулированы теоремы о его погрешности без конкретизации способа построения образов одношаговых операторов достижимости. Как и ранее рассматривается
равномерное разбиение отрезка [0, ?] с шагом ? = ?/I . Одношаговые операторы достижимости A и B задаются равенствами
AS = {x ? Rn :
BS = {x ? Rn :
?u ? P :
?v ? Q :
для любого множества S ? Rn .
16
x + ? a(x, u) ? S},
x + ? b(x, v) ? S},
(20)
(21)
Для игры с нефиксированным временем окончания рассматриваются выпуклозначные многозначные отображения Ga , Gb с замкнутыми значениями, заданные формулами Ga (x) = ?? a(x, P ), Gb (x) = ?? b(x, Q) ?x ? R2 . Из определений модифицированных операторов Минковского (4) следует, что A = A?Ga , B = B?Gb .
Справедливы следующие
Документ
Категория
Без категории
Просмотров
8
Размер файла
1 493 Кб
Теги
нелинейные, оптимальное, построение, игра, дифференциальной, алгоритм, эпсилон, плоскости, стратегия
1/--страниц
Пожаловаться на содержимое документа