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

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

УДК519.711.3

Михалёв Дмитрий Константинович

ПОСТРОЕНИЕ РЕШЕНИЙ В ДИФФЕРЕНЦИАЛЬНЫХ ИГРАХ НА КОНЕЧНОМ ПРОМЕЖУТКЕ ВРЕМЕНИ И ВИЗУАЛИЗАЦИЯ

РЕШЕНИЙ

05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

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

□□3473365

Челябинск-2009

003473365

Работа выполнена на кафедре «автоматика и информационные технологии» Уральского государственного технического университета.

Научный руководитель: член-корреспондент РАН,

доктор физико-математических наук, профессор Ушаков Владимир Николаевич

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

профессор Максимов Вячеслав Иванович

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

Ведущая организация: Институт динамики систем и теории

управления Сибирского отделения РАН

Защита диссертации состоится 25 июня 2009 года в 13:00 на заседании диссертационного совета Д. 212.296.02 в Челябинском государственном университете по адресу:

г. Челябинск, ул. Братьев Кашириных, д. 129 С диссертацией можно ознакомиться в библиотеке Челябинского государственного университета.

Автореферат разослан X 2- мая 2009 г.

Учёный секретарь диссертационного совета доктор физ.-мат. наук, профессор

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

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

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

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

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

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

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

Так для линейных дифференциальных игр наведения на выпуклое целевое множество JI. С. Понтрягиным в 60-е годы был предложен метод построения множества разрешимости для первого игрока как метод конструирования альтернированного интеграла (альтернированный интеграл Л. С. Понтрягина) [27]. Направление теории дифференциальных игр, базирующееся на этом понятии, было в дальнейшем развито в работах самого JI.C. Пон-

3

трягина [28,29], а также в работах [1, 20, 25, 26]. Ряд работ Е. Ф. Мищенко и его учеников также посвящен дифференциальным играм [18,19]. Развитию метода альтернированного интеграла в теории дифференциальных игр как с геометрическими, так и интегральными ограничениями на управления игроков посвящены также работы последнего времени А.Б. Куржанского и его сотрудников [5,14].

Н. Н. Красовским был предложен позиционный подход к формализации дифференциальных игр. Этот подход, охватывающий дифференциальные игры в общей постановке, подробно изложен в работах [9,10] и монографии H.H. Красовского, А. И. Субботина [11]. Основу подхода составил принцип экстремального прицеливания на стабильные многообразия. В дальнейшем теория позиционных дифференциальных игр развивалась, в основном, в работах Н. Н. Красовского, А. Б. Куржанского, А. В. Кряжимского, Ю. С. Оси-пова, А. И. Субботина, А. Г. Ченцова и их сотрудников.

Важные результаты в теории дифференциальных игр, в том числе, относящиеся к нелинейным играм, были получены в Киеве Б.Н. Пшеничным и его учениками А. А. Чикрием, Ю. Н. Онопчуком, В. В. Остапенко [22, 30-32,40].

Большой вклад в развитие теории дифференциальных игр и, в частности, в решение игровых зздач механики внесли Ф. Л. Черноусько, А. А. Меликян и их сотрудники [16,17,39].

Существенную роль в становлении теории дифференциальных игр сыграли Р. Айзеке [2], Д. Бреквелл [43], В. Флеминг [44].

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

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

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

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

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

игр, предложенного Н. Н. Красовским в 60-е годы XX века и развиваемого Уральской научной школой по теории управления [6, 13, 15, 21, 38]. При этом использовалась идеология стабильных мостов и процедур управления с поводырём [9-12].

Апробация работы. Основные результаты диссертационной работы докладывались на научном семинаре «Математическая теория оптимального управления и теория дифференциальных включений», посвященном 60-летию со дня рождения профессора В.И. Благо датских (Москва, МИАН, 2006), на Всероссийской конференции, посвященной памяти академика А. Ф. Сидорова (Дюрсо, 2006), на IX Международной Четаевской конференции «Аналитическая механика, устойчивость и управление движением» (Иркутск, 2006), на Международной конференции «Алгоритмический анализ неустойчивых задач» посвященной 100-летию со дня рождения В. К. Иванова (Екатеринбург, 2008), на Международной конференция «Управление динамическими системами» (Москва, ИПМех РАН, 2009), на городском математическом семинаре по дифференциальным уравнениям и оптимальному управлению в Удмуртском государственном университете (Ижевск, 2009).

Публикации. Основные результаты опубликованы в работах [1*]-[11*].

