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

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

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

Введение.

Глава 1 Позиционные процедуры управления для систем, линейных по управлению второго игрока.

1.1 Введение.

1.2 Постановка игровой задачи о сближении в фиксированный момент времени. Конструкции u-стабильных мостов в игровой задаче.

1.2.1 Постановка игровой задачи о сближении в фиксированный момент времени.

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

1.2.3 Аппроксимирующая система множеств (W(n)(t): t еГп}.

1.3 Первый вариант процедуры управления с поводырём первого игрока, базирующейся на копировании управлений.

1.4 Второй вариант позиционной процедуры управления с поводырём первого игрока, базирующейся на копировании управлений.

Глава 2 Игровая задача о сближении на конечном промежутке времени. Некоторые способы приближённого построения максимальных и-стабильных мостов.

2.1 Введение.

2.2 Постановка игровой задачи о сближении на промежутке [t0, 9]

2.3 Оператор стабильного поглощения и u-стабильные мосты в игровой задаче о сближении на промежутке [t0, 0].

2.4 Аппроксимирующая система множеств в задаче о сближении на промежутке [t0, 9] и её свойства.

Глава 3 Алгоритмы обработки множеств позиционного поглощения

3.1 Введение.

3.2 Информационная структура дерева n-мерных кубов и некоторые алгоритмы работы с ней.

3.2.1 Информационная структура дерева n-мерных кубов.

3.2.2 Процедура добавления точки (вокселя).

3.2.3 Шаблон алгоритма обхода n-мерных кубов с заданной процедурой.

3.2.4 Алгоритм выделения граничных вокселей.

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

3.2.6 Алгоритм объединения двух информационных структур деревьев n-мерных кубов.

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

3.2.8 Алгоритм заливки области пространства R".

3.3 Алгоритмы, необходимые для построения максимального и-стабильного моста.

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

3.3.2 Метод построения выпуклой оболочки конечного множества точек в пространстве R".

3.3.3 Построение выпуклой оболочки конечного множества точек в R", заданных «центрами» вокселей из информационной структуры дерева п-мерных кубов.

3.3.4 Алгоритм приближённого вычисления максимального и-стабильного моста.

3.3.5 Алгоритм построения управления.

3.4. Алгоритмы визуализации.

3.4.1 Алгоритм построения нормалей в граничных вокселях.

3.4.2 Алгоритм подготовки к визуализации информационной структуры дерева n-мерных кубов.

3.4.3 Алгоритм визуализации без кэширования.

3.4.4 Алгоритм визуализации с кэшированием.

Глава 4 Применение воксельных методов расчёта и визуализации при конструировании максимальных u-стабильных мостов и движений.

4.1 Введение.

4.2 Экологическая задача на соотношение двух видов.

4.3 Дифференциальная игра «шофёр-убийца».

4.4 Дифференциальная игра «шофёр-убийца» с модифицированными ограничениями на управления второго игрока.

4.5 Дифференциальная игра «шофёр-убийца» с модифицированной динамикой.

4.6 Дифференциальная игра «шофёр-убийца» с ограниченным ускорением в трёхмерном пространстве.

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

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

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

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

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

Эта часть игровой задачи о сближении является наиболее трудной для решения.

Отметим, что обе игровые задачи рассматриваются в рамках теории позиционных дифференциальных игр [16-38,53-55,85-96], развиваемой Уральской математической школой по теории управления, руководимой Н.Н. Кра-совским.

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

Большое значение для становления и развития теории дифференциальных игр сыграли исследования отечественных математиков.

JI.C. Понтрягиным было введено в работах [73,74] важное в теории дифференциальных игр понятие альтернированного интеграла. Направление теории дифференциальных игр, базирующееся на этом понятии, было развито в дальнейшем в работах самого JI.C. Понтрягина [75-78] и других математиков [1,15,36,51,52,71,72]. Ряд работ Е.Ф. Мищенко и его учеников также посвящены дифференциальным играм [40,47,48,79].

Н.Н. Красовским была предложена позиционная формализация дифференциальных игр [19-21], охватывающая дифференциальные игры в общей постановке. Эта формализация, основу которой составил принцип экстремального прицеливания на стабильные мосты, указывает путь к построению разрешающего позиционного управления. Теория позиционных дифференциальных игр развивалась в дальнейшем в работах Н.Н. Красовского, его сотрудников А.Б. Куржанского, Ю.С. Осипова, А.И. Субботина и их учеников [4,14,15,16,22-3 8,41,53 -55,85-94].

Важные результаты в теории дифференциальных игр были получены в Киеве Б.Н. Пшеничным и его учениками А.А. Чикрием, Ю.Н. Онопчуком, В.В. Остапенко [80-84,56-58,109,110].

Большой вклад в развитие теории дифференциальных игр внесли Ф.Л. Черноусько, А.А. Меликян и их сотрудники [44-46,108]. Здесь отметим монографию Ф.Л. Черноусько и А.А. Меликяна [108], посвященную игровым задачам механики.

Значительные результаты были получены также Э.Г. Альбрехтом, В.Д. Батухтиным, Н.Л. Григоренко, В.И. Жуковским, М.И. Зеликиным, А.Ф. Клейменовым, А.Н. Красовским, А.В. Кряжимским, Ю.С. Ледяевым, Н.Ю. Лукояновым, В.И. Максимовым, М.С. Никольским, О.И. Никоновым, B.C. 6

