Разрывная функция цены в игровых задачах быстродействия тема автореферата и диссертации по математике, 01.01.02 ВАК РФ

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

□03С326ТВ

КАМНЕВА Людмила Валерьевна

РАЗРЫВНАЯ ФУНКЦИЯ ЦЕНЫ В ИГРОВЫХ ЗАДАЧАХ БЫСТРОДЕЙСТВИЯ

01 01 02 — дифференциальные уравнения

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

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

003062676

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

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

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

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

Ухоботов Виктор Иванович, член-корреспондент РАН Ченцов Александр Георгиевич

Ведущая организация Институт проблем механики РАН,

г Москва

Защита состоится 16 мая 2007 года в 11 часов на заседании специализированного совета Д 004 006 01 по защите диссертаций на соискание ученой степени доктора физико-математических наук при Институте математики и механики Уральского отделения РАН по адресу 620219, г Екатеринбург, ул С Ковалевской, 16

С диссертацией можно ознакомиться в библиотеке Института математики и механики УрО РАН

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

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

Н Ю Лукоянов

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

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

В icopiiii дифференциальных игр изучаются задачи управления по принципу обратной связи в условиях неопределенноеiи и помех Исследования дифференциальных шр начались в 1950—60-е юды с рассмотрения ман'машческих моделей конфликтных ситуаций В этих моделях динамика управляемой системы описывается обыкновенными дифференциальными уравнениями, в правую часть которых входят управляющие воздействия Полезное управление рассматривав!ся как действие первого hi рока, минимизирующею некоторый функционал на множестве траектории системы, а помеха счшается резулыагом управления второю шрока, цель которою с ос i от в максимизации того л<е функционала Управления игроков сменены 1еометрическими ограничениями

Основополагающие резулыаты в теории дифференциальных Hip были получены в работах H H Красовского, /Т С Поптрягина, Б II Пшеничного, А И Субботина, R Р Isaacs, W H Fleming, M G Ciandall, PL Lions

Сущее iвенное влияние на кюрию дифференциальных игр оказали рабой.! А Б Куржапского, ЕФ Мищенко, ЮС Осипова Ф Л Черноусы«), J Г Aubin, M Batch Т Basai, L Beikovitz, P Bernhaul, A Blaqmeie ,1 V Bieakwell, A Fnednian, С Leitmann

Большой вклад в теорию дифференциальных игр и ее приложения внесли Э Г Альбрехт, В Д Батухтин, С А Брыкалов, H JI Григоренко, П Б Гусятников, МИ Зеликин, АФ Клейменов, А В Кряжимский А А Меликяп, M С Никольский, В В Оетпенко, НИ Нефов Л А Пегросян ЕС Помошшкин, Б H Соколов II H Субботина, В Е Третьяков, В И Ухоботов, В H Ушаков, А Г' Чепцов, А А Чикрий, I Capu//o-DolccUa, РМ Caidaliaguet, R J Elliot, M Falcone, N.J Kalton,

G Leitmann, J Levvm, A W Merz, S Mírica, G J Olsder, M Qumcampoix, E Roxm, P Saint-Pierre, J Shmar, P Soravia, P Varaiya и многие другие ученые

В монографии Р Айзекеа1 был предложен метод исследования игровых задач управления и рассмотрено большое число содержательных примеров Однако строгой математической постановки дифференциальной игры при этом не было Среди различных вариантов формализации дифференциальных игр отметим подход W II Fleming2, основанный на аппроксимации дифференциальной игры многошаговыми играми, а также подход, использующий понятие неупреждающих стратегий и развитый в работах R J Elliott и N J Kaiton3

Удобной с практической точки зрения является позиционная формализация дифференциальных игр, изложенная в книге Н Н Красовского и А И Субботина4 В рамках позиционной формализации подход к решению дифференциальной игры заключается в поиске функции цены, которая каждой точке пространства состояний системы ставит в соответствие оптимальный гарантированный результат в игре, начинающейся из этой точки На базе функции цены можно построить стратегии оптимального управления по принципу обратной связи0 Отметим, что цена позиционной дифференциальной игры для заданной начальной точки совпадает с ценой в смысле W Н Fleming или с ценой в классе неупреждающих стратегий в случаях, когда обе величины существуют

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

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