Структура и объём диссертации. Диссертация состоит из введения, четырёх глав, заключения, 45 рисунков и 145 наименований литературных ссылок, и составляет 206 страниц машинописного текста.

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

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

В первой главе рассматривается позиционная игровая задача о сближении с целевым множеством в фиксированный момент [11] для конфликтно-управляемых систем нелинейных (вообще говоря) по фазовому вектору и линейных по управлению второго игрока. Управления игроков стеснены геометрическими ограничениями. Обсуждаются вопросы, связанные с прибли-

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

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

— = f(t,x,u,v), x[t0] = x0, te[t0>fl], ueP, ve Q. (1) dt

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

f(t,x,u,v) = f'"(t,x,u) + C(t,x)v, (t,x,u,v)e[t0,fl]xRnxPxQ, (2) Предполагается, что выполнены условия: A. ^''(t.x.u) и C(t,x) определены и непрерывны по совокупности переменных t,x,u и t,x соответственно на [t0,6]xRmxP и [to,6]xRm, и для любого компакта D с [to,6]xRm найдутся такие Lfe(0, и Lce (0, «>), что || f<"(t,x.,u)-f<"(t,x*,u) ||< Lf [[ х. -х* ||, (t,x.,u), (t,x\u) из DxP, (3) IIC(t,x,)v-C(t,x*)v||<Lc ||x. -x* ||, (t,x.,v), (t,x-,v) ibDxQ, (4)

Б. Существует такая константа ye (0, что

||f(t,x,u,v)||<y(l+1|x||), (t,x,u,v)e[t0,$]xRmxPxQ. (5)

Задача о сближении. Первому игроку требуется обеспечить попадание из точки x[to]=Xo движения x[t] системы (1),(2) в момент б на компактное множество М cRm, как бы ни действовал второй игрок в рамках допустимых ограничений.

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

личие наряду с системой (1), (2) вспомогательного движения, именуемого поводырём [11]. Формирование управлений первого игрока в этих процедурах осуществляется в дискретные моменты времени из [to,6] и базируется на информации о реализовавшихся позициях системы (1),(2) и поводыря.

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

Для дифференциальной игры, складывающейся из задач о сближении и об уклонении, справедлива альтернатива [9-11]: существует такое замкнутое множество - множество позиционного поглощения, что для

всех исходных позиций (t„,x,)e W° разрешима задача о сближении, а для всех исходных позиций (t„,x„)e ([to,9]xRm)\W° разрешима задача об уклонении.

Известно [9-11], что W0 есть также максимальный u-стабильный мост, т.е. максимальное в [to,6]xRm множество, оканчивающееся на {(0,х):хеМ} и обладающее свойством u-стабильности. Это свойство, введённое в конце 60х годов в теорию дифференциальных игр H.H. Красовским и А.И. Субботиным (см., например, [9-11]), допускает различные формулировки. В 1970-е годы были опубликованы работы H.H. Красовского [7,8], в которых формулировка свойства стабильности базировалась на унификационных схемах.

В пункте 1.2.2 представлена формулировка стабильности из [34-36], развивающая концепцию унификации [7,8]. Для этого вводятся гамильтониан H(t, х, 1) = шах min < 1, f (t, x,u, v) >, (t,x,l)e[t0,i}]xR"'xS системы (l), (2) и

ue P veQ

семейство многозначных отображений (t,x) н> Fv(t,x), \j/e Ч*, заданных на достаточно большой области D <z [to,0]xRm и удовлетворяющих условиям АЛ-А.З (стр. дисс. 33); здесь S = {leRm: ||l|=l}, Т - некоторое множество.

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

Xv'(t,;t*,X*) = (х.бГ: Xv(t*,t.,x,)nX* * 0}, XcRm.

8

В пункте 1.2.2 приводятся определения оператора к стабильного поглощения и и-стабильного моста \УсГ) в задаче о сближении с М в момент в, базирующиеся на множествах Ху"'(и;Лх*), (М*)еЕ, Х'с Я"™, уе здесь а = {(и,1): 10<1,<1*<9} с [и>, 6]х[1о, в].

От этих определений, выраженных в общей форме, перейдём к определениям в форме, наиболее час то используемой в диссертации. А именно, пусть на В задано семейство отображений (1,х) I—> Ру(1,х), здесь

