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

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

КУМКОВ Сергеи Сергеевич

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

05 13 18 — математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации па соискание ученой степени кандидата физико-математических наук

2 4 ГДП 2007

Екатеринбург — 2007

003060100

Работа выполнена в отделе динамических систем Института математики и механики Уральского отделения РАН

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

Падко Валерий Семенович

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

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

Ведущая организация: Московский государственный университет

им М В Ломоносова

Защита состоится 23 мая 2007 года в 15— на заседании диссертационного совета К 212 286 01 по присуждению ученой степени кандидата физико-математических наук при Уральском государственном университете им А М Горького по адресу 620083, г Екатеринбург, пр Ленина, 51

С диссертацией можно ознакомиться в Научной библиотеке Уральского государственного университета им А М Горького.

Автореферат разослан 20 апреля 2007 г

Ученый секретарь диссертационного совета, доктор физ-мат наук, профессор ь^--*^" В Г Пименов

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

Актуальность темы. Диссертация посвящена численному исследованию особенностей множеств уровня функции цены в линейных дифференциальных играх с фиксированным моментом окончания Предполагается, что непрерывная квазивыпуклая функция платы зависит от некоторых двух компонент фазового вектора в момент окончания игры В рамках данной работы под особенностями понимаются ситуации вырождения временных сечений (i-сечений) множеств уровня — «узкие шейки», специфические соотношения, связывающие f-сечения различных множеств уровня, нарушения регулярной структуры полей оптимальных движений, идущих по границе множеств уровня (излом, расщепление, слияние и тд )

Теория дифференциальных игр в настоящее время — развитая математическая дисциплина Первые отчеты Р Айзекса по дифференциальным играм относятся к 1951 году В 1965 году была опубликована его книга «Дифференциальные игры», переведенная на русский язык в 1967 году1 В нашей стране динамические задачи конфликтного управления рассматриваются с начала 60-х годов прошлого века Первыми были работы JI С Понтрягина и Н Н Красовского В 1974 году опубликована книга Н Н Красовского и А И Субботина2 В ней, в частности, предложена позиционная формализация дифференциальных игр и доказана теорема об альтернативе, родственная теореме существования функции цены Важные результаты были получены в работах JI А Петросяна и Б Н Пшеничного

Среди работ зарубежных авторов конца 60-х - начала 70-х годов прошлого века отметим работы L D Berkovitz, A Blaquiere, J V Breakwell, W H Fleming, A Friedman, G Leitmann, A W Merz В них рассматривались теоремы существования функции цены в подходящем классе стратегий и развивался метод Р Айзекса решения дифференциальных игр при помощи построения сингулярных поверхностей

1 Айзеке Р Дифференциальные игры М Мир, 1967

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

Более поздние результаты, относящиеся к 1980-м годам, связаны с истолкованием функции цены игры как обобщенного решения уравнения Гамильтона-Якоби-Беллмана-Айзекса Теория, опирающаяся на понятие минимаксного решения, была создана А И Субботиным Полученные результаты отражены в книге 2003 года3 Близкое понятие вязкостного решения было введено в работах M G Crandall и Р L Lions В этом направлении интенсивно работают в настоящее время M Bardi и I Capuzzo-Dolcetta

Параллельно с развитием теории разрабатывались и численные методы Опыт создания первых универсальных алгоритмов решения некоторых классов дифференциальных игр отражен в сборнике4, опубликованном в 1984 г в Екатеринбурге Большую роль в создании алгоритмов и их обосновании сыграли работы H J1 Григоренко, M С Никольского, В С Пацко, Е С Половинкина, В H Ушакова

За рубежом численные методы интенсивно развиваются с начала 1990-х годов В этой области проводят исследования итальянские математики M Bardi, M Falcone, P Soravia, французские — P Cardaliaguet, M Qumcampoix, P Saint-Pierre, немецкие — M H Breitner, H J Pesch

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

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

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

3 Субботин А И Обобщенные решения уравнений в частных производных первого порядка перспективы динамической оптимизации — M , Ижевск Ин-т компьютер исслед , 2003

4 Алгоритмы и программы решения линейных дифференциальных игр / Ред А И Субботин, В С Пацко — Свердловск, 1984

алгоритмы

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

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

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

Результаты диссертационной работы являются новыми

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

Структура и объем работы. Диссертация состоит из введения, списка основных обозначений, трех глав, списка литературы и списка иллюстраций Диссертация подготовлена в системе ЖГ^Х Общий объем диссертации составляет 127 страниц Библиографический список включает 83 наименования, в том числе 16 публикаций автора по теме дис-

сертации Список иллюстраций включает 77 позиций

Апробация работы. Основные результаты диссертации докладывались автором и обсуждались на конференциях молодых ученых Института математики и механики УрО РАН (Екатеринбург, 2000, 2001 гг), 28-й, 30-й, 31-й, 33-й региональных молодежных конференциях «Проблемы теоретической и прикладной математики» (Екатеринбург, 1997,

1999, 2000, 2002 гг), на международных конференциях the 8th International Colloquium on Differential Equations, August 18-23, 1997, Plovdiv, Bulgaria, IFAC Workshop on Nonsmooth and Discontinuous Problems of Control and Optimization, Chelyabinsk, Russia, 17-20 June 1998, the 8th International Symposium on Dynamic Games and Applications, July 5-8, 1998, Chateau Vaalsbroek, Maastricht, the Netherlands, the 11th IFAC Workshop "Control Applications of Optimization" (CAO 2000), July 3-6,

2000, St Petersburg, Russia, the 10th International Symposium on Dynamic Games and Applications, July 8-11, 2002, Saint-Petersburg, Russia, the 4th International ISDG Workshop, May 19-21, 2003, Goslar, Germany, конференции «Демидовские чтения на Урале», Екатеринбург, 1-3 марта 2006 г, семинарах отдела динамических систем и отдела управляемых систем ИММ УрО РАН, семинаре лаборатории управляемых систем Института проблем механики РАН, семинарах кафедры оптимального управления факультета ВМиК МГУ и кафедры общих проблем управления механико-математического факультета МГУ, семинаре кафедры кибернетики Московского института электроники и математики, семинаре кафедры дифференциальных уравнений Удмуртского госуниверситета, семинаре кафедры прикладной математики Челябинского госуниверситета

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

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

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

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

Рассматриваются антагонистические линейные дифференциальные игры

с фиксированным моментом окончания Т и квазивыпуклой непрерывной функцией платы <р, зависящей от двух компонент гг, г3 фазового вектора Квазивыпуклой называем функцию, все множества уровня (множества Лебега) которой выпуклые Первый (второй) игрок распоряжается управлением и (ь), выбирая его из выпуклого компакта Р (<3) в своем конечномерном пространстве так, чтобы минимизировать (максимизировать) значение функции <р в момент Т

От игры (1) переходим к эквивалентной дифференциальной игре при помощи замены £(£) = Х1^{Т,€)г(€), где Хгз(Т,Ь) — матрица, составленная из г-й и ,?-й строк фундаментальной матрицы Коши Х(Т, £) для системы г = А{€) г Эквивалентная игра имеет вид

Алгоритм5 попятного построения максимального стабильного моста W для игры (2), вытягиваемого от выпуклого компактного терминального множества М (от множества уровня функции платы), реализует идею альтернированного интеграла JI С Понтрягина6 На выходе алгоритма получаем набор многоугольников W{€), приближающих t-сечения W(t) моста W