-Fleming (VН The convergence problem for differential games // J Math Anal and Appl - Vol 3 -1S61 - P 102-116

1ElUott К J, Kalten N J The existence of value m differential games of pursuit and evasion // J Different

Equat - Vol 12, №3 -1972 -P 504-523

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

^Красовский И Н Дифференциальные игры Аштроксимационные и формальные модели Л Мат сб

- 1978 - Т 107, Л» 4 - С 541-571

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

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

В связи с большими техническими сложностями исследования конкретных задач в настоящее время известно не очень много работ, в которых проведены аналитические построения функции цены дифференциальных игр быстродействия Среди таких исследований отметим работы J V Breakwell, J Lewin, A W Merz, G J Olsder 6,7's, а также А А Меликяна, В С Пацко, С А Чигиря, J Shinar Трудность аналитического решения игровых задач быстродействия требует численных алгоритмов решения, которые разрабатывались В С Пацко, A M Тарасьевым, В JI Туровой, А А Успенским, В H Ушаковым, А П Хрипуновым, M Bardi, РМ Cardahaguet, M Falcone, M Quincampoix, P Saint-Pierre, P Soravia и другими авторами

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

6Lewm J, Breakwell J V The Surveillance-Evasion Game of Degree //J Optimiz Theory and Appl -1975 - V 16, №3-1 - P 339-353

7Lewm J , Olsder G J Conic Surveillance Evasion // J Optimiz Theory and Appl - 1979 - V 27, № 1 - P 107-125

sMerz A W The Homicidal Chauffeur - a Differential Game - PhD thesis - Stanford Univ, 1971

Если функция Беллмана является негладкой, но непрерывной, то для решения задачи в классе управлений по принципу обратной связи может быть использован регулярный синтез В Г Болтянского9 Задачи оптимального быстродействия с разрывной функцией Беллмана исследовались, например, в работах G Leitmann, Н Frankowska, Р Cannarsa, S Koike и многих других

Теория оптимального управления и дифференциальных игр тесно связана с понятиями обобщенных решений уравнений в частных производных первого порядка Исследованиям таких решений уделяется в последние годы много внимания Разрывным обобщенным решениям для различных типов уравнений посвящены работы А И Субботина, М Baidi, G Barles, Е N Barron, Н Frankowska, Н Ishu, R Jensen, P Soravia и других авторов

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

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

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

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

9Болтянский В Г Математические методы оптимального управления М Наука, 1969

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

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

Структура и объем работы. Диссертация состоит из введения, списка основных обозначений, четырех глав и списка литературы Общий объем диссертации составляет 120 страниц, набранных в текстовом редакторе LATEX, библиографический список включает 69 наименований

Апробация работы. Основные результаты диссертации обсуждались и докладывались на конференциях молодых ученых Института математики и механики УрО РАН (Екатеринбург, 2000, 2005, 2006), 33-ей, 35-ой, 37-ой, 38-ой региональных молодежных конференциях "Проблемы теоретической и прикладной математики" (Екатеринбург, 2002, 2004, 2006, 2007), International Conferences "Viscosity Solutions and Applications", July 3-5, 2000, и "Analysis and Control of Deterministic and Stochastic Evolution Equations", July 6-7, 2000, Bressanone-Bnxen, Italy, lOth International Symposium on Dynamic Games and Applications, July 8-11, Samt-Petersburg, Russia, 2002, конференции "Демидовские чтения на Урале", Екатеринбург, 1-3 марта 2006 г, 13th IFAC Workshop "Control Applications of Optimization", 26-28 April, 2006, Paris - Cachan, France, научном семинаре "Математическая теория оптимального управления и теория дифференциальных включений", Москва, 12-13 октября 2006 г, семинарах отдела динамических систем и отдела управляемых систем ИММ УрО РАН, семинарах лаборатории

управляемых систем Института проблем механики РАН, семинарах кафедры оптимального управления факультета ВМиК МГУ и кафедры общих проблем управления механико-математического факультета МГУ, семинаре кафедры прикладной математики Челябинского госуниверситета

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

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

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

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

Рассматривается управляемая система, движение которой описывается уравнением

x{t) = f(x{t),u(t),v(t)), t> О

Здесь x{t) G Rn - фазовое состояние в момент времени t, u(t) G Р и v{t) G Q - управления первого и второго игроков, Р и Q - компактные множества в конечномерных пространствах Предполагается, что функция / непрерывна по совокупности переменных, удовлетворяет неравенству

[|/(а:,и,г>)|| < х{\ + ||х|[), к = const > О, и для нее выполнено локальное условие Липшица по х Пусть

Н(х.р) = mm max (р, fix, u, v)) = max mm(p,/(i,n,t))}, х,р G Rn

u€P veQ veQ uçP

Цель первого игрока - быстрейшее сближение фазовой точки x(t) с заданным замкнутым множеством M С Rn из начальной точки хо Второй игрок стремится либо исключить встречу с М, либо максимизировать время до встречи

В работе используется позиционная формализация игры быстродействия При указанных условиях на функцию / для любого а:о S Rn существует цена игры Т°(хо) ~ наилучший гарантированный результат за обоих игроков Функция Т°( ) Rn —> [0, оо] называется функцией цены игры

Предположим, что на замкнутом множестве Q С Rn определена некоторая функция

<р( ) П-[0,оо]

Задача состоит в нахождении таких условий на функцию ip( ), при которых выполнено равенство ip(x) = Т°(х), i £ П Искомые условия должны быть удобными для практической проверки

Введем понятия и- и v-стабильных10 функций на открытом множестве G CR"

Определение 1. Функция ш(-) G —* [0, оо] и-стабилъна на открытом множестве G С Rn, если она полунепрерывна снизу и для любых уо £ G, V* G Q существуют т > 0 и такое решение у{ ) [0, т] —> G дифференциального включения

y(t) £ со {f(y(t), и, V»), и е Р}, у(0) = 2/0,

■что выполнено неравенство u(y(t)) < ш(уо) — t, t 6 [0, г]

Определение 2. Функция ш{) G —* [0, оо] v-стабилъна на открытом множестве G С Rn, если она полунепрерывна сверху и для любых уо € G, и, 6 Р существуют т > 0 и такое решение у{ ) [0, т] —> G дифференциального включения

y(t) S со{f{y{t),ut,v),v е Q}, 2/(0) = уо, что выполнено неравенство w(y(t)) > и>(уо) —t,t 6 [0, г]

Дадим формулировку первой теоремы о достаточных условиях Будем использовать обозначения А - замыкание множества А С Rn, mt А - внутренность множества А, В(0, г) - шар в R" радиуса г > 0 с центром в начале координат

10Kia.iovilM N N , Subbotin A I Game-Theoretical Control Problems -NY Spnnger-Verlag 1988

Теорема 1. Пусть П С Rn, М С П - замкнутые множества, задана функция (р() О —» [0, оо] и введены обозначения

0 = sup^z), D{t) = {x €fi у(х) < t}, ¿е[о,е),

F{t) = {х е dD{t) <p(x) = t}, B(t) = {x e 8D(t) <p{x)<t},

0, S(t) = 0,

S(t) = F{t) П B(i), G(t, e) = < £ > 0

S{t) + mtB(0,e), S(t)¿0,

Предположим, что функция ip( ) полунепрерывна снизу, D(0) = M, Т С (0, ö) - некоторое конечное (либо пустое) множество и выполнены следующие условия

1) Для любого t G (0,©) \ Т существуют число £о > 0 и множество Gao С G(t,eо) \ D(t), такие, что

а) выполнены соотношения G(t,eо) С G00 U Г2,

lim^sup-fí/^a;) х € G(t, е) \ G^} = t

и функция