РУ0,х)=Р(О(1,х) + С(1,х)у, Р(|)(Ч,х) = со{^"0,х,и): иеР}. В этой форме оператор к определяется равенством п(1.д",Х') = (ид*,Х*)еЕх2к".

\е<3

При решении задачи о сближении основная тяжесть ложится на выделение множества в [1о, 0]х11т. Описать точно при помощи эффективных аналитических соотношений можно лишь в редких случаях. В связи с этим на передний план выступает задача о приближённом вычислении \У°, которая рассматривается в пункте 1.2.3. Приводится определение из [35,36] аппроксимирующего оператора п стабильного поглощения и аппроксимирующей системы множеств {У/^,), ^еГ} в Я"1, отвечающих разбиению Даётся также определение предела О0 систем {^'"'О;), ^ е Гп}, отвечающих разбиениям Гп с диаметрами Д(п), ПшД|п) =0.

п—

В [35] показано: 0.°=^°, что даёт основание для приближённого вычисления в виде системы {У/00^), ^е Гп}. Однако, эта система не очень удобна для вычислений; необходима ещё дискретизация попятно вычисляемых множеств У^00^) в 11т. Поэтому в диссертации предлагается конструировать вместо {УГ""^), е Гп} некоторую новую систему множеств

(I), 1. е Гп, содержащихся в достаточно густой сетке К пространства Я1".

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

В качестве таких способов управления предлагаются позиционные процедуры управления с поводырём первого игрока, базирующиеся на копировании управлений. За работами [11,12] H.H. Красовского и А. И. Субботина, в которых была введена в теорию дифференциальных игр конструкция управления с поводырём, последовал ряд работ, посвященных применению управления с поводырём в задачах теории управления и дифференциальных игр. К ним относится работа [33], близкая к теме диссертации тем, что в ней проводится идея копирования, но не управлений, а ресурсов управлений. В [3] копирование управлений использовалось при построении управления с поводырём первого игрока в системах, линейных по управлениям игроков.

Настоящая диссертация обобщает результаты работы [3].

В параграфе 1.3 рассматривается система (1), (2) более общего вида, чем система из [3]. Здесь позиционная процедура управлений, базирующаяся на копировании управлений, пристраивается к системе {W(n)Oi)> Гп} множеств W'n)(t;) в Rm. Предполагается, что уже вычислена система {W'"'^), te Г,}, отвечающая разбиению r„={to, tIv..,tN(n>1, tN(n)=0}.

В фазовом пространстве Rm конструируются два движения - движение x[t] реальной системы (1), (2) и вспомогательное движение y[t] поводыря на [to, 9]. Конструирование происходит последовательно во времени по шагам [to,t,], [t|,t2],... разбиения Г„ вплоть до [tN(n)_i,tN(n)]. Начальная точка x[to]=xo движения x[t] задана и по ней вычисляется начальная точка y[to]=yo поводыря y[t] как ближайшая на W(n)(t0) к x[to]. На каждом очередном шаге [tk,tk+1], к>1, разбиения Гп первый игрок знает не только x[tk], но и x[tk_i], а также y[tj. Основываясь на этой информации о движениях, он определяет управление uk(t) в системе (1), (2) на шаге [tk,tk+i]: (x[tk.,], x[tk], y[tk]) м- uk(t) на [tk,tk+1). При этом процедура определения uk(t), te[tk, tk+)), к>1, начинается с выбора управления v.k второго игрока в поводыре на шаге [tk, tk+l]. А именно, управ-

1 4

ление v«k выбирается из условия копирования вектора vk"'=- f v(x)dx -

¿4-1 С,

среднего значения управления v(t) второго игрока в реальной системе (1), (2), реализовавшегося на предыдущем шаге [tu, tj. Далее из условия

f.(1)(tk,y[tk]) е Дк'(W<">(tk J- y[tk]-AkC(tk, y[tk])v„k) (6)

определяется вектор f«(l'(tk,y[tk])eF(1) (tk,y[tk]) и затем движение поводыря УМ = y[tk] + (t-tk) f.0) (tk,y[tj) + (t-tk) C(tk, y[tk]) v,k , te [tk,tk+1] (7) Следующим шагом является определение по вектору f*<1i(_tk,y[tij) кусочно-постоянного управления uk(t) первого игрока на [tk,tk+i) (см. стр. 58 диссертации). Управление uk(t) вместе с реализовавшимся на [tk,tk+i) управлением v(t) второго игрока порождает движение x[t] системы (1), (2). Далее процесс конструирования движений x[t] и y[t] переносится на следующий промежуток [tk+i,tk+2] разбиения Гп.

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

Теорема 1. Для любых е>0 и разбиения Г„ промежутка [t0,0] с диаметром А(0), удовлетворяющим eLie"'')T|(A<")) <е, позиционная процедура управления с поводырём первого игрока, базирующаяся на копировании управлении, обеспечивает при любых допустимых управлениях v(t), te[t0, 0] второго игрока включение х[9]еМе для движений x[t], x[t0] е W<n)(t0) конфликтно-управляемой системы (1), (2).