Пацко, Н.Н. Петровым, Н.Никандр. Петровым, JI.A. Петросяном, Н.Н. Субботиной, A.M. Тарасьевым, В.Е. Третьяковым, А.А. Успенским, В.И. Ухобо-товым, А.Г. Ченцовым, С.В. Чистяковым и другими.

К зарубежным математикам, получившим значительные результаты в теории дифференциальных игр, следует отнести Р.Айзекса [2], Д. Бреквелла [115, 116], В. Флеминга [117,118].

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

Задачи, в которых управляемая динамическая система подвержена неконтролируемым помехам, в реальной жизни встречаются достаточно часто. Эти задачи могут быть формализованы как дифференциальные игры. Среди них существенную долю составляют задачи, которые можно трактовать как игровые задачи наведения управляемой системы на заданное целевое множество. В таких задачах на передний план выступает проблема построения множеств разрешимости — таких множеств в пространстве позиций, из которых разрешима задача гарантированного наведения на целевое множество. Как оказывается, эти множества обладают очень важным свойством - свойством стабильности. В теории позиционных дифференциальных игр понятие стабильности и стабильного моста составляет один из основных элементов экстремальной конструкции, решающей задачу гарантированного наведения на целевое множество. Эта конструкция была введена в теорию дифференциальных игр, рассматриваемых в общей постановке, в работах [26-30] Н.Н. Красовского и А.И. Субботина конца 60-х и начала 70-х годов предыдущего века. В силу сложности игровых задач наведения даже в относительно простых случаях не удаётся получить эффективное аналитическое описание стабильного моста. Поэтому актуальной становится проблема приближённого вычисления (максимальных) стабильных мостов и разработка методов и алгоритмов приближённого вычисления этих мостов. 7

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

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

Так, для линейных дифференциальных игр наведения на выпуклое целевое множество J1.C. Понтрягиным в 60-е годы предыдущего столетия был предложен метод построения множества разрешимости для первого игрока как метод конструирования альтернированного интеграла (альтернированного интеграла J1.C. Понтрягина) [73,74]. Развитию метода альтернированного интеграла в теории дифференциальных игр как с геометрическими, так и интегральными ограничениями на управления игроков, посвящены работы сотрудников и учеников Л.С. Понтрягина [1,51,52,71,72,78], а также работы последнего времени А.Б. Куржанского и его учеников[14,15,36-38].

Другим методом, направленным на решение задачи вычисления множества разрешимости, является метод программных итераций в теории позиционных дифференциальных игр, предложенный в 70-е годы предыдущего столетия А.Г. Ченцовым и развиваемый им и его сотрудниками [104-107,114] по настоящее время. В этом направлении проводились также исследования В.И. Ухоботовым [99] и С.В. Чистяковым [111].

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

Поскольку точное определение моста с помощью эффективных аналитических соотношений затруднено даже в относительно простых случаях, стоит серьёзная проблема разработки методов и алгоритмов приближённого вычисления стабильных мостов в позиционных дифференциальных играх. Достаточно эффективным в решении этой проблемы является путь, использующий идеологию попятных пошаговых (по времени) конструкций, отправляющихся в последний момент времени из заданного промежутка от целевого множества. Этот путь родственен по духу методу динамического программирования Р. Беллмана [5]. Этим конструкциям, введённым в теорию позиционных дифференциальных игр весьма общего вида в [26-30], посвящено значительное количество исследований [6,7,10,12,3133,59,60,93,94,100-103,133]. Методам, базирующимся на идеологии попятных пошаговых конструкций, посвящена и настоящая диссертация. В основе исследований, представленных в диссертации, лежат работы Н.Н. Красовского, А.И. Субботина, В.Н. Ушакова, A.M. Тарасьева [30,88,93,94,100-103], выполненные в последние десятилетия.

Кроме сложности построения стабильных мостов существует ещё и сложность хранения информации о них. В основе настоящей диссертации лежат предшествующие работы [59-61], которые уже используют пиксельные методы построения и хранения стабильных мостов. Здесь эти методы будут распространены на задачи более высоких размерностей, стабильные мосты будут аппроксимированы наборами кубиков в пространствах соответствующих размерностей. Координаты вершин этих кубиков будут привязаны к сетке. Однако сам набор кубиков нужно каким-то образом хранить так, чтобы с одной стороны место, отводимое под них, было не очень большим, а с другой стороны скорость выполнения необходимых алгоритмов над этим представлением набора кубиков была бы высокой; кроме всего прочего нам хотелось 9 бы уметь визуализировать этот набор кубиков. Для этого, например, в трёхмерном случае лучше всего использовать структуру, называемую 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. Kaufman[124], однако, их алгоритм вычисления нормалей не может быть применён к задачам визуализации, рассматриваемым здесь. В диссертации приведён более эффективный алгоритм визуализации, чем те которые рассмотрены в [123-128]. Также в настоящей работе трёхмерное понятие вокселя расширено на всевозможные размерности.

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

При достижении поставленных целей используются:

1. идеология приближённого попятного построения стабильных мостов;

2. пошаговые конструкции управления с поводырём первого игрока, включающие составным элементом копирование управлений;