5 Исакова Е А , Логунова Г В , Пацко В С Построение стабильных мостов в линейной дифференциальной игре с фиксированным моментом окончания // Алгоритм мы и программы решения линейных дифференциальных игр — Ред А И Субботин, В С Пацко, Свердловск, 1984 — С 127-158

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

z = A(t)z + B(t)u + C(t)v, te\to,T], zeE", ueP cr, veQcW, <p(zt(T),zj(T)),

(1)

f = D(t)u + E(t)v,

t e \t0,T], £eR2, ueP, v e Q, &(Т))

(2)

Вводится сетка моментов времени {to < t\ < < t,\r = Т} с шагом Д На этой сетке динамика игры (2) подменяется кусочно-постоянной Множества Р, Q, М подменяются выпуклыми многогранными аппроксимациями Р, Q, М Полагаем W(i;v) = М Затем множество W(iIv) пересчитывается в множество которое в свою очередь пересчитывается в множество W(i^-2), и т д Процедура пересчета использует опорную функцию предыдущего (в обратном времени) сечения W(iJ+i) и опорные функции вектограмм первого V(U) = —D(tt)Р и второго Q(tj) = U(ij)Q игроков А именно, опорная функция нового сечения W(£t) есть7 выпуклая оболочка функции

~/(1,1г) = p(l,W(t1+1)) + A p(l,V(U))- Д p(i,Q(i,)), (3)

т е

p(,W(i,))=conv7(,t,) (4)

Процесс построений прекращается либо по достижении момента to, либо когда выпуклая оболочка очередной функции -у( , i,) является несобственной функцией, те W(tt) = 0

Имеет место сходимость численно построенных i-сечений приближенного моста W к сечениям идеального моста W в метрике Хаусдорфа Оценки погрешностей приведены в работе Н Д Боткина8

Первый из примеров, численно исследованных в диссертации при помощи программы, реализующей описанный алгоритм — модельная игра9'10, связанная с задачей воздушного перехвата Преследователем в

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

8 Botkm N D Evaluation of numerical construction error m differential game with fixed terminal time // Problems of Control and Information Theory, Vol 11, №4, 1982 — pp 283-295

9Shmar J , Medmah M , Biton M Singular Surfaces m a Linear Pursuit-Evasion Game with Elliptical Vectograms // Journal of Optimization Theory and Optimization, Vol 43, No 3, 1984 — pp 431—458

10 Shmar J, Zarkh M Pursuit of a Faster Evader — a Linear Game with Elliptical Vectograms // Proceedings of the Seventh International Symposium on Dynamic Games, Yokosuka, Japan, 1996 — pp 855—868

этой задаче выступает ракета-перехватчик, убегающим — маневрирующая воздушная цель (самолет или другая ракета) Естественной платой в такой игре является расстояние наименьшего сближения, т е промах, который минимизируется преследователем Р и максимизируется убегающим Е Векторы номинальных скоростей (Vp)nom и (Ve)nom являются постоянными и направленными так, что имеется точная встреча на номинальных траекториях Управляющее ускорение каждого объекта перпендикулярно вектору его текущей скорости Максимальные значения боковых ускорений ограничены константами ар и а я Полагается, что ар > ое Убегающий непосредственно управляет своим ускорением, а догоняющий — инерционно, с постоянной времени тр Возможности объектов по изменению направления вектора их скорости в процессе движения являются малыми (слабо маневрирующие объекты)

Выбор координат производится следующим образом Начало координат О совмещается с номинальным положением Рпот догоняющего в начальный момент Ось ОХ направлена вдоль начальной номинальной линии визирования Ось OY перпендикулярна ОХ и лежит в плоскости, определяемой векторами номинальных скоростей объектов (рис 1) Ось OZ направлена перпендикулярно первым двум осям

Поскольку отклонения скоростей Vp(t) и Ve(é) от их номиналь-

ных значений (Ур)пот и (Т/Е)пот малы, относительное движение вдоль оси ОХ может рассматриваться как равномерное и промах можно просчитывать в момент номинальной встречи в виде расстояния между объектами в плоскости У 2 в этот момент Стало быть, задача минимизации трехмерного промаха на заданном промежутке времени может быть сведена к минимизации расстояния в плоскости У 2 в фиксированный момент Т номинальной встречи

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

Здесь х — вектор положения первого (догоняющего) игрока, у — вектор положения второго (убегающего) игрока, тр — постоянная времени, характеризующая инерционность отработки управления первого игрока Множества Р и <5, ограничивающие управления первого и второго игроков, являются эллипсами

Полуоси Ар, Вр, Ае, Ве параллельны координатным осям и вычисляются на основе ограничений ар, ае на ускорения игроков и косинусов углов (хр) пот и (,\7',')пшп Момент окончания Т игры фиксирован Платой является геометрическое расстояние между объектами в момент окончания. Первый игрок минимизирует функцию платы, второй — максимизирует

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

х = Р,

-Р = -(Г - и)/тР

у = у,

г е [О,т], ж,уеМ2, и е Р, V е <2, <р(х(Т),у(Т)) = \у(Т)-х(Т)\

(5)

Рис. 2: Множество уровня с узкой шейкой, близкое к критическому (внутреннее темное), и большее множество уровня (внешнее прозрачное)

Рис. 3: Увеличенный фрагмент с узкой шейкой 11

шейки Здесь и далее критическим называем множество уровня функции цены с непустыми Усечениями на [¿о> имеющее на (¿о,Т) одно или более ^-сечений с пустой внутренностью На рис 2 приведен вид двух множеств уровня близкого к критическому и большего Видно, что большее множество уровня имеет гладкую границу Это означает, что именно около узкой шейки сосредоточены нерегулярности функции цены (рис 3) Чтобы правильно отразить их, нужны очень аккуратные вычисления в районе узкой шейки Кроме того, потребовались хорошие средства визуализации трехмерных максимальных стабильных мостов Соответствующие программы были разработаны в 1997-2000 гг в секторе компьютерной визуализации отдела системного обеспечения ИММ УрО РАН В Л Авербухом, А И Зенковым, Д А Юртаевым

Вычислительные качества программы проверялись и на других примерах, относящихся, как и система (5), к классу игр, которые называются «обобщенный контрольный пример Л С Понтрягина»11,12 Среди прочих был подобран и просчитан следующий пример

£ — 0 025£+13х = и, у + у = ь, . .

вер, уеЯ, ф(Т),у(Т)) = \у(Т) - х(т)\

Ограничения на управления игроков были взяты в виде одинаковых эллипсов

" = е = Н2 4 + ш^1}

На рис 4 приведен общий вид множества уровня функции цены, обладающего двумя узкими шейками Отмечены моменты обратного времени, соответствующие узким шейкам Множество уровня построено для значения с = 1 2 функции платы

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

11 Никольский М С Первый прямой метод Л С Понтрягина в дифференциальных играх — М Изд-во Моек ун-та, 1984

12 Чикрий А А Конфликтно управляемые процессы — Киев Наукова Думка, 1992

I

Рис. 4: И фа (6): общий вид множества уровня функции цены с двумя узкими шейками

Геометрической разностью (разностью Минковского) множеств А и В называют13'14 совокупность элементов пространства, «вдвигающих» множество В в множество А при помощи алгебраической суммы:

А ± В = {ж : В + х С ,4}.

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

]3 Хадвпгер Г. Лекции об объеме, площади поверхности и нзоперемегрии. — М: Наука, 1966.

14Понтрягин Л.С. Линейные дифференциальные игры, 1 // Докл. АН СССР, №6, Т. 174, 1967. - С- 1278-1280.

уменьшаемого