Здесь т|(5) > 0,5 > 0 - некоторая функция, т|(8) 4-0 при 5i0; L = Lf+Lc. Во второй главе рассматривается игровая задача о сближении с целевым множеством на конечном промежутке времени. Она подробно изучена рядом авторов. Здесь отметим определяющие теоретические результаты, полученные H.H. Красовским и А.И. Субботиным. Так в [11] изучена позиционная дифференциальная игра сближения-уклонения в общей постановке, сформулирована и доказана теорема об альтернативе в этой игре. Показано, что для начальных позиций игры, принадлежащих множеству W0, решение

И

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

Исследованию дифференциальных игр сближения-уклонения на конечном промежутке времени посвящены работы [4, 25, 30-32].

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

В параграфе 2.2 даётся постановка задачи о сближении с целевым множеством МсЯ"1 на конечном промежутке |Ч(Ь0]. В отличие от первой главы здесь не предполагается линейная зависимость правой части конфликтно-управляемой системы от управления V второго игрока.

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

Считаем, что задано некоторое семейство {Б^, уеЧ1} отображений Р¥: (Ч,х) к> Ру^х) на Б, удовлетворяющих условиям А.1 - А.З.

В параграфе 2.3 приводятся два эквивалентных определения и-стабильного моста [И], относящихся к более раннему этапу развития теории дифференциальных игр, и определения из [37] оператора стабильного поглощения к в задаче о сближении с М на [1!ь0] и и-стабильного моста в

терминах семейства {Ру: Ч'). При этом возникает важный вопрос о кор-

12

ректности определения: «Выделяют ли определения и-стабильного моста, выраженные в терминах двух различных семейств уеЧ'}, удовлетворяющих А.1 - А.З, одни и те же множества в пространстве позиций?»

В параграфе 2.3 даётся утвердительный ответ на этот вопрос. А именно, пусть заданы два множества 0=1,2) элементов у, 0=1,2) и пусть {1^":\)ле (¡=1,2) - два семейства отображений О.х) н» Р^1 (г.х) на Э соответственно. Каждое из этих двух семейств индуцирует свой оператор 7Г; стабильного поглощения в задаче о сближении с М на [10)9].

Теорема 2. Операторы ТГ] и лг эквивалентны, т.е. замкнутое множество \VczD является и-стабильным мостом относительно оператора п, тогда и только тогда, когда оно - и-стабнльный мост относительно оператора

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

Параграф 2.4 посвящён рассмотрению методов приближённого описания множества в задаче о сближении с М на [<:<),9]. В параграфе приводится определение из [37] аппроксимирующего оператора стабильного поглощения 71е в рассматриваемой задаче. Это определение тгЕ связано с некоторой

скалярной положительной функцией Т|(5), 5>0, = 0, которую для

ш 5

простоты обозначаем символом Т|. Каждой такой функции ставится в соот-

—'<■> А)

ветствие система V/ (I): ^ е Гп}. В [37] показано, что « есть предел аппроксимирующих систем множеств '(I/): ^ € Гп} при Д(п)—>0.

Этот факт даёт нам основание вычислять приближённо \У° как систему {„\У(П)(Х) еГ,}. Однако, в силу ряда причин, эта система неудобна для вычислений. Одна из этих причин состоит в том, что при вычислении каждого множества '(Г): ^ е Гп, мы сталкиваемся с необходимостью вычислять

предварительно объединение несчётного числа множеств в Ят. В параграфе

13

2.4 представлены варианты из работ [34,37] конструирования таких систем {^'"'(Г): ^ е Г„} в Г\ которые дают в пределе при Д(п)->0 множество \У° и в

то же время более удобны для вычислений, чем : ^ е Гп}. В этом