10

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

4. информационная структура данных восьмеричного дерева и его расширения на другие pa3MepHOCTH(quadtree, octree, ) с целью компактного представления набора вокселей и ускорения алгоритмов работы с набором вокселей, включая алгоритмы визуализации.

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

В параграфе 1.1 кратко характеризуется содержание первой главы. В параграфе 1.2 рассматривается игровая задача о сближении с целью в фиксированный момент времени. Приводятся попятные (по времени) пошаговые конструкции u-стабильных мостов в этой игровой задаче.

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

Конфликтно-управляемая система задаётся векторным дифференциальным уравнением на промежутке времени [t0,6] (to<Q<co) dx = f(t,x,u,v), x[t0] = x0, te[t0,S], ueP, veQ. (1) dt

Здесь t — время, x — m-мерный фазовый вектор из евклидового пространства Rm, и и v - векторы управлений первого и второго игроков, Р и Q — компакты в евклидовых пространствах Rp и R4 соответственно.

Относительно вектор-функции f(t,x,u,v) предполагается, что f(t,х,u,v) = f(1)(t,х,u) + C(t,х)v, (t,x,u,v)e[t0,S]xRm xPxQ, (2) где вектор-функция f^t^u) и матрица-функция C(t,x) стеснены условиями непрерывности, локальной липшицевости по х и продолжимости решений (см. условия А,Б, стр. 30).

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

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

В задаче о сближении в момент 9, стоящей перед первым игроком, требуется обеспечить попадание из точки x[to]=x0 движения x[t] системы (1), (2) в момент 9 на компактное множество М, содержащееся в Rm. Решение задачи требуется обеспечить в классе позиционных процедур управления с поводырём первого игрока[30].

В этой постановке М выступает как целевое множество.

Особо отметим, что в постановке задачи о сближении речь идёт о позиционных процедурах управления первого игрока. Это предполагает, что первый игрок формирует свои управления на базе информации о реализовавшихся позициях (t,x[t]) системы (1), (2) и информации о позиции (t,y[t]) вспомогательной системы, именуемой поводырём.

В пункте 1.2.1 уточняется понятие множества позиционного поглощения W°cz[to,9]xRm — множества разрешимости игровой задачи о сближении. В работах [26-30] показано, что W0 — максимальный u-стабильный мост.

Свойство u-стабильности — одно из центральных понятий, используемых в диссертации. Оно означает слабую инвариантность множества W0 относительно некоторого семейства дифференциальных включений, тесно связанных с системой (1), (2).

Пункт 1.2.2 посвящён описанию свойства u-стабильности в рассматриваемой игровой задаче о сближении системы (1), (2) с целевым множеством М в момент 9.

Вначале определяется оператор стабильного поглощения. Для этого вводится в рассмотрение функция (гамильтониан системы (1),(2))

H(t,х, 1) = maxmin < 1,f(t, x,u, v) >, (t,x, 1) e [t0,3] x Rm x Rm, ueP veQ где <1,£> - скалярное произведение векторов 1 и f из Rm.

Задаётся некоторое множество Т элементов и семейство {F^t/e^F} отображений F^: (t,x) FV|/(t,x)c:Rm ((t,x)eD), удовлетворяющее условиям A.l, А.2, А.З (см. стр. 30); здесь D- некоторое компактное множество в [to,6]xRm

Полагается X^t ;t*,x*) - множество достижимости дифференциального включениях е F (t,x), x(t.) = х,, отвечающее моменту t*e[t*,9];

Х^" (t*;t ,Х ) = {x*eRm: X^t ,t*,x*)nX ^ 0}, где X - произвольное множество из Rm. $

Элементы \|/ из и Xvi,(t ,t*,x*) можно трактовать как некоторые «обобщённые» управления второго игрока, и множество достижимости, отвечающее этим «обобщённым» управлениям второго игрока.

Определение 1 [94, 101]. Оператором стабильного поглощения % в задаче о сближении с М в момент 0 назовём отображение тс: Ех2к" ь-> 2К , заданное равенством 7i(t.,t*,X') = Р] X^(t.;t*,X*), (t*,t*,X*)eEx2Rm ♦ *

Здесь S= {(t*,t ): t0<t*<t < 0} - множество в [t0, 0]x[to, 0].

Определение 2[94,101]. Замкнутое множество WczD назовём и-стабилъным мостом в задаче о сближении с Me момент 0, если

W(0)c=M; W(t*)c7i(t*;t*,W(t*), (t,,t*)eS.

Здесь W(t)={xeRm: (t,x)eW).

Множество позиционного поглощения W°, как показано в [26,27,30], является максимальным u-стабильным мостом; при этом выполняется равенство W°(9)=M.

Приведённое определение 2 u-стабильного моста является более поздним, чем определение из работ Н.Н. Красовского и А.И. Субботина [26,27,30]. Однако можно показать [92], что они эквивалентны, т.е. выделяют один и те же u-стабильные мосты W в D.

От определения оператора стабильного поглощения и и-стабильного моста в общей форме, приведённой выше, можно перейти к определению оператора стабильного поглощения для конфликтно-управляемой системы (1), (2) при помощи отображений (t,x) I—» Fv(t, х), veQ .

Здесь роль элементов \|/ играют управления v, а роль множества ^Р играет ограничение Q; множество Fv(t,x) определяется равенством Fv(t,x) = F(1)(t,x) + C(t,x)v, veQ, где F(1)(t,x)= cof^'^u): ueP}, co{f) — выпуклая оболочка множества (f) в Rm.

В этом случае оператор % определяется равенством

7T(t., t*, X') = П (t.; f, X'), (t*,t*,X*) еНх 2Rm. veQ

В случае, когда по постановке задачи о сближении с М в момент 6, ограничение Q есть выпуклый многогранник в Rm с множеством Q вершин vtp), оператор % можно определить равенством 7r(t,,t*,X*) = Q X'^t.jt'jX*). v(p)eQ