' ф) -t, хе G(t, £о) \ (Goo U D(t)),

oj(x) = {o, x 6 D[t) nG(í,e0),

ОО, X G Goo

и-стабюгъна на множестве G(t,sо) \D(t),

б) существуют функции

ojk() G(t,e0) -> [О.оо], fceN,

которые v-стабильны на множестве G(t, £(¡) \ D(t), равны нулю и непрерывны в точках множества D(t) П G(í,eо), и

lim u>k(x) — u)(x) X € G(t,eо)

оо

Для любых t S (0, в)\Т и £ > 0 найдется такое S > 0, что функция ip( ) определена, непрерывна и обладает свойствами и- и v-стабильности

на множестве

[ F£(t) + mtB(0,6), FE(t) ф 0,

где

F£{t) = F(t)\G(t,e) 3) Для любых t G (0,0) \ Т и е > О найдутся число 5 > О и функции

GB(t,e,ô) —> [0, оо], k EN,

где

f 0, BAt) = 0,

[ Be(i) + intB(0,J), Be(t) ф 0,

такие, что функции ), /с G N, v-стабилъпы на множестве GB(t,e, \ /?(£), равны нулю и непрерывны в точках множества D(t) П GB(t,e,5), и выполнено предельное соотношение

lim ufix) = оо, a: G GB(i, е, <5) \ D{t)

А—»оо

^J Для любого Х() G il \ M, такого, что <р(хо) = 0 < со, найдется последовательность {za.}î° С Q, для которой ip(xfc) < <р(хо) и хь —+ Хо при к —>• оо

ТЪгЛг = T°(s), z G О

Поясним основную идею теоремы 1 Рассмотрим краевую задачу для уравнения в частных производных первого порядка (уравнения Айзекса -Беллмана)

H{x,VT(x)) =-I, xeRn\M, (1)

Т(х) = 0, х G дМ (2)

В книге Р Айзекса показано, что классическое (т е гладкое) решение задачи (1), (2) (если оно существует) совпадает с функцией цены Т°( ) дифференциальной игры быстродействия С другой стороны, для краевой задачи

Дирихле (1), (2) на множестве Я,™ \М функция цены Т°() содержательно определяет единственное обобщенное решение, т е конструкции теории позиционных дифференциальных игр можно использовать для определения обобщенных решений краевых задач для УЧП первого порядка Такой подход лежит в основе теории минимаксных решений А И Субботина11, где дается определение обобщенного (разрывного) минимаксного решения краевой задачи Дирихле в терминах и- и ^-стабильных функций и доказывается его совпадение с функцией цены соответствующей дифференциальной игры быстродействия Из этой теории следует, что в задачах быстродействия функция цены является единственной полунепрерывной снизу и-стабильной функцией, удовлетворяющей нулевому краевому условию на границе терминального множества, к которой поточечно сходится последовательность полунепрерывных сверху и-стабильных функций, удовлетворяющих тому же краевому условию и непрерывных на границе терминального множества Проверка существования указанной последовательности и, тем более, ее построение затруднительны при решении даже задач на плоскости Условия теоремы 1 требуют проверки свойств, аналогичных свойствам разрывного минимаксного решения, но в сколь угодно малых окрестностях подмножеств, на которые разбиваются границы множеств уровня тестируемой функции Рассмотрение нескольких окрестностей делает полученные условия более удобными для практической проверки, чем непосредственное использование определения разрывного минимаксного решения

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

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

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

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

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

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

В теории дифференциальных игр для функции цены Т°() известны различные типы сингулярных поверхностей, в точках которых оптимальные движения имеют те или иные особенности Исследование сингулярных поверхностей составляет основу книги Р Айзекса Они также изучались в работах А А Меликяна12 и Р Bernhard13 Типы сингулярных поверхностей выделяются на основе анализа поведения оптимальных траекторий в окрестности сингулярной поверхности и учете возможности особых оптимальных движений, идущих вдоль поверхности В частности, важными являются рассеивающие и экивокальные сингулярные поверхности На них функция цены Т°() является недифференцируемой Экивокальные сингулярные поверхности характерны именно для дифференциальных игр и не могут возникать в задачах управления с одним игроком

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

l-Mehkyan A A Generalized Characteristics of the First Order PDEs Applications m Optimal Control and Differential Games Boston Burkhauber, 1998

13 Bernhard P Singular Surfaces in Differential Games an introduction // Differential Games and Apph-tations - Berlin Springer-Vei lag, 1977 -P 1-33

са игр с автономной разделенной динамикой и ограничением на управление второго игрока в виде линейного отрезка доказана теорема 3 о том, что в точках рассеивающей и экивокальной сингулярных поверхностей автоматически выполнены инфинитезимальные свойства и- и ^-стабильности Теорема 3 используется в главах 3 и 4 для доказательства свойств и- и «-стабильности на сингулярных линиях

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

Х\ = Х-1 — V, х2 = и, \и\ < ц, 0<ь<»

Первый игрок минимизирует время перевода фазовой точки х = (хь^г) из заданного начального положения Хо на терминальное множество М = (О, а)т, а > V, интересы второго противоположны

Ранее исследования такой игры проводились в работах В С Пацко 15 и М Ю Филимонова16 Основываясь на результатах этих работ, на некотором ограниченном множестве описывается построение тестируемой функции, которая разрывна на области определения Далее проводится проверка всех условий теоремы 1, что дает совпадение тестируемой функции с функцией цены игры Таким образом, в данной главе результаты глав 1 и 2 применяются к примеру, решение которого известно

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

14Понтрягин Л С, Мищенко Е Ф Задача об убегании одного управляемого объекта от другого // ДАН СССР - 1969 - Т 189, Л* 4 - С 721-723

15Пацко В С Модечьный пример игровой задачи преследования с неполной информацией I // Дифференциальные уравнения - 1971 - Т 7, Л'« 3 - С 424-435 II // Дифференциальные уравнения -1972 - Т 8, № 8 - С 1423-1434