параграфе предложены некоторые модификации {^'"'((^^еГ,) систем {^'"'(^^¡еГ,}, направленные на дальнейшее упрощение процедур приближённого вычисления множеств ЛУ0. Отметим, однако, что сходимость систем {^Й00^): I е Гп} к при Л(п)—»0 пока не обоснована.

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

За основу такого представления взято пиксельное представление, которое уже раньше использовалось в [23] для вычисления максимальных и-стабильных мостов. Это представление было расширено для п-мерного случая в виде набора вокселей (кубиков со стороной 1 и с координатами вершин кратными сетке координат); способ аппроксимации компактного множества с помощью такого набора приводится в параграфе 3.1 диссертации. Для уменьшения размера занимаемой памяти использована информационная структура дерева п-мерных кубов, введённая в пункте 3.2.1; она является расширенным п-мерным вариантом структуры, описанной в работах [42,47].

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

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

Информационная структура дерева п-мерных кубов использует такое представление, что конкретные граничные воксели не обязательно имеют

14

собственный, отведённый именно под них, блок памяти. В пункте 3.2.4 приводится алгоритм выделения (и выборки) таких вокселей, а также граничных кубов большего размера. Информационную структуру дерева п-мерных кубов можно построить не только путём последовательного повоксельного добавления, но и на основе некоторого функционального определения формы множества; в пункте 3.2.5 приводится алгоритм для этого. Этот алгоритм очень похож на алгоритм, описываемый N. БьИе, А. Каи&аап[47], который ими используется только для представления и визуализации (исключение невидимых и слишком мелких кубов из обхода не производится) поверхностей в трёхмерном пространстве, заданных при помощи неявных функций.

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

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

В параграфе 3.3 описаны алгоритмы, применённые при реализации алгоритма построения максимального и-стабильного моста.

В пункте 3.3.2 предложен и обоснован метод построения выпуклой оболочки конечного множества точек в 11". На базе этого метода в пункте 3.3.3 предложен эффективный алгоритм построения выпуклой оболочки конечного множества точек, представленных центрами вокселей, описанных при помощи информационной структуры дерева п-мерных кубов. В качестве вспомогательного для него использован алгоритм нахождения вокселя с минимальным значением заданной функции (пункт 3.3.1). Алгоритм построения выпуклой оболочки отличается от тех, что уже существуют в qhull[41] и некоторых других библиотеках (например, СвАЦ, тем, что он быстрее, чем упомянутые алгоритмы, и, что самое важное, позволяет строить выпуклую оболочку, в случаях, когда её размерность меньше п.

Алгоритм состоит из трёх основных стадий: 1) формирование на базе исходного конечного множества точек в Я" симплекса с вершинами в этом множестве, имеющего максимальную возможную размерность; 2) пошаговое преобразование исходного многогранника (симплекса) в многогранник, описывающий выпуклую оболочку исходного конечного множества точек; 3) преобразование многогранника в воксельное представление (вокселизация).

В qhuH[41] первая стадия не описана и считается, что исходный симплекс может быть быстро сформирован перебором и его размерность равна п. Представленный в диссертации алгоритм последовательно наращивает размерность аффинного многообразия (и количество вершин симплекса), добавляя в симплекс вершины (и перестраивая аффинное многообразие), максимально удалённые в Я" от предыдущего аффинного многообразия.

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

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

В пункте 3.3.4 приводится алгоритм приближённого вычисления Этот алгоритм использует результаты первой главы и приближённое представление сечений множества вексельными множествами в Я". Разработка этого алгоритма - одна из основных целей диссертации. Именно для этого потребовалась разработка алгоритма построения выпуклой оболочки.

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

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

16

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

Как и в [47], нет необходимости визуализировать каждый воксель множества. В отличие от [47] визуализируются только те кубы из дерева, которые в значительной степени определяют результирующую картинку; для этого необходимо знать для каждого куба цвет и нормаль. Если для наиболее мелких кубов - векселей эта информация уже известна, то можно построить её и для более крупных кубов с использованием алгоритма из пункта 3.4.2.

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

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

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

17

экологической задаче при конкретных параметрах, отягощенной наличием фазовых ограничений на экологическую систему, построена система множеств : 1 € Гп}, аппроксимирующая \У°.

Система уравнений, описывающая экологическую задачу, имеет вид: х, =0,5х1(1-х1) + и1 + V, , хг =-0,5х2(1-х,) + и2 + у2 где и=(и|,и2) е Р, у=(уьу2) е<2 соответственно векторы управлений первого и второго игроков; Р и С? - многоугольники в Л2.

В четвёртой главе рассматривается также известная задача Р. Айзекса «шофёр-убийца» [2] и связанная с ней игровая задача о сближении с терминальным множеством МсР2, имеющим вид круга радиуса 1. Система уравнений в этой задаче в редуцированном пространстве имеет вид:

V7, . V/,

