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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М В ЛОМОНОСОВА

Механико - математический факультет

На правах рукописи УДК 517 977

Локуциевский Лев Вячеславович

ВИХРЕВЫЕ ОСОБЕННОСТИ ОПТИМАЛЬНЫХ СТРАТЕГИЙ В ЗАДАЧАХ ПОИСКА

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

АВТОРЕФЕРАТ

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

□□3449174

Москва - 2008 | '

003449174

Работа выполнена на кафедре оптимального управления мехапико-математическо! о факультет а Московского государственного университета имени M В Ломоносова

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

профессор М И Зеликин,

Официальные оппоненты члеп кориспондент РАН,

профессор А А Меликян

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

Ведущая организация Математический институт РАН

им В А Стеклова

Защита состоится 31 октября 2008 г в 16 часов45 минут на заседании диссертационного совета Д 501 001 85 при Московском государственном университете имени M В Ломоносова по адресу 119991, ГСП-1 Москва, Ленинские Горы, Главное здание МГУ, механико-математический факультет, аудитория 16-24

С диссертацией можно ознакомиться в библиотеке механико-математического факультета (Главное здание, 14 этаж)

Автореферат разослан 30 сентября 2008 г

Ученый секретарь диссертационного

совета Д 501 001 85 при МГУ,

доктор физико - математических ___

наук, профессор ' S" ' Сергеев И H

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

Актуальность темы. Теория дифференциальных игр возникла в шестидесятые годы прошлого столетия, и практически сразу оформилась как самостоятельная дисциплина Причиной этого можно считать высокий интерес к обобщению теории дискретных игр на непрерывный случай Основателем теории дифференциальных игр является известный американский математик Р Айзеке Он развил идеи Дж фон Неймана и Д Морген-штерна, вложенные ими в теорию дискретных игр и предложил следующую постановку задачи1 пусть в игре участвуют два игрока, преследующие различные интересы Назовем их Р и Е Их фазовые координаты х(£) и ?/(£) из некоторого аффинного пространства Е" подчиняются следующим уравнениям

где и и V - их управления, а функции ) и ■0() описывают возможности воздействия игроков на состояние игры

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

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