16 Филимонов М Ю Сопряжение сингулярных -шннй в дифференциальной игре Исслед задач ми-нимакс упр сб ст Свердловск УНЦАНСССР, 1985 - С 117-124

17Лаврентьев М А , Люстерник Л А Курс вариационного исчисления М,Л Гостехиэдат, 1938

Рис 1 Траектории, определяющие тестируемую функцию при h = 6, w — 2

Кроме того, в динамику системы была добавлена помеха, рассматриваемая как действие второго игрока Выбраны множества ограничений на управление второго игрока и терминальное множество Решение, приведенное в книге Р Айзекса, в дальнейшем было уточнено и дополнено в работах М Л Лидова18 и С А Чигиря19

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

х\ = у/хг cos u, х2 — y/^siiiu + wv,

и € Р = [0, 2тг], ve<?=[-l,lj, f>0, xqQRI,

где R\ - верхняя полуплоскость Первый (второй) шрок минимизирует (максимизирует) время достижения терминального множества М — [-¿,0] х [0, h], w,d,h> 0

Основываясь на методе Айзекса обработки полей классических характеристик, строится тестируемая функция <р( ), определенная в полуплос-

1ЦЛидов М Л Об одной задаче дифференциальных игр // Автоматика к ге гелгеханика - 1971 -V- 4, С 173 175

^Чигирь С А Об игровой задаче о долихобрачнсгохроне // Прикл математика и механика -1976 Т 40, вып 6 - С 1003-1013

кости В процессе построения возникают барьерные линии, на которых функция <р{ ) разрывна, а также рассеивающие и экивокальные сингулярные линии, на которых функция <р() является негладкой

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

Исследована зависимость решения от высоты И терминального множества Решение симметрично относительно вертикальной прямой х\ = —<1/2 Выделяются три случая Л > ш2, к < иг и /г = из2 Структура оптимального решения в случае к> ги2 показана на рис 1 Здесь V и £ - рассеивающая и экивокальная сингулярные линии, 5 - линия переключения, а и Ь - крайние точки экивокальной линии, В - барьерная линия Цена игры равна оо на прямолинейном участке линии В и ниже ее

Основные результаты диссертации

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

2 Доказана теорема о достаточных условиях выполнения инфинитези-мальных свойств стабильности в терминах сингулярных (рассеивающих и экивокальных) точек

3 Исследована задача о брахистохроне в игровой постановке, полученное решение обосновано

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

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

[1] Кампева Л В Достаточные условия стабильности функции цены в терминах сингулярных точек // Проблемы теоретической и прикладной математики тр 33-й Регион молодеж конф - Екатеринбург МММ УрО РАН, 2002 - С 249-253

[2] Kamneva L V, Patsko V S, Turova V L Construction of the Value Function for Game Brachistochrone Problem // Proc 10th Intern Simposium on Dynamic Games and Appl - St -Petersburg Russia, 2002 - Vol 1 -P 408-415

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

[4] Васильева ТВ, Кампева Л В Построение семейства экивокальных линий для .заданного поля характеристик в игровой задаче о брахистохроне // Проблемы теорет и прикл математики тр 35-й Регион молодеж конф - Екатеринбург ИММ УрО РАН, 2004 - С 212-216

[5] Камнева Л В О свойствах разрывной функции цены в игровой задаче быстродействия // Доклады РАН - 2006 - Т 408, №3 - С 301 -304

[6J Камнева Л В Об условиях совпадения разрывной функции с функцией цены игры в задаче быстродействия // Прикл математика и механика - 2006 - Т 70, вып 5 - С 739-752

[7] Камнева Л В О свойствах разрывной функции цены в игровой задаче быстродействия // Проблемы теоретической и прикладной математики тр 37-й Регион молодеж конф - Екатеринбург ИММ УрО РАН, 2006 - С 321-325

[8] Kamncua L V On optimahty of a discontinuous function in a time-optimal diffeiential game // Proc 13tli IFAC Woikshop 'C'ontiol Лрр] of Opli-mi7ation", Pans C'achan, Fiance, 26 - 28 Apul 2006 - P 317-322

|9] Камневп Л В О разрывной функции цепы в игровой задаче быстродействия // Проблемы георет и прнкл математики ip 38-н Ретион молодок конф - Екатеринбург ИММ УрО РАН, 2007 - С 296 300

Камнева Людмила Валерьевна

РАЗРЫВНАЯ ФУНКЦИЯ ЦЕНЫ В ИГРОВЫХ ЗАДАЧАХ БЫСТРОДЕЙСТВИЯ

Автореферат

Подписано в печать 05 04 2007 Формат 60x84 1/16 Объем 1 п л Тираж 100 экз Заказ №

Откопировано ООО "Таймер КЦ" Екатеринбург, ул Луначарского, 136 тел (343) 350-39-03, 355-93-63

Основные обозначения

Введение

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

1.1 Постановка задачи.

1.2 Свойства и- и г>-стабильных функций.

1.3 Свойства функции цены игры.

1.4 Теорема 1 о достаточных условиях.

1.5 Теорема 2 о достаточных условиях.

1.5.1 Корректно сжимаемые множества.

1.5.2 Формулировка и доказательство теоремы.

1.5.3 Пример.

2 Достаточные условия стабильности функции в терминах сингулярных точек

2.1 Критерии стабильности полунепрерывной функции.

2.2 Простейшие сингулярные точки

2.3 Рассеивающие и экивокальные сингулярные точки.

2.4 Теорема 3 о достаточных условиях стабильности.

3 Управление материальной точкой на прямой при наличии помехи

3.1 Постановка задачи.

3.2 Обоснование решения задачи.

4 Игровая задача о брахистохроне

4.1 Постановка задачи.

4.2 Характеристическая система для уравнения Айзекса - Белл-мана.

4.3 Первичные семейства характеристик.

4.4 Построение рассеивающей линии.

4.5 Построение экивокальной линии при h > w2.

4.6 Вторичное поле характеристик при h> w2.

4.7 Определение функции </?(•)

4.8 Обоснование решения задачи.

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

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

В отчетах Р. Айзекса [44-48] и его монографии [1] был предложен метод исследования игровых задач управления и рассмотрено большое число содержательных примеров. Однако строгой математической постановки дифференциальной игры при этом не было.

В дальнейшем были разработаны различные варианты формализации дифференциальных игр, среди которых отметим подход W.H. Fleming [43], основанный на аппроксимации дифференциальной игры многошаговыми играми, а также подход, использующий понятие неупреждающих стратегий и развитый в работах R.J. Elliott и N.J. Kalton [42].

Удобной с практической точки зрения является позиционная формализация дифференциальных игр, изложенная в книге Н.Н. Красовского и А.И.Субботина [6]. В рамках позиционной формализации подход к решению дифференциальной игры заключается в поиске функции цены, которая каждой точке пространства состояний системы ставит в соответствие оптимальный гарантированный результат в игре, начинающейся из этой точки. На базе функции цены можно построить стратегии оптимального управления по принципу обратной связи [5]. Отметим, что цена позиционной дифференциальной игры для заданной начальной точки совпадает с ценой в смысле W.H. Fleming или с ценой в классе неупреждающих стратегий в случаях, когда обе величины существуют.

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

Предположим, что динамика управляемой системы описывается уравнением x(t) = f(x{t),u{t), v(t)), t > 0, s(0) = x0eRn\M.

Здесь x(t) G Rn - фазовый вектор в момент времени t; u(t) € Р и v(t) € Q - управления минимизирующего и максимизирующего игроков; Р и Q -компакты в конечномерных пространствах. Пусть функция / непрерывна по совокупности переменных, удовлетворяет условию подлинейного роста и локальному условию Липшица по переменной х. Кроме того,

Н(х,р) = min max (р, f(x, u, v)) = max min(p, f(x,u,v)}. uGP veQ v€.Q u&P

В рамках позиционной формализации указанные условия обеспечивают существование функции цены Xq ь-> Т°(хо) £ [0, оо] дифференциальной игры быстродействия.

Рассмотрим краевую задачу для уравнения в частных производных первого порядка (уравнения Айзекса - Беллмана):

H(x,VT(x)) = -1, xeRn\M, (0.1)

Т(х) = 0, х G дМ. (0.2)

В книге Р. Айзекса [1] показано, что классическое решение задачи (0.1), (0.2) (если оно существует) совпадает с функцией цены Т°(-) дифференциальной игры быстродействия. Таким образом, при некоторых дополнительных условиях гладкости для нахождения дифференцируемой функции цены может быть использован метод классических характеристик [9] решения краевой задачи (0.1), (0.2).

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

В связи с большими техническими сложностями исследования конкретных задач в настоящее время известно не очень много работ, в которых проведены аналитические построения функции цены дифференциальных игр быстродействия. Среди таких исследований отметим результаты А.А. Меликяна [12,13], B.C. Пацко [14,15], С.А. Чигиря [29], J.V. Break well, J.Lewin, A.W.Merz, G. J. Olsder [51,52,54], J. Shinar [60]. Трудность аналитического решения игровых задач быстродействия требует численных алгоритмов решения, которые разрабатывались B.C. Пацко, В.Л.Туровой [27, 58, 59], В.Н.Ушаковым [61], M.Bardi, M.Falcone, P.Soravia [31-34], P.M.Cardaliaguet, M.Quincampoix, P.Saint-Pierre [38,40] и другими авторами.

В теории оптимального управления аналогом подхода к решению задачи на базе функции цены является метод динамического программирования. Если функция оптимального результата (функция Беллмана) дифференцируема, то ее поиск сводится к решению соответствующей краевой задачи для уравнения в частных производных (УЧП) первого порядка. В этом случае с помощью функции Беллмана определяется оптимальное управление по принципу обратной связи. Если функция Беллмана является негладкой, но непрерывной, то для решения задачи в классе управлений по принципу обратной связи может быть использован регулярный синтез В.Г.Болтянского [2]. Задачи оптимального быстродействия с разрывной функцией Беллмана исследовались, например, в работах G. Leitmann, Н. Frankowska, P. Cannarsa [37,50] и многих других [30,55].

Поскольку для краевой задачи Дирихле (0.1), (0.2) на множестве Rn\M функция цены Т°(-) содержательно определяет единственное разрывное решение, то конструкции теории позиционных дифференциальных игр можно использовать для определения обобщенных решений краевых задач для УЧП первого порядка. Такой подход лежит в основе теории минимаксных решений А.И. Субботина [22,23], которую можно применить для обоснования правильности построения функции цены.

В своих работах А.И. Субботиным дано определение разрывного минимаксного решения и(-) краевой задачи Дирихле:

H{x,Vu>(x))-u(x) = -1, xERn\M, (0.3) w(x) = 0, х Е dM. (0.4)

Для этого сначала вводятся определения верхних и нижних минимаксных решений уравнения (0.3). Верхнее (нижнее) минимаксное решение уравнения (0.3) определяется как полунепрерывная снизу (сверху) функция j(-) : ~RF\M —» R, надграфик (подграфик) которой слабо инвариантен относительно соответствующего характеристического дифференциального включения. Указанные свойства слабой инвариантности совпадают со свойствами w-стабильности и -^-стабильности функции цены. Кроме того, существуют различные эквивалентные способы определения верхних и нижних минимаксных решений.

Верхним решением задачи (0.3), (0.4) называется верхнее минимаксное решение и(-) уравнения (0.3), удовлетворяющее краевому условию (0.4) и оценке

Мс)|<1, xeRn\ М. (0.5)

