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

• Локуциевский, Лев Вячеславович
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Локуциевский, Лев Вячеславович

Введение

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

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

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.

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Локуциевский, Лев Вячеславович, 2008 год

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.