гдедуь Л - параметры системы, и( - скалярное управление первого игрока, |и)|<1, \'=(уьу2) - управление второго игрока, ||у|[<1.

Эта задача рассматривалась различными авторами, в том числе, в работах [24,43,45,46] как в традиционной постановке, так и в различных её модификациях; проводилось моделирование на ЭВМ. Эта задача также рассматривается в различных вариантах; вычисляются системы множеств {^"'О,), ^ е Гп} , аппроксимирующие \У°, и для некоторых вариантов реализуется разрешающая процедура управления с поводырём первого игрока, представленная в пункте 3.3.5 диссертации. Отличие этой работы от упомянутых выше работ состоит в применении вексельных методов в моделировании и в использовании разрешающих процедур управления с поводырём, базирующихся на копировании управлений. Моделирование задачи и её модификаций на плоскости приведено в параграфах 4.3-4.5.

В параграфе 4.6 рассмотрена нелинейная по фазовой переменной конфликтно-управляемая система в Л3, в основу динамики которой положены уравнения задачи «шофёр-убийца»

V/, о

-х,и, + \угу2+|Зх3 + у, х3=лу,и2

11(1 +(рх3)2) 21 2 " 2 11(1 + (рх3)2) где, и=(иьи2), у—^^уг) - векторы управлений игроков, ||и||<1, |М|<1.

Множество М в этой задаче - шар в Я3 радиуса 1 с центром в начале координат; 11=1, \У|=3, \у2=1, |3=0,1, у=0,5; = [0;6,3]. Для этой задачи вычислена система {А^'"'^,): ^ е Гп}, аппроксимирующая множество

Основные результаты.

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

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

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

• алгоритм выделения граничных вокселей множества в Я";

• алгоритмы пересечения и объединения вексельных представлений множеств в Я";

• алгоритм построения выпуклой оболочки множества в Я", состоящего из конечного числа точек;

• алгоритм заливки области в К".

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

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

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

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

Список цитируемой литературы

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

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

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

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

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

6. Красовский А.Н., Красовский H.H., Третьяков В.Е. Стохастический программный синтез для детерминированной позиционной дифференциальной игры. II Прикл. мат. и механика. - 1981. - Т. 45. № 4. - С. 579-586.

7. Красовский H.H. К задаче унификации дифференциальных игр. // Докл. АН. СССР. -1976. - Т.226. № 6, - С. 1260-1263.

8. Красовский H.H. Унификация дифференциальных игр. // Игровые задачи управления. - УНЦ АН СССР. Свердловск, 1977. - С. 32-34.

9. Красовский H.H., Субботин А.И. Экстремальные стратегии в дифференциальных играх. //Докл. АН СССР. - 1971. - Т. 196., № 2. - С. 278-281.

10. Красовский H.H., Субботин А.И. Альтернатива для игровой задачи сближения // Прикл. мат. и механика. - 1970. -Т. 34. вып. 6. - С. 1005-1022.

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

12. Красовский H.H., Субботин А.И. Аппроксимация в дифференциальных играх // Прикл, математика и механика. 1973. Т. 37, вып. 2. С. 197-204.

13. Кряжимский A.B., Максимов В.И. Аппроксимация линейных дифференциально-разностных игр //Прикл. мат. и механика. - 1978. - Т.42., вып.2. - С.202-209.

14. Куржанский А.Б. Альтернированный интеграл Понтрягина в теории синтеза управлений // Труды Мат. Ин-та им. Стеклова. - 1999. - Т. 224. - С. 234-248.

15. Лукоянов Н. Ю. О свойствах функционала цены дифференциальной игры с наследственной информацией // Прикладная математика и механика. - 2001. - Т. 65. вып.З. - С. 375-384.

16. Меликян A.A., Овакимян H.B. Игровая задача простого преследования на двумерном конусе//Прикл. математика и механика. - 1997.-Т. 55, вып. 5. - С.741-751.

17. Меяикяи A.A., Черноусько Ф.Л. Выбор моментов наблюдений в линейной игре сближения. //Изв. АН СССР. Техн. кибернетика. - 1979. - № 1. - С. 11 -16.

18. Мищенко Е.Ф. Задачи преследования и уклонения от встречи в теории дифференциальных игр. // Изв. АН СССР. Техн. кибернетика. - 1971. -№5. - С. 3-9.

19. Мищенко Н.Ф., Никольский М.С., Сатимов Н. Задача уклонения от встречи в дифференциальных играх многих лиц. // Тр. МИАН СССР. - 1977. - Т. 143. - С.105-128.