Нижним решением задачи (0.3), (0.4) называется нижнее минимаксное решение си(-) уравнения (0.3), непрерывное в каждой точке х Е дМ, удовлетворяющее краевому условию (0.4) и оценке (0.5). '

Минимаксным решением задачи (0.3), (0.4) называется функция и(>) : Rn\M R такая, что существует последовательность верхних решений си^(-) и последовательность нижних решений w/c(-), k Е N, которые поточечно сходятся к функции и(-).

Определения верхних и нижних решений несимметричны: нижние решения должны быть непрерывны в каждой точке х £ дМ, что не требуется для верхнего решения. Это связано со свойством единственности минимаксного решения.

В работах А.И.Субботина доказано существование и единственность минимаксного решения краевой задачи (0.3), (0.4) и его совпадение с минимальным верхним решением. Классическое (т.е. гладкое) решение задачи (0.3), (0.4) (если оно существует) удовлетворяет определению минимаксного решения. Кроме того, показано, что функция цены Т°(-) дифференциальной игры быстродействия и минимаксное решение и>(-) связаны равенством uj(x) = 1 - exp(-T°(z)), х е Rn\M. (0.6)

Отмечено также, что в случае непрерывного минимаксного решения оно одновременно является верхним и нижним решением соответствующей краевой задачи. Преобразование вида (0.6), предложенное С.Н. Кружковым [7], используется в теории УЧП первого порядка в тех случаях, когда нужно перейти к ограниченным решениям.

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

