[ «КАМНЕВА ЛЮДМИЛА ВАЛЕРЬЕВНА РАЗРЫВНАЯ ФУНКЦИЯ ЦЕНЫ В ИГРОВЫХ ЗАДАЧАХ БЫСТРОДЕЙСТВИЯ 01.01.02 дифференциальные уравнения ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук Научный руководитель: ...»
РОССИЙСКАЯ АКАДЕМИЯ НАУК
УРАЛЬСКОЕ ОТДЕЛЕНИЕ
ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ
На правах рукописи
КАМНЕВА ЛЮДМИЛА ВАЛЕРЬЕВНА
РАЗРЫВНАЯ ФУНКЦИЯ ЦЕНЫ
В ИГРОВЫХ ЗАДАЧАХ БЫСТРОДЕЙСТВИЯ
01.01.02 дифференциальные уравнения
ДИССЕРТАЦИЯ
на соискание ученой степени кандидата физико-математических наук
Научный руководитель:
кандидат физико-математических наук В.С.Пацко Екатеринбург 2007 Оглавление Основные обозначения Введение 1 Достаточные условия совпадения разрывной функции с функцией цены в игровых задачах быстродействия 1.1 Постановка задачи........................ 1.2 Свойства u- и v-стабильных функций............. 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 Обоснование решения задачи.................. Литература Основные обозначения – множество вещественных чисел;
R Rn – n-мерное евклидово пространство;
скалярное произведение векторов x и y;
x, y евклидова норма вектора x, равная x, x 2 ;
x выпуклая оболочка множества A;
co A замыкание множества A Rn ;
A граница множества A Rn ;
A внутренность множества A Rn ;
int A нимающая неотрицательные вещественные значения или несобственное значение ;
(x) A+B B(z, r) C k (G) пространство функций y(·) : G R, непрерывных Введение В диссертации исследуются вопросы, связанные с обоснованием аналитического построения разрывной функции цены в дифференциальных играх быстродействия. Используется подход, основанный на теории минимаксных решений краевой задачи для уравнения в частных производных первого порядка, разработанной А.И. Субботиным.
В теории дифференциальных игр изучаются задачи управления по принципу обратной связи в условиях неопределенности и помех. Исследования дифференциальных игр начались в 195060-е годы с рассмотрения математических моделей конфликтных ситуаций. В этих моделях динамика управляемой системы описывается обыкновенными дифференциальными уравнениями, в правую часть которых входят управляющие воздействия. Полезное управление рассматривается как действие первого игрока, минимизирующего некоторый функционал на множестве траекторий системы, а помеха считается результатом управления второго игрока, цель которого состоит в максимизации того же функционала. Управления игроков стеснены геометрическими ограничениями.
В отчетах Р. Айзекса [44–48] и его монографии [1] был предложен метод исследования игровых задач управления и рассмотрено большое число содержательных примеров. Однако строгой математической постановки дифференциальной игры при этом не было.
В дальнейшем были разработаны различные варианты формализации дифференциальных игр, среди которых отметим подход W.H. Fleming [43], основанный на аппроксимации дифференциальной игры многошаговыми играми, а также подход, использующий понятие неупреждающих стратегий и развитый в работах R.J. Elliott и N.J. Kalton [42].
Удобной с практической точки зрения является позиционная формализация дифференциальных игр, изложенная в книге Н.Н. Красовского и А.И. Субботина [6]. В рамках позиционной формализации подход к решеВведение нию дифференциальной игры заключается в поиске функции цены, которая каждой точке пространства состояний системы ставит в соответствие оптимальный гарантированный результат в игре, начинающейся из этой точки. На базе функции цены можно построить стратегии оптимального управления по принципу обратной связи [5]. Отметим, что цена позиционной дифференциальной игры для заданной начальной точки совпадает с ценой в смысле W.H. Fleming или с ценой в классе неупреждающих стратегий в случаях, когда обе величины существуют.
В диссертации рассматриваются игры, в которых функционалом платы является время до попадания фазовой точки на заданное замкнутое терминальное множество M Rn. Такие игры называются дифференциальными играми быстродействия. К ним относятся, например, задачи преследования–уклонения, а также задачи оптимального быстродействия в теории управления, которые можно рассматривать как игровые задачи при нулевом ограничении на управление второго игрока.
Предположим, что динамика управляемой системы описывается уравнением Здесь x(t) Rn – фазовый вектор в момент времени t; u(t) P и v(t) Q – управления минимизирующего и максимизирующего игроков; P и Q – компакты в конечномерных пространствах. Пусть функция f непрерывна по совокупности переменных, удовлетворяет условию подлинейного роста и локальному условию Липшица по переменной x. Кроме того, В рамках позиционной формализации указанные условия обеспечивают существование функции цены x0 T 0(x0) [0, ] дифференциальной игры быстродействия.
Рассмотрим краевую задачу для уравнения в частных производных первого порядка (уравнения Айзекса – Беллмана):
В книге Р. Айзекса [1] показано, что классическое решение задачи (0.1), (0.2) (если оно существует) совпадает с функцией цены T 0 (·) Введение дифференциальной игры быстродействия. Таким образом, при некоторых дополнительных условиях гладкости для нахождения дифференцируемой функции цены может быть использован метод классических характеристик [9] решения краевой задачи (0.1), (0.2).
В общем случае функция цены дифференциальной игры быстродействия может быть негладкой, разрывной, и, кроме того, может принимать несобственное значение. Метод построения кусочно-гладкой или разрывной функции цены, предложенный Р. Айзексом, заключается в последовательном нахождении гладких ветвей решения при помощи классических характеристик. Основная трудность применения метода Айзекса состоит в обнаружении поверхностей стыковки (сингулярных поверхностей) гладких ветвей функции цены. Р. Айзексом были рассмотрены различные типы сингулярных поверхностей и некоторые способы их построения.
В связи с большими техническими сложностями исследования конкретных задач в настоящее время известно не очень много работ, в которых проведены аналитические построения функции цены дифференциальных игр быстродействия. Среди таких исследований отметим результаты А.А. Меликяна [12, 13], В.С. Пацко [14, 15], С.А. Чигиря [29], J.V. Breakwell, J. Lewin, A.W. Merz, G.J. Olsder [51, 52, 54], J. Shinar [60].
Трудность аналитического решения игровых задач быстродействия требует численных алгоритмов решения, которые разрабатывались В.С. Пацко, В.Л. Туровой [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, H. Frankowska, P. Cannarsa [37, 50] и многих других [30, 55].
Введение Поскольку для краевой задачи Дирихле (0.1), (0.2) на множестве Rn \ M функция цены T 0(·) содержательно определяет единственное разрывное решение, то конструкции теории позиционных дифференциальных игр можно использовать для определения обобщенных решений краевых задач для УЧП первого порядка. Такой подход лежит в основе теории минимаксных решений А.И. Субботина [22,23], которую можно применить для обоснования правильности построения функции цены.
В своих работах А.И. Субботиным дано определение разрывного минимаксного решения (·) краевой задачи Дирихле:
Для этого сначала вводятся определения верхних и нижних минимаксных решений уравнения (0.3). Верхнее (нижнее) минимаксное решение уравнения (0.3) определяется как полунепрерывная снизу (сверху) функция надграфик (подграфик) которой слабо инвариантен относительно соответствующего характеристического дифференциального включения.
Указанные свойства слабой инвариантности совпадают со свойствами u-стабильности и v-стабильности функции цены. Кроме того, существуют различные эквивалентные способы определения верхних и нижних минимаксных решений.
Верхним решением задачи (0.3), (0.4) называется верхнее минимаксное решение (·) уравнения (0.3), удовлетворяющее краевому условию (0.4) и оценке Нижним решением задачи (0.3), (0.4) называется нижнее минимаксное решение (·) уравнения (0.3), непрерывное в каждой точке x M, удовлетворяющее краевому условию (0.4) и оценке (0.5).
Минимаксным решением задачи (0.3), (0.4) называется функция (·) :
Rn \ M R такая, что существует последовательность верхних решений (k) (·) и последовательность нижних решений k (·), k N, которые поточечно сходятся к функции (·).
Введение Определения верхних и нижних решений несимметричны: нижние решения должны быть непрерывны в каждой точке x M, что не требуется для верхнего решения. Это связано со свойством единственности минимаксного решения.
В работах А.И.Субботина доказано существование и единственность минимаксного решения краевой задачи (0.3), (0.4) и его совпадение с минимальным верхним решением. Классическое (т.е. гладкое) решение задачи (0.3), (0.4) (если оно существует) удовлетворяет определению минимаксного решения. Кроме того, показано, что функция цены T 0 (·) дифференциальной игры быстродействия и минимаксное решение (·) связаны равенством Отмечено также, что в случае непрерывного минимаксного решения оно одновременно является верхним и нижним решением соответствующей краевой задачи. Преобразование вида (0.6), предложенное С.Н. Кружковым [7], используется в теории УЧП первого порядка в тех случаях, когда нужно перейти к ограниченным решениям.
Опираясь на связь функции цены дифференциальной игры и минимаксного решения краевой задачи (0.3), (0.4), получаем, что в задачах быстродействия функция цены является единственной полунепрерывной снизу u-стабильной функцией, удовлетворяющей нулевому краевому условию на границе множества M, к которой поточечно сходится последовательность полунепрерывных сверху v-стабильных функций, удовлетворяющих тому же краевому условию и непрерывных на границе множества M. Однако проверка существования указанной последовательности и, тем более, ее построение во всем пространстве игры затруднительны при решении даже задач на плоскости.
Отметим, что существуют другие подходы к определению обобщенных решений краевой задачи (0.3), (0.4). Наиболее известно понятие непрерывного вязкостного решения, которое ввели в начале 80-х годов M.G. Crandall и P.L. Lions [41]. В работах M. Bardi, I. Capuzzo-Dolcetta [32], S. Bottacin, M. Falcone [31], P. Soravia [34] было предложено и исследовано понятие разрывного e-решения (envelope solution) краевой задачи (0.3), (0.4), определение которого опирается на понятия вязкостных верхних и нижних решений, отмечено совпадение e-решения с минимаксным решением и разработаны численные схемы построения e-решения.
Введение Первая глава диссертации состоит из пяти параграфов и посвящена формулировке и доказательству двух теорем о достаточных условиях совпадения разрывной тестируемой функции с функцией цены рассматриваемой дифференциальной игры.
В параграфе 1.1 описывается дифференциальная игра быстродействия в позиционной формализации и дается определение ее функции цены Предположим, что на замкнутом множестве Rn определена некоторая функция Задача состоит в нахождении таких условий на функцию (·), при которых выполнено равенство (x) = T 0(x), x. Искомые условия должны быть удобными для практической проверки.
В параграфе 1.2 определяются понятия u- и v-стабильных функций на открытом множестве G Rn.
Определение 0.1. Функция (·) : G [0, ] u-стабильна на открытом множестве G Rn, если она полунепрерывна снизу и для любых y0 G, v Q существуют > 0 и такое решение y(·) : [0, ] G дифференциального включения что выполнено неравенство (y(t)) (y0) t, t [0, ].
Определение 0.2. Функция (·) : G [0, ] v-стабильна на открытом множестве G Rn, если она полунепрерывна сверху и для любых y0 G, u P существуют > 0 и такое решение y(·) : [0, ] G дифференциального включения что выполнено неравенство (y(t)) (y0) t, t [0, ].
По аналогии с теорией минимаксных решений в леммах 1.1, 1.2 устанавливается связь u- и v-стабильных функций с функцией цены T 0 (·) дифференциальной игры.
Введение Основные свойства функции цены игры, которые используются в дальнейшем, приведены в параграфе 1.3. Там же доказана лемма 1.3 о непрерывном изменении цены игры для заданной начальной точки при расширении терминального множества.
Параграф 1.4 посвящен формулировке и доказательству теоремы 1 о достаточных условиях. В работах А.И. Субботина при доказательстве теоремы о связи функции цены игры и минимаксного решения соответствующей краевой задачи последовательность v-стабильных функций (нижних решений) используется для конструирования подходящих позиционных стратегий уклонения от окрестности множества M на заданном промежутке времени. Если указанная последовательность определена лишь в некоторой открытой окрестности, пересекающейся с множеством M, то такие же методы построения позиционных стратегий уклонения можно применить для начальных точек, из которых допустимые траектории системы не покидают эту окрестность на заданном промежутке времени. Эта идея используется для доказательства теоремы 1. Условия теоремы требуют проверки свойств, аналогичных свойствам разрывного минимаксного решения, но в сколь угодно малых окрестностях подмножеств, на которые разбиваются границы множеств уровня тестируемой функции. Рассмотрение нескольких окрестностей делает полученные условия более удобными для практической проверки, чем непосредственное использование определения разрывного минимаксного решения. Применение теоремы 1 проиллюстрировано в третьей и четвертой главах диссертации на двух примерах игровых задач быстродействия на плоскости.
В параграфе 1.5 формулируется и доказывается теорема 2 о достаточных условиях. Условия теоремы предполагают проверку u-стабильности тестируемой функции, v-стабильности ее перезамыкания (т.е. функции с замкнутым подграфиком) и проверку введенного в диссертации свойства корректной сжимаемости множеств уровня тестируемой функции.
Проверка последнего свойства затруднительна. Поэтому применение теоремы 2 не иллюстрируется. Однако приводится пример игровой задачи быстродействия на плоскости, показывающий, что требование корректной сжимаемости множеств уровня тестируемой функции исключить нельзя (без какой-либо замены).
Предлагаемые в первой главе достаточные условия оптимальности справедливы и для задач управления, поскольку задачи теории управлеВведение ния можно рассматривать как частный случай задач теории дифференциальных игр (при нулевом ограничении на управление второго игрока).
Однако каких-либо упрощений в формулировке условий не появляется.
Условия обеих теорем включают в себя проверку свойств u- и v-стабильности полунепрерывных функций. Во второй главе, состоящей из четырех параграфов, сформулированы утверждения, упрощающие такую проверку. При этом используются различные инфинитезимальные критерии u- и v-стабильности.
В параграфе 2.1 в виде утверждения 2.1 сформулированы инфинитезимальные критерии стабильности функции на открытом множестве G, доказанные в работах А.И. Субботина. Такие критерии предполагают в каждой точке рассматриваемой области проверку неравенств для верхней или нижней производной по направлению функции, получаемой после преобразования Кружкова. Утверждения 2.2– 2.7 упрощают проверку указанных неравенств в некоторых частных случаях.
В теории дифференциальных игр для функции цены T 0 (·) известны [1,35,53] различные типы сингулярных поверхностей, в точках которых оптимальные движения имеют те или иные особенности. Классификация основана на анализе поведения оптимальных траекторий в окрестности сингулярной поверхности и учете возможности особых оптимальных движений, идущих вдоль самой сингулярной поверхности. В частности, важными являются рассеивающие и экивокальные сингулярные поверхности.
На них функция цены T 0(·) является недифференцируемой. Экивокальные сингулярные поверхности характерны именно для дифференциальных игр и не могут возникать в задачах управления с одним игроком.
В параграфах 2.2, 2.3 понятия рассеивающей и экивокальной сингулярных поверхностей распространяются на случай функции (·) : G R. В параграфе 2.4 для класса игр с автономной разделенной динамикой и ограничением на управление второго игрока в виде линейного отрезка доказана теорема 3 о том, что в точках рассеивающей и экивокальной сингулярных поверхностей автоматически выполнены инфинитезимальные свойства uи v-стабильности. Теорема 3 используется в главах 3 и 4 для доказательства свойств u- и v-стабильности на сингулярных линиях.
Введение Третья глава диссертации состоит из двух параграфов. В ней рассматривается игровая задача быстродействия на плоскости, представляющая собой модификацию известной задачи “мальчик и крокодил” [19, 21]. Динамика системы и ограничения на управления игроков имеют вид Первый игрок минимизирует время перевода фазовой точки x = (x1, x2) из заданного начального положения x0 на терминальное множество M = (0, a)T, a >, интересы второго противоположны.
Ранее исследования такой игры проводились в работах В.С. Пацко [14, 15] и М.Ю. Филимонова [28]. Основываясь на результатах этих работ, в параграфе 3.1 на некотором ограниченном множестве описывается построение тестируемой функции, которая разрывна на области определения. В параграфе 3.2 проведена проверка всех условий теоремы 1, которая дает совпадение тестируемой функции с функцией цены игры.
В четвертой главе, состоящей из восьми параграфов, рассматривается игровая задача о брахистохроне.
Впервые вариант игровой постановки задачи о брахистохроне был исследован в книге Р. Айзекса, где классическая задача вариационного исчисления о кривой наискорейшего спуска [10] была записана в виде задачи управления. Кроме того, в динамику системы была добавлена помеха, рассматриваемая как действие второго игрока. Выбраны множества ограничений на управление второго игрока и терминальнoe множествo. Решение, приведенное в книге Р. Айзекса, в дальнейшем было уточнено и дополнено в работах М.Л. Лидова [11] и С.А. Чигиря [29].
Постановка рассматриваемой в четвертой главе задачи о брахистохроне отличается от постановки Р. Айзекса формой терминального множества и ограничением на управление второго игрока. Динамика системы и ограничения на управления игроков имеют вид где R+ – верхняя полуплоскость. Первый (второй) игрок минимизирует (максимизирует) время достижения терминального множества M = [d, 0] [0, h]; w, d, h > 0.
Введение В параграфах 4.1–4.7, основываясь на методе Айзекса обработки полей классических характеристик, строится тестируемая функция (·), определенная в полуплоскости R+. В процессе построения возникают барьерные линии, на которых функция (·) разрывна, а также рассеивающие и экивокальные сингулярные линии, на которых функция (·) является негладкой. Отметим, что экивокальные сингулярные линии являются специфическими именно для дифференциальных игр и не могут возникать в задачах управления с одним игроком. Исследована зависимость функции (·) от высоты h терминального множества.
С помощью теоремы 1 в параграфе 4.8 показывается совпадение тестируемой функции с функцией цены игры. Обоснование решения задачи усложняется тем, что правая часть динамики системы не удовлетворяет классическим условиям существования цены игры, а именно, локальному условию Липшица по фазовой переменной.
1. Доказаны две теоремы о достаточных условиях совпадения разрывной тестируемой функции с функцией цены дифференциальной игры быстродействия.
2. Доказана теорема о достаточных условиях выполнения инфинитезимальных свойств стабильности в терминах сингулярных (рассеивающих и экивокальных) точек.
3. Исследована задача о брахистохроне в игровой постановке, полученное решение обосновано.
Автор работы глубоко благодарен научному руководителю к.ф.-м.н.
Пацко Валерию Семеновичу за постоянное внимание к работе.
Глава Достаточные условия совпадения разрывной функции с функцией цены в игровых задачах быстродействия В данной главе рассматривается дифференциальная игра быстродействия в позиционной формализации. Ставится задача о поиске таких условий на некоторую (тестируемую) разрывную функцию, заданную на замкнутом множестве, выполнение которых обеспечивает ее совпадение с функцией цены игры. Приводятся определения u- и v-стабильных функций и отмечается их связь с функцией цены игры. Доказывается свойство непрерывного изменения цены игры для заданной начальной точки при расширении терминального множества. Формулируются и доказываются две теоремы о достаточных условиях совпадения заданной разрывной функции с функцией цены игры. Условия второй теоремы предполагают проверку свойства корректной сжимаемости множеств уровня тестируемой функции. Приводится пример игровой задачи быстродействия на плоскости, показывающий, что требование корректной сжимаемости множеств уровня тестируемой функции исключить нельзя.
1.1 Постановка задачи Дадим описание дифференциальной игры быстродействия в позиционной формализации [6, 23].
Рассматривается управляемая система, движение которой описывается уравнением Глава Здесь x(t) Rn – фазовое состояние в момент времени t; u(t) P и v(t) Q – управления минимизирующего и максимизирующего игроков;
P и Q – компактные множества в конечномерных пространствах.
Предполагается, что функция f непрерывна по совокупности переменных, удовлетворяет неравенству и в каждой ограниченной области X Rn выполнено условие Липшица по переменной x, т.е.
для всех x(1), x(2) X, u P, v Q. Кроме того, пусть для любых x, p Rn выполнено условие седловой точки [6]:
Здесь угловыми скобками обозначено скалярное произведение векторов.
Функция H называется гамильтонианом системы (1.1).
Позиционными стратегиями [6, 23] первого и второго игроков назовем произвольные функции U : [0, ) Rn P и V : [0, ) Rn Q.
Стратегии U, V порождают пучки X1 (x0, U ), X2 (x0, V ) конструктивных движений, выходящих из начальной позиции x0 при t = 0.
Конструктивным движением x(·) X1 (x0, U ) называется функция x(·) : [0, ) Rn, для которой на любом отрезке [0, ], > 0, найдется последовательность ломаных Эйлера x(k) (·) : [0, ) Rn, определяемых условиями равномерно сходящаяся к x(·) и такая, что supi(i+1 i ) 0 при k.
Здесь интервалы [i, i+1), i = 1, 2,..., разбивают полуось t 0, v (k) (·) – измеримая функция со значениями в множестве Q. Аналогично определяются элементы множества X2 (x0, V ).
Цель первого игрока – быстрейшее сближение точки x(t) с заданным замкнутым множеством M Rn. Второй игрок стремится либо исключить встречу с M, либо максимизировать время до встречи. Таким образом, Глава оптимизируемый функционал для игровой задачи быстродействия имеет вид Если в точке x0 выполнено равенство то значение T (x0; M) [0, ] называется ценой игры в точке x0.
При указанных условиях на функцию f для любого x0 Rn существует [6, 23] цена игры. Более того, в формуле (1.5) инфимум по U достигается, т.е. существует оптимальная позиционная стратегия первого игрока.
Функция T ( · ; M) : Rn [0, ] называется функцией цены игры.
Пусть на замкнутом множестве Rn определена некоторая функция Задача состоит в нахождении таких условий на функцию (·), при которых выполнено равенство (x) = T (x; M), x. Искомые условия должны быть удобными для практической проверки.
1.2 Свойства u- и v-стабильных функций С функцией цены тесно связаны понятия u- и v-стабильных функций [23, 49].
Определение 1.1. Функция (·) : G [0, ] u-стабильна на открытом множестве G Rn, если она полунепрерывна снизу и для любых y0 G и v Q существует такое решение y(·) : [0, ] G дифференциального включения где – некоторое положительное число, что В случае, когда функция (·) конечна, неравенство (1.7) означает выполнение включения Глава где epi – надграфик функции (·):
Траекторию y(·), удовлетворяющую неравенству (1.7), будем называть локально выживающей в надграфике функции (·).
Определение 1.2. Функция (·) : G [0, ] v-стабильна на открытом множестве G Rn, если она полунепрерывна сверху и для любых y0 G и u P существует такое решение y(·) : [0, ] G дифференциального включения где – некоторое положительное число, что В случае, когда функция (·) конечна, неравенство (1.9) означает выполнение включения где hypo – подграфик функции (·):
Траекторию y(·), удовлетворяющую неравенству (1.9), будем называть локально выживающей в подграфике функции (·).
Заметим, что в работах [23,49] определения u- и v-стабильных функций даны для конечных функций.
Сформулируем утверждения о продолжимости локально выживающих траекторий.
Утверждение 1.1. Пусть функция (·) : G [0, ] – u-стабильна на открытом множестве G Rn. Тогда для любых y0 G и v Q существует решение y(·) : [0, ) G дифференциального включения (1.6), где либо =, либо y() G, такое, что (y(t)) (y0 ) t для всех t [0, ).
Утверждение 1.2. Пусть функция (·) : G [0, ] – v-стабильна на открытом множестве G Rn. Тогда для любых y0 G и u P существует решение y(·) : [0, ) G дифференциального включения (1.8), где либо =, либо y() G, такое, что (y(t)) (y0 ) t для всех t [0, ).
Глава Утверждения 1.1, 1.2 доказываются от противного, см. также [23, c. 312], замечание A8.2. Таким образом, можно дать эквивалентное определение стабильных функций, в котором траектория дифференциального включения обладает соответствующими свойствами вплоть до выхода из множества G. В случае, когда u-стабильная (v-стабильная) функция конечна на множестве G, эквивалентное определение стабильности функции означает свойство стабильности надграфика (подграфика) этой функции, которое введено в работе [6].
Сформулируем леммы, устанавливающие связь между u- и v-стабильными функциями и функцией цены игры для подходящего терминального множества.
Определение 1.3. Допустимой траекторией называется решение уравнения (1.1) при некоторых измеримых управлениях u(·) : [0, ) P и v(·) : [0, ) Q.
Лемма 1.1. Пусть функция (·) : G [0, ] u-стабильна на открытом множестве G \ D Rn, D Rn – замкнутое множество, t 0 и Предположим, что x G \ D и все допустимые траектории из начальной точки x не покидают множества G на отрезке времени [0, (x)t ]. Тогда Лемма 1.2. Пусть функция (·) : G [0, ] v-стабильна на открытом множестве G \ D Rn, D Rn – замкнутое множество, t 0, и функция (·) непрерывна в точках множества D G. Предположим, что x G \ D, [0, (x) t ) и все допустимые траектории из начальной точки x не покидают множества G на отрезке времени [0, ]. Тогда Глава В случае G = Rn доказательства лемм 1.1, 1.2 приведены в [6] и основываются на свойствах стратегий, экстремальных к надграфику (подграфику) u-стабильной (v-стабильной) функции. Другие доказательства даны в [23] при условии, что правая часть динамики системы является глобально липшицевой по переменной x. В случае G Rn идея доказательства по сравнению с [6] не изменяется, поскольку допустимые траектории не выходят из G на рассматриваемом промежутке времени. Для полноты изложения приведем доказательство леммы 1.1.
Доказательство леммы 1.1. В силу u-стабильности функции (·) на множестве G и в силу утверждения 1.1 о продолжимости локально выживающих траекторий множество является u-стабильным мостом [6, c. 52] на множество D, где т.е. для любой точки (t0, y0) W и любых значений > 0 и v Q найдется такое решение y(·) : [t0, t0 + ] Rn дифференциального включения (1.6) с начальным условием y(t0 ) = y0, что либо (, y( )) W, либо (, y()) D для некоторого [t0, t0 + ].
Имеем (0, x) W. Построим u-стабильный мост W0 [0, (x)t]G на множество [0, (x) t ] D, такой, что (0, x) W0.
Пусть = (x) t. Обозначим через Vk множество всех функций vk (·) : [0, ] Q, кусочно-постоянных на равномерном разбиении отрезка [0, ] с шагом k = 2k, k N, непрерывных справа в точках разрыва. Обозначим через Yk (x, vk (·)) множество всех непрерывных функций y(·) : [0, ] G, удовлетворяющих начальному условию y(0) = x, дифференциальным включениям и условию (t, y(t)) W, t [0, tD (y(·))], где i = ik, i 0, 2k 1, tD (y(·)) – первый момент попадания траектории y(·) на множество D. Множество Yk (x, vk (·)) непусто в силу того, что W – u-стабильный мост на множество D и все допустимые траектории из начальной точки x не покидают множество G на отрезке [0, ].
Глава Пусть Последовательность множеств Wk монотонно возрастает по включению при k и содержится в некотором ограниченном множестве. Следовательно, в метрике Хаусдорфа существует предельное множество. Обозначим замыкание предельного множества через W0, т.е.
Имеем (0, x) W0.
Покажем, что множество W0 является u-стабильным мостом на множество [0, ] D. Пусть (t0, y0) W0. Найдется такая последовательность точек {(k, yk )}, что k t0, yk y0 при k и yk = yk (k ), где yk (·) Yk (x, vk (·)), vk (·) Vk, момент k принадлежит равномерному разбиению отрезка [0, ] с шагом k.
Пусть v Q. Положим Найдем такое yk (·) Yk (x, vk (·)), что yk (t) = yk (t), t [0, k ]. По определению множества W0 имеем (t, yk (t)) W0, t [0, tD (yk (·))]; tD (yk (·)).
Функции {yk (·)} равномерно ограничены и равностепенно непрерывны. Следовательно, найдется подпоследовательность функций {yk (·)}, равномерно сходящаяся к некоторой функции y(·), которая удовлетворяет дифференциальному включению и условию y(t0 ) = y0. В силу замкнутости множества W0 получаем, что (t, y(t)) W0, t [0, tD (y(·))]. Таким образом, множество W0 является u-стабильным мостом на множество [0, ] D.
Стратегия экстремального прицеливания [6, c. 57] на u-стабильный мост W0 гарантирует приведение системы на множество D на отрезке времени [0, (x) t ]. Таким образом, доказано неравенство (1.10).
Глава 1.3 Свойства функции цены игры Приведем основные свойства функции цены, которые будут использоваться в дальнейшем. Введем обозначение Для любого > 0 и любого x W ( ; M) выполнено [6] равенство Из известных результатов [6, 23] следует, что M = W (0; M), функция T ( · ; M) полунепрерывна снизу и обладает свойством u-стабильности на множестве Rn \ M. Верхнее замыкание функции цены обладает [23, стр. 258] свойством v-стабильности на множестве Rn.
Лемма 1.3. Пусть замкнутые множества D Rn, > 0, монотонно убывают по включению при +0 и >0 D = M. Тогда Доказательство. 1. Обозначим через M замкнутую -окрестность терминального множества M, т.е.
Покажем, что Для всех x M равенство (1.13) очевидно. Выберем x Rn \ M.
Предположим, что T (x; M) <. Поскольку M M, то Из известных результатов [6] следует, что для любого > 0 существует такое = () > 0, что второй игрок уклоняется от множества M из точки x на отрезке времени [0, T (x; M) ]. Следовательно, Глава Учитывая (1.14), (1.15), получаем равенство (1.13) для точки x.
Предположим, что T (x; M) =. Согласно [6], для любого K > 0 существует такое > 0, что второй игрок уклоняется от множества M на отрезке времени [0, K], т.е. T (x, M) > K. Следовательно, и равенство (1.13) для точки x выполнено.
2. Пусть x Rn и = T (x; M) <. Существует замкнутое ограниченное множество Z Rn, содержащее все возможные траектории системы (1.1) с начальным условием x(0) = x на отрезке времени [0, ].
Для числа > 0 определим значение Имеем ( ) +0 при +0.
Из вложений M D и D Z M( ) Z, > 0, следуют неравенства Отсюда при учете соотношения (1.13) получаем, что Таким образом, равенство (1.12) доказано.
3. Пусть x Rn и T (x; M) =. Выберем произвольное K > 0.
Обозначим через Z(K) замкнутое ограниченное множество в пространстве Rn, содержащее все траектории системы (1.1) с начальным условием x(0) = x на отрезке времени [0, K]. В силу соотношения (1.13) найдется такое = (K) > 0, что T (x; M ) > K. Поскольку >0 D = M, то существует такое = (K) > 0, что D Z(K) M Z(K). Следовательно, T (x; D ) > K. Поскольку число K выбрано произвольно, получаем равенство и соотношение (1.13) выполнено.
Глава 1.4 Теорема 1 о достаточных условиях Сформулируем и докажем теорему 1.
Теорема 1. Пусть Rn, M – замкнутые множества, задана функция и введены обозначения Предположим, что функция (·) полунепрерывна снизу, D(0) = M, T (0, ) – некоторое конечное (либо пустое) множество и выполнены следующие условия.
1) Для любого t (0, ) \ T существуют число 0 > 0 и множество G G(t, 0) \ D(t), такие, что а) выполнены соотношения G(t, 0) G, и функция u-стабильна на множестве G(t, 0) \ D(t);
б) существуют функции которые v-стабильны на множестве G(t, 0) \ D(t), равны нулю и непрерывны в точках множества D(t) G(t, 0), и Глава 2) Для любых t (0, ) \ T и > 0 найдется такое > 0, что функция (·) определена, непрерывна и обладает свойствами u- и v-стабильности на множестве где 3) Для любых t (0, ) \ T и > 0 найдутся число > 0 и функции где такие, что функции k (·), k N, v-стабильны на множестве GB (t,, ) \ D(t), равны нулю и непрерывны в точках множества D(t) GB (t,, ), и выполнено предельное соотношение 4) Для любого x0 \ M, такого, что (x0) = <, найдется последовательность {xk }, для которой (xk ) < (x0) и xk x0 при Тогда Доказательство. Сначала докажем теорему для случая T =.
Предположим, что = 0. Тогда (x) = 0, x. В силу условия D(0) = M теоремы получаем, что = M и заключение теоремы очевидно.
Далее будем считать, что > 0.
Пусть t (0, ). Для момента t выберем число 0 > 0, множество G и функции k (·), k N, о существовании которых говорится в условии 1) теоремы. Пусть функция (·) определяется формулой (1.17) при t = t.
Глава Для краткости будем использовать обозначения 1. Покажем, что найдется такое (0, 0), что а) Пусть 1 < 0. Найдется такое 1 > 0, что из любой начальной точки x0 G (1) допустимые траектории не покидают множество G (0) на отрезке времени [0, 1]. В силу равенства (1.16) существует такое 2 (0, 1], что Выберем x0 G (2)\(G D ). Поскольку все допустимые траектории из начальной точки x0 не покидают множество G (0) на отрезке времени [0, 1], (x0) < 1 и функция (·) u-стабильна, то в силу леммы 1. справедливо неравенство Заметим, что (x0) > 0. Выберем произвольное число (0, (x0)].
В силу условия (1.18) найдется такое k N, что выполнены неравенства Кроме того, (x0) 0. Функция k (·) v-стабильна на множестве G (0), равна нулю и непрерывна в точках множества G (0) D. В силу леммы 1.2 справедливо неравенство Переходя к пределу при 0 и учитывая соотношение (1.23), получаем равенство (1.21) во всех точках множества G (2) \ (G D ).
б) По условию теоремы найдется такое (0, 2], что функция (·) непрерывна и u- и v-стабильна на множестве GF (2, ). Пусть 1 (0, ).
Выберем такое 2 (0, 1], что из любой начальной точки x0 GF (2, 1) допустимые траектории не покидают множество G (2, ) на отрезке времени [0, 2]. В силу непрерывности и u-стабильности функции (·) на множестве GF (2, ) существует такое (0, 1], что Глава В силу лемм 1.1, 1.2 для любой точки x0 GF (2, ) справедливы неравенства Переходя к пределу при 0, получаем равенство (1.21) во всех точках множества GF (2, ).
Поскольку то равенство (1.21) доказано.
2. Покажем, что найдется > 0, для которого выполнены соотношения где Для значения найдем число 2 (0, ] и функции которые удовлетворяют свойствам, приведенным в условии 3) теоремы.
Пусть 3 (0, 2). Выберем такое 3 (0, 2], что из любой начальной точки x0 GB (, 3) допустимые траектории не покидают множество G (, 2) на отрезке времени [0, 3].
Пусть x0 GB (, 3) \ D. В силу (1.19) выберем такое k N, что k (x0) > 3. Поскольку функция k (·) v-стабильна на множестве GB (, 2), равна нулю и непрерывна в точках множества D GB (, 2), то в силу леммы 1.2 справедлива оценка Таким образом, Пусть x0 G G (). В силу (1.18) можно выбрать такое k N, что k (x0) > 3. Поскольку функция k (·) v-стабильна на множестве G (0), равна нулю и непрерывна в точках множества D G (0), и из начальной Глава точки x0 все допустимые траектории не покидают множество G (0) на отрезке времени [0, 3], то в силу леммы 1.2 справедлива оценка Таким образом, Найдем такое (0, 3], что для произвольной начальной точки x0 D + B(0, 3) допустимые траектории не достигают множества D на отрезке времени [0, ]. Имеем T (x0; D) >, x0 D + B(0, 3). Следовательно, Учитывая соотношения (1.25), (1.26), получаем, что В силу равенства (1.21) соотношения (1.24) выполнены.
3. Выберем (0, ). Определим функцию (·) : [0, ] следующим образом:
Покажем, что Для краткости положим Пусть Из результатов раздела 2 следует, что > 0.
Покажем, что Пусть Глава В силу равенства E() = W (; D ) имеем t, t1 [0, ]. Следовательно, Поскольку x W (t; D )E(t1), то x W (t1 ; D )E(t). Отсюда получаем, что и равенство (1.28) доказано.
Рассмотрим следующие случаи.
Случай 1: =. Возможны два варианта:
Для последнего варианта выберем x \ 0E(). Имеем (x) =.
Учитывая определение величины, находим, что x 0W (; D ), и, следовательно, T (x; D ) =. Таким образом, (x) = T (x; D ) =.
В силу (1.28) соотношения (1.27) для случая 1 доказаны.
Случай 2: 0 < <. Выберем x E() \ [0,) E().
Имеем (x) =. Учитывая определение величины, находим, что x [0,) W (; D ), и, следовательно, T (x; D ).
В силу свойств u-стабильности из условий 1), 2) и в силу условия 4) теоремы найдется такая последовательность {xk }, что (xk ) < (x) и xk x при k. Имеем Учитывая полунепрерывность снизу функции (·), получаем, что tk при k. Поскольку W (tk ; D ) = E(tk ) и xk E(tk ), то справедливо неравенство T (xk ; D ) tk. Принимая во внимание полунепрерывность снизу функции T (·; D ), имеем Следовательно, T (x; D ) =.
В силу (1.28) доказано равенство Покажем, что Глава Включение E() W (; D ) следует из (1.29). Докажем обратное включение. Пусть x W (; D ) и t = T (; D ). Имеем t.
Предположим, что t <. Учитывая определение величины, находим, что В силу u-стабильности функции T (·; D ) найдется такая последовательность {yk }, что tk = T (yk ; D ) < и yk x при k. Поскольку W (tk ; D ) = E(tk ) и yk W (tk ; D ), то yk E(tk ) E(). В силу замкнутости множества E() получаем включение x E().
Таким образом, равенство (1.30) доказано.
Из результатов пункта 2, равенства (1.30) и определения числа следует, что =. В силу (1.28) и (1.29) справедливы соотношения (1.27) для случая 2.
Пусть x \ M. Тогда при малых > 0 имеем равенство (x) = (x). В силу леммы 1.3 и равенства (1.27) получаем откуда следует утверждение теоремы.
Теорема доказана для случая T =.
Предположим теперь, что T = {a1 }, a1 (0, ). Доказательство, аналогичное случаю T =, примененное к функции (·) : D(a1 ) [0, ), дает равенство (x) = T (x; M), x D(a1 ). Далее, вводя обозначения аналогичное доказательство применяем к функции 1(·) : [0, ] и дифференциальной игре с терминальным множеством M1. Получаем равенство 1(x) = T (x; M1), x. Используя соотношение T (x; M1) = T (x; M) a1, находим, что (x) = T (x; M), x.
Аналогичные рассуждения проводятся для случая любого конечного множества T (0, ).
Глава 1.5 Теорема 2 о достаточных условиях В данном разделе будет доказана еще одна теорема о достаточных условиях совпадения разрывной функции с функцией цены игры. Условия теоремы предполагают полунепрерывность снизу и u-стабильность тестируемой функции, v-стабильность верхнего замыкания тестируемой функции, а также выполнение условия корректной сжимаемости замкнутых множеств уровня тестируемой функции. Проверка условия корректной сжимаемости замкнутого множества представляет собой самостоятельную задачу, решение которой в общем случае неочевидно. Поэтому в дальнейшем условия теоремы 2 на примерах не проверяются.
1.5.1 Корректно сжимаемые множества Пусть M Rn – замкнутое множество, int M – внутренность множества M. При условии int M = положим В дальнейшем понадобится следующее утверждение.
Лемма 1.4. Пусть M – замкнутое множество, int M =, x Rn и Тогда функция T (·; M) непрерывна в точке x.
Доказательство. Пусть = T (x; M). Выберем произвольную последовательность {xn}, сходящуюся к x. Требуется доказать, что Учитывая полунепрерывность снизу функции T (·; M), имеем Отсюда находим, что если =, то (1.32) выполнено. Кроме того, если x int M, то равенство (1.32) также справедливо.
Предположим, что < и x int M. Пусть > 0. В силу соотношения (1.31) найдется такое > 0, что T (x; M[]) +. Следовательно, Глава существует [6] множество W [0, + ] Rn, обладающее свойством u-стабильности относительно множества [0, + ] M[], и (0, x) W.
Если первый игрок использует стратегию экстремального прицеливания на множество W, а за второго игрока реализуется измеримое программное управление v(·) со значениями в множестве Q, то для возникающего конструктивного движения x(·) системы (1.1) из начальной точки xn справедлива [6, стр. 62] оценка Здесь L(X ) – постоянная Липшица по x функции f в некоторой ограниченной области X Rn, содержащей все рассматриваемые движения, dist (x(t), M[]) – расстояние от точки x(t) до множества M[]. Следовательно, если Учитывая (1.33), имеем Переходя к пределу при 0, получаем (1.32).
Определение 1.4. Множество M Rn называется корректно сжимаемым по отношению к динамике (1.1), если существует такое число > 0, что (C1) W (; M) = M и W (t; M) = int W (t; M), t [0, ];
(C2) для любой точки x int W (; M) \ M выполнено равенство Здесь множество W (t; M) определяется формулой (1.11).
Заметим, что если W (; M) = M, то в силу свойства u-стабильности функция T (·; M) должна принимать все значения из интервала (0, ). Отсюда получаем, что для корректно сжимаемого множества M величина > 0, удовлетворяющая условиям (C1) и (C2), может быть выбрана сколь угодно малой.
Приведем простейшие условия корректной сжимаемости множества M.
Глава Пусть множество M имеет гладкую границу M, M = int M и для любой точки x M выполнено неравенство где (x) – внешняя нормаль к множеству M в точке x M.
Покажем, что множество M корректно сжимаемо. Выберем > 0 и x W (; M). Из условия (1.34) и определения цены игры следует, что для любого > 0 первый игрок гарантирует попадание из точки x на множество int M на отрезке времени [0, T (x; M)+ ]. Следовательно, найдется такое = ( ) > 0, что Имеем Учитывая невозрастание значений T (x; M[]) при +0, получаем, что Таким образом, для любого > 0 условие (C2) из определения корректной сжимаемости множества выполнено.
Для любого x Rn \ 0W (; M) имеем В силу леммы 1.4 получаем непрерывность функции цены T (·; M) на Rn.
Заметим, что условия непрерывности функции цены при более слабых предположениях на множество M доказаны ранее [32].
Справедливость условия (С1) для любого > 0 следует из непрерывности функции T (·; M) и свойства u-стабильности.
Таким образом, множество M является корректно сжимаемым.
Более сложные достаточные условия корректной сжимаемости множеств связаны с разрывной функцией цены и в работе не рассматриваются.
Глава 1.5.2 Формулировка и доказательство теоремы Теорема 2. Пусть Rn и M – замкнутые множества, функция ( · ) : [0, ] полунепрерывна снизу и выполнены условия:
(A1) (x) = 0, x M;
(A2) (u-стабильность) для любых y0 \ M, v Q и > 0 существует такое решение y(·) : [0, ] дифференциального включения что либо выполнено неравенство либо y(t) M для некоторого t [0, ];
(A3) (v-стабильность) для любых y0 \ M, u P и > 0 существует такое решение y(·) : [0, ] Rn дифференциального включения что выполнено неравенство где (A4) множества уровня являются корректно сжимаемыми.
Тогда Полунепрерывную сверху функцию (·) : Rn [0, ], определяемую формулой (1.35), будем называть верхним замыканием функции (·) : [0, ].
Глава Замечание 1. Пусть для функции (·) выполнены условия (A1)–(A3) и условие корректной сжимаемости множеств D(t) нарушено лишь в некоторой точке a (0, supz (z)). Тогда теорему о достаточных условиях можно применить сначала к функции (·) : D(a) [0, ). Это даст равенство (x) = T (x; M), x D(a). Далее, вводя обозначения теорему можно применить к функции 1(·) : [0, ] и дифференциальной игре с терминальным множеством M1. Отсюда, используя соотношение T (x; M1) = T (x; M) a, получаем равенство (x) = T (x; M) для всех x.
Аналогичным образом теорема может быть применена в случае, когда корректная сжимаемость множеств уровня D(t) функции (·) нарушена в конечном числе точек из интервала (0, supz (z)).
Замечание 2. Из свойства u-стабильности функции цены и свойства v-стабильности верхнего замыкания функции цены следует, что условия (A1)–(A3) являются необходимыми для функции цены игры T (·; M) : Rn [0, ].
После доказательства теоремы будет приведен пример, показывающий, что в случае разрывной функции (·) условий (A1)–(A3) недостаточно для выполнения равенства (1.36), т.е. нельзя отказаться от условия (A4).
Докажем сначала несколько вспомогательных утверждений.
Лемма 1.5. Пусть замкнутое множество M Rn и полунепрерывная снизу функция ( · ) : [0, ] удовлетворяют условиям (A1) и (A2). Тогда T (x0; M) (x0), x0.
Доказательство. Если x0 M, то по условию (A1) имеем Если x0 \ M и (x0) =, то T (x0; M) = (x0).
Пусть x0 \ M, = (x0) <, 0 = T (x0; M). Покажем, что Рассмотрим множество Глава Из условия (A2) следует, что W – u-стабильный мост [6] в задаче приведения точки (t, x(t)) на множество [0, ] M. Так как (0, x0) W, то первый игрок обладает [6] позиционной стратегией, гарантирующей попадание на множество M на отрезке времени [0, ].
Из определения цены игры, для любого > 0 второй игрок обладает позиционной стратегией, гарантирующей уклонение от окрестности множества M на отрезке времени [0, 0 ] при любых действиях первого игрока. Отсюда имеем неравенство 0 < для любого > 0. Следовательно, 0.
Лемма 1.6. Пусть замкнутое множество M Rn и полунепрерывная снизу функция (·) : [0, ] удовлетворяют условиям (A1) и (A3). Кроме того, пусть int M =. Тогда (x0) T (x0; M [] ), x0 Rn, (0, M ].
Доказательство. Пусть x0 Rn и = (x0) <. Положим Из условия (A3) следует, что W – v-стабильное множество [6]. Так как (0, x0) W, то второй игрок обладает [6] позиционной стратегией, гарантирующей удержание системы в множестве W на отрезке времени [0, ].
Поскольку то второй игрок уклоняется от некоторой окрестности множества M [] на отрезке времени [0, ] при любых действиях первого игрока. Но первый игрок обладает позиционной стратегией, гарантирующей попадание на M [] на отрезке времени [0, T (x0; M [] )]. Таким образом, < T (x0; M [] ), Пусть x0 Rn и (x0) =. Положим Множество W замкнуто и (0, x0) W. Из условия (A3) следует, что W – v-стабильное множество. Поскольку (x) = 0 для любого x int M, то Следовательно, Глава Отсюда получаем, что для любого > 0 второй игрок обладает [6] позиционной стратегией, гарантирующей уклонение от окрестности множества M [] на отрезке времени [0, ]. Значит, T (x0; M [] ) = для всех Доказательство теоремы. Если M =, то заключение теоремы очевидно выполнено.
Пусть M =. Условие (A1) дает соотношение W (0; M) = M D(0).
Из условия (A2) u-стабильности следует отсутствие точек локального минимума функции (·) вне множества M, в которых она принимает конечные значения. Таким образом, получаем равенство W (0; M) = D(0).
Поскольку M = и D(0) = M, то supx (x) > 0.
Выберем (0, supx (x)). Пусть Покажем, что Для краткости положим D = D( ). Множество D и полунепрерывная снизу функция (·) удовлетворяют условиям (A1)–(A4), в которых обозначения M и (·) заменены на D и (·).
Пусть Заметим, что для любых [0, ) и x E() выполнено равенство (x) = T (x; D ). Действительно, пусть t = T (x; D ). Поскольку E() = W (; D ), имеем t [0, ] и x W (t; D ) = E(t). В силу леммы 1.5 выполнено неравенство t (x). С другой стороны, поскольку x E(t), то (x) t. Следовательно, (x) = T (x; D ).
Рассмотрим следующие случаи.
(x) = T (x; D ). Если x \ 0E(), то, учитывая (1.38), находим, что x 0W (; D ), и, следовательно, T (x; D ) =. В силу леммы 1. Глава получаем равенство (x) =. Таким образом, соотношение (1.37) доказано.
Случай 2: < и =. Если x E() для некоторого [0, ), то равенство (1.37) выполнено.
Покажем, что T (x; D ). Предположим, что t = T (x; D ) <. Тогда x W (t; D ) = E(t), что противоречит выбору точки x.
Учитывая лемму 1.5, имеем Таким образом, равенство (1.37) доказано.
Случай 3: [0, ). Введем обозначения Имеем supx (x) =.
Множество M и полунепрерывная снизу функция ( · ) : [0, ] удовлетворяют условиям (A1)–(A3), в которых обозначения M и ( · ) заменены на M и ( · ). Учитывая условие (A4) теоремы и равенство M = D( + ), где 0 < + < supx (x), находим, что множество M корректно сжимаемо. Следовательно, существует такое > 0, что выполнены условия (C1) и (С2). Число выберем так, что <.
Покажем, что Выберем t (0, ). Учитывая лемму 1.5, получаем Предположим, что Так как ( · ) – полунепрерывная снизу функция, то D(t) – замкнутое множество. Пусть x int W (t; M) \ D(t). Имеем T (x; M) (0, t]. Если x, то из соотношения x D(t) получаем неравенство t < (x). Таким образом, t < (x), где (·) – верхнее замыкание функции (·), определяемое Глава формулой (1.35). Если x, то (x) = > t. Следовательно, С другой стороны, на основании леммы 1.6 выполнено неравенство Из условия (C2) корректной сжимаемости множества M получаем, что Следовательно, (x) T (x; M), что противоречит (1.41). Таким образом, предположение (1.40) неверно, и свойство (1.39) доказано.
Учитывая соотношения получаем равенство W (t; D ) = E(t) для любого t [0, + ), что противоречит определению. Следовательно, случай [0, ) невозможен.
Таким образом, соотношение (1.37) доказано.
В силу леммы 1.3 и равенства (1.37) получаем откуда следует утверждение теоремы.
1.5.3 Пример Приведем пример, показывающий, что в случае разрывной функции (·) нельзя отказаться от условия (A4).
Пусть динамика системы имеет вид где Глава Множество M зададим с помощью системы неравенств Если управляющие воздействия игроков постоянны, т.е. u(t) = u, v(t) = v, то движение x(t) системы (1.42) представляет собой вращение по часовой стрелке вокруг точки xc, которая является нулем правой части системы (1.42). Точку xc находим из равенства Axc + u + v = 0.
Поскольку A1 = A, то Действие матрицы A на вектор представляет собой поворот вектора на угол /2 по часовой стрелке.
1. Пусть m1 = (2, 2)T, m2 = (2, 2)T, l – меньшая дуга окружности радиуса 2 2 с центром в начале координат, соединяющая точки m1 и m2.
Покажем, что Положим Обозначим через Zi, i = 1, 2, часть множества Zi, состоящую из точек, лежащих строго ниже дуги li. Пусть Z (Z + ) – часть множества Z, лежащая строго ниже (выше) дуги l. Множества Z ±, Z1, Z2 показаны на рис. 1.1.
Определим на множестве R2 \ (l M) стратегию V 0 второго игрока:
Глава Покажем, что стратегия V 0 не допускает попадание траектории системы на множество l M из любой начальной точки x0 R2 \ (l M).
Пусть x0 Z +. Тогда до выхода из множества Z + второй игрок применяет постоянное управление v = (0, 1)T. Если первый игрок использует управление u P, то из (1.43) получаем следующие условия на координаты центра вращения:
Следовательно, при любых действиях первого игрока, траектория системы (1.42) будет лежать не ниже дуги окружности радиуса x0 с центром в начале координат и при выходе из Z + пересечет прямую x1 = x2 выше точки m1. Аналогично, для множества Z имеем Поэтому траектория системы (1.42) будет лежать не выше дуги окружности радиуса x0 с центром в начале координат и при выходе из Z окажется на линии x1 = |x2| ниже точек m1 и m2.
Пусть x0 Z1 Z2. Тогда до выхода из множества Z1 Z2 второй игрок применяет постоянное управление v = (1, 0)T. Из (1.43) получаем условия на координаты центра вращения:
Следовательно, при выходе из Z1 траектория системы (1.42) пересекает прямую x2 = 0 строго выше (правее) дуги l1, а при выходе из Z2 – прямые x2 = x1 и x2 = 0 строго ниже (правее) дуги l2 при любых действиях первого игрока.
Глава Пусть x0 (Z1 Z2 ) \ M. Тогда до выхода из множества Z1 Z второй игрок применяет постоянное управление v = (1, 0)T. Из (1.43) получаем условия на координаты центра вращения:
Следовательно, при выходе из Z2 траектория системы пересекает прямую x2 = x1 выше точки m2, а при движении в Z1 не пересекает множество M и попадает либо на прямую x2 = 0 строго ниже (левее) дуги l1, либо на прямую x2 = x1 строго ниже точки m1. Таким образом, равенство (1.44) доказано.
2. Найдем значение T (x; M) цены игры для любого x l. Пусть в некоторый момент времени t система находится в точке z = z(t) l. Для любого v = v (t) Q определим такое u = u(t, v) P, что вектор скорости будет направлен по касательной к дуге l. Поскольку касательная к дуге l в точке z перпендикулярна вектору z, то Выражая отсюда величину u2 и учитывая ограничение u P, получаем Самое медленное движение по дуге l будет при выборе вторым игроком управления v = v (t) из условия минимизации величины по всем v Q. Имеем v (t) = (1, 0)T.
Пусть z(0) = m2 и в момент t игроки применяют управляющие воздействия v (t) и u (t) = u(t, v (t)). Тогда траектория z(t) системы (1.42) идет вдоль дуги l и описывается уравнениями Время попадания траектории z(t) в точку m1 конечно. Действительно, поскольку z2 (t) 2, t [2, 2], то z1 = z2 1 1 и момент, определяемый условием z( ) = m1, оценивается неравенством Глава Для любого x l обозначим через (x) момент времени t, удовлетворяющий равенству z(t) = x. Таким образом, (x) – это наибольшее время попадания из точки m2 в точку x при движении вдоль l и дискриминации второго игрока. Имеем (m1 ) =, (m2 ) = 0. Учитывая результат, полученный в разделе 1, заключаем, что множество является максимальным u-стабильным мостом в задаче сближения с множеством [0, ] M. Имеем ( (x), x) W, x l.
Используя стратегию экстремального прицеливания на множество W, первый игрок гарантирует из точки m2 достижение множества M на отрезке времени [0, ]. При оптимальном управлении второго игрока время достижения M равно. Для произвольной точки x0 l находим, что 3. Пусть (x) = 2T (x; M), x R2. Из свойства u-стабильности функции T (·; M) следует, что функция (·) также обладает свойством u-стабильности. Поскольку (x) = T (x; M), x R2, то функция (·) обладает свойством v-стабильности. Здесь T (·; M), (·) – верхние замыкания функций T (·; M), (·), определяемые формулой (1.35), где = R2.
Таким образом, для функции (·) : R2 [0, ] выполнены условия (A1)–(A3), но (x) = T (x; M), x l \ {m1 }.
Функция (·) не удовлетворяет условию (A4), так как условие (C1) нарушено для всех > 0. Кроме того, поскольку условие (A4) не выполнено и для функции цены T (·; M), то оно не является необходимым.
Глава Достаточные условия стабильности функции в терминах сингулярных точек Данная глава посвящена проверке свойств u- и v-стабильности функции, заданной на открытом множестве. Сформулированы инфинитезимальные критерии стабильности функции, доказанные в работах А.И.Субботина.
Такие критерии предполагают в каждой точке рассматриваемой области проверку неравенств для верхней или нижней производной по направлению для функции, получаемой после преобразования Кружкова. Приведены утверждения, упрощающие проверку указанных неравенств в некоторых частных случаях. Введены понятия регулярной и простейших сингулярных точек рассеивающего и экивокального типа рассматриваемой функции, аналогичные введенным ранее [1, 53] для функции цены игры.
В окрестности таких точек функция предполагается непрерывной. Сформулирована и доказана теорема о том, что для класса игр с автономной разделенной динамикой и ограничением на управление второго игрока в виде линейного отрезка в сингулярных точках указанных типов выполнены инфинитезимальные условия u- и v-стабильности.
2.1 Критерии стабильности полунепрерывной функции Пусть задана функция (·) : G [0, ], где G Rn – открытое множество. Применим к функции (·) преобразование Кружкова [7]:
Глава Имеем w(·) : G [0, 1], т.е. функция w(·) принимает только конечные значения.
Свойство u-стабильности полунепрерывной снизу функции (·) эквивалентно [23, с. 265] слабой инвариантности надграфика epi w функции w(·) относительно дифференциального включения Здесь многозначное отображение E+ определяется формулой где x G, z R, v Q. Это свойство характеризует функцию w(·) как верхнее минимаксное решение [23, с. 38] уравнения в частных производных первого порядка Воспользовавшись одним из эквивалентных критериев [23, с. 38] верхнего минимаксного решения, находим, что свойство u-стабильности функции (·) равносильно выполнению неравенства Здесь dw(x; ) – нижняя производная функции w(·) в точке x по направлению :
Аналогично можно показать, что свойство v-стабильности полунепрерывной сверху функции (·) равносильно выполнению неравенства Здесь – верхняя производная функции w(·) в точке x по направлению.
После несложных преобразований неравенств (2.3), (2.4) получаем следующее утверждение.
Глава Утверждение 2.1. Полунепрерывная снизу (сверху) функция где G Rn – открытое множество, будет u-стабильной (v-стабильной) тогда и только тогда, когда для любого x G выполнено неравенство Здесь функция w(·) определена формулой (2.1), Следующие утверждения упрощают проверку неравенств (2.5), (2.6) в некоторых частных случаях.
Утверждение 2.2. Пусть задана функция (·) : G [0, ], x G, (x) < и для любого v Q найдутся число > 0 и такая функция (·) : [0, ) G, что Тогда в точке x выполнены неравенства (2.5).
Доказательство. Пусть (t) = w((t)), t [0, ). Имеем Покажем, что dw(x; ) (+0), где = (+0). Выберем произвольную последовательность k 0. По формуле Тейлора имеем Следовательно, Глава Таким образом, Пусть k = max{k, k }. Имеем Следовательно, Учитывая (2.7), получаем, что откуда следуют неравенства (2.5).
Утверждение 2.3. Пусть задана функция : G [0, ], x G и для любого u P найдутся число > 0 и такая функция (·) : [0, ) G, что и для случая (x) < выполнены условия а для случая (x) = имеем (t) = ((t)) =, t [0, ). Тогда в точке x выполнены неравенства (2.6).
Доказательство. Пусть (t) = w((t)), t [0, ). В случае (x) < имеем В случае (x) = выполнено равенство (t) = 0, t (0, ). Следовательно, (+0) = 0 w(x) 1. Таким образом, в обоих случаях имеем Аналогично доказательству утверждения 2.2 можно показать, что откуда следуют неравенства (2.6).
Глава Утверждение 2.4. Пусть функция (·) : G [0, ] конечна и непрерывна в открытой окрестности точки x G. Тогда неравенства (2.5) [(2.6)] эквивалентны неравенствам Доказательство. Покажем, что Введем обозначения Используя формулу Тейлора, находим, что Имеем 1 [w(x + )w(x)] = 1 [e1 e0 ] = 1[e0 (1 0 )+o(1 0 )] = где (, ) 0 при 0. Отсюда получаем равенство (2.10).
В силу равенства (2.10) имеем откуда следует формула (2.8) [(2.9)].
Нетрудно проверяются следующие утверждения.
Утверждение 2.5. Пусть функция (·) : G [0, ] конечна и дифференцируема в окрестности точки x G. Тогда неравенства (2.5) [(2.6)] эквивалентны неравенству Глава Утверждение 2.6. Пусть функция (·) : G [0, ] равна в окрестности точки x G. Тогда в точке x выполнены неравенства (2.5) и (2.6).
Утверждение 2.7. Пусть функция (·) : G [0, ] конечна в окрестности точки x G и точка x – точка локального минимума функции (·).
Тогда в точке x выполнены неравенства (2.6).
Если отсутствует хорошее описание функции (·), то непосредственная проверка условий стабильности (2.8), (2.9) затруднительна. Однако оказывается, что в ряде случаев выполнение условий стабильности в точке полностью зависит от структуры функции (·) в окрестности этой точки.
В следующих разделах определим некоторые типы таких точек и докажем выполнение в них условий стабильности.
2.2 Простейшие сингулярные точки Дадим ряд определений, перенося на случай функции (·) : G R понятия, введенные ранее [53] для функции цены игры.
Определение 2.1. Область G0 G называется регулярной областью функции (·), если 2) H C 2(G0 Y ), где Y – некоторая окрестность множества Уравнение (2.13) называется уравнением Айзекса – Беллмана [1].
Если точка x принадлежит регулярной области, то в некоторой окрестности произвольно выбранного момента времени t существует и единственно решение (x(·), p(·)) характеристической системы уравнения (2.13), удовлетворяющее условиям Глава и такое, что p(t) = (x(t)) [9]. Из последнего равенства следует, что через любую точку регулярной области проходит единственное решение x(·) дифференциального уравнения x = Hp (x, (x)), которое будем называть характеристикой уравнения Айзекса – Беллмана (2.13). Таким образом, в любой регулярной области определено поле характеристик.
Условие седловой точки (1.4) обеспечивает существование функций U (x) и V (x) таких, что В регулярной области G0 имеем и функция x Hp (x, (x)) принадлежит классу C 1(G0 ). Следовательно, позиционные стратегии U (·), V (·), определенные в области G0, порождают движения, идущие вдоль характеристик. Функции U (·) и V (·) ограничены и, значит, имеют конечные частичные пределы для любого x G0.
Определение 2.2. Точка x G, для которой существует регулярная открытая область G0 G, содержащая x, называется регулярной точкой, иначе точка называется сингулярной.
Поверхности, состоящие из сингулярных точек, будем называть сингулярными поверхностями.
Определение 2.3. Cингулярную точку x G назовем простейшей, если существует окрестность G0 G точки x, такая, что 1) функция непрерывна на G0 ;
2) G0 = G+ G, где – гладкая гиперповерхность, G± – регулярные области;
3) функция (·) : G± Rn имеет непрерывное продолжение на гиперповерхность.
Пусть () – множество простейших сингулярных точек функции (·) : G R. Для точки x () будем использовать следующие обозначения: G± – регулярные области (из определения простейшей сингулярной точки), разделенные гиперповерхностью ; ± (·) – сужения функции (·) Глава на области G± ; U (·), V (·) – позиционные стратегии игроков, порождающие движения вдоль характеристик в областях G±. Кроме того, пусть где символы u±, v ± обозначают произвольные частичные пределы значений U (x), V (x) при x x, x G±.
В силу непрерывности функции H(·) имеем Отметим некоторые свойства простейших сингулярных точек.
В случае p+ = p функция (x) дифференцируема в точке x (но не в окрестности этой точки), причем H(x, (x)) = 1.
В случае p+ = p функции ± (x), определенные на G±, непрерывно продолжимы [53] на всю область G0 так, что ± C 1(G0 ). При этом гиперповерхность, разделяющая области G±, представима в виде Поскольку гиперповерхность можно рассматривать как поверхность уровня функции + (x) (x), то вектор p+ p ортогонален в точке x. Кроме того, в области G0 верно представление если вектор p+ p направлен из G в G+ (из G+ в G ). Следовательно, для любого вектора Rn существует производная (x) по направлению :
Кроме того [4], если вектор p+ p направлен из G в G+ (из G+ в G ).
2.3 Рассеивающие и экивокальные сингулярные точки В теории дифференциальных игр для функции цены T (·; M) известны [1, 53] различные типы сингулярных поверхностей, в точках которых Глава Рис. 2.1: Рассеивающая и экивокальная сингулярные точки оптимальные движения имеют те или иные особенности. Классификация основана на анализе поведения оптимальных траекторий в окрестности сингулярной поверхности и учете возможности особых оптимальных движений, идущих вдоль самой сингулярной поверхности.
Распространим понятия рассеивающей и экивокальной [1, 53] сингулярной поверхности на случай функции (·) : G R. Для этого сначала определим соответствующие типы простейших сингулярных точек и поясним геометрический смысл данных определений.
Определение 2.4. Точка x () называется рассеивающей, если Простейшая сингулярная точка x будет рассеивающей, eсли характеристики из смежных регулярных областей G+ и G покидают ее под ненулевым углом к разделяющей гиперповерхности (рис. 2.1, a).
Определение 2.5. Точка x () называется экивокальной (относительно второго игрока), если и, кроме того, существует вектор управления u(x) P такой, что Здесь f = f (x, u(x), v ) (f (x, u(x), v +)), когда вектор p+ p направлен Глава В экивокальную точку приходит характеристика из регулярной области G и покидает (под ненулевым углом к ) характеристика, определенная в регулярной области G+ ; кроме того, существует управление первого игрока, обеспечивающее равную 1 скорость движения вдоль поверхности в случае, когда второй игрок использует предельное управление, соответствующее области G (рис. 2.1, б).
Назовем гладкую гиперповерхность рассеивающей или экивокальной, если она образована соответственно рассеивающими и экивокальными точками.
2.4 Теорема 3 о достаточных условиях стабильности Теорема 3. Пусть f (x, u, v) = f1 (x, u) + f2(x, v) и множество f2(x, Q) := {f2(x, v) : v Q} – линейный отрезок в Rn. Если точка x () – рассеивающая или экивокальная, причем f2(x, v +) = f2 (x, v ), то в ней выполнены условия стабильности (2.8), (2.9).
Доказательство. Рассмотрим точку x () и предположим, что вектор p+ p направлен из G в G+.
Учитывая выражение (2.15) для производной по направлению в простейшей сингулярной точке и разделенную динамику системы (1.1), перепишем условия стабильности (2.8), (2.9) в точке x в следующем виде:
1) для любого вектора v Q существует такой вектор v co f1(x, P ), что p±, v + f2 (x, v) 1 (u-стабильность);
2) для любого вектора u P существует такой вектор u f2(x, Q), что (v-стабильность).
Пусть Так как f2(x, Q) – отрезок в Rn, то множество либо одноэлементно и содержит один из концов отрезка f2 (x, Q), либо совпадает со всем отрезком f2(x, Q). По определению имеем Глава Поскольку G± – регулярные области, то f2 (x, V (x)) C 1(G±). Следовательно, f2(x, V (x)) – один из концов отрезка f2 (x, Q) для любого x G±.
Введем обозначения Из определения векторов v ± и условия f2 = f2 получаем, что f2 – различные концы отрезка f2 (x, Q). Таким образом, можно записать представление Докажем выполнение условия 1) в точке x. Для произвольного v Q найдем такое число v [0, 1], что 1. Пусть x – рассеивающая точка. Положим Поскольку f1 f1(x, P ), то v co f1(x, P ). Имеем В силу определения рассеивающей точки получаем, что Следовательно, Так как f ± = f1 + f2, то из (2.16) и (2.17) получаем Для случая рассеивающей точки u-стабильность доказана.
2. Пусть x – экивокальная точка. Положим Здесь u(x) – особое управление первого игрока из определения экивокальной точки. Так как f1, f1 f1(x, P ), то v co f1 (x, P ). Кроме того, верно равенство, аналогичное (2.16) при замене f1 на f1.
Глава В силу определения экивокальной точки получаем, что Следовательно, Таким образом, верно неравенство (2.18). Для случая экивокальной точки u-стабильность доказана.
Выполнение условия 2) в точке x следует из неравенства если положить u = f2.
Заметим, что предположение о направлении вектора p+ p из G в G+ обеспечивает выполнение неравенств (2.9) в рассеивающей и экивокальной точках без тех ограничений на динамику системы (1.1), которые указаны в условии теоремы. Аналогично, если вектор p+ p направлен из G+ в G, то условия теоремы не используются при доказательстве неравенств (2.8) в рассеивающей и экивокальной точках.
Глава Управление материальной точкой на прямой при наличии помехи Рассматривается игровая задача быстродействия на плоскости, представляющая собой модификацию известной задачи “мальчик и крокодил” [19, 21]. Цель первого игрока привести движение как можно скорее в заданную точку на плоскости, второй игрок препятствует этому. Ранее исследования такой игры проводилось в работах [14, 15, 28]. Основываясь на результатах этих работ, на некотором ограниченном множестве описывается построение тестируемой функции, которая разрывна на области определения. Далее проводится проверка всех условий теоремы 1, что дает совпадение тестируемой функции с функцией цены игры. Таким образом, в данной главе результаты глав 1 и 2 применяются к примеру, решение которого известно.
3.1 Постановка задачи Рассмотрим модельный пример игровой задачи преследования на прямой. Уравнения движения и ограничения на управления преследователя и убегающего имеют вид Преследователь стремится за наименьшее время совместить точку yP с точкой yE так, чтобы в момент совмещения скорость yP точки yP равнялась наперед заданному числу a >.
Такая задача преследования формулируется как задача быстродейГлава ствия, если ввести замену В силу системы (3.1), имеем Первый игрок минимизирует время перевода фазовой точки x = (x1, x2) из заданного начального положения x0 на терминальное множество M = (0, a)T, a >, интересы второго противоположны.
Если = 0, то получаем задачу оптимального управления, решение которой известно (см., например, [50]). Кратко опишем его. На рис. 3. показаны траектории, составленные из частей парабол, образующих два семейства. Левое семейство соответствует управлению u = µ, правое – управлению u = µ. Время (x0) движения из точки x0 вдоль указанных кривых до попадания в точку M является временем оптимального быстродействия. Функция (·) разрывна на кривой, составленной из дуг B + и B и недифференцируема на дуге E параболы левого семейства.
Опишем построение траекторий при > 0, при помощи которых зададим функцию (·). Такие траектории исследованы ранее в [14, 15, 28].
1. Запишем уравнение кривой B, вдоль которой идет траектория системы (3.2) при v(t) = 0, u(t) = µ, приходящая в точку M (рис. 3.2, а).
Глава Имеем Найдем наихудшее для первого игрока движение по параболе B.
Пусть в некоторый момент времени t система (3.2) находится в точке z = z(t) B. Для любого v = v (t) [0, ] определим такое u = u(z, v) [µ, µ], что вектор скорости будет направлен по касательной к параболе B. Нормаль к кривой B в точке z имеет вид (µ, z2 )T.
Следовательно, значение u находим из уравнения Получаем, что Самое медленное движение по дуге B будет при выборе вторым игроком управления v (z) из условия минимизации по v модуля вектора скорости системы при управлениях uB (z) = u(z, v) и v, т.е. из условия Имеем v (z) =.
Пусть z(0) B и в момент t игроки применяют управляющие воздействия v (z) = и u(z) = u(z, v (z)) = µ(1 /z2). Тогда траектория z(t) идет вдоль дуги B и описывается уравнениями На траектории z(t), t 0, реализуется время 1(z(0)) самого медленного движения вдоль кривой B до точки M. Интегрируя второе уравнение в (3.4), находим, что Построим семейство траекторий системы при u(t) = µ, v(t) =, обрывающихся на линии B (первое семейство). Такое семейство описывается дифференциальными уравнениями и является семейством парабол. Обозначим через 1 замкнутое множество, которое покрывают траектории первого семейства (рис. 3.2, а).
Глава Глава Продолжим функцию 1(·) с кривой B на множество 1 следующим образом. Для точки x 1 \ B положим значение 1(x) равным времени движения из начальной точки x вдоль траектории первого семейства при u(t) = µ, v(t) = до пересечения с кривой B плюс значение функции 1 (·) в точке пересечения.
2. Найдем уравнение кривой B +, вдоль которой идет траектория системы при v(t) = 0, u(t) = µ, выходящая с оси Ox1 и приходящая в точку M. Имеем Парабола B + пересекается c осью x1 в точке x = (a2 /(2µ), 0) (рис. 3.2, б).
В нижней полуплоскости построим кривую E, удовлетворяющую дифференциальному уравнению и проходящую через точку x. Кривая E характеризуется тем, что из начальной точки x0 E время движения вдоль кривой E при u = uE (x) и v = 0 до точки x равно значению 1(x0) 1 (x). По терминологии Р.Айзекса кривая E является экивокальной [1].
Составная кривая B B +E разделяет на плоскости два открытых множества + и, где + ( ) – часть плоскости левее (правее) кривой B B +E. На множестве рассмотрим семейство траекторий системы (3.2) при u(t) = µ, v(t) = 0, обрывающихся на линии E (второе семейство, фиг. 3.1, б).
Определим функцию 2 (·) : (0, ) следующим образом. Для точки x положим значение 2(x) равным времени движения из начальной точки x вдоль траектории второго семейства при u(t) = µ, v(t) = до пересечения с кривой E плюс значение функции 1 (·) в точке пересечения.
Пусть Подчеркнем принципиальное отличие синтеза, соответствующего игровой задаче (рис. 3.2, б), от синтеза, соответствующего задаче управления (рис. 3.1). В игровом случае линия E, на которой переключается управление в нижней части, не является дугой параболы. Она описывается диффеГлава ренциальным уравнением, которое в явном виде не интегрируется. Кроме того, на верхней параболе B принятое значение функции (·) соответствует самому медленному движению системы по этой кривой при управлении v =, хотя сама парабола B является траекторией при u = µ, v = 0.
Кривая E пересекает ось x2 в некоторой точке y. Положим На рис. 3.2, в множество показано серой заливкой. Изображены линии уровня функции (·) на множестве. В множестве функция (·) : (0, ) разрывна на дуге B + int \ {x}.
Далее покажем, что на множестве функция (·) совпадает с функцией T (·; M) цены рассматриваемой дифференциальной игры быстродействия.
Для доказательства равенства воспользуемся теоремой 1.
3.2 Обоснование решения задачи Способ определения функции (·) на множествах ± реализует известный метод характеристик [9] построения дважды непрерывно дифференцируемого решения дифференциального уравнения в частных производных первого порядка с краевым условием (x) = 1(x) для x B при выборе знака “+” в уравнении (3.7), и для x E при выборе знака “”. Здесь При этом выполнены соотношения Гамильтониан (1.4) дифференциальной игры имеет вид Глава Учитывая неравенства (3.8), получаем, что По построению функция (·) : [0, ) полунепрерывна снизу и D(0) = M. Выполнение условия 4) теоремы очевидно.
Положим T = {(x)}. Проверим выполнение условий 1) – 3) для 1. Имеем Поскольку множество S(t) конечно, то выполнение условия 1) теоремы достаточно проверить для каждой из точек b S(t) отдельно. Возможны три случая:
Б. b = b+(t ), t (0, (x));
A. Пусть b = b(t ), t (0, ) \ T. Выберем число 0 > 0 так, что множество G = int B(b, 0) представимо в виде a) Имеем Определим функцию (·) : G [0, ] по формуле (1.17), в которой обозначения D(t) и G(t, 0) заменены на D(t ) и G. Проверим u-стабильность функции (·) на множестве G \ D(t ). Для этого достаточно проверить выполнение неравенств (2.5) в любой точке x G \ D(t).
Поскольку (x) =, x G, и H(x, (x)) = 1, x G+, то в силу утверждений 2.5, 2.6 неравенства (2.5) выполнены для всех точек Пусть x. Для любого v Q существуют число > 0 и функция (·) : [0, ) G, которая удовлетворяет уравнению Глава Рис. 3.3: Проверка условий теоремы для трех типов точек b S(t ) Глава и начальному условию (0) = x. Здесь управление u(·, v) определяется формулой (3.3). Имеем (t), t [0, ).
Пусть (t) = ((t)), t [0, ); z(·) – траектория самого медленного движения вдоль параболы B из начальной точки x. Имеем Следовательно, Учитывая утверждение 2.2, получаем u-стабильность функции (·) на множестве G \ D(t ).
б) Определим функции следующим образом. Сдвинем параболу B на величину 1/k вправо вдоль оси x1 и обозначим ее через Bk (рис. 3.3, а). Продолжим линию F (t ) гладкой линией l на множество G так, чтобы траектории первого семейства, продолженные выше линии B, пересекались с кривой l.
Линия F (t) имеет вертикальную касательную в точке b. В качестве l возьмем отрезок вертикальной прямой. Обозначим через l1 параболу первого семейства, проходящую через точку l Bk (рис. 3.3, а).
Положим k (x) = для точек x G, лежащих выше параболы Bk включительно; k (x) = 0 для точек x G, лежащих строго ниже кривой Bk и правее кривой F (t ) l включительно. Для точки x G, лежащей строго левее кривой F (t) l и не выше параболы l1, определим k (x) как время движения из начальной точки x вдоль параболы первого семейства при u = µ, v = до момента попадания на множество F (t ) l. Для точки x G, лежащей между кривыми Bk и l1, определим k (x) как время движения из начальной точки x вдоль параболы первого семейства при u = µ, v = до момента пересечения с кривой Bk плюс время самого медленного движения вдоль параболы Bk из точки пересечения до точки Функции k (·), k N, полунепрерывны сверху, равны нулю и непрерывны в точках множества D(t ) G. Нетрудно видеть, что выполнено предельное соотношение Глава Проверим v-стабильность функции k (·), k N, на множестве G\D(t ).
Для этого достаточно проверить выполнения неравенств (2.6) в любой точке x G \ D(t ).
Заметим, что по определению функции k (·) выполнено равенство H(x, k (x)) = 1 в точках G \ l1, таких, что k (x) (0, ). Следовательно, в силу утверждений 2.5, 2.6 неравенства (2.6) выполнены для точек x G \ (D(t) Bk l1 ).
Пусть x Bk. Для любого u P положим v = 0 и определим функцию (·) : [0, ) G как решение начальной задачи Имеем (t) Bk G, t [0, ). В силу утверждения 2.3 в точке x выполнены неравенства (2.6).
начальной задачи (3.12) не пересекает кривую l1. Пусть (t) = ((t)), t [0, ). Если u = µ, то (t) l1, t [0, ), и по определению функции (·) имеем (+0) = 1. Если u = [µ, µ), то точка (t), t (0, ), лежит ниже параболы l1. Следовательно, и (+0) 1. В силу утверждения 2.3 в точке x выполнены неравенства (2.6).
Б. Пусть b = b+(t ), t (0, (x)). Выберем число 0 > 0 так, что множество G = int B(b, 0) представимо в виде a) Соотношения (3.10) очевидны. На множестве G \ D(t ) проверим u-стабильность функции (·), определяемой аналогично случаю А. Для этого достаточно проверить выполнения неравенств (2.5) в любой точке x G \ D(t ).
Поскольку (x) =, x G, и H(x, (x)) = 1, x G+, то в силу утверждений 2.5, 2.6 неравенства (2.5) выполнены для всех точек x \ ( D(t )).
Глава Пусть x. Для любого v Q положим u = µ. Пусть (·) : [0, ) G – решение начальной задачи (3.12). Справедливо включение (t) G+, t [0, ). Используя обозначение (t) = ((t)), t [0, ), имеем = lim 1((t)), f ((t), u, v) lim H((t), 1((t))) = 1.
Учитывая утверждение 2.2, получаем u-стабильность функции (·) на множестве G \ D(t ).
б) Определим функции следующим образом.
Сдвинем параболу B + на величину 1/k вправо вдоль оси x1 и обозначим ее через Bk (рис. 3.3, б). Продолжим линию F (t ) гладкой линией l на множество G так, чтобы траектории первого семейства ниже линии B + приходили на кривую l.
Положим k (x) = для точек x G, лежащих не выше параболы Bk ;
k (x) = 0 для точек x G, лежащих строго выше параболы Bk и выше кривой F (t ) l включительно. Для остальных точек x G определим значение k (x) как время движения из начальной точки x вдоль параболы первого семейства при u = µ, v = до момента попадания на множество Функции k (·), k N, полунепрерывны сверху, равны нулю и непрерывны в точках множества D(t ) G. Нетрудно видеть, что выполнено предельное соотношение (3.11).
Проверим v-стабильность функции k (·), k N, на множестве G\D(t ).
Для этого достаточно проверить выполнения неравенств (2.6) в любой точке x G \ D(t ).
Заметим, что по определению функции k (·) выполнено равенство H(x, k (x)) = 1 в точках G, таких, что k (x) (0, ). Следовательно, в силу утверждений 2.5, 2.6 неравенства (2.6) выполнены для точек x G \ (D(t) Bk ).
Пусть x Bk. Для любого u P положим v = 0 и определим функцию (·) : [0, ) G как решение начальной задачи (3.12). Имеем Глава (t) Bk G, t [0, ). В силу утверждения 2.3 в точке x выполнены неравенства (2.6).
В. Пусть b = b+(t ), t ((x), ). Выберем число 0 > 0 так, что для множества G = int B(b, 0) выполнено включение G \ D(t ) (рис. 3.3, в). Положим G =.
a) Соотношения (3.10) очевидны. Пусть функция (·) определяется аналогично случаю A. Поскольку то в силу утверждения 2.5 неравенства (2.5) выполнены для всех x G \ D(t ). Следовательно, функция (·) u-стабильна на множестве G \ D(t ).
б) Определим функции следующим образом. Сдвинем параболу B + на величину 1/k вправо вдоль оси x1 и обозначим ее через Bk (рис. 3.3, в).
Положим k (x) = (x) для точек x G, лежащиx правее параболы Bk включительно, k (x) = 0 для всех остальных точек x G.
Функции k (·), k N, полунепрерывны сверху, равны нулю и непрерывны в точках множества D(t ) G. Нетрудно видеть, что выполнено предельное соотношение (3.11).
Покажем выполнение неравенств (2.6) для функции k (·), k N, в любой точке множества G \ D(t ).
В точке x G \ (D(t ) Bk ) неравенства (2.6) выполнены в силу утверждений 2.5, 2.7 и уравнения (3.13).
Пусть x G Bk. Для любого u P положим v = 0 и определим функцию (·) : [0, ) G как решение начальной задачи (3.12).
Поскольку траектория (·) не переходит в область выше кривой Bk, имеем k ((t)) = ((t)), t [0, ). Используя обозначение (t) = ((t)), t [0, ), находим, что Глава Рис. 3.4: Проверка условий теоремы для множеств F (t ) и B(t ) Учитывая утверждение 2.3, получаем, что в точке x выполнены неравенства (2.6). Таким образом, функция k (·) v-стабильна на множестве G \ D(t ).
2. Для любого > 0 найдется такое > 0, что выполнено включение Для t (0, (x)) окрестность GF (t,, ) показана на рис. 3.4, a.
В силу равенств (3.9) точки множества ± являются регулярными точками функции (·), а точки кривой E – простейшими сингулярными точками экивокального типа. В силу теоремы 3 функция (·) обладает свойствами u- и v-стабильности на множестве GF (t,, ).
3. Для любого > 0 выберем такое > 0, что выполнены соотношения Для t (0, (x)) окрестность GB (t,, ) показана на рис. 3.4, б.
Определим функции следующим образом. Сдвинем составную кривую B B + вправо вдоль оси x1 на величину 1/k, обозначим ее через Bk (рис. 3.4, б). Положим k (x) = 0 в точках x GB (t,, ), расположенных строго левее кривой Bk, и k (x) = во всех остальных точках множества GB (t,, ).
Глава Покажем v-стабильность функции k (·). В силу утверждений 2.6, 2. неравенства (2.6) выполнены в точках x GB (t,, )\(D(t)Bk ). Пусть x Bk GB (t,, ). Для любого u P положим v = 0 и определим функцию (·) : [0, ) G как решение начальной задачи (3.12).
Поскольку траектория (·) не переходит в область левее кривой Bk, имеем k ((t)) =, t [0, ). В силу утверждения 2.3 в точке x выполнены неравенства (2.6). Следовательно, функция k (·) v-стабильна на множестве GB (t,, ) \ D(t).
Предельное соотношение очевидно.
Таким образом, все условия теоремы 1 выполнены и равенство (3.6) доказано.
Заметим, что аналогично равенство (3.6) можно доказать для множества, более широкого, чем. А именно, существует такое значение t ((), ), что линия F (t) представляет собой замкнутую кривую. Раy венство (3.6) будет справедливо для всех точек x Rn, таких, что (x) t.
Глава Игровая задача о брахистохроне Игровая задача о брахистохроне (кривой наискорейшего спуска) рассматривалась P. Айзексом [1] как обобщение классической задачи вариационного исчисления [10]. Решение, предложенное P. Айзексом, было уточнено и дополнено [11, 29]. Исследуемая в данной работе игровая задача отличается от задачи в постановке P. Айзекса видом терминального множества и вектограммой второго игрока.
В данной главе, применяя метод Айзекса обработки полей классических характеристик, в верхней полуплоскости R+ определяем тестируемую функцию (·) : R+ [0, ]. Функция строится при различных значениях высоты терминального множества. Обоснование решения задачи усложняется тем, что правая часть динамики системы не удовлетворяет классическим условиям существования цены игры, а именно, локальному условию Липшица по фазовой переменной. Поэтому сначала дается эквивалентное определение цены игры в терминах пучков ломаных Эйлера.
Далее, теорема 1 применяется к вспомогательной дифференциальной игре и функции (·), которая конструируется на основе функции (·). Этот результат используется для доказательства совпадения тестируемой функции (·) с функцией цены исходной дифференциальной игры в смысле эквивалентного определения. При проверке выполнения условий теоремы применяется теорема 3.
4.1 Постановка задачи Рассмотрим дифференциальную игру быстродействия Глава где R+ – верхняя полуплоскость.
Первый (второй) игрок минимизирует (максимизирует) время достижения терминального множества M = [d, 0] [0, h]. Здесь d, h > 0. От величины w > 0 зависят возможности второго игрока.
Сначала, используя метод Айзекса, определим функцию Затем, применяя теоремы 1 и 3, покажем, что функция (·) будет функцией цены в игровой задаче о брахистохроне.
Так как правая часть системы (4.1) не зависит от x1, игра симметрична относительно вертикальной прямой x1 = d/2. Далее все построения будем проводить для множества и использовать обозначения 4.2 Характеристическая система для уравнения Айзекса – Беллмана Характеристическая система. Для рассматриваемой задачи экстремальные управления u0 и v 0, доставляющие минимум и максимум в (1.4), при условии p = 0 определяются формулами Следовательно, гамильтониан (1.4) имеет вид Рассмотрим краевую задачу для уравнения Айзекса–Беллмана:
Глава При дополнительных условиях гладкости на функции (·) и H(·) для задачи (4.3), (4.4) применим метод характеристик. Он сводится к интегрированию характеристической системы (2.14).
При условиях p2 = 0, x2 > 0 запишем характеристическую систему для уравнения (4.3) (в обратном времени):
Здесь Заметим, что функция H(·) является первым интегралом системы (4.5), а именно, Интегрирование характеристической системы. Проинтегрируем систему (4.5). Так как p1 = 0, то в дальнейшем символом p1 будем обозначать постоянную, определяемую из начальных условий системы (4.5).
Рассмотрим два случая: p1 = 0 и p1 = 0.
Пусть p1 = 0. Первые два уравнения системы (4.5) принимают вид При условии x2 = w2 находим первые интегралы характеристической системы:
Здесь C и D – некоторые постоянные. Первый интеграл (4.6) при p1 = принимает вид Для случая p1 = 0 характеристическая система проинтегрирована. Характеристики являются вертикальными прямыми.
Пусть теперь p1 = 0. Первый интеграл (4.6) принимает вид и задает зависимость между значениями x2 и p2:
Глава Функция P() монотонно возрастает на отрезке [0, wp2] и На интервале [wp2, ) функция P(·) монотонно убывает. Кроме того, P() +w при, то есть x2 = wp2 – горизонтальная асимптота функции P(·). Таким образом, на интервалах [ 0, wp2 ] и [ wp2, ) функция P(·) является обратимой. Зависимость между |p2 | и x2, задаваемая функцией P(·), показана на рис. 4.1 для значений p1 = 0.3 и w = 2.
Перепишем (4.10) в виде В случае x2 = w2 имеем Пусть теперь x2 = w2. Положим Если R(x2, p1) = 0 (т.е. x2 = w2 + 1/p2), то уравнение (4.11) имеет единственный корень |p2 | = wp1. Если R(x2, p1) > 0 (т.е. x2 < w2 + 1/p2), то без учета положительности величины |p2 | уравнение (4.11) имеет два решения Глава Заметим, что правая часть равенства (4.12) является пределом функции + (x2) в точке x2 = w2. Поэтому в дальнейшем вместо отдельного рассмотрения случая x2 = w2 будем считать функцию + (x2) доопределенной по непрерывности в точке x2 = w2. C учетом положительности величины |p2 | функция + (x2) определена на отрезке [1/p2, w2 + 1/p2], а функция (x2) – на интервале (w, w + 1/p1]. Имеем (x2) + при x2 w2 + 0.
Итак, при |p2| ( 0, wp2 ] обратной к функции P(·) является функция + (·); при |p2| [ wp1, ) обратной к функции P(·) будет функция (·).
Пусть Тогда Из уравнения (4.9) находим, что Подставив в последнее равенство выражение для |p2 |, получим С учетом (4.14) и (4.16) первые два уравнения системы (4.5) принимают вид Если = 1, то правая часть формул (4.17) определена и непрерывна при x2 (w2, w2 + 1/p2]. Если = 1, то правую часть формул (4.17) считаем доопределенной по непрерывности при x2 = w2, то есть она определена и непрерывна при x2 [1/p2, w2 + 1/p2].
Фазовые траектории системы (4.17) являются решениями дифференциального уравнения где Глава Интегрируя (4.18) при постоянном значении, находим первый интеграл системы (4.17), а значит и системы (4.5):
Здесь µi = sign pi, i = 1, 2, C – некоторая постоянная.
Подставляя выражение для x2 по формуле (4.10) в последнее уравнение характеристической системы (4.5), получим Интегрирование уравнения (4.21) определяет еще один первый интеграл системы (4.5):
Здесь D – некоторая постоянная.
Значения µ1, µ2, определяются исходя из заданной начальной точки x0. Равенства (4.9), (4.20), (4.22) представляют собой алгебраическую систему трех уравнений относительно трех неизвестных p2, s и. Она неявно определяет величину – время движения вдоль характеристики от начальной точки x0 до точки x – как функцию от x.
Построение характеристики. Покажем, как с помощью найденных первых интегралов строится характеристика при заданных начальных условиях Если 1 = 0, то ограничимся случаем µ2 = sign 2 > 0 и 2 > w2, который понадобится в дальнейшем. В этом случае x1 = 0, x2 > 0 и характеристикой будет луч {x R2 : x1 = 1, x2 2 }.
Более сложным является случай 1 = 0. Пусть 1 > 0 (т.е. µ1 = 1).
Исходя из начального условия, имеем p1 = 1 Построение характеристики будет основано на уравнении (4.20).
Часть характеристики, выходящая из точки, явно задается равенством Глава Рис. 4.2: Вид характеристики при µ2 = 1, 0 = 1 (а) и µ2 = 1, 0 = 1 (б) где Пусть сначала µ2 = 1. Рассмотрим случай 0 = 1. Из соотношения (4.10) получаем 2 (1/p2, (p1)). Характеристика выходит из точки в положительном направлении оси x2 до момента касания с прямой x2 = (p1), на которой (p1, p2) = 0. Точку касания обозначим через l = (l1, l2), где l2 = (p1 ).
Поскольку p2 < 0, величина p2 монотонно убывает и p1 = 1 вдоль характеристики, то величина wp2 |p2 | монотонно убывает. Следовательно, в точке l происходит смена значения c +1 на 1. Вторая часть характеристики выходит из точки l в отрицательном направлении оси x2 и задается равенством где Поскольку |p2| при, то x2 w2 +0 при после пересечения точки l. Следовательно, характеристика приближается к прямой x2 = w2 неограниченно долго.
Вид характеристики при µ2 = 1, 0 = 1 показан на рис. 4.2, a.
В случае 0 = 1 характеристика выходит из точки в отрицательном направлении оси x2 и ее поведение аналогично поведению характеристики в случае 0 = 1 после прохождения точки l.
Пусть теперь µ2 = 1. Рассмотрим случай 0 = 1. Из соотношения (4.10) получаем 2 (w2, (p1)). Характеристика выходит из точки в положительном направлении оси x2 до момента касания с прямой Глава x2 = (p1 ), на которой (p) = 0. Точку касания вновь обозначим через l = (l1, l2).
Поскольку p2 > 0, величина p2 монотонно убывает и p1 = 1 вдоль характеристики, то величина wp2 |p2| монотонно возрастает. Следовательно, в точке l происходит смена значения c 1 на +1. Вторая часть характеристики выходит из точки l в отрицательном направлении оси x и задается равенством (4.23) при x2 [l2, 1/p2) и = 1.
При µ2 > 0 и x2 1/p2 имеем p2 +0. Характеристика попадает на прямую x2 = 1/p1 за конечное время.
Вид характеристики при µ2 = 1, 0 = 1 показан на рис. 4.2, б.
В случае 0 = 1 характеристика выходит из точки в отрицательном направлении оси x2 и ее поведение аналогично поведению характеристики в случае 0 = 1 после прохождения точки l.
Случай 1 < 0 рассматривается аналогично.
4.3 Первичные семейства характеристик Построим первичные характеристики, выходящие с допустимой зоны A(M) [1] терминального множества M.
Допустимая зона терминального множества. Дадим сначала определение внешней нормали [4] к замкнутому множеству M Rn и определение допустимой зоны A(M).
Вектор (z) R2, |(z)| = 1, называется внешней нормалью к замкнутому множеству M в точке z M, если существует такое > 0, что Обозначим через N (z; M) множество внешних нормалей к множеству M в точке z M.
«