В + (А ± В) С А

Если же множества А и В таковы, что в предыдущем соотношении имеет место равенство, т е

В + (А — В) = А,

то говорят, что множество А полностью выметается множеством В (множество В полностью выметает множество А) Понятие полного выметания введено в работе П Б Гусятникова и М С Никольского15

Пусть / — скалярная функция аргумента х и Мс — {х /(я) ^ с} — ее множество уровня, соответствующее константе с Будем говорить, что функция обладает свойством уровневого выметания, если для любой пары констант с\ < С2 в случае непустоты множества уровня МС1 этой функции оно полностью выметает множество уровня МС2

Результатом второй главы является следующая Теорема. Пусть непрерывная квазивыпуклая функция платы (р() дифференциальной игры (2) обладает свойством уровневого выметания для любых двух констант с\ < сг ее множество уровня МС1 (если оно непусто) полностью выметает множество уровня МС2

Тогда соответствующие множества уровня И^ и 1¥С2 функции цены У( ) игры (2) обладают аналогичным свойством для каждого момента £ [¿о^] такого, что сечение меньшего множества уровня непусто, сечение \УС1(1„) полностью выметает сече-

ние У/С2{и) большего множества уровня

Обоснование теоремы базируется на рекуррентном правиле пересчета (3), (4), записанном на языке множеств

\У(гг) = + д г (и)) ^ д й{и)

Таким образом, для того, чтобы проверить наличие полного выметания сечения УУС2{1*) сечением множеств уровня в некоторый мо-

15 Гусятников П Б , Никольский М С Об оптимальности времени преследования // Докл АН СССР, Т 168, № 3, 1969 — С 518-521

мент в предположении о полном выметании множества МС2 множеством МС1, следует проверить сохранение этого свойства при операциях алгебраической суммы, геометрической разности и при предельном переходе с измельчением шага сетки по времени

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

Лемма (2.5.1). Пусть множества А и В таковы, что множество А полностью выметается множеством В, т е А = В + [А — В) Тогда для любого множества Р имеем

(А + Р) — (В + Р) + ((Л + Р) — (В + Р))

Лемма (2.5.2). Пусть выпуклые компакты А, В С К2 таковы, что множество А полностью выметается множеством В Тогда для любого выпуклого компакта <5 С К2 такого, что В — С} ^ 0, имеем

(А^О) = {В ((А д))

Отметим, что первая из этих лемм верна в пространстве любой размерности и для любых множеств А, В, Р (от них не требуется ни выпуклость, ни замкнутость, ни ограниченность) Вторая же лемма специфична для пространства К2, что показывается соответствующими контрпримерами

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

Типы сингулярных поверхностей описаны в книге Р Айзекса «Дифференциальные игры» Исходя из вариантов поведения оптимальных

движений (другими словами, обобщенных характеристик уравнения Га-мильтона-Якоби-Беллмана-Айзекса), выделяют следующие виды сингулярных поверхностей рассеивающие, универсальные/фокальные, эки-вокальные, поверхности переключения Необходимые условия, характеризующие тот или иной тип сингулярной поверхности, получены Р Bernhard16 и А А Меликяном17 В работах A W Merz, J Lewm, J G Olsder, J Shinar исследованы сингулярные поверхности, возникающие в конкретных задачах Автору неизвестны работы, посвященные численным алгоритмам глобального построения сингулярных поверхностей в дифференциальных играх

В диссертации предложена следующая схема построения сингулярных поверхностей В процессе нахождения очередного сечения W (¿г) максимального стабильного моста W на границе öW(ij) выделяются сингулярные точки, которые классифицируются и связываются с точками на границе öW(ii+i) ранее построенного в обратном времени сечения W(fj+i) В итоге после построения рассматриваемого стабильного моста имеем совокупность сингулярных линий на его границе Сингулярные поверхности строятся на основе набора сингулярных линий, снятых с системы мостов (множеств уровня функции цены)

Таким образом, первичными являются сингулярные линии на границе множеств уровня

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

Для случая скалярных управлений сингулярными оказываются точки на границе сечения W(it), для которых конус внешних нормалей содержит нормали отрезков вектограмм 7-,(ii) и Q(tt) игроков

Bernhard Р Singular Surfaces in Differential Games an Introduction // Differential Games and Applications — Springer-Verlag, Berlin, 1977. — pp 1-33

17 Melikyan A A Generalized Characteristics of the First Order PDEs Applications in Optimal Control and Differential Games — Burkhauser, Boston, 1998

Классификация типа сингулярности основана на анализе дополнительных меток, которые присваиваются векторам, описывающим строение положительно-однородной кусочно-линейной функции 7(,£г) (3), и затем проходят сквозь процесс построения выпуклой оболочки этой функции Для выделения сингулярных точек некоторых типов дополнительно требуется анализ «негладкости» соответствующих вершин многоугольника \У(£г) Вершина называется «гладкой», если ее конус внешних нормалей имеет раствор меньше заданного порога

Для случая строго выпуклых ограничений обнаружение особых точек основано на поиске «негладких» вершин построенного сечения Найденные точки связываются с точками на предыдущем сечении \У(£г+1) Точки считаются соответствующими, если их конусы внешних нормалей пересекаются Классификация сингулярных точек основана на анализе развития конуса Если в обратном времени конус раскрывается, точка помечается как рассеивающая Если конус сужается, точка помечается как фокальная Если конус поворачивается (необязательно сохраняя величину раствора), то точка помечается как экивокальная

Приведем результаты построения сингулярных поверхностей в игре « конфликтно-управляемый осциллятор »

хг = Х2 + V, х2 = —х\ +и, £ € [0, 81,

(7)

М ^ 1, Н ^0 9, (р(х1,х2) = х\ + х2

Рисунок 5 показывает два ракурса системы сингулярных поверхностей для игры (7) в исходных координатах х\, х2 Сингулярные поверхности разного типа отмечены соответствующими цифровыми выносками В пояснении к выноскам добавочные слова «за первого игрока» означают, что на соответствующей поверхности скачком меняется управление первого игрока При этом оптимальное управление второго игрока одно и то же по разные стороны вблизи от поверхности Добавочные слова «за обоих игроков» означают скачкообразное изменение оптимального управления каждого игрока

Обратное время т на рис 5 идет справа налево Вблизи начала обрат-

Рис. 5: Два ракурса системы сингулярных поверхностей для задачи «конфликтно-управляемый осциллятор» (7): 1 — поверхность переключения за первого игрока, 2 — поверхность рассеивания за второго игрока, 3 - экивокальная поверхность, 4 — поверхность рассеивания за обоих игроков

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

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

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

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

XI = XI + 2х2 + VI, М < 1, (У1,У2)Г € <3, ^

х2=х2+и + у 2, (р(х\,х2) = х\ + х2

Общий вид характерного максимального стабильного моста в исходных координатах XI, х2 приведен на рис 6 Стабильный мост просчитан для случая, когда множество С} было выбрано в виде отрезка {|г>1| ^ 0 9, г>2 = 0} Значение платы было взято равным с = 7 0

Рис. 6: Общий вид характерного множества уровня функции цены для игры (8)

Обрыв моста произошел в момент г = 6.9 обратного времени.

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

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

Рассматриваемый пример был использован для исследования зависимости строения сингулярных поверхностей от параметров игры. Для одного и того же интервала значений платы с €1 [0.5, 7.0] было просчитано шесть вариантов игры с различным размером и ориентацией отрезка Ц ограничения на управление второго игрока. Выли взяты два размера отрезка ф: отрезок длины 1.8 — случай «сильного» первого игрока — и отрезок длины 2.2 — случай «слабого» первого игрока. (В первом случае длина отрезка <2 меньше длины отрезка Р, а во втором больше.)

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

а) отрезок <3 на горизонтальной оси ь\

б) отрезок С} на биссектрисе первого и третьего координатных углов