В пункте 1.2.3 рассматривается один из центральных вопросов — вопрос о приближённом вычислении максимального u-стабильного моста W0.

В связи с этим, в пункте 1.2.3 вводится аппроксимирующий оператор стабильного поглощения к. С использованием оператора тс определяется аппроксимирующая система множеств { W(I,)(tj), t; еГп } в пространстве Rm, отвечающая разбиению rn={t0,ti,.,tN(n).btN(n):=6} промежутка [to,0].

Определение 5[94,101]. W(n)(6) = MCN(n), W(n)(ti) = 7c(t.;ti+1,W(n)(ti+1)), где i=N(n)-l,N(n)-2,.,l, 0; здесь eN(n) - некоторое положительное число.

Так определённая последовательность {W(n)(t;), t; еГ } представляет собой заданную попятно (во времени) последовательность множеств в Rm, которая в силу ряда причин не очень удобна для вычисления. Поэтому эту последовательность приходится подправлять для того, чтобы она (измененная последовательность) стала удобной для вычислений.

В случае системы (1), (2) и множества Q — выпуклого многогранника в Rq с вершинами v(p), вместо аппроксимирующей системы множеств {W(n)(ti), t; е Гп} в Rm вычисляется система множеств { W(n)(tj), t; е Гп}. Эта система множеств возникает в результате подмены множества Р некоторой достаточно мелкой конечной — сетью Р5 "' множества Р и подмены пространства Rm некоторой достаточно густой регулярной сеткой К(п) в Rm. Так, вместо множества W(n)(tN(n)) = MEfj( ^, исходного в попятной процедуре вычисления множеств W(n)(t;), рассматривается некоторый, аппроксимирующий это множество, конечный набор точек в К(п), обозначаемый символом W(n)(tN(n)). Далее, в предположении, что уже вычислено множество W{n)(t.+1), отвечающее моменту tj+i (0< i< N(n)-l), вычисляется множество W^tJczK^ в соответствии с процедурами, описанными на стр. 49 диссертации. Процедура вычисления множеств W^t,) продолжается вплоть до момента to или до того последнего момента tj, которому отвечает непустое множество W(n)(t,).

Параграф 1.3 посвящён рассмотрению позиционных способов управления первого игрока, обеспечивающих попадание движений x[t] реальной конфликтно-управляемой системы (1), (2) в 8-окрестность целевого множества М в конечный момент 6.

В качестве таких разрешающих позиционных способов управления первого игрока в параграфе 1.3 предлагаются позиционные процедуры управления с поводырём первого игрока, базирующиеся на копировании управлений. К достоинствам этих процедур относится то, что они просты в реализации управлений и устойчивы по отношению к информационным помехам, возникающим при вычислении движения x[t] системы (1), (2) и движения поводыря y[t] в моменты t; разбиения Гп.

Конструкция управления с поводырём в теории дифференциальных игр имеет богатую предысторию. Она была введена в теорию дифференциальных игр в работах Н.Н. Красовского и А.И. Субботина [26-30] в начале 70-х годов прошлого столетия. В последующие годы был опубликован ряд работ, по-свящённых применению позиционного управления с поводырём в задачах теории управления и дифференциальных игр.

В частности, отметим работы А.И. Субботина, В.Н. Ушакова[89] и А.И. Субботина, Н.Н. Субботиной[90], относящиеся к дифференциальным играм с интегральными ограничениями на управления обоих игроков. Эти работы близки по духу к диссертационной работе тем, что в каком-то смысле там реализуется идея копирования, но не управлений, а ресурсов управления.

Значительно позже идея копирования управлений при построении позиционного управления с поводырём первого игрока была применена В.Н. Ушаковым, В.А. Вахрушевым в [10], а также в диссертации В.А. Вахрушева [8] при исследовании дифференциальных игр с геометрическими ограничениями, линейных по управлениям обоих игроков.

Настоящая диссертационная работа обобщает, в частности, результаты работ [8,10], относящиеся к процедурам управления с поводырём. В параграфе 1.3 рассматривается система (1), (2) более общего вида, чем конфликтно-управляемая система из [8,10].

Помимо копирования управлений в позиционной процедуре управления с поводырём активно используется идея усреднения постоянных управлений на отрезках разбиения Гп. Разумеется, что эта идея усреднения не нова. Ранее она активно использовалась, например, в работах [17,28,29].

Опишем кратко суть позиционной процедуры управления с поводырём, базирующейся на копировании управлений.

Предполагается, что заданы некоторое разбиение rn={to,ti,.;tN(n)-btN(n):=0} промежутка [to,0] и уже вычисленная аппроксимирующая система множеств { W00^), t, е Гп}, отвечающая разбиению Гп.