20. Никольский М.С. Об альтернированном интеграле Л.С. Понтрягина.//Мат.сб. - 1981. -Т.П6,№ 1. — С.136-144.

21. Осипов Ю.С. К теории дифференциальных игр в системах с распределёнными параметрами. // Докл. АН СССР. - 1975. - Т. 223., №6. - С. 1314-1317.

22. Остапенко В.В. Аналитические и приближённые методы решения задач сближения-уклонения в дифференциальных играх: Автореф. дис. д-ра физ.-мат. наук. - Киев, 1987. - 320 с.

23. Пахотинских В.Ю., Успенский A.A., Ушаков В.Н. Конструирование стабильных мостов в дифференциальных играх с фазовыми ограничениями // Прикл. математика и механика. - 2003. - Т. 67, вып. 5. - С.771-783.

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

25. Половинкин Е.С. Об аналитическом описании оператора в неавтономных дифференциальных играх. // Мат. методы упр. и обработки информации. - М., 1984. — С. 110115.

26. Пономарёв А.П., Розов Н.Х. Устойчивость и сходимость альтернированных сумм Понтрягина. //Вести. МГУ. Вычисл. Математика и кибернетика. - 1978. - вып.1. - С. 82-90.

27. Понтрягин Л.С. О линейных дифференциальных играх, II // Докл. АН СССР. —1967. — Т. 175, № 4. - С. 764-766.

28. Понтрягин Л.С. Математическая теория оптимальных процессов и дифференциальные игры // Тр. МИАН СССР. - 1985. - Т. 169. - С.119-157.

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

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

31. Пшеничный Б.Н., Онопчук Ю.Н. Линейные дифференциальные игры с интегральными ограничениями // Изв. АН СССР. Техн. кибернетика. - 1968. -№ 1. - С. 13-22.

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

33. Субботина H.H., Субботин А.И. Альтернатива для дифференциальной игры сближения-уклонения при ограничениях на импульсы управления игроков. // Прикл. математика и механика. - 1975.-Т. 39, вып. 3. -С. 397-406.

34. Тарасьев А.М. Некоторые задачи теории дифференциальных игр на конечном промежутке времени: Автореф. дис. канд. физ.-мат. наук. - Свердловск, 1985. - 14 с.

35. Тарасьев A.M., Ушаков В.Н. О построении стабильных мостов в минимаксной игре сближения-уклонения. - Свердловск, 1983.-61с.-Деп. В ВИНИТИ 19.04.83. №245483.

36. Тарасьев A.M., Ушаков В.Н., Хрипунов А.П. Об одном вычислительном алгоритме решения игровых задач управления. // Прикл. математика и механика. - 1987. - Т. 51. вып. 2.-С. 216-222.

37. Ушаков В.Н. Процедуры построения стабильных мостов в дифференциальных играх: Дис. д-ра физ.-мат. наук. - Свердловск, 1991. - 308 с.

38. Ченцов А.Г. Об игровой задаче сближения в заданный момент времени // Мат. сб. -1976. - Т.99, №3 - С. 394-420.

39. Черноусысо Ф.Л., Меликян A.A. Игровые задачи управления и поиска - М.: Наука, 1976.-270 с.

40. Чикрий A.A. Нелинейная задача об уклонении от встречи с терминальным множеством сложной структуры // Прикл. математика и механика. - 1975. - Т. 39. вып. 1. - С. 3-11.

41. Barber C.B., Dobkin D.P., and Huhdanpaa, H.T. The Quickhull algorithm for convex hulls // ACM Trans, on Mathematical Software. 1996. - V. 22 N.4. - P. 469-483. -http://wwyv.qhull.org

42. Benson D., Davis J. Octree Textures // ACM TRANSACTIONS ON GRAPHICS, Academic Press - 2002. - V.21, N.3, - P. 785-790.

43. Breakwell J. V., Merz A. W. Toward a complete solutions of the homicidal chauffeur game // Proc. 1st Intern. Conf. Theoiy and Appl. Different. Games. - Amherst, Mass., 1969. - S.I., S.a.-P.III/1-111/5.

44. Fleming W.H. The convergence problem for differential games // J. Math. Anal, and Appl. -1961.-Vol. 3, No.l.-P. 102-116.

45. Marchai С. Analytical study of case of the homicidal chauffer game problem // Lect. Notes Comput. Sei. - 1975. - Vol. 27. - P. 472-481.

46. Merz A.W. The homicidal chauffer // AIAA Journal. 1974. - Vol. 12, No. 3. - P.259-260.