<3 = {и! = и2} П {и? +

в) отрезок <3 на вертикальной оси г>2

<2 = {г>1 = 0} П {и? + VI ^ I2} Здесь I — половина длины отрезка (3, равная, соответственно, 0 9 или 1 1 Результаты построения системы сингулярных поверхностей в исходных координатах х\, приведены на рис 7 и 8 Обозначения подри-сунков соответствуют вариантам ориентации отрезка С} Цифровые выноски сохраняют тот же смысл, что и на рис 5 Все рисунки сделаны в одинаковом масштабе

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

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

Рис. 7: Изменение структуры сингулярных поверхностей в игре (8) при сближении отрезков Р и <2 в случае сильного первого игрока

Рис. 8: Изменение структуры сингулярных поверхностей в игре (8) при сближении отрезков Р и С? в случае слабого первого игрока

ностей, сравнивались с известными в литературе результатами аналитических исследований. Алгоритм для случая скалярных управлений был применен к задаче, исследованной в работе B.C. Пацко и С.И.Тарасовой18. Алгоритм для случая строго выпуклых ограничений

,яПацко B.C., Тарасова С.И. Свойства сингулярной поверхности в игре сближения второго порядка // Исследования задач минимаксного управления, Ред. А.И.Субботин, В.С.Пацко. - Свердловск: УНЦ АН СССР, 1985. - С. 48-65.

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

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

Основные результаты, выносимые на защиту

1) исследование численными методами феномена узких шеек множеств уровня функции цены в линеаризованной задаче воздушного перехвата, а также в линейных дифференциальных играх типа «обобщенный контрольный пример Л С Понтрягина»,

2) формулировка и доказательство теоремы о свойстве уровневого выметания функции цены,

3) разработка алгоритмов автоматического глобального построения сингулярных поверхностей для двух классов линейных дифференциальных игр

Автор работы глубоко благодарен научному руководителю к ф -м н Пацко Валерию Семеновичу за постоянное внимание к работе

Публикации по теме диссертации

[1] Ганебный С А , Кумков С С , Пацко В С Построение управления в задачах с неизвестным уровнем динамической помехи // Прикл математика и механика — 2006 — Т 70 — Вып 5 — С 753-770

[2] Kumkov S S , Patsko V S Parallel algorithm for construction of singular surfaces m linear differential games Analysis of singular surfaces // Proceedings of the Eighth International Colloquium on Differential Equations, August 18-23, Plovdiv, Bulgaria, 1997 — Bainov D (Ed ) — Utrecht, the Netherlands, 1998 - pp 275-284

[3] Кумков С С О разработке параллельной программы решения линейных дифференциальных игр // Алгоритмы и программные средства параллельных вычислений, Вып 3 — Екатеринбург УрО РАН, 1999 - С 145-164

[4] Kumkov S S , Patsko V S Level sets of value function and singular surfaces m linear differential games // A Proceedings Volume from the IFAC Workshop on Nonsmooth and Discontinuous Problems of Control and Optimization, Chelyabinsk, Russia, 17-20 June 1998 — Batukhtin V D , Kirillova F M , Ukhobotov V I (Eds ) — Pergamon Press, Great Britain, 1999 - pp 143-148

[5] Averbukh V L , Kumkov S S , Shilov E A , Yurtaev DA, and Zen-kov, A I Specialized Scientific Visualization Systems for Optimal Control Application // A Proceedings Volume from the IFAC Workshop on Nonsmooth and Discontinuous Problems of Control and Optimization, Chelyabinsk, Russia, 17-20 June 1998 — Batukhtm V D , Kirillova F M , and Ukhobotov, V I (Eds ) — Pergamon Press, Great Britain, 1999 - pp 28-33

[6] Kumkov S S , Patsko V S Backward procedures in linear differential games of small dimension // Modern Applied Mathematics Techniques

m Circuits, Systems and Control — Mastorakis N (Ed) — World Scientific and Engineering Society Press, 1999 — pp 138-143

[7] Averbukh V L , Kumkov S S , Patsko V S , Pykhteev О A , and Yurtaev D A Specialized visualization systems for differential games // Progress m Simulation, Modelling, Analysis and Synthesis of Modern Electrical and Electronic Devices and Systems — Mastorakis N (Ed ) — World Scientific and Engineering Society Press, 1999 — pp 301-306

[8] Жаринов A H , Кумков С С Построение пучка оптимальных движений в линейной дифференциальной игре // Проблемы теоретической и прикладной математики, Труды 31-й Региональной молодежной конференции — Екатеринбург УрО РАН, 2000 — С 87-88

[9] Кумков С С , Пацко В С Максимальные стабильные мосты в контрольном примере JT С Понтрягина // Вестник Удмуртского Университета (Математика, Механика), Ижевск — 2000 - № 1 -С 92-103

[10] Kumkov S S , Patsko V S , Shmar J Level Sets of the Value Function in Linear Differential Games with Elliptical Vectograms // Proceedings of the 11th IFAC Workshop «Control Applications of Optimization» (CAO 2000), (July 3-6, 2000, St Petersburg, Russia), Vol 2 — Zakharov V (Ed ) - Saint-Petersburg, 2000 - pp 579-584

[11] Averbukh V L , Kumkov S S , Pykhteev О A , and Yurtaev D A Visualization of Level Sets and Singular Surfaces m Differential Games // Proceedings of the 15th Conference on Scientific Computing «ALGO-RITMY 2000», Vysoke Tatry — Podbanske, Slovakia, September 10-15, 2000 — Handlovicova A , Komornikova M , Mikula К , and Sevcovic D (Eds ) — Slovak University of Technology, Bratislava Faculty of Civil Engineering Department of Mathematics and Descriptive Geometry, 2000 - pp 196-206

[12] Кумков С С О разработке параллельной программы решения линейных дифференциальных игр // Сборник трудов конференции

«Высокопроизводительные вычисления и их приложения», Черноголовка, 30 октября — 2 ноября 2000 г — М Изд-во МГУ, 2000 — С 268-271

[13] Kumkov S S , Patsko V S Construction of Singular Surfaces m Linear Differential Games // Annals of the International Society of Dynamic Games, Vol 6 — Altman E , Pourtallier О (Eds ) — Birkhauser, Boston, 2001 — pp 185-202

[14] Жаринов A H , Кумков С С Построение пучка оптимальных движений в линейной дифференциальной игре с эллиптическими век-тограммами // Проблемы теоретической и прикладной математики Труды 33-й Региональной молодежной конференции — Екатеринбург УрО РАН, 2002 - С 239-243

[15] Kumkov S S , Patsko V S , Shmar J On level sets with «narrow throats» in linear differential games // International Game Theory Review — 2005 — Vol 7 — No 3, September — pp 285-312

[16] Kumkov S S , Patsko V S Level Sweeping of the Value Function m Linear Differential Games // Annals of the International Society on Dynamic Games, Vol 8 — Haurie A , Raghavan T E S (Eds ) — Birkhauser, Boston, 2006 — pp 23-37

Кумков Сергей Сергеевич

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

Автореферат

Подписано в печать 19 04.2007 Формат 60x84 1/16 Объем 2 п л Тираж 150 экз

Введение

Список обозначений

