Динамические игры преследования на поверхностях

Актуальность темы

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

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

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

В работах Р. Айзекса [46]-[49], [1] был предложен метод исследования игровых задач и рассмотрено большое число содержательных примеров. Однако строгой математической постановки дифференциальной игры при этом не было. В дальнейшем были разработаны различные варианты формализации дифференциальных игр, среди которых был подход W.H. Fleming [40], основанный на аппроксимации дифференциальной игры многошаговыми играми, подход R.J. Elliott и N.J. Kalton [39], использующий понятие неупреждающих стратегий. В данной диссертации мы придерживаемся позиционной формализации дифференциальных игр, введенной в работах отечественных ученых Н. Н. Красовского и А. И. Субботина [10]. В данном случае подход к решению дифференциальной игры заключается в поиске функции цены, которая каждой точке пространства состояний системы ставит в соответствие оптимальный гарантированный результат в игре, начинающейся из этой точки. Зная функцию цены, можно построить стратегии оптимального управления по принципу обратной связи. Цена позиционной дифференциальной игры для заданной начальной точки совпадает с ценой в смысле W.H. Fleming или с ценой в классе неупреждающих стратегий в случаях, когда обе величины существуют. Также известны несколько иные подходы к формализации дифференциальных игр, разработанные J1.C. Понтрягиным, Б. Н. Пшеничным и представителями созданных ими научных школ. Отметим, что довольно подробно базисная постановка задач обсуждается в монографии A. Friedman [42] но дифференциальным играм.

Была доказана [10] следующая теорема существования функции цены при достаточно общих условиях. Пусть динамика управляемой системы записывается в виде r (t) = f (x (J), «(/), u (t)), t > 0, ж (0) =х0еМ где x (t) € Q С К» — фазовый вектор в момент времени t, М — часть границы множества О, на которой заданы краевые условия, u (t) G U и v (t) € V — управления минимизирующего и максимизирующего игроковU и V — компакты в конечномерных пространствах. Пусть далее функция / непрерывна по совокупности переменных, удовлетворяет условию подлинейного роста и локальному условию Липшица, но переменной х. Кроме того, i (x, p) = minmax (p, f (x, u, v)) = maxmin (p, f (x, u, v)). ueU veV veV ueU.

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

Кроме того, были сформулированы и доказаны аналогичные теоремы существования и единственности обобщенного решения уравнения Гамильтона-Якоби на гладких многообразиях [11].

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

ОТ Г.

П (х, р) = -1, xett CR" = (!).

V{x) = 0, G M С дП.

В монографии [1] было показано, что классическое решение краевой задачи (1) (если оно существует) совпадает с функцией цены V (x) дифференциальной игры быстродействия. Таким образом, при некоторых дополнительных условиях гладкости для нахождения дифференцируемой функции цены может быть использован классический метод характеристик [31, 12].

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

При развитии теории дифференциальных игр необходимо возникают нелинейные уравнения в частных производных первого порядка, в которые могут входить значения самой функции V (x). Иными словами, уравнения Беллмана-Айзекса имеют вид dV.

F{x, Vyp) = 0, жбПсГ ¦)> (2) с краевыми условиями.

V{x) = W (x), хеМсдП.

Здесь под функцией V — V (x) понимается неизвестная функция п переменных х — (xi,., хп), F — скалярная функция, называемая гамильтонианом.

В случае, когда функция V{x) и гамильтониан F (x, V, p) дважды дифференцируемы по своим аргументам, решение задачи (2) локально сводится к интегрированию системы классических (регулярных) характеристик x = Fpt V = {V, FP) p = -Fx-pFv. (3).

Однако во многих задачах теории оптимального управления и дифференциальных игр одна или обе функции V (x), F (x, V, p) являются негладкими. В этом случае решение задачи (2) (и (1) в частности) понимается в обобщенном смысле.

Одним из наиболее известных подходов к определению обобщенного решения является теория вязкостных решений, разработанная в последние десятилетия M.G. Crandall, Р.Н. Lions [38], [54], а также C.L. Evans [29]. В работах М. Bardi, I. Capuzzo-Dolcetta [34], S. Bottacin, M. Falcone [33], P. Soravia [35] было введено и исследовано понятие разрывного е-решения (envelope solution) краевой задачи (2), определение которого опирается на понятие вязкостного решения.