Отметим, что существуют другие подходы к определению обобщенных решений краевой задачи (0.3), (0.4). Наиболее известно понятие непрерывного вязкостного решения, которое ввели в начале 80-х годов M.G. Crandall и P.L. Lions [41]. В работах M.Bardi, I. Capuzzo-Dolcetta [32], S.Bottacin, М. Falcone [31], P. Soravia [34] было предложено и исследовано понятие разрывного е-решения (envelope solution) краевой задачи (0.3), (0.4), определение которого опирается на понятия вязкостных верхних и нижних решений, отмечено совпадение е-решения с минимаксным решением и разработаны численные схемы построения е-решения.

Краткое содержание работы

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

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

Т°(.) :Rn\M^ R+.

Предположим, что на замкнутом множестве Q С Rn определена некоторая функция О -* [0, оо].

Задача состоит в нахождении таких условий на функцию </?(■), при которых выполнено равенство <р{х) = Т°(х), х £ IX Искомые условия должны быть удобными для практической проверки.

В параграфе 1.2 определяются понятия и- и ^-стабильных функций на открытом множестве G С Rn.

Определение 0.1. Функция и(-) : G —[0, оо] и-стабилъна на открытом множестве G С Д", если она полунепрерывна снизу и для любых у$ £ G, v* е Q существуют г > 0 и такое решение у(-) : [0,т] —>■ G дифференциального включения y(t) £ со {f(y(t), и, г>*) : и £ Р}, у{0) = у0, что выполнено неравенство uj{y(t)) < и>(уо) — t,t£ [0, г].

Определение 0.2. Функция <£>(•) : G —> [0, оо] v-стабильна на открытом множестве G С Rr\ если она полунепрерывна сверху и для любых £ G, и* Е Р существуют г > 0 и такое решение у(-) : [0,г] —> G дифференциального включения y(t) £ со {f(y(t), и,, v) : v £ Q}, у(0) = у0, что выполнено неравенство uj{y(t)) > to{yo) — t,t£ [0, г].

По аналогии с теорией минимаксных решений в леммах 1.1,1.2 устанавливается связь и- и ^-стабильных функций с функцией цены Т°(-) дифференциальной игры.

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

Параграф 1.4 посвящен формулировке и доказательству теоремы 1 о достаточных условиях. В работах А.И. Субботина при доказательстве теоремы о связи функции цены игры и минимаксного решения соответствующей краевой задачи последовательность v-стабильных функций (нижних решений) используется для конструирования подходящих позиционных стратегий уклонения от окрестности множества М на заданном промежутке времени. Если указанная последовательность определена лишь в некоторой открытой окрестности, пересекающейся с множеством М, то такие же методы построения позиционных стратегий уклонения можно применить для начальных точек, из которых допустимые траектории системы не покидают эту окрестность на заданном промежутке времени. Эта идея используется для доказательства теоремы 1. Условия теоремы требуют проверки свойств, аналогичных свойствам разрывного минимаксного решения, но в сколь угодно малых окрестностях подмножеств, на которые разбиваются границы множеств уровня тестируемой функции. Рассмотрение нескольких окрестностей делает полученные условия более удобными для практической проверки, чем непосредственное использование определения разрывного минимаксного решения. Применение теоремы 1 проиллюстрировано в третьей и четвертой главах диссертации на двух примерах игровых задач быстродействия на плоскости.

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

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

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

В параграфе 2.1 в виде утверждения 2.1 сформулированы инфинитезимальные критерии стабильности функции oj(-) :G-> [0, оо] на открытом множестве G, доказанные в работах А.И. Субботина. Такие критерии предполагают в каждой точке рассматриваемой области проверку неравенств для верхней или нижней производной по направлению функции, получаемой после преобразования Кружкова. Утверждения 2.22.7 упрощают проверку указанных неравенств в некоторых частных случаях.

В теории дифференциальных игр для функции цены Т°(-) известны [1,35,53] различные типы сингулярных поверхностей, в точках которых оптимальные движения имеют те или иные особенности. Классификация основана на анализе поведения оптимальных траекторий в окрестности сингулярной поверхности и учете возможности особых оптимальных движений, идущих вдоль самой сингулярной поверхности. В частности, важными являются рассеивающие и экивокальные сингулярные поверхности. На них функция цены Т°(-) является недифференцируемой. Экивокальные сингулярные поверхности характерны именно для дифференциальных игр и не могут возникать в задачах управления с одним игроком. В параграфах 2.2, 2.3 понятия рассеивающей и экивокальной сингулярных поверхностей распространяются на случай функции и(-) : G —> R. В параграфе 2.4 для класса игр с автономной разделенной динамикой и ограничением на управление второго игрока в виде линейного отрезка доказана теорема 3 о том, что в точках рассеивающей и экивокальной сингулярных поверхностей автоматически выполнены инфинитезимальные свойства ии ^-стабильности. Теорема 3 используется в главах 3 и 4 для доказательства свойств и- и ^-стабильности на сингулярных линиях.