1 «Узкие шейки» в линейных дифференциальных играх

1.1 Линейные дифференциальные игры.

1.2 Построение множеств уровня функции цены.

1.3 Задача воздушного перехвата.

1.3.1 Задача перехвата: случай быстрого преследователя

1.3.2 Задача перехвата: случай медленного преследователя

1.4 Обобщенный контрольный пример Л.С.Понтрягина.

1.4.1 Пример

1.4.2 Пример 2.

1.4.3 ПримерЗ.

2 Уровневое выметание функции цены

2.1 Альтернированные суммы.

2.2 Связь операций над множествами и опорными функциями

2.3 Локальная выпуклость

2.4 Разность выпуклых функций.

2.4.1 Контрпример к обобщению лемм 2.4.1 и 2.4.2.

2.5 Доказательство факта о сохранении уровневого выметания

2.5.1 Сохранение полного выметания при алгебраической сумме.

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

2.5.3 Контрпример к обобщению леммы 2.5.2.

2.5.4 Сохранение полного выметания при предельном переходе .G

3 Численное построение сингулярных поверхностей

3.1 Оптимальные движения.

3.2 Типы сингулярных поверхностей.

3.3 Игры со скалярными управлениями.

3.3.1 Построение сингулярностей в случае скалярных ограничений

3.3.2 Пример 1: материальная точка на прямой.

3.3.3 Пример 2: конфликтно-управляемый осциллятор

3.3.4 Пример 3: «кнопка».

3.3.5 Сравнение с аналитическими результатами.

3.3.6 Замечание к таблице классификации сингулярностей

3.3.7 Пример линии переключения за второго игрока с покиданием

3.3.8 Уточнение таблицы классификации сингулярностей

3.3.9 Структура сингулярных поверхностей.

3.4 Игры с нескалярными управлениями

3.4.1 Построение сингулярностей в случае нескалярных ограничений.

3.4.2 Пример 1: задача воздушного перехвата.

3.4.3 Пример 2: «обобщенный контрольный пример Л.С.Понтрягина».

Теория дифференциальных игр в настоящее время — развитая математическая дисциплина. Первые отчеты Р.Айзекса по дифференциальным играм относятся к 1951-1954 годам [58, 59, 60, 61]. В 1965 году была опубликована его книга «Дифференциальные игры», переведенная на русский язык в 1967 году [1]. В нашей стране динамические задачи конфликтного управления рассматриваются с начала 60-х годов прошлого века. Первыми были работы Л.С.Понтрягина [27, 28] и Н.Н.Красовского [12, 13].

В 1967 году вышли две знаменитые статьи [29, 30] Л.С.Понтрягина о линейных дифференциальных играх. В 1968 году опубликована книга [14] Н.Н.Красовского по оптимальному управлению, в заключительной части которой был большой раздел, связанный с дифференциальными играми. В 1974 году вышла книга Н.Н.Красовского и А.И.Субботина «Позиционные дифференциальные игры». В ней, в частности, предложена позиционная формализация дифференциальных игр и доказана теорема об альтернативе, родственная теореме существования функции цены.

В эти же годы были опубликованы основополагающие работы [33, 34] Б.Н.Пшеничного о структуре дифференциальных игр.

Среди работ зарубежных авторов конца 60-х - начала 70-х годов прошлого века отметим работы L.D.Berkovitz [46], A.Blaquiere [48], J.V.Breakwell [50, 64], W.H.Fleming [56, 57], G.Leitmann [63]. В этих работах рассматривались теоремы существования функции цены в подходящем классе стратегий и развивался метод Айзекса решения дифференциальных игр при помощи построения сингулярных поверхностей.

Более поздние результаты, относящиеся к 1980-м годам, связаны с истолкованием функции цены игры как обобщенного решения уравнения Гамильтона-Якоби-Беллмана-Айзекса. Теория, опирающаяся на понятие минимаксного решения, была создана А.И.Субботиным. Полученные результаты отражены в книгах [36, 37]. Близкое понятие вязкостного решения было введено в работах M.G.Crandall и P.L.Lions [55]. В этом направлении интенсивно работают в настоящее время M.Bardi и I.Capuzzo-Dolcetta [43].

Параллельно с развитием теории разрабатывались и численные методы. Опыт создания первых универсальных алгоритмов решения некоторых классов дифференциальных игр отражен в сборнике [2], опубликованном в 1984 г. в Екатеринбурге. Большую роль в создании алгоритмов и их обосновании сыграли работы Н.Л.Григоренко, М.С.Никольского, В.С.Пацко, Е.С.Половинкина, В.Н.Ушакова. Соответствующие результаты изложены в работах [39, 38, 7, 72, 31, 19].

За рубежом численные методы интенсивно разрабатываются с начала 1990-х годов. В этой области проводят исследования итальянские математики M.Bardi, M.Falcone, P.Soravia [44, 43, 45]; французские — P.Cardaliaguet, M.Quincampoix, P.Saint-Pierre [52, 53, 54]; немецкие — M.H.Breitner, H.J.Pesch [51].

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

Стимулом этой модернизации явилось желание получить результаты счета с хорошей точностью, что позволило использовать современные методы научной компьютерной визуализации для адекватного представления результатов. Программы для визуализации решений дифференциальных игр были созданы в 1997-2000 годах в процессе совместной работы с В.Л.Авербухом, А.И.Зенковым, Д.А.Юртаевым (сектор компьютерной визуализации отдела системного обеспечения ИММ УрО РАН). Другим стимулирующим фактором явилась попытка создания алгоритмов и программ автоматического построения сингулярных поверхностей в указанном классе игр. Такие программы были созданы автором, и они базируются на программе построения множеств уровня функции цены.

Перейдем к изложению содержания диссертации по главам.

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

Далее рассматривается задача воздушного перехвата одного слабома-неврирующего объекта другим (ракеты или самолета антиракетой). Задача рассматривается в линеаризованной постановке. При помощи разработанной программы детально исследуются особенности множеств уровня функции цены. Изучаемые особенности заключаются в том, что ^-сечения множеств уровня функции цены могут иметь пустую внутренность. Такое явление создает «узкую шейку» множества уровня. Адекватное воспроизведение формы множества уровня вблизи узкой шейки требует хорошей точности вычислений. Исследование узких шеек важно, поскольку значительная часть тонкостей решения дифференциальной игры (в частности, наличие сингулярных поверхностей) сосредоточена именно в районе узкой шейки. Некоторое теоретическое исследование дифференциальной игры, связанной с задачей перехвата, проводилось в работах J.Shinar и его сотрудников [70, 71, 67]. Результаты численных построений, приведенные в первой главе, сравниваются с результатами этих работ.

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

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

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

Рассмотрение сингулярных поверхностей составляет основу книги Р.Айзекса. Им предложена классификация сингулярных поверхностей: экивокальпые, рассеивающие, универсальные, поверхности переключения. Необходимые условия, связанные с различными типами сингулярных поверхностей, рассматривались в работах P.Bernhard [47] и А.А.Меликяна [66]. Автору неизвестны работы, в которых описывались бы численные алгоритмы автоматического глобального построения сингулярных поверхностей.

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

В настоящее время пока не удалось провести полное аккуратное обоснование разработанных алгоритмов. Однако правильность их работы тщательным образом проверялась на примерах, в которых сингулярные поверхности были исследованы аналитическими методами [22, 23, 70, 71].

На защиту выносятся следующие результаты:

1) исследование численными методами феномена узких шеек множеств уровня функции цены в линеаризованной задаче воздушного перехвата, а также в линейных дифференциальных играх типа «обобщенный контрольный пример Л.С.Понтрягина»;