Известен также несколько иной способ обоснования решения с помощью теории минимаксных решений. разработанной А. И. Субботиным [25]. Было доказано совпадение е-решения с минимаксным решением и разработаны численные схемы построения решения краевой задачи (2) для обоих подходов. Случай совпадения разрывной функции с функцией цены для игры быстродействия (1) исследовался в работах JI.B. Камневой [6, 7].

Приведем определение вязкостного решения в терминах тестовых функций, которое было введено M.G. Crandall, P.L. Lions [38, 54] и C.L. Evans [29]. Обобщенным вязкостным решением краевой задачи (2) с терминальными граничными условиями называется непрерывная функция V (x), удовлетворяющая граничному условию на М:

V (x) = W (x), хеМ. и являющаяся одновременно верхним и нижним вязкостным решением.

В свою очередь верхнее решение определяется так. Для всякой пробной функции <�р (х), гладкой в окрестности точки .г'о и такой, что минимум.

Жо: min (V (a-) — ^(-0) X достигается в точке хо, верхнее решение удовлетворяет неравенству.

F{xо, У (жо), V<p{xо)) >0, х0 е П U М. (4).

Для нижнего решения должно выполняться неравенство.

F{xо, КЫ, Чфо)) <0, € П (5) для всякой гладкой пробной функции, такой что максимум xq: тах (У (гг) — ip{x)) х достигается в точке Xq .

Заметим, что условие (5), определяющее нижнее решение, выполнено в открытой области О, в то время как условие (4) для верхнего решения выполняется вплоть до границы <9П на ее подмножестве М. Подобное различие было впервые подчеркнуто в работе [41] для случая уравнения Гамильтона-Якоби, когда левая часть уравнения имеет специальный вид:

F (x, V, p) = рп + Н (х, V, p), р = (pi,., pni).

Выделенная переменная хп обычно имеет смысл времени.

Если рассматривается краевая задача (2) с начальными граничными условиями, то неравенства (4) и (5) берутся с обратным знаком. Выбор того, какого именно типа заданы граничные условия на dQ, терминального или начального, зависит от постановки рассматриваемой задачи. В теории оптимального управления и теории дифференциальных игры граничные условия, как правило, имеют терминальный тип, а в задачах физики они — начального типа. При этом вязкостное решение для начальной и терминальной краевой задачи (2) могут быть существенно различными. Данный вопрос исследуется в работах автора, А. А. Меликяна и Н. В. Овакимян [70, 66] и нашел отражение на страницах данной диссертации.

Кроме того заметим, что если построение гладкой тестовой функции <�р (х) с достижением максимума или минимума в точке xq невозможно, то проверка соответствующего условия на вязкостное решение (4) или (5) не требуется, и оно считается выполненным автоматически. Легко также проверить, что классическое (т.е. гладкое) решение задачи (2) (если оно существует) удовлетворяет определению вязкостного решения.

Для описания сингулярных решений задачи (2) введем понятие регулярной и сингулярной точки вязкостного решения. Будем говорить, что точка ж о 6 R7lQ называется регулярной точкой вязкостного решения краевой задачи (2), если существует открытая окрестность D С Шп. точки ж о. такая что функция V (.—) дважды дифференцируема в окрестности D, V (x) 6 C2(D)J и гамильтониан F (x, V, р) также дважды дифференцируем в любой точке расширенного пространства (x, V, p) G N, F <Е C2(N), где iV С R2″ +1 — открытая окрестность точки (ж0Л/(гсо), Ро), где ро = dV (xo)/dx, из пространства Ш2п+1 векторов (x, V, p).

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

Рассмотрим следующую ситуацию. Пусть V{x) является непрерывным вязкостным решением краевой задачи (2) в некоторой открытой окрестности D С 1″ точки х0. Кроме того, пусть имеется гладкая гиперповерхность Г такая, что xq? Г С D, а решение задачи V (x) 6 C (D) представимо в виде V (x) — min[Vo (a-), где.

Vi{x)? С2(A), i — 0,1, -Do и D — открытые полуокрестности точки xq, D = Do + Г + D. Тогда точка Xq называется сингулярной точкой простейшего типа.

Было доказано [56], что для проверки вязкостного условия (5) в случае сингулярности простейшего типа достаточно рассмотреть одиоиараметрическое семейство тестовых функций: <�р (х) = АУЦж) + (1 — A) Vo (z), Л 6 [0,1], и исследовать поведение гамильтониана F (xо, V (xo), Vcp (xo)) как функции параметра Л на отрезке [0,1]. Было получено обобщение данного утверждения на случай сингулярностей более общего вида.

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