В фазовом пространстве Rm конструируются два движения - движение x[t] реальной управляемой системы (1), (2) и вспомогательное движение y[t] поводыря на [to,0]. Они конструируются последовательно во времени по шагам [t0, ti], [ti,t2], [t2,t3], . разбиения Гп вплоть до последнего шага tN(n)-l,tN(n)]

Начальная точка x[t0]=x0 движения x[t] задана, и по ней вычисляется начальная точка y[to]=yo поводыря y[t] как ближайшая на W(n)(t0) к x[to]. На каждом очередном шаге [tk,tk+1], к>1, разбиения Гп первый игрок знает не только x[tk], но и x[tki], а также y[tk].

Основываясь на этой информации о движениях, он определяет управление uk(t) в системе (1), (2) на шаге [tk,tk+i]: x[tk.,], x[tk], y[tk]) н> uk(t) на [tk,tk+1). При этом процедура определения uk(t), te[tk, tk+i), к>1, начинается с выбора управления v*k второго игрока в поводыре y[t] на шаге [tk, tk+1]. Управление v*k второго игрока в поводыре y[t] на шаге [tk, tk+1] выбирается из неко1 торого условия копирования вектора vk~' =- J v(x)dt — среднего значения k-i »k. управления v(t) второго игрока в реальной системе (1), (2), реализовавшегося на предыдущем шаге [tk.b tk]. Далее из условия