47. Stolte N. Kaufman A. Novel Techniques for Robust Voxelization and Visualization of Implicit Surface // Graphical Models, Academic Press. -2001. - V.63, N.6.-P. 387-412.

Работы автора по теме диссертации

1*. Михалёв Д.К. Использование 2"-дерева (дерева n-мерных кубов) для хранения и обработки данных // ПРОБЛЕМЫ ТЕОРЕТИЧЕСКОЙ И ПРИКЛАДНОЙ МАТЕМАТИКИ: Труды 37-й Региональной молодежной конференции. - Екатеринбург: УрО РАН, 2006. -С. 487-491.

2*. Михалёв Д.К. Использование 2"-мерных кубических деревьев для реализации пиксельного метода расчёта областей достижимости в n-мерном пространстве и визуализации результатов. //ИЗВЕСТИЯ ИНСТИТУТА МАТЕМАТИКИ И ИНФОРМАТИКИ: Конференция по теории управления и математическому моделированию. - Ижевск: Удмуртский Государственный Университет. 2006. Вып. 3. №37 - С. 105-106.

3*. Михалёв Д.К. Использование 2° дерева (дерева п мерных кубов) для определения взаимодействий объектов и построения множеств достижимости.// АКТУАЛЬНЫЕ ПРОБЛЕМЫ ПРИКЛАДНОЙ МАТЕМАТИКИ И МЕХАНИКИ: Тезисы докладов III Всероссийской конференции, посвященной памяти академика А. Ф. Сидорова (4-10 сентября 2006 г.) - Екатеринбург: ИММ УрО РАН. 2006. - С. 77-78.

4*. Михалёв Д.К. Модифицированное хранение информации для вычисления множеств достижимости пиксельным методом. Алгоритмы визуализации и других операций над такими множествами. // Математическая теория оптимального управления и теория дифференциальных включений. Программа и аннотация докладов научного семина-ра(12-13октября). -М. МГУ. 2006. - С. 40.

5*. Ушаков В.Н., Михалёв Д.К. О свойстве стабильности в дифференциальных играх // ИЗВЕСТИЯ ИНСТИТУТА МАТЕМАТИКИ И ИНФОРМАТИКИ: Конференция по теории управления и математическому моделированию. - Ижевск; Удмуртский Государственный Университет. 2006. Вып. 3. №37 - С. 155-156

6*. Ушаков В.Н., Михалёв Д.К. О некоторых игровых задачах управления на конечном промежутке времени. //Труды IX Международной Четаевской конференции «Аналитическая механика, устойчивость и управление движением». Иркутск. Институт динамики систем и управления (Сибирское отделение РАН). - 2007. Т.1 - С.208-222.

7*. Ушаков В.Н., Михалёв Д.К. О двух алгоритмах приближённого построения множества позиционного поглощения в игровой задаче сближения. // Автоматика и Телемеханика.- 2007. №11- С. 178-194. 8*. Ушаков В.Н., Михалёв Д.К. Об одном варианте управления в игровых задачах о сближении. // Международная конференция «Управление динамическими системами». ИПМех РАН. Тезисы докладов,- М. 2009. - С. 89. 9*.Ушаков В.Н., Михалёв Д.К. Об одном варианте управления с поводырём в игровых задачах о сближении. //Алгоритмический анализ неустойчивых задач. Тезисы докладов Международной конференции посвящённой 100-летию со дня рождения В. К. Иванова. - Екатеринбург: изд-во УРГУ, 2008 - С. 244. 10*.Ушаков В.Н., Решетов В.М., Байдосов И.В., Михалёв Д.К. Свойство стабильности в дифференциальных играх с фазовыми ограничениями. // Известия Уральского государственного университета. Екатеринбург. - 2006. Вып. 10,№46 —С. 196-219. ll*.Gubkin A., Shturkin N., Mikhalev D., Ovechkina E.. Voxel Technologies in modeling and visualization // The 1st Korea-Russia International Workshop on Mobile and Telecommunication Technology, Ekaterinburg. -2005. - P. 3-5.

Работа выполнена при поддержке программы Президиума РАН №29 «Математическая теория управления», гранта РФФИЛ» 08-01-00587_а.

Подписано в печать 20.05.2009. Формат 60x84 1/16. Усл. печ. л. 1,5. Тираж 100 экз. Заказ № 107.

Типография «Уральский центр академического обслуживания» 620219, г. Екатеринбург, ул. Первомайская, 91

Введение.

Глава 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].

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.