Для его иллюстрации рассмотрим построение сингулярной поверхности (или кривой в случае п = 2), заданной многообразием Г С Q. Сингулярные характеристики возникают, когда в исходной дифференциальной игре появляется естественным образом гиперповерхность W3 коразмерности 3 в расширенном пространстве с точками (x, V, p), где ж G ln, F Е М и р G М7 которая заключает в себе особенности задачи [15]. Она задается с помощью условий.

И/3: Fi (x, V, p) = 0, F0(x, V, p) = 0, F-i (x, V, p) = 0, где выбор функции определяется типом сингулярной поверхности, свойствами вязкостного решения или условиями подхода/выхода регулярных характеристик с многообразия Г. Одной из функций F{ может быть правая часть исходного уравнения F (x, V, p) = 0. Для записи системы уравнений сингулярных характеристик, подобной (3), требуется полное определение W3.

Необходимые условия существования сингулярной поверхности экивокального типа имеют вид.

F0 = F (x, V, p) = 0, F^x, V) = V — S (x) = 0,.

F-1 = {F1F} = (Fp, p-q) = 0 (q = dS/dx).

Последнее равенство описывает условие касания выходящей характеристики к экивокальной поверхности Г, а функция S (x) Е С2 задает известное гладкое решение по одну из ее сторон. Фигурные скобки {••} обозначают скобки Якоби (Пуассона), определяемые следующим образом.