х = (р(х,у,и), У = ф(х,у,ь),

и(*) = Ф(:о» г/СО)

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

гократно пересмотрена и модернизирована многими известными математиками

Цели преследуемые игроками в каждой конкретной игре могут быть различными Например, в игре преследования игрок Р старается догнать игрока Е, то есть старается достигнуть состояния игры ||x(t) — y(t) || < R, игрок же Е наоборот пытается избежать данного состояния Итак результат в игре преследования - это возможность или невозможность поймать игрока Е Однако, оценивать такой результат очень не удобно в силу его дискретности, поэтому обычно рассматриваются другие критерии, например.

1 Игрок Р старается минимизировать время поимки, а игрок Е, соответственно, максимизировать

2 Игрок Р старается минимизировать расстояние \\x(t)—y(t)\\, а игрок Е, соответственно, максимизировать

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

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

2 Я{уковгкт1 В И i Чигрий А А, "Линейно квадратичные дифференциальные игры", Киев,-HdJ копа думка, 1994 г

^Пшеничный В Я, "О решении игр с линией житии", Киев, математические методы исследования и оптимтации систем, №3, с 38-46,1969 г

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

Млскгрр в В М , Тихомиров В М , Фомин С В, "Оптимальное у прав пение", 2-е ичд , Москва, ФИЗМАТ-ЛИТ, 2005г

^ Иоффе АД, Титомуров В М, "Теория экстремальных тадач", Москва, Наука, глав ред Физико-Математической литературы, 1974 г

в вырожденных случаях7, выпуклый анализ8 и методы линеаризации910

Сейчас в теории оптимального управления бурно развивается теория четтеринг режимов11 Простейшим примером, в котором возникает четтеринг режим, может служить задача Фуллера массивный шар движется по прямой под воздействием внешней ограниченной по модулю силы Эта сила служит управлением Требуется остановить шар в точке 0 - начале координат, минимизировав при этом среднеквадратичное отклонение от О

т

f x2dt —* mm, о

х(0) = хо, х(0) = Уо> х{Т) = 0, х{Т) = О, X — и, |lt| < 1

В отличие от задачи быстродействия (в тех же условиях необходимо минимизировать время достижения точки О Т —> mm), оптимальная траектория в простейшей задаче Фуллера достигает начала координат за конечное время, но при этом совершает счетное число переключений, накапливающихся к началу координат Такое поведение оптимальной траектории является характерным для задач в теории четтеринг режимов

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

7 Арутюнов А В "Утопия экстремума Анормальные и вырожденные задачи Москва, Факториат, 1997 г

8Половипкин В С, Балашов И В, "Элементы выпуклого и сильно выпуклого анализа", Москва, ФИЗМАТ ПИТ, 2004 г

"Никольский М С, "Пимеартуемые объекты и их применение в дифференциальных играх ггресчедо-вания", Доклады Академии Наук СССР, том 205 N>4, 1972 г

тПшеничный Б Н, 'Метод пинеаричации", Москва Наука, глав ред Фичико-МатематическоЯ литературы, 1983 г

11 Zehhn MI, Bomov VF "Theory of Chattering Control with Applications to Astronautics, Robotics Economics and Engmeenng' Birkhauser, Boston 1994

Особое место в теории дифференциальных игр занимают так называемые игры с неполной информацией Их принципиальное отличие от описанных выше игр с полной информацией заключается в том, что игрок Р не располагает точной информацией о фазовых координатах игрока Е и вынужден строить свою стратегию поведения исходя лишь из частичной информации об игроке Е В семидесятых-восьмидесятых годах в работах Черноусько и Меликяна исследовались подобные игры12 Ими был предложен метод сканирования для поиска подвижного игрока В предположении, что игрок Р знает фазовые координаты игрока Е в начальный момент времени и, возможно, в какие-то другие промежутки времени, удается доказать, что такие игры с неполной информацией эквивалентны так называемым импульсным играм с полной информацией

Другой подход к играм с неполной информацией относится к играм преследования и сопряжен с теорией вероятностей игрок Р не знает точного расположения игрока Е, однако ему известна плотность вероятности возможного нахождения игрока Е и наоборот В такого рода задачах практически никогда не удается найти оптимальные стратегии, так так каждый из игроков должен определять свое поведение исходя из поведения противника и седловой точки 13 не возникает Единственным исключением, пожалуй, может считаться работа М И Зеликина14 о задаче преследования на окружности, в которой удалось найти оптимальные траектории в классе смешанных стратегий, ввиду наличия большого количества симметрий в задаче

В настоящей диссертации рассмотрена задача поиска с неполной информацией, стоящая на стыке таких областей математи-

'2 Чррноуськп Ф Л, Меликяп А А , "Игровые задачи управления и поиска', Москва, Наука, 1978 г

11 Краговгкпй Н Я, Субботин А И , "Почиционныедиффрреицияльные игры", Москва, Наука, глав ред Фичико-Математичрской литературы, 1974 г

и3еликин МИ, "Об одной дифференциальной игре с неполной информацией", Доклады Академии Наук СССР, том 202, №5, 1972 г

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

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

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

Научная новизна. Все полученные результаты являются новыми и состоят в следующем

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

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

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

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

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

Апробация диссертации. Результаты диссертации докладывались автором неоднократно на семинаре проф М И Зеликина по геометрической теории оптимального управления на механико-математическом факультете МГУ (2006-2008 г), на конференции «Ломоносовские чтения» механико-математического факультета МГУ (Москва 2007 г), на семинаре проф Е С Половинкина кафедры высшей математики Московского Физико-Технического Института (2008 г), на международной конференции "Дифференциальные уравнения и топология", посвященной 100-летию со дня рождения Л С Понтрягина (Москва, 2008г)

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

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

Общий объем текста - 64 страницы Список литературы содержит 31 наименование

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

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

В первой главе дана постановка задач поиска на римановом многообразии М, в которых участвуют два игрока Игрок Р -преследователь, движущийся с ограниченной по модулю скоростью < г>о и начинающий свое движение в начальный момент времени = 0 из некоторой фиксированной точки о е М Он ищет игрока Е, который в свою очередь неподвижен (этого "игрока" вернее было было бы назвать неподвижным объектом, но традиция требует называть его игроком и в дальнейшем мы будем придерживаться именно такого термина) Игроку Р неизвестно точное расположение игрока Е, однако ему известна функция ф(х) плотности вероятности расположения игрока Е

Поиск заканчивается в тот момент времени, когда игрок Р впервые увидит игрока Е Область видимости игрока Р в момент времени Ь - это замкнутый шар радиуса Д0 с центром в точке х(Ь) расположения игрока Р Обозначим так же через Во - область видимости игрока Р в начальный момент времени Естественно считать, что тр(х) = 0 для всех х Е Во

Поскольку игрок Е неподвижен, то стратегией игрока Р в данном классе задач служит заранее выбранная траектория = 7(2) Естественно, она должна начинаться в точке о и удовлетворять условию Липшица15

|7(*2)-7(*1)1<г>о|*2-*1| ^!>0,:£2>0

"Дотпонгон И П, "Конструктивная теория функций", Могкпа-Леиинград ТехТеорПит 1949 г

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

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

Также в первой главе изучаются простейшие свойства таких особенностей на римановых многообразиях, в которых открытая окрестность II(о, 1 -I- 5) точки о радиуса 1 + 5 изоморфна как риманово многообразие открытому шару такого же радиуса в евклидовом пространстве

Определение (1 1). Будем говорить, что траектория ^(Ь) имеет вихревую особенность (см [1]) при начале движения, если для любого полного выпуклого остроугольного конуса К+ с вершиной в точке о и сколь угодно малого найдется момент времени 0 < < такой что

7(0 $ К+.

Стратегия с вихревой особенностью при начале движения как минимум не имеет производной при £ — О Так, например, в задаче поиска на отрезке преследователь Р за сколь угодно малый начальный интервал времени бесконечное число раз меняет направление своего движения, чтобы за этот начальный интервал времени побывать с обеих сторон от точки о В случае двумерного многообразия вектор скорости игрока Р совершает за любой сколь угодно малый начальный интервал времени счетное число полных оборотов (это и послужило причиной названия таких особенностей вихревыми) Еще более трудно представимые оптимальные стратегии возникают при поиске на многообразиях с размерностью больше двух Здесь за любой сколь угодно малый начальный интервал времени игрок Р стремится полностью

осмотреть окрестность границы области видимости в начальный момент времени16

В §1 3 доказана основная теорема для задач поиска на гс-мерном многообразии

Теорема (1 1). Если 7(£) - оптимальная стратегия, иф(х) равномерно стремится к +оо при х —> дВо снаружи ша,ра, тогда 7(£) им,ест вихревую особенность при начале движения

Таким образом, если г/>(я) устроена как в теореме 11, тогда при оптимальном поиске игрок Р должен начать свое движение с того, что "вздрогнуть" - то есть осмотреть всю малую внешнюю окрестность границы шара дВо за любой сколь угодно малый начальный интервал времени

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

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

Теорема (2 1). Если 7(2) - оптимальная стратегия в задаче поиска на двумерной евклидовой плоскости М, и на функцию ф(х) вблизи границы круга дВо наложено дополнительное ограничение (р(-, •) обозначает расстояние на М)

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

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

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

г _ еКч>-чъ)

на круге [/(о, 1 + 5) С М с центром в точке о и радиуса 1 + 6 с симметричной функцией плотности ф(х) = ф(р(х, о))

Теорема (2 2). Существуют такие константы 0 < ктгп < ктаг < независящие от 5 и тр, что при достаточно малом 5 и произвольной функции 1р(р) существует ко Е [ктт,ктаъ], при котором траектория является оптимальной сре-

ди всех логарифмических спиралей

Основное содержание главы 3 состоит из исследования одномерного случая В §3 1 подробно изучен класс стратегий 5И/00(А, В) на отрезке {—А, В) с не более чем счетным числом переключений и выявлены основные его свойства §§3 2 и 3 3 содержат два ключевых результата про существование оптимальной стратегии в одномерной задаче поиска на отрезке Во-первых доказано, что для любой допустимой липшицевой стратегии 7^) всегда можно найти стратегию 7(£) е ^(А, В), имеющую не худшее математическое ожидание времени поиска

Теорема (3 1). Независимо от функции ф(х) в задаче поиска на, отрезке [—А, В] по любой допустимой тпшицевой стратегии 7(t) можно построить стратегию 7(t) G SW^A, В) с таким Dice или меньшим математическим ожиданием времени поиска Следовательно, инфимум математического ожидания, времени поиска совпадает для классов допустимых стратегий и стратегий с не более чем счетным числом переключений

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

Теорема (3 2). В задаче поиска на отрезке с любой функцией плотности ф(х) существует стратегия 7(£) € S,W00(A, В), являющаяся оптимальной среди всех допустимых липшицевых стратегий

В главе 4 исследовано поведение оптимальной стратегии на отрезке как для функций плотности ф(х), которые стремятся к -foo при приближении х к границе шара дВ0 = {До, —-Rob так и в противном случае, когда ф(х), наоборот, ограничена (Rq -радиус видимости игрока Р\А,В> Rq, и за точку о, естественно, взят 0)

Теорема (4 4). Пусть функция плотности вероятности ф(х) непрерывна на объединении [—Л, —Rq) U (Rq, В] Если ф(х) +оо при х —► Rq справа и х —> — Rq слева, тогда оптимальная стратегия 7(t) имеет счетное количество переключений вблизи О Если же ф(х) ограничена в окрестности хотя бы, одной из точек —Rq или Rq, тогда, оптимальная стратегия 7(t) имеет конечное количество переключений в окрестности О

Также в главе 4 получен другой неожиданный феномен поведения оптимальной стратегии при t —> -boo, в каком-то смысле

двойственный вихревой особенности при i —► 0. если функция плотности ф(х) стремится к нулю на концах отрезка [—А, В], то игрок Р счетное число раз меняет направление движения при приближении к концам отрезка А именно, когда вероятность найти игрока Е около данного конца отрезка становится достаточно малой преследователь Р бежит к другом концу отрезка и там, в свою очередь, не добежав до самого конца, поворачивает обратно, и так происходит счетное число раз. При этом, поиск может в принципе занять сколь угодно большое время, несмотря на то, что обзор всего отрезка требует фиксированного конечного времени Тем не менее математическое ожидание времени поиска оказывается минимальным

Результатом §4 1 помимо теоремы 4 4, которая была описана выше, является следующая теорема о характере особенностей оптимальной стратегии в задаче поиска на отрезке М = [—А, В] (см [2])

Теорема (4 3). Пусть функция, ф(х) непрерывна па объединении [-Д -Я0) и (Яо, В] Если ф(х) -»• 0 при х ->■ -А и х В, тогда оптимальная стратегия, 7(2) имеет счетное количество переключений вблизи концов интервала (—А 4- Яо, В — Яо) Если же ф(х) отделена от 0 в окрестности готя бы одной из точек —А или В, тогда оптимальная, стратегия 7(2) имеет конечное количество переключений в окрестности концов интервала {-А + Я0,В-Яо).

Также в главе 4 найдены формулы для точек переключения (см [3]) и в случае бесконечного числа точек переключения вычислена асимптотика точек поворота как вблизи точки 0, так и вблизи концов интервала (—.4 + Яо,В — Яо). Если вблизи и —Яо функция ф(х) ведет себя как степенная функция

Ф(х) ~ при X > До,

Ф(х) ~ ПРИ Х < где аи/Зиз интервала (0,1), тогда точки переключения оптимальной стратегии ., Х-п, x_n+i,. ., ж_ь жо, (по теореме 4 4 нумерация точек переключения идет от -оо) устроены следующим образом

ill \xn-2\ ~ при х„ > Д0

iii |Х„_2| ~ |Х„Р, При Ж,, < Д0

Аналогичным образом устроена асимптотика точек переключения при приближении к концам интервала {—А 4- До, В — До), если ф{х) 0 при х -+ —Л как степенная функция

ф(х) ~ са(х + Л)а, при ж -А + О, ф(х) ~ сь(В — ж)^, при х —* В — О,

где а и (3 положительны, тогда получаем (для положительных и отрицательных s,r'l_l соответственно)

п-г+И \сь{А+В){1+,

Показательным примером модет служить следующие задачи поиска на отрезке [—2,2] (радиус видимости Д = 1)

1 Функция плотности ф(х) устроена следующим образом

_ / 2-Й» если 1 ^ \х\

П ' ~ 1 0, если |ж| < 1

В этом случае по теореме 4 3 в оптимальной стратегии при £ —> +оо точки переключения накапливаются к концам отрезка Асимптотика следующая £о с* 1,66, £1 ~ —1,972, х2 1,999798, . , |ж„| ~ 2 - 4 12~2" .

В этом примере задача поиска тоже происходит на отрезке [—2,2], только функция плотности ф(х) устроена подругому

если 1 < [ж| < 2,

ф(Х) = ^ 4ч/1аИ'

[ 0, если |х| < 1,

Тогда по теореме 4 4 игрок Р при оптимальном поиске делает счетное число переключений при начале движения ~

х-1 -0,00694, х_2 ~ 0,00000301, , |ж_„| ~ 16-48~2~П (нумерация точек переключения по теореме 4 4, естественно, идет от —оо)

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

образом отличается от типичного поведения оптимальных траекторий при четтеринг режиме (в задаче Фуллера, например, точки переключения приближаются к 0 со скоростью геометрической прогрессии)

Автор благодарит профессора М И Зеликина за предложенную тему, постоянное внимание к работе, ценные замечания и многочисленные обсуждения, Р А Усачева за обсуждения и ценные замечания

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

[1] Локуциевский Л В., "Вихревые особенности оптимальных стратегий при начале движения в задачах поиска на п-мерных многообразиях", Доклады Академии Наук, том 417, N 3, ноябрь 2007, С 316-318

[2] Локуциевский Л В, "Накопление переключений в задачах поиска", Современная математика, Фундаментальные направления, 2006 г, 19, 70-77

[3] Локуциевский Л В , Зеликин М И, Усачев Р А , "Вихревые особенности оптимальных стратегий при начале движение в задачах поиска на n-мерных римановых многообразиях", Современная матеметика и ее приложения, РУДН, том 58, 2008 г, стр 56-78

В работе Зеликину М И принадлежит постановка задачи, Локуциевскому Л В принажяежат доказательства, за исключением теоремы 10 Я, Усачеву РА принадлежит доказательство теоремы 10 S

[4] Lokutsievskii L V, Zehhn MI, "Vortex Singularity m search game problems at the beginning and ending of search", Международная конференция Дифференциальные уравнения и топология, посвященная 100-летию со дня рождения Л С Понтрягина, Москва, 2008 г, 265-266

В работе Зеликину М И принадлежит постановка задачи, Локуциевскому Л В принажлежат доказательства

Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж [00 экз Заказ №36

Введение

Общая характеристика работы.

Содержание диссертации.

1 Вихревые особенности в n-мерном многообразии

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

1.2 Вихревые особенности и их простейшие свойства.

1.3 Вихревые особенности оптимальных стратегий на n-мерных ри-мановых многообразиях.

2 Оптимальные стратегии на двумерном многообразии

2.1 Особенности оптимальной стратегии в случае двумерного многообразия

2.2 Класс двумерных логарифмических спиралей

3 Теорема существования в одномерном случае

3.1 Переключения в стратегиях в одномерном случае.

3.2 Свойства траекторий со счетным числом переключений.

3.3 Существование оптимальной стратегии в одномерном случае

4 Асимптотика оптимальных стратегий вблизи вихревых особенностей

4.1 Накопление переключений в оптимальном решении в одномерном случае

4.2 Асимптотика переключений в оптимальной траектории.

4.3 Примеры

Общая характеристика работы

Теория дифференциальных игр возникла в шестидесятые годы прошлого столетия, и практически сразу оформилась как самостоятельная дисциплина. Причиной этого можно считать высокий интерес к обобщению теории дискретных игр на непрерывный случай. Основателем теории дифференциальных игр является известный американский математик Р. Айзеке. Он развил идеи Дж. фон Неймана и Д. Моргенштерна, вложенные ими в теорию дискретных игр и предложил следующую постановку задачи (см. [1]): пусть в игре участвуют два игрока, преследующие различные интересы. Назовем их Р и Е. Их фазовые координаты x{t) и y(t) из некоторого аффинного пространства R71 подчиняются следующим уравнениям: X = (р(х,у,и), \ у = ф{х,у,у), где и и v - их управления, а функции </?(•) и ip(-) описывают возможности воздействия игроков на состояние игры.

Основной принцип, использовавшийся Р. Айзексом при решении конкретных задач и построении общей теории заключался в том, что игроки Р и Е выбирают свое управление независимо друг от друга и исходя только из текущих фазовых координат игры, не используя ни предшествующую историю игры, ни управление, выбираемое противником в данный момент времени: u(t)=u(x(t),y{t)), v(t)=v(x(t),y{t)).

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

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

Е, то есть старается достигнуть состояния игры — y(t)|| < R, игрок же

Е наоборот пытается избежать данного состояния. Итак результат в игре преследования - это возможность или невозможность поймать игрока Е. Однако, оценивать такой результат очень не удобно в силу его дискретности, поэтому обычно рассматриваются другие критерии, например:

1. Игрок Р старается минимизировать время поимки, а игрок Е, соответственно, максимизировать.

2. Игрок Р старается минимизировать расстояние — y(t) ||, а игрок Е, соответственно, максимизировать.

Естественно, теория дифференциальных игр не ограничивается приведенной выше игрой преследования, а включает в себя широкий спектр задач, таких как линейно квадратичные игры (см. [8]), позиционные игры (см. [13]), игры с линией жизни (см. [22]) и многие другие (см. [1, 23, 25]), находящие частое и обширное применение в экономике, военном деле и т.д.

Теория дифференциальных игр тесно связана с теорией оптимального управления, и поэтому при различных исследованиях в этой области часто используются методы вариационного исчисления и принцип максимума Понт-рягина (см. [2, 10]), условия экстремума в вырожденных случаях (см. [5]), выпуклый анализ (см. [20]) и методы линеаризации (см. [19, 21]).

Сейчас в теории оптимального управления бурно развивается теория чет-теринг режимов (см. [31]). Простейшим примером может служить задача Фуллера (см. [31]): массивный шар движется по прямой под воздействием внешней ограниченной по модулю силы. Эта сила служит управлением. Требуется остановить шар в точке 0 - начале координат, минимизировав при этом среднеквадратичное отклонение от 0: т f х2 dt —» min, о ar(0) = xq, ж(0) = г/о, x(T) = 0, х(Т) = 0, X = и, |li| < 1.

В отличие от задачи быстродействия (в тех же условиях необходимо минимизировать время достижения точки 0: Т —> min), оптимальная траектория в простейшей задаче Фуллера достигает начала координат за конечное время, но при этом совершает счетное число переключений, накапливающихся к началу координат. Такое поведение оптимальной траектории является характерным для задач в теории четтеринг режимов.

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

Особое место в теории дифференциальных игр занимают так называемые игры с неполной информацией. Их принципиальное отличие от описанных выше игр с полной информацией заключается в том, что игрок Р не располагает точной информацией о фазовых координатах игрока Е и вынужден строить свою стратегию поведения исходя лишь из частичной информации об игроке Е (см. [9]). В семидесятых-восьмидесятых годах в работах Черноусь-ко и Меликяна исследовались подобные игры (см. [25]). Ими был предложен метод сканирования для поиска подвижного игрока. В предположении, что игрок Р знает фазовые координаты игрока Е в начальный момент времени, удается доказать, что такие игры эквивалентны так называемым импульсным играм с полной информацией.

Другой подход к играм с неполной информацией относится к играм преследования и сопряжен с теорией вероятностей: игрок Р не знает точного расположения игрока Е, однако ему известна плотность вероятности возможного нахождения игрока Е и наоборот. В такого рода задачах практически никогда не удается найти оптимальные стратегии, так так каждый из игроков должен определять свое поведение исходя из поведения противника и седловой точки (см. [13]) не возникает. Единственным исключением, пожалуй, может считаться работа М.И. Зеликина (см. [9]) о задаче преследования на окружности, в которой удалось найти оптимальные траектории в классе смешанных стратегий, ввиду наличия большого количества симметрий в задаче.

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

Содержание диссертации

В диссертации исследованы задачи поиска на римановом многообразии М, в которых участвуют два игрока. Игрок Р - преследователь, движущийся с ограниченной по модулю скоростью < г>о и начинающий свое движение в начальный момент времени to = 0 из некоторой фиксированной точки о €

М. Он ищет игрока Е, который в свою очередь неподвижен (этого "игрока" вернее было было бы назвать неподвижным объектом, но традиция требует называть его игроком и в дальнейшем мы будем придерживаться именно такого термина). Игроку Р неизвестно точное расположение игрока Е, однако ему известна функция ip(x) плотности вероятности расположения игрока Е.

Поиск заканчивается в тот момент времени, когда игрок Р впервые увидит игрока Е. Область видимости игрока Р в момент времени t - это замкнутый шар радиуса Ro с центром в точке x{t) расположения игрока Р. Обозначим так же через Bq - область видимости игрока Р в начальный момент времени. Естественно считать, что ф(х) = 0 для всех х G Bq.

Поскольку игрок Е неподвижен, то стратегией игрока Р в данном классе задач служит заранее выбранная траектория x(t) = 7(t). Естественно, она должна начинаться в точке о и удовлетворять условию Липшица (см. [18]):

7№2) - 7(*i)l < vo\t2 ~ h\ Vii > 0, f2 > 0.

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

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

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

2. Алексеев В.М., Тихомиров В.М., Фомин С.В., "Оптимальное управление", 2-е изд., Москва, ФИЗМАТЛИТ, 2005г. ISBN 5-9221-0589-2

3. Александров П.С., "Введение в теорию множеств и общую топологию", Москва, Наука, 1977 г.

4. Арнольд В.И., "Обыкновенные дифференциальные уравнения", Москва, Наука, 1971 г.

5. Арутюнов А.В., "Условия экстремума. Анормальные и вырожденные задачи.", Москва, Факториал, 1997 г.

6. Данфорд Н., Шварц Дж.Т., "Линейные операторы", М.:Наука, 1974 г.

7. Дубровин В А., Новиков С.П., Фоменко А.Т., "Современная геометрия", Москва "Наука", 1979 г.

8. Жуковский В.И., Чикрий А. А, "Линейно квадратичные дифференциальные игры", Киев, Наукова думка, 1994 г.

9. Зеликин М.И., "Об одной дифференциальной игре с неполной информацией", Доклады Академии Наук СССР, том 202, №5, 1972 г.

10. Иоффе А.Д., Тихомиров В.М., "Теория экстремальных задач", Москва, Наука, глав. ред. Физико-Математической литературы, 1974 г.

11. Ким Д.П., "Методы поиска и преследования подвижных объектов." М.: Наука, 1989 г.

12. Колмогоров А.Н., Фомин С.В., "Элементы теории функций и функциональный анализ", Москва, Наука, 1972 г.

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

14. Локуциевский Л.В., "Вихревые особенности оптимальных стратегий при начале движения в задачах поиска на n-мерных многообразиях", Доклады Академии Наук, том 417, N 3, Ноябрь 2007, С. 316-318.

15. Локуциевский Л. В., "Накопление переключений в задачах поиска", Современная математика, Фундаментальные направления, 2006 г., 19, 70-77

16. Локуциевский Л. В., Зеликин М.И, Усачев Р.А., "Вихревые особенности оптимальных стратегий при начале движение в задачах поиска на п-мерных римановых многообразиях", Современная матеметика и ее приложения, РУДН, том 58, 2008 г., стр 56-78

17. Милютин А.А., Илютович А.Е., Осмоловский Н.П., Чуканов С.В., "Оптимально е управление в линейных системах.", Москва, Наука, 1993 г.

18. Натансон И.П., "Конструктивная теория функций", Москва-Ленинград, ТехТеорЛит, 1949 г.

19. Никольский М.С., "Линеаризуемые объекты и их применение в дифференциальных играх преследования", Доклады Академии Наук СССР, том 205 Ш, 1972 г.

20. Половинкин Е.С., Балашов М.В, "Элементы выпуклого и сильно выпуклого анализа", Москва, ФИЗМАТЛИТ, 2004 г.

21. Пшеничный Б.Н., "Метод линеаризации", Москва, Наука, глав. ред. Физико-Математической литературы, 1983 г.

22. Пшеничный Б.Н., "О решении игр с линией жизни", Киев, математические методы исследования и оптимизации систем, №3, с. 38-46, 1969 г.

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

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

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

26. Эрроусмитп Д., Плейс К., "Обыкновенные дифференциальные уравнения. Качественная теория с приложениями", Москва, Мир, 1986 г.

27. Franklin, S. P., "Spaces in Which Sequences Suffice", Fund. Math. 57 (1965), 107-115.

28. Franklin, S. P., "Spaces in Which Sequences Suffice II", Fund. Math. 61 (1967), 51-56.

29. Marshall Hall, Jr., "Combinatorial theory", Waltham Toronto - London, "Blaisdell publishing company", 1967.

30. Sternberg S., "Lecturs on differential geometry", Prentice Hall, Inc.Englewood Cliffs, N.J. 1964

31. Zelikin M.I., Borisov V.F. "Theory of Chattering Control with Applications to Astronautics, Robotics, Economics and Engineering". Birkhauser, Boston. 1994.