Akf,(1)(tk,y[tk]) g W(n)(tk+1)- y[tk|- AkC(tk, y[tk])v*k (3) определяется вектор f*(1)(tk,y[tk]), который можно трактовать как управление первого игрока в движении поводыря y[t] на [tk, tk+i). Движение поводыря y[t] на [tk,tk+i] определяется равенством

УМ = УЫ + (t-tk) f*(,) (tk,y[tk]) + (t-tk) C(tk, y[tk]) v,k , te [tk,tk+1] (4)

Следующим шагом является определение по вектору f*(l)(tk,y[tk]) кусочно-постоянного управления uk(t) первого игрока на [tk,tk+i).

Это управление имеет не более (т+1) промежутков постоянства.

Управление uk(t) вместе с реализовавшимся на [tk,tk+i) управлением v(t) второго игрока порождает движение x[t] реальной конфликтно-управляемой системы (I), (2).

Далее процесс конструирования движений x[t] и y[t] переносится на следующий промежуток [tk+i,tk+2] разбиения Гп.

В заключительной части параграфа 1.3 строго обосновывается тот факт, что приведённая выше позиционная процедура управления первого игрока, обеспечивает решение задачи о сближении с любой малой 8-окрестностью Мс множества М, если только диаметр Д(п)= тах А разбиения Гп выбран достаi=I,N(n)-l ' точно малым.

Более точно это утверждение выражено в теореме 1.2 (стр. 64). Обоснование теоремы 1.2 является одним из основных результатов первой главы и настоящей диссертации.

Для реализации движений x[t] и y[t] на [tk,tk+i], согласно приведённой выше процедуре управления с поводырём первого игрока, этот игрок уже в момент tk должен знать управление u(t), te[tk,tk+i), то есть для реализации движений x[t] и y[t] первый игрок должен мгновенно осуществить ряд операций (алгебраических и теоретико-множественных).

Для устранения этой трудности в параграфе 1.4 предлагается второй вариант позиционной процедуры управления с поводырём, также базирующийся на копировании управлений. Этот вариант подробно изложен в параграфе 1.4. В нём управление uk(t), te[tk,tk+1), к>1 первого игрока в реальной системе (1), (2) вычисляется заранее уже на предыдущем промежутке [tkb tk].

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

В рассматриваемой в этой главе игровой задаче о сближении, так же как и в задаче о сближении из первой главы, не существует эффективного аналитического описания максимальных u-стабильных мостов. Здесь также на первый план выступает проблема приближённого вычисления максимальных u-стабильных мостов.

Вторая глава диссертации посвящена исключительно решению этой проблемы. В ней не рассматриваются позиционные способы управления первого игрока, разрешающие задачу о сближении, а обсуждаются методы приближённого построения максимальных u-стабильных мостов. Концептуальная основа этих методов та же, что у методов приближённого построения максимальных u-стабильных мостов в игровой задаче о сближении из первой главы. Это — переход к дискретному времени и попятные (в дискретном времени) пошаговые процедуры приближённого построения u-стабильных мостов.

Следует отметить, что игровая задача о сближении на конечном промежутке, являющаяся весьма значимой в теории дифференциальных игр, подробно изучалась различными авторами. Здесь мы отметим, прежде всего, определяющие теоретические результаты, полученные Н.Н. Красовским и А.И. Субботиным. Так, в известной монографии Н.Н. Красовского, А.И. Субботина [30], изучена позиционная дифференциальная игра сближения-уклонения в общей постановке, сформулирована и доказана теорема об альтернативе в этой игре. Показано, что для тех начальных позиций игры, которые принадлежат множеству позиционного поглощения W0, решение игровой задачи о сближении может быть получено с помощью позиционной стра

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

Работы Б.Н. Пшеничного [80,81] также посвящены исследованию дифференциальных игр сближения-уклонения на конечном промежутке времени.

Эти дифференциальные игры подробно рассматриваются в монографии Б.Н. Пшеничного, В.В. Остапенко [131].

Отметим также работы П.Б. Гусятникова [13] и Е.С. Половинкина [69,70], посвящённые игровым задачам о сближении-уклонении.

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

Перейдём к более детальному изложению содержания второй главы диссертации.

В параграфе 2.1 излагается кратко содержание второй главы.

В параграфе 2.2 даётся постановка игровой задачи о сближении с целевым множеством М на конечном промежутке [to,0].

Отметим, что во второй главе, в отличие от первой главы, не предполагается линейная зависимость правой части конфликтно-управляемой системы (2.1) от управления v второго игрока. Но здесь и не рассматривается вопрос о разрешающих позиционных процедурах управления первого игрока.

Параграф 2.3 посвящён описанию свойства u-стабильности в рассматриваемой игровой задаче о сближении. Так же, как и в задаче о сближении в фиксированный момент, стабильность некоторого множества WgD означает слабую инвариантность W относительно включений, связанных с (2.1) и рассматриваемых на [to,0].

Так же, как и в задаче о сближении в момент 9, считаем, что компактная область D выбрана настолько большой в [to,0]xRm, что все множества из аппроксимирующей конструкции (см. стр. 85,86), а также W0 и WM=[t0,9]xM содержатся в D; здесь McRm - целевое множество в нашей задаче.

Считаем также, что задано некоторое семейство (F^: отображений FV|): (t,x) ь» F^t^czR™, (t,x)eD, удовлетворяющих условиям A.l, А.2, А.З.

В параграфе 2.3 приводятся две эквивалентные формулировки и-стабильности [30] (определения 2.1, 2.2 u-стабильного моста), относящиеся к более раннему периоду исследований в теории дифференциальных игр.

Далее в параграфе 2.3 приводится определение оператора стабильного поглощения 7Г в задаче о сближении с М к моменту 9 и u-стабильного моста в терминах семейства {F^rij/e^}.

Определение 4[102,103]. Оператором стабильного поглощения л в задаче о сближении с М к моменту Э назовем отображение л-: 5 х 2К"' f-> 2R"', заданное соотношением 7r(t,;t*,H) = П U x;'(t

Ve>Pte[t,,t*] здесь Mt(H) =

M, te[t„t'), MUH, t = t*;

Определение 5[102,103]. Замкнутое множество WcD назовем и-стабилъным мостом в задаче о сближении с М к моменту 9, если для любых (t„t*)eS

W(S) с= М, W(t.) <= 7u(t.; t*, W(t*)).

При этом возникает важный вопрос о корректности определения 5. Дело в том, что семейство {Fvt,:\|/e4/} отображений (t,x) ь-> Fv(t,x), удовлетворяющих условиям A.l, А.2, А.З, может быть задано различными способами, иными словами - таких семейств не одно, а больше.

Вопрос состоит в следующем: «Выделяют ли операторы стабильного поглощения, отвечающие этим семействам, одни и те же u-стабильные мосты в пространстве позиций игры?»

В этом параграфе диссертации даётся утвердительный ответ на этот вопрос: «Различные семейства {F^i/e^F} отображений (t,x) I—> Fv(t,x), удовлетворяющих условиями A.l, А.2, А.З, эквивалентны в том смысле, что соответствующие им операторы те выделяют одни и те же u-стабильные мосты W в D».

Уточним сформулированное утверждение.

Пусть заданы два множества (i=l,2) элементов if/j (i=l,2). Пусть : D i-> 2Rm} - два семейства отображений (t,x) i—> F;°(t,x), отвечающие множествам ^ (i=l,2). Каждое из этих семейств индуцирует свой оператор Л; стабильного поглощения в задаче о сближении с М:

7C,(t.;t\H)= П U Xf (t.;t,M,(H)), (t.,t*,H)eEx 2R™.

V.c'f, te|t„l*]

Здесь Xf (t.;t,Mt(H))={x*eRm: X^^t^JflM.CH)) * 0 множество достижимости в момент te[t*,t*] дифференциального включения х е F^0(t,x), x(t*)=x* и множество Mt(H) определены выше.

Теорема 2.1. Операторы те, и %2 эквивалентны, т.е. замкнутое множество WcD является u-стабильным мостом относительно оператора те, тогда и только тогда, когда оно — u-стабильный мост относительно оператора те2.

Далее в параграфе 2.3 приводится доказательство теоремы 2.1. Теорема 2.1 и её доказательство представляют собой один из основных теоретических результатов второй главы и диссертационной работы.

Таким образом, теорема 2.1 утверждает, что все операторы стабильного поглощения те, определяемые всевозможными семействами {F^,: хуеЧ'} отображений (t,x) I—> F4,(t,x), удовлетворяющих условиям 3, эквивалентны.

Тогда возникает вопрос о нахождении такого семейства {F^: уеЧ'}, которое бы порождало наиболее простой оператор п. Для вычислений и-стабильных мостов было бы уже хорошо, если удалось бы найти конечное семейство отображений (t,x) ь-> F^tjX). В этом случае становилась бы реальной процедура вычисления оператора к. Было бы ещё лучше, если бы удалось найти семейство с небольшим количеством (а, может быть, и минимальным количеством) отображений (t,x) ь-> F4,(t,x).

Параграф 2.4 посвящён рассмотрению вопросов приближённого вычисления множества позиционного поглощения W0 в задаче о сближении с М к моменту 8. Множество W0, так же, как и множество стабильного поглощения в игровой задаче о сближении с М в момент 8, является максимальным и-стабильным мостом. Это свойство u-стабильности активно используется при приближённом вычислении множества W0, однако оно используется не в чистом виде, а в трансформированном виде, использующем понятие аппроксимирующего оператора стабильного поглощения.

В параграфе 2.4 приводятся определения из работ [102,103] аппроксимирующего оператора стабильного поглощения лс в задаче о сближении с М к моменту 0. Это определение оператора кс связано с некоторой скалярной положительной функцией г^(5), 8>0, lim = 0. Дабы не усложнять обозначений, обозначим её ниже символом ц. Каждой такой функции г|(8), 8>0 и разбиению Гп ставится в соответствие аппроксимирующая система множеств

У^^еГЛ.

Приводится определение 2.7 предела nW° аппроксимирующей системы { W* \ti):ti еГп} при Д(п)—>0, а также утверждение из [102,103] (теорема 2.2, см. стр. 87) о том, что предел совпадает с W . Аппроксимирующая сис-23 тема множеств {n W (tf): t; е Гп} неудобна для вычислений. Так, например,

-"(п) та для вычисления множества nW (t.) в R необходимо вычислить несчётное

--1 —(п) число множеств. Xv (t.;t,Mj'M(nW (ti+1))), te[tj,ti+i], их объединение I--1 ~-(n)

J Xv (t,;t,M^'(n W (tj+l))) и, затем, пересечение их te[t,.t,4il fl U Xv(t.;t,M;%W(n)(ti+,))) (см. [102, 103]).

Далее в параграфе 2.4 рассматривается вопрос о конструировании таких систем множеств {W( ^t):еГп}, которые в определённом смысле близки к

----(п) аппроксимирующей системе множеств {n W (t;): t; е Гп}, дают в пределе при

А(п)—>0 множество W0 и в то же время более удобны для вычислений.

В связи с этим, в двух различных случаях (случай I и случай II) предлагаются два разных варианта построения таких систем множеств

W00^):^ еГп}. Эти варианты были рассмотрены в работах В.Н. Ушакова, A.M. Тарасьева[93,101] и В.Н. Ушакова, А.П. Хрипунова, А.А. Успенского [102, 103]. В указанных работах обоснована сходимость систем множеств

W(n)(t) :t е Гп} при А(п)—>0 к множеству W0.

В настоящей диссертации в параграфе 2.4 предложены некоторые модификации (Q^tj):^ еГп} этих систем множеств, направленные на дальнейшее упрощение процедур приближенного вычисления множеств W0.