2) формулировка и доказательство теоремы о свойстве уровневого выметания функции цены;

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

Список обозначений

N — множество натуральных чисел

R+ (R~) — множество положительных (отрицательных) вещественных чисел

Моо — множество вещественных чисел, расширенное ±оо

Rn — евклидово пространство размерности п z — фазовая переменная размерности п в исходной дифференциальной игре Т — момент окончания в рассматриваемых дифференциальных играх

V(t, z) — функция цены исходной дифференциальной игры

Wc — множество уровня функции цены исходной дифференциальной игры, соответствующее константе с X(T,t) — фундаментальная матрица Коши исходной дифференциальной игры, вычисленная в момент t для момента окончания Т Xij(T,t) — матрица, составленная из г'-й и j-Pi строк фундаментальной матрицы Коши X(T,t), соответствующих компонентам фазового вектора, определяющим функцию платы эквивалентная фазовая переменная размерности 2

0 функция цены эквивалентной дифференциальной игры

Wc — множество уровня функции цены эквивалентной дифференциальной игры, соответствующее константе с р(1,А), рл(1) — значение опорной функции выпуклого компактного множества А на векторе I (а, Ь) — скалярное произведение векторов а и b транспонирование матрицы А или вектора а т — обратное время в рассматриваемых дифференциальных играх \А — сужение функции / на множество А

А — В — геометрическая разность множеств (разность Минковского) conv / — операция взятия выпуклой оболочки функции / conv|^/ — операция взятия выпуклой оболочки функции / на выпуклом множестве А gr / — график функции / epi / — надграфик функции / epi \Af — надграфик функции / на множестве А

0£(хо) — открытая г-окрестность точки хо

Dom / — область определения функции / int А — внутренность множества А дА — граница множества А diam А, \А\ — диаметр множества А: \А\ = sup Ця — у\\ х,уеА diam^, — диаметр разбиения & = {to <t\ < . < tдг}: тах{£г+1 - U} г

Af(t, x) — конус внешних нормалей в точке (t, х) к временному сечению W(t) соответствующего максимального стабильного моста W (множества уровня функции цены) Р — многогранная аппроксимация множества Р ограничений на управление первого игрока Q — многогранная аппроксимация множества Q ограничений на управление второго игрока Wc — аппроксимация максимального стабильного моста Wc

V(t) — вектограмма первого игрока в момент t (точная или приближенная)

Q(t) — вектограмма второго игрока в момент t (точная или приближенная) n-p(t) — в случае скалярного управления первого игрока нормаль к отрезку его вектограммы в момент t TiQ(t) — в случае скалярного управления второго игрока нормаль к отрезку его вектограммы в момент t

1. Айзеке Р. Дифференциальные игры. — М: Мир, 1967. — 480 с.

2. Алгоритмы и программы решения линейных дифференциальных игр / Ред. А.И. Субботин, B.C. Пацко. — Свердловск, 1984. — 295 с.

3. Боткин Н.Д. Погрешность аппроксимации в линейной дифференциальной игре // Автоматика и телемеханика, № 12, 1984. — С. 5-12.

4. Брайсон А., Хо Ю-Ши Прикладная теория оптимального управления. — М: Мир, 1972. — 544 стр.

5. Вязгин В.А. Об одной дифференциальной игре сближения // Прикл. математика и механика, Т.47, Вып.6, 1983. — С. 904-908.

6. Григоренко H.JI. Математические методы управления несколькими динамическими процессами. — М: Изд-во Моск. ун-та, 1990. — 197 с.

7. Григоренко H.JL, Киселев Ю.Н., Лагунова Н.В., Силин Д.Б., Тринь-ко Н.Г. Методы решения дифференциальных игр // Математическое моделирование, 1993. — С. 296—316.

8. Гусятников П.Б., Никольский М.С. Об оптимальности времени преследования // Докл. АН СССР, Т. 168, № 3, 1969. С. 518-521.

9. Исакова Е.А., Логунова Г.В., Пацко B.C. Построение стабильных мостов в линейной дифференциальной игре с фиксированным моментом окончания // В сборнике 2]. — С. 127-158.

10. Зарх М.А., Пацко B.C. Построение управления второго игрока в линейной дифференциальной игре н основе отталкивания // Управление с гарантированным результатом: Сб. науч. трудов, Свердловск: УНЦ АН СССР, 1987. С. 37-70.

11. Камнева JI.B. Достаточные условия стабильности для функции цены дифференциальной игры в терминах сингулярных точек // Прикл. математика и механика, Т. 67, вып. 3, 2003. — С. 366-383.

12. Красовский Н.Н. Об одной задаче преследования // Прикл. математика и механика, Т. 26, вып. 2, 1962. С. 218-232.

13. Красовский Н.Н. Об одной задаче преследования // Прикл. математика и механика, Т. 27, вып. 3, 1963. С. 244-254.

14. Красовский Н.Н. Теория управления движением. — М.: Наука, 1968. — 476 с.

15. Красовский Н.Н. Игровые задачи о встрече движений. — М: Наука, 1970. 420 с.

16. Красовский Н.Н., Субботин А.И. Позиционные дифференциальные игры. — М.: Наука, 1974. — 455 стр.

17. Мезенцев А.В. О некотором классе дифференциальных игр // Изв. АН СССР, Техн. киб., № 6, 1971. С. 3-7.

18. Никольский М.С. Первый прямой метод Л.С.Понтрягина в дифференциальных играх. — М: Изд-во Моск. ун-та, 1984. — 64 с.

19. Никольский М.С. О приближенном вычислении геометрическойразно-сти множеств // Вестник Московского университета, Сер. 15, вычислительная математика и кибернетика, №1, 2003. — С. 49-54.

20. Пацко B.C., Тарасова С.И. Дифференциальная игра сближения с фиксированным моментом окончания, Деп. в ВИНИТИ, 1983, Свердловск, № 5320-83, 112 с.

21. Пацко B.C., Тарасова С.И. Нерегулярная дифференциальиая игра сближения // Изв. АН СССР, Техн. кибернетика, № 4,1984. С. 134142.

22. Пацко B.C., Тарасова С.И. Дифференциальная игра сближения второго порядка / Исследования задач минимаксного управления, Ред. А.И.Субботин, В.С.Пацко. Свердловск: УНЦ АН СССР, 1985. -С. 29-47.

23. Пацко B.C., Тарасова С.И. Свойства сингулярной поверхности в игре сближения второго порядка / Исследования задач минимаксного управления, Ред. А.И.Субботин, В.С.Пацко. — Свердловск: УНЦ АН СССР, 1985. С. 48-65.

24. Петров Н.Н. К нестационарному примеру Л.С.Понтрягина с фазовыми ограничениями // Изв. ин-та матем. и механ., Удмурт. Гос. унив., Ижевск, Вып.2, 1998. С. 53-58.

25. Петросян Л.А. Дифференциальные игры преследования. — Л: Изд-во Ленингр. ун-та, 1977. — 224 с.

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

27. Понтрягин Л.С. О некоторых дифференциальных играх // Докл. АН СССР, Т. 156, №4,1964. С. 738-741.

28. Понтрягин Л.С. К теории дифференциальных игр // Успехи мат. наук, Т.21, №4, 1966. С. 193-246.

29. Понтрягин Л.С. Линейные дифференциальные игры, 1 // Докл. АН СССР, Т. 174, №6, 1967. С. 1278-1280.

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

