Содержание к диссертации
Введение
Глава 1 Позиционные процедуры управления для систем, линейных по управлению второго игрока 29
1.1 Введение 29
1.2 Постановка игровой задачи о сближении в фиксированный момент времени. Конструкции u-стабильных мостов в игровой задаче 29
1.2.1 Постановка игровой задачи о сближении в фиксированный момент времени 29
1.2.2 Оператор стабильного поглощения и стабильные мосты в игровой задаче о сближении с целью в фиксированный момент времени 32
1.2.3 Аппроксимирующая система множеств (W(n)(t.): tf є Гп} 39
1.3 Первый вариант процедуры управления с поводырём первого игрока, базирующейся на копировании управлений 50
1.4 Второй вариант позиционной процедуры управления с поводырём первого игрока, базирующейся на копировании управлений 64
Глава 2 Игровая задача о сближении на конечном промежутке времени. Некоторые способы приближённого построения максимальных и-стабильных мостов 72
2.1 Введение 72
2.2 Постановка игровой задачи о сближении на промежутке [to, 9] .73
2.3 Оператор стабильного поглощения и u-стабильные мосты в игровой задаче о сближении на промежутке [t0, 0] 75
2.4 Аппроксимирующая система множеств в задаче о сближении на промежутке [to, 0] и её свойства 85
Глава 3 Алгоритмы обработки множеств позиционного поглощения .101
3.1 Введение 101
3.2 Информационная структура дерева n-мерных кубов и некоторые алгоритмы работы с ней 103
3.2.1 Информационная структура дерева n-мерных кубов 103
3.2.2 Процедура добавления точки (вокселя) 106
3.2.3 Шаблон алгоритма обхода n-мерных кубов с заданной процедурой. 113
3.2.4 Алгоритм выделения граничных вокселей 115
3.2.5 Алгоритм построения информационной структуры дерева п-мерных кубов в соответствии с заданной функцией 118
3.2.6 Алгоритм объединения двух информационных структур деревьев n-мерных кубов 119
3.2.7 Алгоритм пересечения двух информационных структур деревьев п-мерных кубов 121
3.2.8 Алгоритм заливки области пространства R" 123
3.3 Алгоритмы, необходимые для построения максимального и стабильного моста 127
3.3.1 Алгоритм нахождения вокселя с минимальным значением заданной функции 127
3.3.2 Метод построения выпуклой оболочки конечного множества точек в пространстве R" 132
3.3.3 Построение выпуклой оболочки конечного множества точек в R", заданных «центрами» вокселей из информационной структуры дерева п-мерных кубов 142
3.3.4 Алгоритм приближённого вычисления максимального и-стабильного моста 155
3.3.5 Алгоритм построения управления 158
3.4. Алгоритмы визуализации 162
3.4.1 Алгоритм построения нормалей в граничных вокселях 162
3.4.2 Алгоритм подготовки к визуализации информационной структуры дерева n-мерных кубов 167
3.4.3 Алгоритм визуализации без кэширования 168
3.4.4 Алгоритм визуализации с кэшированием 172
Глава 4 Применение вексельных методов расчёта и визуализации при конструировании максимальных u-стабильных мостов и движений 178
4.1 Введение 178
4.2 Экологическая задача на соотношение двух видов 179
4.3 Дифференциальная игра «шофёр-убийца» 182
4.4 Дифференциальная игра «шофёр-убийца» с модифицированными ограничениями на управления второго игрока 188
4.5 Дифференциальная игра «шофёр-убийца» с модифицированной динамикой 190
4.6 Дифференциальная игра «шофёр-убийца» с ограниченным ускорением в трёхмерном пространстве 194
Заключение 196
Библиографический список использованной литературы 197
- Постановка игровой задачи о сближении в фиксированный момент времени. Конструкции u-стабильных мостов в игровой задаче
- Постановка игровой задачи о сближении на промежутке [to, 9]
- Информационная структура дерева n-мерных кубов и некоторые алгоритмы работы с ней
- Дифференциальная игра «шофёр-убийца» с модифицированными ограничениями на управления второго игрока
Введение к работе
Диссертация посвящена исследованию дифференциальных игр с геометрическими ограничениями на управления игроков. Изучаются антагонистические позиционные дифференциальные игры двух игроков на конечном промежутке времени.
Рассматриваются, в основном, две игровые задачи о сближении конфликтно-управляемой системы с целевым множеством в конечномерном фазовом пространстве.
В первой игровой задаче конфликтно-управляемая система является линейной по управлению второго игрока. Первому игроку требуется построить позиционный способ управления, обеспечивающий сближение системы с целевым множеством в конечный момент из заданного промежутка времени, как бы ни действовал при этом второй игрок в рамках заданных ограничений на управления.
Во второй задаче рассматривается конфликтно-управляемая система общего вида. Первому игроку требуется построить позиционный способ-управления, обеспечивающий сближение с целевым множеством на заданном промежутке времени, то есть не позже конечного момента из заданного промежутка времени. В рамках этой крупной задачи в диссертации рассмотрена подробно и изучена та часть задачи, которая относится к построению множества позиционного поглощения, т.е. множества всех точек в пространстве позиций, из которых разрешима задача о сближении.
Эта часть игровой задачи о сближении является наиболее трудной для решения.
Отметим, что обе игровые задачи рассматриваются в рамках теории позиционных дифференциальных игр [16-38,53-55,85-96], развиваемой Уральской математической школой по теории управления, руководимой Н.Н. Кра-совским. К настоящему времени в теории дифференциальных игр накоплен богатый арсенал методов, ориентированных на исследование и решение упомянутых игровых задач и ряда других не менее значимых задач.
Большое значение для становления и развития теории дифференциальных игр сыграли исследования отечественных математиков.
Л.С. Понтрягиным было введено в работах [73,74] важное в теории дифференциальных игр понятие альтернированного интеграла. Направление теории дифференциальных игр, базирующееся на этом понятии, было развито в дальнейшем в работах самого Л.С. Понтрягина [75-78] и других математиков [1,15,36,51,52,71,72]. Ряд работ Е.Ф. Мищенко и его учеников также посвящены дифференциальным играм [40,47,48,79].
Н.Н. Красовским была предложена позиционная формализация дифференциальных игр [19-21], охватывающая дифференциальные игры в общей постановке. Эта формализация, основу которой составил принцип экстремального прицеливания на стабильные мосты, указывает путь к построению разрешающего позиционного управления. Теория позиционных дифференциальных игр развивалась в дальнейшем в работах Н.Н. Красовского, его сотрудников А.Б. Куржанского, Ю.С. Осипова, А.И. Субботина и их учеников [4,14,15,16,22-38,41,53-55,85-94].
Важные результаты в теории дифференциальных игр были получены в Киеве Б.Н. Пшеничным и его учениками А.А. Чикрием, Ю.Н. Онопчуком, В.В. Остапенко [80-84,56-58,109,110].
Большой вклад в развитие теории дифференциальных игр внесли Ф.Л. Черноусько, А.А. Меликян и их сотрудники [44-46,108]. Здесь отметим монографию Ф.Л. Черноусько и А.А. Меликяна [108], посвященную игровым задачам механики.
Значительные результаты были получены также Э.Г. Альбрехтом, В.Д. Батухтиным, Н.Л. Григоренко, В.И. Жуковским, М.И. Зеликиным, А.Ф. Клейменовым, А.Н. Красовским, А.В. Кряжимским, Ю.С. Ледяевым, Н.Ю. Лукояновым, В.И. Максимовым, М.С. Никольским, О.И. Никоновым, B.C. Пацко, Н.Н. Петровым, Н.Никандр. Петровым, Л.А. Петросяном, Н.Н. Субботиной, A.M. Тарасьевым, В.Е. Третьяковым, А.А. Успенским, В.И. Ухобо-товым, А.Г. Ченцовым, СВ. Чистяковым и другими.
К зарубежным математикам, получившим значительные результаты в теории дифференциальных игр, следует отнести Р.Айзекса [2], Д. Бреквелла [115, 116], В. Флеминга [117,118].
В настоящее время прежде всего практические потребности обуславливают развитие теории дифференциальных игр. Этому развитию способствует также в значительной мере наличие высокопроизводительной вычислительной техники.
Задачи, в которых управляемая динамическая система подвержена неконтролируемым помехам, в реальной жизни встречаются достаточно часто. Эти задачи могут быть формализованы как дифференциальные игры. Среди них существенную долю составляют задачи, которые можно трактовать как игровые задачи наведения управляемой системы на заданное целевое множество. В таких задачах на передний план выступает проблема построения множеств разрешимости — таких множеств в пространстве позиций, из которых разрешима задача гарантированного наведения на целевое множество. Как оказывается, эти множества обладают очень важным свойством - свойством стабильности. В теории позиционных дифференциальных игр понятие стабильности и стабильного моста составляет один из основных элементов экстремальной конструкции, решающей задачу гарантированного наведения на целевое множество. Эта конструкция была введена в теорию дифференциальных игр, рассматриваемых в общей постановке, в работах [26-30] Н.Н. Красовского и А.И. Субботина конца 60-х и начала 70-х годов предыдущего века. В силу сложности игровых задач наведения даже в относительно простых случаях не удаётся получить эффективное аналитическое описание стабильного моста. Поэтому актуальной становится проблема приближённого вычисления (максимальных) стабильных мостов и разработка методов и алгоритмов приближённого вычисления этих мостов. В случае, когда удалось сконструировать стабильный мост, относительно просто построить позиционный способ управления, разрешающий игровую задачу наведения на целевое множество. В качестве такого способа может быть выбрана позиционная стратегия первого игрока, базирующаяся на правиле экстремального прицеливания на стабильный мост, или же некоторая позиционная процедура управления с поводырём первого игрока. Отметим, что в случае выбора позиционной процедуры управления с поводырём в качестве позиционного способа управления поводырь формируется как некоторое вспомогательное движение для управляемой системы, идущее по стабильному мосту [30, 87].
В теории дифференциальных игр существуют различные подходы к решению центральной задачи выделения множеств разрешимости в пространстве позиций.
Так, для линейных дифференциальных игр наведения на выпуклое целевое множество Л.С. Понтрягиным в 60-е годы предыдущего столетия был предложен метод построения множества разрешимости для первого игрока как метод конструирования альтернированного интеграла (альтернированного интеграла Л.С. Понтрягина) [73,74]. Развитию метода альтернированного интеграла в теории дифференциальных игр как с геометрическими, так и интегральными ограничениями на управления игроков, посвящены работы сотрудников и учеников Л.С. Понтрягина [1,51,52,71,72,78], а также работы последнего времени А.Б. Куржанского и его учеников[14,15,36-38].
Другим методом, направленным на решение задачи вычисления множества разрешимости, является метод программных итераций в теории позиционных дифференциальных игр, предложенный в 70-е годы предыдущего столетия А.Г. Ченцовым и развиваемый им и его сотрудниками [104-107,114] по настоящее время. В этом направлении проводились также исследования В.И. Ухоботовым [99] и СВ. Чистяковым [111].
В методе программных итераций стабильный мост конструируется как предел некоторой убывающей последовательности замкнутых множеств в пространстве позиций. Каждое из этих множеств определяется в терминах программных игровых конструкций с учётом уже построенного ранее элемента последовательности.
Поскольку точное определение моста с помощью эффективных аналитических соотношений затруднено даже в относительно простых случаях, стоит серьёзная проблема разработки методов и алгоритмов приближённого вычисления стабильных мостов в позиционных дифференциальных играх. Достаточно эффективным в решении этой проблемы является путь, использующий идеологию попятных пошаговых (по времени) конструкций, отправляющихся в последний момент времени из заданного промежутка от целевого множества. Этот путь родственен по духу методу динамического программирования Р. Беллмана [5]. Этим конструкциям, введённым в теорию позиционных дифференциальных игр весьма общего вида в [26-30], посвящено значительное количество исследований [6,7,10,12,31 33,59,60,93,94,100-103,133]. Методам, базирующимся на идеологии попятных пошаговых конструкций, посвящена и настоящая диссертация. В основе ис следований, представленных в диссертации, лежат работы Н.Н. Красовского, А.И. Субботина, В.Н. Ушакова, A.M. Тарасьева [30,88,93,94,100-103], выполненные в последние десятилетия.
Кроме сложности построения стабильных мостов существует ещё и сложность хранения информации о них. В основе настоящей диссертации лежат предшествующие работы [59-61], которые уже используют пиксельные методы построения и хранения стабильных мостов. Здесь эти методы будут распространены на задачи более высоких размерностей, стабильные мосты будут аппроксимированы наборами кубиков в пространствах соответствующих размерностей. Координаты вершин этих кубиков будут привязаны к сетке. Однако сам набор кубиков нужно каким-то образом хранить так, чтобы с одной стороны место, отводимое под них, было не очень большим, а с другой стороны скорость выполнения необходимых алгоритмов над этим представлением набора кубиков была бы высокой; кроме всего прочего нам хотелось бы уметь визуализировать этот набор кубиков. Для этого, например, в трёхмерном случае лучше всего использовать структуру, называемую octree [121,123-128] или восьмеричное дерево. Впервые применительно к графике она упоминается в работе 1978 года R.Reddy и S.Rubin [121]. Эта структура может быть распространена на другие размерности, например, для двумерного случая она известна как quadtree[122] или дерево квадратов. Octree давно используется как компактное средство хранения трёхмерной информации с целью последующей визуализации; это видно из работ N. Stolte, A. Kaufman [123,124], D. Benson, J. Davis[125], S. Lefebvre, S. Hornus, F. Neyret[126],T. Moller, R. Machiraju, T. Ertl, M. Chen[127]. Работа Jingliang Peng, C.C. Jay Kuo [128] показывает, что octree может также использоваться для компактного представления полигональных объектов. В диссертационной работе используется дерево для визуализации поверхности множества способом, похожим на тот, что изложен в работах N. Stolte и A. Kaufrnan[124], однако, их алгоритм вычисления нормалей не может быть применён к задачам визуализации, рассматриваемым здесь. В диссертации приведён более эффективный алгоритм визуализации, чем те которые рассмотрены в [123-128]. Также в настоящей работе трёхмерное понятие вокселя расширено на всевозможные размерности.
Цель диссертационной работы - проведение теоретических исследований и получение теоретических результатов, обосновывающих решение рассматриваемых игровых задач о сближении. Другой, не менее важной целью, является разработка эффективных алгоритмов приближённого построения решений рассматриваемых игровых задач о сближении, а также решение задачи о представлении результатов вычисления в наглядном виде.
При достижении поставленных целей используются:
1. идеология приближённого попятного построения стабильных мостов;
2. пошаговые конструкции управления с поводырём первого игрока, включающие составным элементом копирование управлений; 3. приближённые воксельные представления множеств, вычисляемых в процессе конструирования решений игровых задач о сближении;
4. информационная структура данных восьмеричного дерева и его расширения на другие pa3MepHOCTn(quadtree, octree, ) с целью компактного представления набора вокселей и ускорения алгоритмов работы с набором вокселей, включая алгоритмы визуализации.
В первой главе диссертации рассматривается игровая задача о сближении в фиксированный момент времени, стоящая перед первым игроком. Управления первого и второго игроков стеснены геометрическими ограничениями.
Формулируются игровые задачи о сближении и об уклонении, стоящие перед первым и вторым игроками соответственно. Решение этих задач требуется определить в классах позиционных процедур управления с поводырём первого игрока.
Опишем несколько подробнее постановку игровой задачи о сближении в фиксированный момент 9, поскольку она является одним из предметов исследования в настоящей диссертации.
В задаче о сближении в момент 8, стоящей перед первым игроком, требуется обеспечить попадание из точки x[t0]=x0 движения x[t] системы (1), (2) в момент 0 на компактное множество М, содержащееся в Rm. Решение задачи требуется обеспечить в классе позиционных процедур управления с поводырём первого игрока[30].
В этой постановке М выступает как целевое множество.
Особо отметим, что в постановке задачи о сближении речь идёт о позиционных процедурах управления первого игрока. Это предполагает, что первый игрок формирует свои управления на базе информации о реализовавшихся позициях (t,x[t]) системы (1), (2) и информации о позиции (t,y[t]) вспомогательной системы, именуемой поводырём.
В пункте 1.2.1 уточняется понятие множества позиционного поглощения W°c:[to,0]xRm — множества разрешимости игровой задачи о сближении. В работах [26-30] показано, что W0 — максимальный u-стабильный мост.
Свойство u-стабильности — одно из центральных понятий, используемых в диссертации. Оно означает слабую инвариантность множества W0 относительно некоторого семейства дифференциальных включений, тесно связанных с системой (1), (2).
В растровой графике очень часто применяется операция заливки, в которой замена цвета распространяется через грани соседних вокселеи, имеющих заданный исходный цвет. Как будет показано в пункте 3.2.8, в информационной структуре дерева n-мерных кубов эта операция также реализуется, причём время её исполнения может не уступать времени работы алгоритмов, использующихся в растровой графике в аналогичных случаях.
В параграфе 3.3 описаны математические алгоритмы, необходимые для реализации алгоритма построения максимального u-стабильного моста.
В пункте 3.3.2 предложен и обоснован метод построения выпуклой оболочки конечного множества точек в n-мерном пространстве. На базе этого метода в пункте 3.3.3 предложен эффективный алгоритм построения выпуклой оболочки конечного множества точек, представленных центрами вокселеи, описанных при помощи информационной структуры дерева п-мерных кубов. При создании этого эффективного алгоритма использовался в качестве вспомогательного алгоритм нахождения вокселя с минимальным значением заданной функции (пункт 3.3.1). Алгоритм построения выпуклой оболочки отличается от тех, что уже существуют в библиотеках qhull[129] и CGAL[130], тем, что он быстрее, чем упомянутые алгоритмы, и, что самое важное, позволяет строить выпуклую оболочку, в случаях, если её размерность получается меньше размерности исходного пространства. Кроме того, он более устойчив, чем соответствующий алгоритм из библиотеки
CGAL[130]. В пункте 3.3.4 приводится алгоритм приближённого вычисления максимального u-стабильного моста, в создании которого и заключалась одна из основных целей настоящей диссертационной работы. Он с незначительной модификацией подходит как для моделирования задачи в момент, так и задачи сближения к моменту. Именно для реализации этого алгоритма потребовалась разработка алгоритма построения выпуклой оболочки множества.
В пункте 3.3.5 приводится алгоритм вычисления движения, порождённого разрешающей позиционной процедурой управления с поводырём первого игрока в задачах о сближении на конечном промежутке времени. В процессе выполнения этого алгоритма используются данные, полученные алгоритмом вычисления максимального u-стабильного моста.
В параграфе 3.4 приводятся алгоритмы, связанные с визуализацией множеств. Рассматриваемые в настоящей диссертации множества таковы, что для их анализа достаточно визуализировать границы множества. Однако в отличие от случая, представленного в работах N. Stolte, A. Kaufman[124], в нашем случае нет возможности вычислить градиент задающей функции и таким образом нормаль в граничной точке. Поэтому пришлось сформулировать другие соответствующие ситуации определения нормалей и разработать алгоритмы их вычисления; они представлены в пункте 3.4.1. Из этих двух приведённых алгоритмов на практике был реализован только первый, и в некоторых редких случаях (когда часть множества становится «тонкой») видны его недостатки.
В отличие от алгоритмов, представленных в работах N. Stolte, A. Kaufman [123,124], в этой диссертационной работе нет необходимости визуализировать каждый воксель множества. Визуализируются только те кубы из дерева, которые в значительной степени определяют результирующую картинку и, таким образом, значительно уменьшается время визуализации. Однако для этого необходимо знать для каждого куба цвет (хотя фактически в этой работе цвет не используется - он всегда серый) и нормаль. Считая, что для наиболее мелких кубов - векселей эта информация уже известна, можно построить её для более крупных кубов с использованием алгоритма, приведённого в пункте 3.4.2.
Для построения одиночной картинки достаточно алгоритма, приведённого в пункте 3.4.3. Однако, если мы хотим использовать визуализацию для интерактивного (с точки зрения пользователя) процесса изучения множества (например, максимального u-стабильного моста), то нам может пригодиться техника, давно известная как кэширование, которая наиболее часто применяется для частичного сохранения медленно получаемых данных в памяти, откуда их можно извлечь значительно быстрее. Алгоритм визуализации с использованием этой техники приводится в пункте 3.4.4.
Постановка игровой задачи о сближении в фиксированный момент времени. Конструкции u-стабильных мостов в игровой задаче
Пусть задана конфликтно-управляемая система, поведение которой на промежутке времени [to,9] (to 9 oo) определяется векторным дифференциальным уравнением Здесь f - норма вектора f в соответствующем евклидовом пространстве.
Будем рассматривать дифференциальную игру сближения-уклонения управляемой системы (1.1), (1.2), которая складывается из задачи о сближении и задачи об уклонении (см. [30]).
В задаче о сближении, стоящей перед первым игроком, требуется обеспечить попадание из точки x[to]=Xo движения x[t] системы (1.1), (1.2) в момент 0 на компактное множество М, содержащееся в Rm. Решение задачи требуется обеспечить в классе позиционных процедур управления с поводырём первого игрока [30].
В задаче об уклонении, стоящей перед вторым игроком, требуется обеспечить уклонение из точки xfoj xo движения x[t] системы (1.1), (1.2) от некоторой с-окрестности Мє (є 0) множества М. Решение задачи требуется определить в классе позиционных процедур управления второго игрока .
Отметим, что в постановке задачи об уклонении число є 0 своё персональное для каждой точки x[to]=Xo- Кроме того, игровые задачи о сближении и уклонении точно так же, как и для начальной точки x[to]=Xo, могут быть сформулированы для произвольной точки (t ,x[t,])=(t ,x ) из [t0, 9]xRm.
Для сформулированной дифференциальной игры справедлива альтернатива [26-30]: существует такое замкнутое множество W z[to,0]xRm, называемое множеством позиционного поглощения, что для всех исходных позиций (t ,x )eW разрешима задача о сближении, а для всех исходных позиций (t ,x )e([to,0]xRm)\W разрешима задача об уклонении.
Важный факт, который был установлен при этом, состоит в том, что W0 есть максимальный u-стабильный мост, т.е. максимальное множество в [to,G]xRm, содержащееся в множестве (0, М)={(0, х): х є М} и обладающее свойством u-стабильности. Свойство же u-стабильности есть свойство, означающее наличие слабой инвариантности множества W0 относительно некоторого набора дифференциальных включений, тесно связанных с системой (1.1), (1.2). Следует отметить, что свойство слабой инвариантности базируется на концепции инвариантности, очень распространённой в современной математике и, в частности, в теории оптимального управления, дифференциальных игр, алгебре, теории чисел и математическом анализе.
Определение свойства стабильности можно дать различными способами: существуют, начиная с конца 60-х годов XX века, несколько формулировок этого свойства. Самая ранняя формулировка этого свойства появилась в работах Н.Н. Красовского и А.И. Субботина (см., например, [28,29]). В 70-е годы XX века в теории дифференциальных игр формулируется новое направление — унификация дифференциальных игр. Здесь, прежде всего, следует отметить исследования [22,23] Н.Н. Красовского, в которых было дано определение унификационных моделей, изучены их свойства и указаны перспективы применения в различных классах дифференциальных игр. Суть унификации, представленной в [22,23], состоит в том, что свойство стабильности выражается в терминах векторов сопряжённых переменных и гамильтониана управляемой системы (1.1), (1.2).
Также важный момент заключается в том, что унификация в последние десятилетия успешно используется для разработки методов и алгоритмов приближённого вычисления множества W0 позиционного поглощения в различных игровых задачах о сближении (см., например [10,94,100-103,59,60]).
В следующем пункте определим основные конструкции стабильности, в основе которых лежит унификация. Эти конструкции развивают концепцию стабильности, представленную в работах [26-30].
Будем рассматривать задачу о сближении системы (1.1),(1.2) с целевым множеством М в момент 0.
Как отмечалось выше, W есть максимальный u-стабильный мост в этой задаче о сближении. Стабильность некоторого множества W, содержащегося в [to,0]xRm, означает слабую инвариантность W относительно включений, связанных с (1.1), (1.2) и рассматриваемых на [to,6]. Семейство дифференциальных включений мы определим здесь, следуя работам [92,101], при помощи условий (аксиом) АЛ — А.З.
Для этого введём в рассмотрение функцию (гамильтониан системы) где 1, f — скалярное произведение векторов 1 и f из Rm. Определим при помощи условий АЛ - А.З оператор стабильного поглощения, задающий свойство u-стабильности множеств W в рассматриваемой задаче о сближении.
Не нарушая общности рассуждений и принимая во внимание условие Б, наложенное на конфликтно-управляемую систему (1.1), (1.2), выделим в пространстве [to, G]xRm позиций (t,x) системы (1.1), (1.2) такую достаточно большую ограниченную и замкнутую область D, что она содержит все конструкции нашей игровой задачи о сближении (движения управляемой системы (1.1), (1.2), движения поводыря, u-стабильные мосты W, а также множество (6, М) = {(0,х) є [to, 9]xRm; х є М}).
Постановка игровой задачи о сближении на промежутке [to, 9]
В этом параграфе излагается постановка игровой задачи о сближении на конечном промежутке времени и предлагаются алгоритмы приближённого вычисления множества позиционного поглощения для конфликтно-управляемой системы общего вида. При этом укажем, как будут выглядеть соотношения, описывающие аппроксимирующую систему множеств для конфликтно-управляемой системы, линейной по управлению второго игрока.
Пусть задана конфликтно-управляемая система, поведение которой на [t0, 6] (-co t0 6 oo) описывается векторным дифференциальным уравнением Здесь x — m-мерный фазовый вектор системы, и и v - управления первого игрока и второго игроков соответственно, Р и Q - компакты в евклидовых пространствах Rp и Rq. Предполагается, что выполнены условия: А. Вектор-функция f(t,x,u,v) непрерывна по совокупности переменных t,x,u,v и для любой ограниченной и замкнутой области D z[to,9]xRm существует такая константа L=L(D)e(0,oo), что
В. Существует такая константа ує(0,оо), что Рассматриваемая здесь дифференциальная игра сближения-уклонения складывается из задачи о сближении и задачи об уклонении [30].
В задаче о сближении, стоящей перед первым игроком, требуется обеспечить попадание фазового вектора x[t] системы (2.1) не позже момента 9 на ограниченное и замкнутое терминальное множество М в пространстве Rm. Решение задачи требуется обеспечить в классе позиционных стратегий U(t,x) или в классе позиционных процедур управления первого игрока.
В задаче об уклонении, стоящей перед вторым игроком, требуется обеспечить уклонение фазового вектора x[t] системы (2.1) от М на всем промежутке времени [to,6]. Решение задачи требуется обеспечить в классе контрстратегий V(t,x,u) второго игрока или его контр-позиционных процедур управления с поводырем [30].
В этой дифференциальной игре, как и в игре с фиксированным моментом окончания, важно уметь вычислять множество позиционного поглощения W , которое представляет собой совокупность всех исходных позиций (t ,x ), для каждой из которых существует позиционная стратегия U(t,x), обеспечивающая при любых допустимых помехах V(t,x,u) второго игрока выполнение включения х[т]єМ в некоторый момент xe[t ,9]. Момент т, вообще говоря, свой для каждой помехи V(t,x,u).
Однако какое-либо эффективное аналитическое описание множества W0, позволяющее вычислять это множество, в общем случае отсутствует. В связи с этим актуальным является вопрос о приближенном построении W0. Во второй главе рассматриваются алгоритмы приближенного построения W , базирующиеся на попятных конструкциях и унификации.
Важную роль в вычислении множества WcD играет свойство и-стабильности [26-30], которым обладает это множество. Так же, как и в задаче о сближении в фиксированный момент, стабильность множества W0 означает слабую инвариантность W0 относительно некоторого семейства дифференциальных включений, связанных с (2.1) и рассматриваемых на [t0,6]. Но эта слабая инвариантность несколько отличается от слабой инвариантности множеств в задаче о сближении в фиксированный момент; здесь ещё учитывается специфика задачи о сближении на конечном промежутке времени. Постараемся здесь объяснить, в чём состоит эта специфика.
Так же, как и в задаче о сближении в фиксированный момент, считаем, что ограниченная замкнутая область D выбрана настолько большой в полосе [t0,9]xRm пространства R xR"1, что множества W0 и WN— [t0,9]xM, а также все множества из аппроксимирующей конструкции (см. параграф 2.4) содержатся в D; здесь McRm - терминальное множество в нашей задаче.
Считаем также, что задано некоторое множество W элементов \\J и семейство {Fv: ij/e } отображений Fv: (t,x) ь- F,v(t,x)c:Rm, (t,x)eD, удовлетворяющих условиям АЛ, А.2, А.З (см. гл.1. стр. 33).
Приведём одно из самых ранних определений стабильности некоторого ограниченного замкнутого множества W, содержащегося в D. Это определение [30] дано в терминах семейства отображений UI- V(U)GQ, иєР и отвечающих им отображений Fv(.): (t,x) ь- FV(.)(t,x)eR; (t,x)sD, заданных равенством FV(.)(t,x) = co{f(t,x,u,v(u)): иєР}, (t,x) є D.
Определение 2.1 [30]. Непустое замкнутое множество WczD называется и-стабильным мостом в игровой задаче о сближении с М на промежутке [t0,0], если W(0)czM и для любых (t ,t )єЕ, (U,x )eW и UH- V(U)GQ существует решение x[t] дифференциального включения удовлетворяющее включению (t ,x[t ])eW или включению (т, x[x])eWM при некотором Tet»,t J. Здесь символ W(t) определён на стр. 13, ui- v(u)eQ — борелевское отображение.
Информационная структура дерева n-мерных кубов и некоторые алгоритмы работы с ней
Для этого представим координаты Хі,х2,...,хп в виде таблицы, строками которой будут соответствующие двоичные представления координат (рис. 3.1). При этом, введя один целочисленный параметр а, можно посмотреть на таблицу координат, представленных в двоичном виде, как на задающую набор вложенных кубов со стороной равной 2а. При этом здесь и далее мы считаем биты координат с номером, меньшим, чем а, произвольными (тогда множество точек со строго заданными фиксированными старшими битами координат и не связанными какими-либо ограничениями, младшими битами, является кубом со стороной 2а). Для простоты дальнейшей организации ограничим а снизу нулём (ос 0), чтобы избежать дробных чисел, а сверху некоторым числом m (поэтому 0 a m). На 32-битных машинах удобнее выбирать т=32; обычно этого ограничения достаточно. Если мы зафиксируем все числа bj (i=l,2,...n, j=0,l,...,m-l), то, изменяя а (но, по-прежнему, не связывая биты координат, меньшие по номеру, чем а, никаким ограничениями), мы получим ряд вложенных кубов, сходящийся при 0,=0, к некоторому конкретному вокселю, заданному этими битами b j, или, что тоже самое — координатами Xj. Однако, для представления произвольно заданного набора вокселей, одной такой таблицы недостаточно и для сохранения иерархии вложенных кубов нам потребуется использовать понятие 2п-арного дерева.
Здесь и далее информационную структуру, хранящую информацию об аппроксимирующем наборе вокселей, будем называть деревом n-мерных кубов. Опишем подробнее, из чего состоит эта информационная структура, т.е. дерево n-мерных кубов.
Под узлом такого дерева будем понимать некоторую структуру участка памяти, описывающую один куб в пространстве Rn, которая включает в себя массив из 2" описателей вложенных кубов. Под описателем будем понимать маленький объём информации (на 32-битных машинах удобнее выделять под описатель 32 бита памяти), который либо описывает соответствующий вложенный куб целиком, либо ссылается на другой узел дерева. Для того чтобы отличить ссылку от описания, будем использовать старший из 32 бит; в случае, если он - 0, будем считать, что оставшиеся 31 бит используются под ссылку (индекс в массиве) на узел. Кроме того, в случае, если куб пуст (пустая ссылка), полагаем оставшиеся 31 бит содержащими нули, т.е. полагаем в этом случае, что весь описатель равен 0. Это означает, что ни один узел не может иметь нулевой индекс. В случае если старший бит отличен от 0, полагаем оставшиеся 31 бит содержащими описание того, что находится в кубе. Проще назвать в этом случае такое описание цветом куба. Кроме массива описателей в узле хранится индекс (вышестоящего) непосредственного узла-родителя (естественно, что старший из 32 бит этого индекса равен 0, так, что можно считать, что это — (2п+1)-ый описатель).
Заметим, что информации, находящейся в узле дерева, недостаточно для определения координат куба; поэтому, кроме узла куба, необходимо такое понятие как ссылка на узел-куб. Здесь и далее под ссылкой на узел-куб понимаем тройку:. индекс узла в массиве узлов;. соответствующий кубу параметр а, далее называемый уровнем узла-куба;. Координаты куба, т.е. старшие биты bj(i=l,2,...n, j=a,ot+1,...,m-2,m-l) на рис. 3.1. Заметим здесь, что проще хранить все биты bj(i=l,2,...n, j=0,1,...,m-2,m-l), а потом только учитывать старшие биты. Если же обнулить младшие (незначащие) биты, то получатся координаты вершины куба с наименьшими координатами.
У дерева есть корень — узел, описывающий куб, который пространственно содержит все остальные кубы дерева и как следствие — воксели. Вместе с деревом внутри информационной структуры дерева n-мерных кубов всегда хранится ссылка на этот узел-куб. Далее будем называть её ссылкой на корень дерева. Она определяет координаты (и размер) куба, описанного корневым узлом дерева. А также её можно модифицировать некоторым образом, чтобы определить координаты любого куба, описываемого соответствующим узлом в дереве. При переходе от большего куба к вложенному меньшему кубу (от узла к дочернему узлу) номер потомка (индекс описателя в массиве описателей данного узла) определяется битами b a_i i=l,2,...,n из ссылки на узел-куб. Кроме ссылки на корень дерева будем для удобства внутри информационной структуры дерева n-мерных кубов всегда хранить ссылку на некоторый текущий узел-куб. Будем считать, что изначально это ссылка совпадает со ссылкой на корень дерева.
Заметим что, что в дереве не существует узлов, ссылка на которые имела бы ос=0. Информация о кубах со стороной 1 (т.е. о вокселях) хранится всегда только в описателях внутри узла с a=l.
Дифференциальная игра «шофёр-убийца» с модифицированными ограничениями на управления второго игрока
Диссертация посвящена исследованию дифференциальных игр с геометрическими ограничениями на управления игроков. Изучаются антагонистические позиционные дифференциальные игры двух игроков на конечном промежутке времени.
Рассматриваются, в основном, две игровые задачи о сближении конфликтно-управляемой системы с целевым множеством в конечномерном фазовом пространстве.
В первой игровой задаче конфликтно-управляемая система является линейной по управлению второго игрока. Первому игроку требуется построить позиционный способ управления, обеспечивающий сближение системы с целевым множеством в конечный момент из заданного промежутка времени, как бы ни действовал при этом второй игрок в рамках заданных ограничений на управления.
Во второй задаче рассматривается конфликтно-управляемая система общего вида. Первому игроку требуется построить позиционный способ-управления, обеспечивающий сближение с целевым множеством на заданном промежутке времени, то есть не позже конечного момента из заданного промежутка времени. В рамках этой крупной задачи в диссертации рассмотрена подробно и изучена та часть задачи, которая относится к построению множества позиционного поглощения, т.е. множества всех точек в пространстве позиций, из которых разрешима задача о сближении. Эта часть игровой задачи о сближении является наиболее трудной для решения.
Отметим, что обе игровые задачи рассматриваются в рамках теории позиционных дифференциальных игр [16-38,53-55,85-96], развиваемой Уральской математической школой по теории управления, руководимой Н.Н. Кра-совским. К настоящему времени в теории дифференциальных игр накоплен богатый арсенал методов, ориентированных на исследование и решение упомянутых игровых задач и ряда других не менее значимых задач.
Большое значение для становления и развития теории дифференциальных игр сыграли исследования отечественных математиков.
Л.С. Понтрягиным было введено в работах [73,74] важное в теории дифференциальных игр понятие альтернированного интеграла. Направление теории дифференциальных игр, базирующееся на этом понятии, было развито в дальнейшем в работах самого Л.С. Понтрягина [75-78] и других математиков [1,15,36,51,52,71,72]. Ряд работ Е.Ф. Мищенко и его учеников также посвящены дифференциальным играм [40,47,48,79].
Н.Н. Красовским была предложена позиционная формализация дифференциальных игр [19-21], охватывающая дифференциальные игры в общей постановке. Эта формализация, основу которой составил принцип экстремального прицеливания на стабильные мосты, указывает путь к построению разрешающего позиционного управления. Теория позиционных дифференциальных игр развивалась в дальнейшем в работах Н.Н. Красовского, его сотрудников А.Б. Куржанского, Ю.С. Осипова, А.И. Субботина и их учеников [4,14,15,16,22-38,41,53-55,85-94].
Важные результаты в теории дифференциальных игр были получены в Киеве Б.Н. Пшеничным и его учениками А.А. Чикрием, Ю.Н. Онопчуком, В.В. Остапенко [80-84,56-58,109,110].
Большой вклад в развитие теории дифференциальных игр внесли Ф.Л. Черноусько, А.А. Меликян и их сотрудники [44-46,108]. Здесь отметим монографию Ф.Л. Черноусько и А.А. Меликяна [108], посвященную игровым задачам механики.
Значительные результаты были получены также Э.Г. Альбрехтом, В.Д. Батухтиным, Н.Л. Григоренко, В.И. Жуковским, М.И. Зеликиным, А.Ф. Клейменовым, А.Н. Красовским, А.В. Кряжимским, Ю.С. Ледяевым, Н.Ю. Лукояновым, В.И. Максимовым, М.С. Никольским, О.И. Никоновым, B.C. Пацко, Н.Н. Петровым, Н.Никандр. Петровым, Л.А. Петросяном, Н.Н. Субботиной, A.M. Тарасьевым, В.Е. Третьяковым, А.А. Успенским, В.И. Ухобо-товым, А.Г. Ченцовым, СВ. Чистяковым и другими.
К зарубежным математикам, получившим значительные результаты в теории дифференциальных игр, следует отнести Р.Айзекса [2], Д. Бреквелла [115, 116], В. Флеминга [117,118].
В настоящее время прежде всего практические потребности обуславливают развитие теории дифференциальных игр. Этому развитию способствует также в значительной мере наличие высокопроизводительной вычислительной техники.
Задачи, в которых управляемая динамическая система подвержена неконтролируемым помехам, в реальной жизни встречаются достаточно часто. Эти задачи могут быть формализованы как дифференциальные игры. Среди них существенную долю составляют задачи, которые можно трактовать как игровые задачи наведения управляемой системы на заданное целевое множество. В таких задачах на передний план выступает проблема построения множеств разрешимости — таких множеств в пространстве позиций, из которых разрешима задача гарантированного наведения на целевое множество. Как оказывается, эти множества обладают очень важным свойством - свойством стабильности. В теории позиционных дифференциальных игр понятие стабильности и стабильного моста составляет один из основных элементов экстремальной конструкции, решающей задачу гарантированного наведения на целевое множество. Эта конструкция была введена в теорию дифференциальных игр, рассматриваемых в общей постановке, в работах [26-30] Н.Н. Красовского и А.И. Субботина конца 60-х и начала 70-х годов предыдущего века. В силу сложности игровых задач наведения даже в относительно простых случаях не удаётся получить эффективное аналитическое описание стабильного моста. Поэтому актуальной становится проблема приближённого вычисления (максимальных) стабильных мостов и разработка методов и алгоритмов приближённого вычисления этих мостов.