Третья глава диссертации состоит из двух параграфов. В ней рассматривается игровая задача быстродействия на плоскости, представляющая собой модификацию известной задачи "мальчик и крокодил" [19,21]. Динамика системы и ограничения на управления игроков имеют вид

Х\ = Х2 — v, Х2 = и, \и\ < ц, 0 < v < V.

Первый игрок минимизирует время перевода фазовой точки х = (^1,^2) из заданного начального положения xq на терминальное множество М = (О, а)т, а > v, интересы второго противоположны.

Ранее исследования такой игры проводились в работах B.C. Пацко [14, 15] и М.Ю. Филимонова [28]. Основываясь на результатах этих работ, в параграфе 3.1 на некотором ограниченном множестве описывается построение тестируемой функции, которая разрывна на области определения. В параграфе 3.2 проведена проверка всех условий теоремы 1, которая дает совпадение тестируемой функции с функцией цены игры.

В четвертой главе, состоящей из восьми параграфов, рассматривается игровая задача о брахистохроне.

Впервые вариант игровой постановки задачи о брахистохроне был исследован в книге Р.Айзекса, где классическая задача вариационного исчисления о кривой наискорейшего спуска [10] была записана в виде задачи управления. Кроме того, в динамику системы была добавлена помеха, рассматриваемая как действие второго игрока. Выбраны множества ограничений на управление второго игрока и терминальное множество. Решение, приведенное в книге Р. Айзекса, в дальнейшем было уточнено и дополнено в работах M.JI. Лидова [11] и С.А. Чигиря [29].

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

Xi = \/x2Cosu, Х2 —\fx~2 smu + wv, ueP=[0,2тг], vzQ = [-1,1], t> 0, x0gRI, где R2+ - верхняя полуплоскость. Первый (второй) игрок минимизирует (максимизирует) время достижения терминального множества М = [-d, 0] х [0,h]; w,d,h> 0.

В параграфах 4.1-4.7, основываясь на методе Айзекса обработки полей классических характеристик, строится тестируемая функция </?(•), определенная в полуплоскости R+. В процессе построения возникают барьерные линии, на которых функция <р{-) разрывна, а также рассеивающие и экивокальные сингулярные линии, на которых функция ip(-) является негладкой. Отметим, что экивокальные сингулярные линии являются специфическими именно для дифференциальных игр и не могут возникать в задачах управления с одним игроком. Исследована зависимость функции ip(-) от высоты h терминального множества.

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

Основные результаты диссертации

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

2. Доказана теорема о достаточных условиях выполнения инфинитези-мальных свойств стабильности в терминах сингулярных (рассеивающих и экивокальных) точек.

3. Исследована задача о брахистохроне в игровой постановке, полученное решение обосновано.

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

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

2. Болтянский В.Г. Математические методы оптимального управления. -М.: Наука, 1969.- 408 с.

3. Болтянский В. Г. Пример нелинейного синтеза // Дифференц. уравнения. 1970. - Т. 6, № 4. - С. 644-649.

4. Кларк Ф. Оптимизация и негладкий анализ. М.: Наука, 1988. - 280 с.

5. Красовский Н.Н. Дифференциальные игры. Аппроксимационные и формальные модели // Мат. сб. 1978. - Т. 107, № 4. - С. 541-571.

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

7. Кружков С.Н. Обобщенные решения уравнений Гамильтона Якоби типа эйконала. I // Мат. сб. - 1975. - Т. 98, №3. С. 450-493.

8. Кряжимский А.В. К теории позиционных дифференциальных игр сближения-уклонения // ДАН СССР. 1978. - Т. 239, № 4. С. 779782.

9. Курант Р., Гильберт Д. Методы математической физики. Т. 2. М.; JL: Гостехиздат, 1945. - 620 с.

10. Лаврентьев М.А., Люстерник Л.А. Курс вариационного исчисления. М.; JI: Гостехиздат, 1938. - 192с.

11. Лидов М.Л. Об одной задаче дифференциальных игр // Автоматика и телемеханика. 1971. - № 4. - С. 173-175.

12. Меликян А.А. О минимальных наблюдениях в одной игре сближения // Прикл. математика и механика. 1973. - Т. 37, вып. 3. - С. 426-433.

13. Меликян А.А. Об оптимальном выборе интервалов помех в дифференциальных играх сближения // Прикл. математика и механика. -1975. Т. 39, вып. 2. - С. 207-215.

14. Пацко B.C. Модельный пример игровой задачи преследования с неполной информацией. I. // Дифференц. уравнения. 1971. - Т. 7, № 3. - С. 424-435.

15. Пацко B.C. Модельный пример игровой задачи преследования с неполной информацией. II. // Дифференц. уравнения. 1972. - Т. 8, № 8. - С. 1423-1434.

16. Пацко B.C. Задача качества в линейных дифференциальных играх второго порядка // Дифференц. игры и задачи упр.: сб. ст. Свердловск: УНЦ АН СССР, 1975. - С. 167-227.

17. Пацко B.C. Дифференциальная игра уклонения на плоскости // Прикл. математика и механика. 1977. - Т, 41, вып. 4. - С. 604-608.

18. Пацко B.C., Турова В.Л. Численное решение дифференциальных игр на плоскости: препринт. Екатеринбург: ИММ УрО РАН, 1995. 77 с.

19. Пашков А.Г. Об одной игре сближения // Прикл. математика и механика. 1970. - Т. 34, вып. 5. - С. 804-811.

20. Понтрягин Л.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф. Математическая теория оптимальных процессов. М.: Наука, 1969. -384 с.

21. Понтрягин Л.С., Мищенко Е.Ф. Задача об убегании одного управляемого объекта от другого // ДАН СССР. 1969. - Т. 189, № 4. -С. 721-723.

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

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

24. Алгоритмы и программы решения линейных дифференциальных игр: сб. науч. тр. / ред. А.И. Субботин, B.C. Пацко; АН СССР, УНЦ. -Свердловск, 1984. 296 с.