Однако следует отметить, что сходимость систем множеств

Q°°(tj): t е Гп} пока не обоснована.

В третьей главе диссертации рассматривается способ приближённого представления замкнутого множества точек пространства R", а также алгоритмы работы с ним, позволяющие визуализировать его, и, используя это представление, вычислять максимальные u-стабильные мосты.

За основу такого представления было взято пиксельное представление, которое уже раньше использовалось в работах [59-61] для вычисления максимальных u-стабильных мостов. Это представление было расширено для п-мерного случая в виде набора вокселей (кубиков со стороной 1 и с координатами вершин кратными сетке координат), термин введён в параграфе 3.1. Однако, кроме этого, для уменьшения размера занимаемой памяти была использована информационная структура дерева n-мерных кубов, введённая в пункте 3.2.1; она является расширенным n-мерным вариантом структуры, описанной в работах R.Reddy и S.Rubin[121], N. Stolte, A. Kaufman [123,124], D. Benson, J. Davis [125], S. Lefebvre, S. Hornus, F. Neyret[126],T. Moller, R. Ma-chiraju, T. Ertl, M. Chen[127], Jingliang Peng, C.C. Jay Kuo [128].

Перейдём к более детальному изложению содержания третьей главы диссертации.

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

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

В пункте 3.2.2 описывается способ модификации этой структуры при добавлении точки (создании вокселя) в замкнутое множество, описанное этой структурой.

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

Информационная структура дерева n-мерных кубов использует такое представление, что конкретные граничные воксели не обязательно имеют собственный, отведённый именно под них, блок памяти. Граничными будем называть такие непустые воксели, которые имеют общую грань с пустыми вокселями. В пункте 3.2.4 приводится алгоритм выделения (и выборки) таких вокселей, а также граничных кубов большего размера.

Информационную структуру дерева n-мерных кубов можно построить не только путём последовательного повоксельного добавления, но и на основе некоторого функционального определения формы множества; в пункте 3.2.5 приводится алгоритм для этого. Этот алгоритм очень похож на алгоритм, описываемый N. Stolte, A. Kaufman[123,124].

Выбранная нами структура особенно удобна для операций объединения и пересечения множеств, ею описываемых; алгоритмы выполнения этих операций приводятся в пунктах 3.2.6 и 3.2.7.