31. Половинкин Е.С., Иванов Г.Е., Балашов М.В., Константинов Р.В., Хо-рев А.В. Алгоритмы численного решения линейных дифференциальных игр // Математический сборник, Т.192, №10, 2001. С. 95-122.

32. Препарата Ф., Шеймос М. Вычислительная геометрия: введение. — М: Мир, 1989. 480 стр.

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

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

35. Рокафеллар Р.Т., Выпуклый анализ. — М.:Мир, 1973. — 469 с.

36. Субботин А.И. Минимаксные неравенства и уравнения Гамильтона-Якоби. М.: Наука, 1991. - 216 с.

37. Субботин А.И. Обобщенные решения уравнений в частных производных первого порядка: перспективы динамической оптимизации. — М.;Ижевск: Ин-т компьютер, исслед., 2003. — 336 с.

38. Тарасьев A.M., Ушаков В.Н., Хрипунов А.П. О построении множеств позиционного поглощения в игровых задачах управления // Труды Института математики и механики, Том 1. — Екатеринбург: УрО РАН, 1992. С. 160-177.

39. Ушаков В.Н. К задаче построения стабильных мостов в дифференциальной игре сближения-уклонения // Известия АН СССР. Техническая кибернетика, №4, 1980. — С. 29—36.

40. Хадвигер Г. Лекции об объеме, площади поверхности и изоперемет-рии. М: Наука, 1966. - 416 с.

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

42. Чикрий А.А. Конфликтно управляемые процессы. — Киев:Наукова Думка, 1992. 384 с.

43. Bardi М., Capuzzo-Dolcetta I. Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equation. — Burkhauser, Boston, 1997. — 570 p.

44. Bardi M., Falcone M. An Approximation Scheme for the Minimum Time Function // SIAM J. Contr. and Optim., Vol.28, №4,1990. pp. 950-965.

45. Bardi M., Falcone M., Soravia P. Numerical Methods for Pursuit-Evasion Games via Viscosity Solutions // Stochastic and Differential Games: Theory and Numerical Methods: Annals Intern. Soc. Dynamic Games, Vol.4. — Birkhauser, Boston, 1999. pp. 105-175.

46. Berkovitz L.D. A variational approach to differential games // Advances in game theory, Vol.3, 1964, Princeton Univ. Press, Princeton, N.J. — pp. 127-174.

47. Bernhard P. Singular Surfaces in Differential Games: an Introduction // Differential Games and Applications. — Springer-Verlag, Berlin, 1977. — pp. 1-33.

48. Blaquiere A., Gerard F., Leitmann G. Quantitive and Qualitative Games. — Acad. Press., New York, London, 1969. — 172 p.

49. Botkin N.D. Evaluation of numerical construction error in differential game with fixed terminal time // Problems of Control and Information Theory, Vol. 11, №4, 1982. pp. 283-295.

50. Breakwell J.V., Merz A.W. Towards a Complete Solution of the Homicidal Chauffeur Game // Proc. 1st Intern. Conf. Theory and Appl. of Differential Games, Amherst, Mass., 1969. pp. III-1-III-5.

51. Breitner M.H., Lachner R., Pesch H.J. Three-Dimensional Air Combat Analysis An Example for the Numerical Solution of Complex Differential Games // Annals of the International Society of Dynamic Games., Vol.3. — Birkhauser, Boston, 1996. — pp. 53-77.

52. Cardaliaguet P., Quincampoix M., Saint-Pierre P. Some Algorithms for Differential Games with Two Players and One Target // RAIRO-Modelisation-Matematique-et-Analyse-Numerique, Vol. 28, No. 4, 1994. — pp. 441-461.

53. Cardaliaguet P., Quincampoix M., Saint-Pierre P. Numerical Methods for Optimal Control and Differential Games. — Ceremade CNRS URA 749, Univ. of Paris Dauphine. — 1995.

54. Crandall M.G., Lions P.L. Viscosity solutions of Hamilton-Jacobi equations // Trans. Amer. Math. Soc., Vol.277, №1, 1983. pp. 1-42.

55. Fleming W.H. The convergence problem for differential games // J. Math. Anal, and Appl., №3, 1961. pp. 102-116.

56. Fleming W.H. The convergence problem for differential games, 2 // Adv. in Game Theory, Ann. Math. Studies, №52, 1964. pp. 195-210.

57. Isaacs R.P. Games of Pursuit, Paper P-257. — RAND Corporation, Santa Monica, California. — 1951.

58. Isaacs R.P. Differential Games, I: Introduction. Research Memorandum RM-1391. RAND Corporation, Santa Monica, California. — 1954.

59. Isaacs R.P. Differential Games, II: The Definition and Formulation. Research Memorandum RM-1399. — RAND Corporation, Santa Monica, California. — 1954.

60. Isaacs R.P. Differential Games, III: The Basic Principles of the Solution Process. Research Memorandum RM-1411. — RAND Corporation, Santa Monica, California. — 1954.

61. Kurzhanski A.B., Valyi I. Ellipsoidal Calculus for Estimation and Control. — Birkhauser, Boston, 1997. — 321 p.

62. Leitmann G. A differential game of pursuit and evasion // Internat. J. Non-Linear Mech., Vol.4, №4, 1969. pp. 72-89.

63. Lewin J., Breakwell J.V. The surveillance-evasion game of degree // J. Optimiz. Theory and Appl., Vol.16, №3-4, 1975. pp. 339-353.

64. Lewin J., Olsder G.J. Conic Surveillance Evasion // J. Optimiz. Theory and Appl., Vol. 27, №1, 1979. pp. 107-125.

65. Melikyan A.A. Generalized Characteristics of the First Order PDEs: Applications in Optimal Control and Differential Games. — Burkhauser, Boston, 1998. 310 p.

66. Melikyan A.A., Shinar J. Identification and Construction of Singular Surface in Pursuit-Evasion Games / Annals of the International Society of Dynamic Games, Vol.5, Eds. J.A. Filar and V. Gaitsgory, 2000. — pp. 151-176.

67. Merz A.W., The homicidal chauffeur — a differential game, PhD Thesis, Stanford University, 1971.

68. Shinar J., Davidovitz A. A Two-Target Game Analysis in Line-of-Sight Coordinates // Comput. Math. Applic., Vol. 13, No. 1-3, 1987. pp. 123140.

69. Shinar J., Medinah M., Biton M. Singular Surfaces in a Linear Pursuit-Evasion Game with Elliptical Vectograms // Journal of Optimization Theory and Optimization, Vol.43, No.3, 1984. pp. 431-458.

70. Shinar J., Zarkh M. Pursuit of a Faster Evader — a Linear Game with Elliptical Vectograms // Proceedings of the Seventh International Symposium on Dynamic Games, Yokosuka, Japan, 1996. — pp. 855—868.

71. Ганебный С.А., Кумков С.С., Пацко B.C. Построение управления в задачах с неизвестным уровнем динамической помехи // ПММ, Т. 70, Вып. 5, 2006. С. 753-770.

72. Кумков С.С. О разработке параллельной программы решения линейных дифференциальных игр // Алгоритмы и программные средства параллельных вычислений, Вып. 3. — Екатеринбург: УрО РАН, 1999. С. 145-164.

73. Кумков С.С. О разработке параллельной программы решения линейных дифференциальных игр // Сборник трудов конференции «Высокопроизводительные вычисления и их приложения», Черноголовка, 30 октября 2 ноября 2000 г., М: Изд-во МГУ. - С. 268-271.