25. Субботин А.И., Ченцов А.Г. Оптимизация гарантии в задачах управления. М.: Наука, 1981. - 288 с.

26. Турова В. Л. Нелинейная дифференциальная игра качества на плоскости // Исслед. задач минимакс. упр.: сб. ст. Свердловск: УНЦ АН СССР, 1985.-С.91-116.

27. Турова В.Л. Построение множества позиционного поглощения в линейной дифференциальной игре второго порядка с нефиксированным временем окончания // Управление с гарантированным результатом: сб. науч. трудов. Свердловск: УНЦ АН СССР, 1987. - С. 92-111.

28. Филимонов М.Ю. Сопряжение сингулярных линий в дифференциальной игре // Исслед. задач минимакс. упр.: сб. ст. Свердловск: УНЦ АН СССР, 1985. С. 117-124.

29. Чигирь С.А. Об игровой задаче о долихобрахистохроне // Прикл. математика и механика. 1976. - Т. 40, вып. 6. - С. 1003-1013.

30. Alvarez О., Koike S., Nakayama I. Uniqueness of lower semicontinuous viscosity solutions for the minimum time problem // SIAM J. Contr. and Optim. 2000. - Vol. 38, № 2. - P. 470-481.

31. Bardi M., Bottacin S., Falcone M. Convergence of descrete schemes for discontinuous value functions of pursuit-evasion games // New Trends in Dynamic Games and Appl. Boston: Burkhauser, 1995. - P. 273-307.

32. Bardi M., Capuzzo-Dolcetta I. Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equation. Boston: Burkhauser, 1997. 570 p.

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

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

35. 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. P. III-1-III-5.

36. Cannarsa P., Frankowska H., Sinestrari C. Optimality Conditions and Synthesis for the Minimum Time Problem // Set-Valued Analysis. 2000.- Vol. 8. P. 127-148.

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

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

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

40. Elliott R.J.) Kalton N.J. The existence of value in differential games of pursuit and evasion //J. Different. Equat. -1972. Vol. 12, № 3. - P. 504523.

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

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

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

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

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

46. Isaacs R.P. Differential Games, IV: Mainly Examples. Research Memorandum RM-1486. RAND Corporation, Santa Monica, California. - 1955.

47. Krasovskii N.N., Subbotin A.I. Game-Theoretical Control Problems. -N.Y.: Springer-Verlag, 1988. 518 p.

48. Leitmann G. The calculus of variations and optimal control. An introduction. New York etc.: Plenum Press, 1981. - 311c.

49. Lewin J., Breakwell J. V. The Surveillance-Evasion Game of Degree // J. Optimiz. Theory and Appl. 1975. - Vol. 16, №3-4. - P. 339-353.

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

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

52. Merz A.W. The Homicidal Chauffeur a Differential Game: PhD thesis.- Stanford Univ., 1971.

53. Mignanego F., Pieri G. Minimal time Function in Problems without Local Controllability // J. Optimiz. Theory and Appl. 1993. - Vol. 78, № 1. -P. 49-58.

54. Raivio Т., Ehtamo H. On Numerical Solution of a Class of Pursuit-Evasion Games // Annals Intern. Soc. Dynamics Games. Boston: Birkhauser, 2000. -Vol.5.-P. 177-192.

55. Patsko V.S., Turova V.L. Minimum-Time Problem for Linear Second-Order Conflict-Controlled Systems // Proc. UKACC Intern. Conf. CON-TROL'96, Exeter, United Kingdom, 1996. P. 947-952.

56. Patsko V.S., Turova V.L. Numerical Solutions to the Minimum-Time Problem for Linear Second-Order Conflict-Controlled Systems // Proc. 7th Intern. Colloquium on Differential Equations, Plovdiv, Bulgaria, 1997.- P. 327-338.

57. Patsko V.S., Turova V.L. Level Sets of the Value Function in Differential Games with the Homicidal Chauffeur Dynamics // Intern. Game Theory Review, 2001. Vol. 3, № 1. - P. 67-112.

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

59. Ushakov V.N. Construction of Solutions in Differential Games of Pursuit-Evasion // Differential Inclusions and Optimal Control. Torun, 1998. -P. 269-281. (Lect. Notes in Nonlinear Anal., Vol. 2).

60. Камнева Л. В. Достаточные условия стабильности функции цены в терминах сингулярных точек // Проблемы теорет. и прикл. математики: тр. 33-й Регион, молодеж. конф. Екатеринбург: ИММ УрО РАН, 2002. - С. 249-253.

61. Karnneva L.V., Patsko V.S., Turova V.L. Construction of the Value Function for Game Brachistochrone Problem // Proc. 10th Intern. Simposium on Dynamic Games and Appl. St.-Petersburg, Russia, 2002. - Vol. 1. -P. 408-415.

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

63. Камнева Л. В. О свойствах разрывной функции цены в игровой задаче быстродействия // Доклады РАН. 2006. - Т. 408, №3. - С. 301-304.

64. Камнева Л. В. Об условиях совпадения разрывной функции с функцией цены игры в задаче быстродействия // Прикл. математика и механика. 2006. - Т. 70, вып. 5. - С. 739-752.

65. Камнева Л. В. О свойствах разрывной функции цены в игровой задаче быстродействия // Проблемы теорет. и прикл. математики: тр. 37-й Регион, молодеж. конф. Екатеринбург: ИММ УрО РАН, 2006. -С. 321-325.

66. Kamneva L. V. On optimality of a discontinuous function in a time-optimal differential game // Proc. 13th IFAC Workshop "Control Appl. of Optimization", Paris-Cachan, France, 26 28 April, 2006. - Paris, 2006. -P. 317-322.

67. Камнева JI. В. О разрывной функции цены в игровой задаче быстродействия // Проблемы теорет. и прикл. математики: тр. 38-й Регион, молодеж. конф. Екатеринбург: МММ УрО РАН, 2007. - С. 296-300.