В растровой графике очень часто применяется операция заливки, в которой замена цвета распространяется через грани соседних вокселей, имеющих заданный исходный цвет. Как будет показано в пункте 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], в этой диссертационной работе нет необходимости визуализировать каждый воксель множества. Визуализируются только те кубы из дерева, которые в значительной степени определяют результирующую картинку и, таким образом, значительно уменьшается время визуализации. Однако для этого необходимо знать для каждого куба цвет (хотя фактически в этой работе цвет не используется - он всегда серый) и нормаль. Считая, что для наиболее мелких кубов - вокселей эта информация уже известна, можно построить

27 её для более крупных кубов с использованием алгоритма, приведённого в пункте 3.4.2.

Для построения одиночной картинки достаточно алгоритма, приведённого в пункте 3.4.3. Однако, если мы хотим использовать визуализацию для интерактивного (с точки зрения пользователя) процесса изучения множества (например, максимального u-стабильного моста), то нам может пригодиться техника, давно известная как кэширование, которая наиболее часто применяется для частичного сохранения медленно получаемых данных в памяти, откуда их можно извлечь значительно быстрее. Алгоритм визуализации с использованием этой техники приводится в пункте 3.4.4.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Михалев, Дмитрий Константинович

Заключение

В заключение кратко сформулируем основные результаты работы

1. Предложены два варианта позиционной процедуры управления с поводырём, решающей игровую задачу о сближении в фиксированный момент для конфликтно-управляемой системы, линейной по управлению второго игрока [146].

2. В игровой задаче о сближении на конечном промежутке времени исследованы свойства оператора стабильного поглощения. Доказана корректность определения оператора стабильного поглощения в этой задаче [141-144].

3. Предложена информационная структура хранения воксельной аппроксимации компактного множества в пространстве Кп [137-140] и некоторые алгоритмы, связанные с ней, например:

• выделение граничных вокселей;

• пересечение и объединение воксельных множеств;

• построение выпуклой оболочки конечного множества М с К";

• заливка воксельной области в К".

4. Разработан воксельный алгоритм приближённого вычисления множества позиционного поглощения в игровой задаче о сближении[144,145].

5. Разработаны алгоритмы построения разрешающих процедур управления с поводырём для конфликтно-управляемых систем, линейных по управлению игроков [146].

6. Разработан алгоритм интерактивной визуализации в реальном времени воксельной аппроксимации компактного множества в К3 [138].

7. Для ряда конкретных игровых задач вычислены и визуализированы аппроксимации множеств позиционного поглощения и движения, порождённые разрешающими процедурами управления с поводырём [144].

Список литературы диссертационного исследования кандидат физико-математических наук Михалев, Дмитрий Константинович, 2009 год

1. Азамов А. О втором методе Понтрягина в линейных дифференциальных играх преследования // Мат. сб. — 1982. — Т. 118. вып.З, — С.422-430.

2. Айзеке Р. Дифференциальные игры. М.: Мир, 1967. - 479 с.

3. Алексейчик М.И. Дальнейшая формализация основных элементов антагонистической дифференциальной игры // Мат. анализ и его прил. Ростов. Ун-т. Ростов-на-Дону, 1975. - Т.7. - С.191-199.

4. Альбрехт Э.Г. О сближении квазилинейных объектов в регулярном случае // Дифференц. уравнения. 1971. - Т.7, №7. - С.1171-1178

5. Беллман Р. Динамическое программирование. М.: ИЛ, 1960. — 400с.

6. Боткин Н.Д.; Пацко B.C. Универсальная стратегия в дифференциальной игре с фиксированным моментом окончания. // Проблемы упр. и теории информации. 1982. — T.l 1, № 6. - С.419-432.

7. Вахрамеев С.А. Альтернативные условия разрешимости одной дифференциальной игры сближения-уклонения. // Прикл. математика и механика. 1981.-Т. 45, № 1. - С.20-25

8. Вахрушев В.А. Методы решения нелинейных дифференциальных игр на плоскости: Дис.канд.физ.-мат.наук. — Свердловск, 1989. -113 с.

9. Вахрушев В.А., Махова А.В. К решению дифференциальной игры «шофер-убийца» и обобщенной задачи Цермело. // Тез. докл. 7 Всес. конф. «Упр. в мех. системах». — Свердловск, 1990. — С.20

10. Вахрушев В.А., Ушаков В.Н. О вычислительной реализации процедур управления с поводырём. // Прикл. математика и механика. —2002. Т. 66, № 2. - С. 228-237.

11. Григоренко Л.Н. К задаче группового преследования // Тр. МИАН СССР. 1988.-Т. 185. - С.66-73.

12. Гусейнов Х.Г., Ушаков В.Н. Дифференциальные свойства интегральных воронок и стабильных мостов. // Прикл. мат. и механика. 1991.-Т. 55, вып. 1. -С. 72-78.

13. Гусятников П.Б. Задача преследования и убегания в теории дифференциальных игр. : Автореф. дис. д-ра физ-мат наук. Свердловск, -1981.-46 с.

14. Дарьин А.Н., Куржанский А.Б. Управление в условиях неопределённости при двойных ограничениях // Дифференц. уравнения. —2003. Т.39, №11. - С. 1474-1486

15. Дарьин А.Н. Синтез управлений при двойных и разнотипных ограничениях: Дис.канд.физ.-мат.наук. — М., 2004. 141 с.16.