GH} = (Gx + pGv, Нр) — (Нх + pHv, Gp). Тогда система сингулярных характеристик записывается в виде = FP, V=(p, Fp), р = —Fx — PFV — (P ~ .

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

Одной из первых работ, посвященных исследованию дифференциальных игр с простым движением, можно считать работу Н. Steinhaus [62], опубликованную в 1925 г. Далее, с начала 50-х годов появляются работы Р. Апзекса [1], А. С. Безиковича, Н. Н. Петрова [18], J1.A. Петросяна [19], Б. Н. Пшеничного [22], Ф. Л. Черноусько [27], J.O. Flynn [43], A. Zieba [63], проводящие более глубокое исследование. В ходе их решения были получены интересные факты, относящиеся к геометрии. Каждая из приведенных работ дала предпосылки к появлению целого цикла работ по дифференциальным играм с простым движением. Здесь можно упомянуть работы H.JI. Григоренко [4], А. А. Меликяна, М. С. Никольского [17], Г. К. Пожарицкого, Б. Б. Рихсиева [24], И. И. Шевченко и многих других.

В монографии Р. Айзекса [1] была рассмотрена игра сближеиия/пре-следования двух катеров в море при наличии кругового острова между ними. Ее полное решение и обобщение на случай препятствия произвольной формы было получено позже Г. К. Пожарицким [20] и А. А. Меликяном совместно с J1.C. Вишневецким [2]. Это дало толчок для исследования дифференциальных игр на двумерных многообразиях более сложной формы. В 90-х годах были исследованы свойства дифференциальных игр простого преследования па неограниченных поверхностях и получено полное решение для случая дифференциальной игры простого преследования на конусе [14, 45, 58], были изучены особенности дифференциальных игр преследования на плоских двусторонних фигурах [13]. Обзор по данной проблематике был проведен в работе [59]. Одним из вкладов автора диссертации является изучение свойств дифференциальных игр простого преследования на ограниченных поверхностях, таких как эллипсоиды вращения, двусторонние плоские эллипсы. Для некоторых значений параметров задачи (например, отношение скоростей игроков или эксцентриситет рассматриваемого эллипса) преследование, но кратчайшей геодезической линии, соединяющей игроков, является оптимальным во всем фазовом пространстве. При других значениях параметров задачи — это не так, и преследование по особым траекториям движения должно быть рассмотрено. Поэтому переход от первого случая ко второму, когда особые (сингулярные) траектории появляются — вопрос зарождения бифуркации, как перестройки картины оптимального синтеза, является одной из целей настоящего исследования.

Стоит отметить также работы представителей научной школы Н. Ю. Сатимова по схожей тематике. Были рассмотрены задачи простого преследования на евклидовой плоскости с препятствиями [32, 50, 53], на сфере [51], игровые задачи простого преследования на двумерных многообразиях с несколькими преследователями [61, 52].

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

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

Основные положения работы. На защиту выносятся следующие результаты.

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

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

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

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

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

Апробация и публикации. Результаты диссертации докладывались автором на научной конференции МФТИ, ноябрь, 2004 г.- на весенней математической школе «Понтрягинские чтения», посвященной 100-летию академика С. М. Николького, май, 2005 г.- на международном семинаре «Теория управления и теория обобщенных уравнений Гамильтона-Якоби», посвященном 60-летию академика А. И. Субботина, в Екатеринбурге, июнь, 2005 г.- на американской конференции по теории управления (АСС) в Портленде, США, июнь, 2005 гна 12-м международном симпозиуме, но динамическим играм и их приложениям, София-Антиполпс, Франция, в июле, 2006 г.- на международной конференции «Управление динамическими системами» в Институте проблем механики им. А. Ю. Ишлинского РАН, январь, 2009 г. Был сделан доклад на семинаре кафедры высшей математики МФТИ под руководством проф. Е. С. Половинкина в апреле 2009 г. По теме диссертации опубликовано 11 работ, из них 2 публикации в реферируемых журналах из перечня ВАК, одна публикация в рецензируемом ежегодном сборнике трудов международного сообщества по динамическим играм (ISDG).

Структура и объем диссертации

Диссертация состоит из введения и четырех глав. Нумерация формул, теорем, замечаний и т. д. — двойная и раздельная по главам. Первая цифра означает номер главы, втораяформулы или утверждения. Объем диссертации — 109 страниц. Список цитированной литературы включает [74] наименования.

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

2. Втиневецкий JI.C., Меликян А. А. Оптимальное преследование на плоскости при наличии препятствия // ПММ 1982. — Т. 46, вып. 4. с. 613−620.

3. Гельфанд И. М., Фомин С. В. Вариационное исчисление. М., Физматгиз, 1961.

4. Григоренко H.JI. Дифференциальные игры преследования несколькими объектами. М.: Изд-во МГУ, 1983. — 77 с.

5. Демьянов В. Ф. Минимакс: дифференцируемость по направлениям. Л.: Изд-во ЛГУ, 1974.

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

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

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

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

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

11. Кривоносое А. Т. Обобщение решения уравнения Гамильтона-Якоби на гладком многообразии // Труды Института математики и механики УрО РАН. 1992. — Т. 2. — С. 156−165.

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

13. Меликян А. А. Первичные стратегии простого преследования в дифференциальных играх па двусторонних плоских фигурах // ПММ. Т. 68, вып. 4. — С. 611−622.

14. Меликян А. А., Овакимян Н. В. Игровая задача простого преследования на двумерном конусе // ПММ 1991. — Т. 55, вып. 5. — С. 741−751.

15. Меликян А. А., Овсеевич А. И. Гамильтоновы системы с заданным инвариантным многообразием и некоторые их приложения // ПММ- 1984. Т. 48, вып. 2. — С. 205−213.

16. Мищенко А. С., Фоменко А. Т. Курс дифференциальной геометрии и топологии. М., Факториал, 2000.

17. Никольский М. С. О квазилинейной задаче убегания // Доклады АН СССР 1975. — Т. 221, № 3. — С. 539−542.

18. Петров Н. Н. Одна оценка в дифференциальной игре со многими убегающими // Вести. ЛГУ. 1985. — Т. 4, № 22. — С. 107−109.

19. Петросян Л. А. Дифференциальные игры на выталкивание со многими участниками // Доклады АН СССР. 1965. — Т. 161, № 2. С. 285−287.

20. Пожарицкий Г. К. Задача Айзекса об огибании острова // ПММ. -1982. Т. 46, вып. 5. — С. 707−713.

21. Прасолов В. В., Соловьев Ю. П. Эллиптические функции и алгебраические уравнения. М.: Факториал, 1997. — 290 с.

22. Пшеничный Б. Н. О линейных дифференциальных играх // Кибернетика. 1968. — № I. — С. 47−53.

23. Пшеничный Б. Н., Остапенко В. В. Дифференциальные игры. -Киев: Наукова думка, 1992.

24. Рихсиев Б. Б. Дифференциальные игры с простыми движениями.- Ташкент: Фан, 1990. 232 с.

25. Субботин А. И. Обобщенные решения уравнений в частных производных первого порядка: перспективы динамической оптимизации. Москва-Ижевск: Институт компьютерных исследований, 2003.26 27 [28 [2930 3132.