74. Кумков С.С., Пацко B.C. Максимальные стабильные мосты в контрольном примере Л.С.Понтрягина // Вестник Удмуртского Университета (Математика, Механика), Ижевск, №1, 2000. — С. 92-103.

75. Kumkov S.S., Patsko V.S. Construction of Singular Surfaces in Linear Differential Games // Annals of the International Society of Dynamic Games, Vol.6. Altman E., Pourtallier O. (Eds.), Birkhauser, Boston, 2001. -pp. 185-202.

76. Kumkov S.S., Patsko V.S. Level Sweeping of the Value Function in Linear Differential Games // Annals of the International Society on Dynamic Games, Vol.8. — Haurie A., Raghavan T.E.S. (Eds.), Birkhauser, Boston, 2006. pp. 23-37.

77. Kumkov S.S., Patsko V.S., Shinar J. On level sets with "narrow" throats in linear differential games // International Game Theory Review, Vol. 7, No. 3, September 2005. pp. 285-312.Список иллюстраций

78. Система координат в задаче трехмерного преследования . . 18

79. Геометрия номинального перехвата для случая быстрого преследователя.22

80. Эллиптические ограничения на управления игроков в случае быстрого преследователя.23

81. Трубки вектограмм для случая быстрого преследователя . . 23

82. Увеличенный фрагмент трубок вектограмм.23

83. Сечения трубок вектограмм в некоторые моменты времени . 24

84. Множество уровня, близкое сверху к кртическому.25

85. Увеличенный фрагмент множества уровня, близкого к критическому .25

86. Наложение трубок вектограмм.26

87. Наложение трубок вектограмм и множества уровня, близкого к критическому.26

88. Эллиптические ограничения на управления игроков в случае медленного преследователя.28

89. Общий вид множества уровня функции цены с узкой шейкой 29

90. Увеличенный фрагмент узкой шейки .29

91. Общий вид трубок вектограмм игроков.31

92. Сечения трубок вектограмм для некоторых моментов времени 31

93. Группы i-сечений множества уровня, близкого к критическому для некоторых промежутков обратного времени.32

94. Сокращение размера £-сечения по вертикали вследствие сжатия ио горизонтали.33

95. Множество уровня с узкой шейкой и множество уровня, просчитанное для меньшего значения с. 34

96. Множество уровня с узкой шейкой и множество уровня, просчитанное для большего значения с. 34

97. Пример 1. Эллиптические вектограммы игроков. 38

98. Пример 1. Конечный во времени максимальный стабильный мост. 38

99. Пример 1. Максимальный стабильный мост с узкой шейкой 39

100. Пример 1. Увеличенный фрагмент шейки. 39

101. Пример 1. Максимальный стабильный мост для значения параметра с, большего критического. 39

102. Пример 2. Вектограммы игроков. 411.2G Пример 2. Вектограммы игроков. Трубка вектограмм второго игрока сделана прозрачной. 41

103. Пример 2. Общий вид максимального стабильного моста с двумя узкими шейками. 42

104. Пример 2. Вид первой узкой шейки максимального стабильного моста. 42

105. Пример 3. Общий вид трубок вектограмм. 43

106. Пример 3. а) Общий вид максимального стабильного моста с тремя узкими шейками; б) Крупный план наиболее узкойиз трех имеющихся шеек . 44

107. Пример 3. Общий вид максимального стабильного моста с наложенными на него трубками вектограмм игроков . 45

108. Примеры вычисления геометрической разности . 46

109. Сумма геометрической разности и множества-вычитаемогодля примеров на рис. 2.1 . 47

110. Иллюстрация к определению опорной функции: а) опорная гиперплоскость; б) опорное полупространство . 50

111. Конус линейности опорной функции. 50

112. Иллюстрация к доказательству леммы 2.3.2 . 52

113. Иллюстрация к лемме 2.3.3. 54

114. Область исправления функции д в лемме 2.4.2. 59

115. К доказательству выпуклости функции hi в лемме 2.4.2 . 60

116. Графики функций / (а), — д (б) и — convg (в). 61

117. Сечения графиков conv/ = / (а), — convg (б) и conv / — convg (в) . 62

118. Контрпример к сохранению полной выметаемости после геометрической разности в случае множеств размерности триили выше. 64

119. Типы сингулярностей: а) переключение с покиданием; б) переключение без покидания; в) рассеивающая поверхность; г) универсальная/фокальная поверхность; д) экивокальная поверхность. 73

120. Схема фрагмента границы максимального стабильного моста с пучком оптимальных движений . 74

121. Схема оптимальных движений в прямом времени аппроксимирующей игры (1.4) вблизи линии переключения с покиданием за первого игрока. 77

122. Схема оптимальных движений в прямом времени аппроксимирующей игры (1.4) вблизи линии переключения без покидания за первого игрока. 78

123. Общий вид максимального стабильного моста и сингулярных линий на нем в игре (3.1): а) с функцией платы (pi, б) сфункцией платы .83

124. Поведение пучков оптимальных движений вблизи линий переключения первого игрока.85

125. Три максимальных стабильных моста для игры (3.2) . 86

126. Общий вид максимального стабильного моста и сингулярных линий на нем в игре (3.2).87

127. Поведение пучка оптимальных движений вблизи экивокальной линии. 88

128. Два вида системы сингулярных поверхностей для игры (3.2):1 — поверхность переключения за первого игрока; 2 — рассеивающая поверхность за второго игрока; 3 — экивокальная поверхность; 4 — рассеивающая поверхность за обоих игроков 89

129. Общий вид типичного моста для игры (3.3). 91

130. Изменение структуры сингулярных поверхностей в игре (3.3) при сближении отрезков Р и Q в случае сильного первого игрока. 92

131. Изменение структуры сингулярных поверхностей в игре (3.3)при сближении отрезков Р и Q в случае слабого первого игрока 92

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

133. Ситуация первого игрока, сильного к моменту исчезания горизонтальных площадок: схема конструирования нового сечения при дискретных построения с увеличением вертикального размера. 95

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

135. Численно просчитанная система сингулярных линий для игры (3.4). 97

136. Проекция экивокальных линий на плоскость xi, х2 . 97321 Фрагмент рис. 3.20. 98

137. Фрагмент границы моста для игры (3.2) около скачка рассеивающей линии. 99

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

139. Терминальное множество для игры (3.5) .101

140. Оптимальное движение, выходящее в обратном времени из точки А, и точка приложения вектограммы второго игрока . 101

141. Схема структуры сингулярных поверхностей в случае, когда функция платы удовлетворяет условию уровневого выметания 103

142. Ситуации «микрорасщепления» (а) и «микрослияния» (б) в аппроксимирующей игре с нескалярными управлениями . . 105

143. Основная идея алгоритма выявления и классификации сингулярностей — обнаружение «негладких» точек на границах сечений максимальных стабильных мостов и анализ динамики развития конуса внешних нормалей вдоль линий негладкости .106

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

145. Сингулярные линии и пучки оптимальных движений в районе узкой шейки.109

146. Максимальный стабильный мост, близкий к критическому, для игры типа «обобщенный контрольный пример Л.С.Понтрягина». На границе моста нанесены сингулярные лииии и оптимальные движения.111

147. Строение сингулярных линий и пучков оптимальных движений в районе узкой «шейки» .111

148. Увеличенный фрагмент рис. 3.31, вид сверху на утоныне-ние моста, следующее в прямом времени после узкой шейки. Прохождение оптимального движения «мимо» сингулярных линий.111

149. Поведение пучка оптимальных движений, попавшего на эки-вокальную линию.112

150. Увеличенный фрагмент рис. 3.34.112