Стационарные стратегии в многошаговых играх с задержкой информации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение

Г л а в а I. Бесконечношаговая игразадержкой информации

§ I. Описание задачи "корабль против бомбардировщика".

§ 2. Формулировка критерия оптимальности .12с.

§ 3. Применение принципа оптимальности Беллмана к задаче "корабль против бомбардировщика" .20с.

Г л а в а П. Исследование основных функциональных уравнений. 23с.

§ I. Предварительные сведения . 23с.

§ 2. Общая формулировка задачи .26с.

§ 3. Сильная квазивыпуклость функций Ч5.^ и существование непрерывного предела ^сос)^ = turw Чч Сое) . 29с.

§ 4. Существование стационарной по значению оптимальной стратегии поведения . 33с.

§ 5. Существование стационарной стратегии поведения для случая, , и симметричной задачи .41с.

§ 6. Следствия из теоремы о стационарности .47с.

Глава!. Стационарность оптимальных смешанных стратегий поведения . 54с.

§ I. Проверка условий основных теорем для задачи корабль против бомбардировщика . 54с.

§ 2. Решение задачи "корабль против бомбардировщика". 59с.

§ 3. Обобщение задачи "корабль против бомбардировщика". 52с.

Г л а в а ГУ. Приложение к одной игре с бесконечным числом альтернатив . 66с.

§ I. Описание многошаговой игры .66с.

§ 2. Обоснование и вывод основных функциональных уравнений. 69с.

§ 3. Стационарные стратегии поведения .71с.

Л и т е р а т у р а . 75с.

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

К настоящему времени хорошо исследованы многошаговые игры с полной информацией. Вместе с тем, многие даже самые простые по постановке, многошаговые игры с неполной информацией, с трудом поддаются анализу. Если же учесть, что в целом ряде практических задач полнота информации о текущем значении фазовых координат явление исключительное, то становится ясно, что исследование математических моделей многошаговых игр с неполной информацией, особенно поиски оптимальных в каком-либо смысле решений таких игр, цредставляет собой действительно актуальную задачу. Систематическое исследование бесконечношаговых игр с неполной информацией начато в середине 60-х годов. Здесь следует отметить работы Л.А.Петросяна Г9-12J , Н.М.Слобожанина [l7-2l] , Т.В.Слободинской [14-16] , И.Н.Врублевской Гз] , а также иностранных авторов Айзекса [I] , Дубинса [4] , Скарфа [133 , Шешш Г13] .

Большинство указанных выше работ посвящено исследованию вопроса существования решения в том или ином виде. Конечно же, очень важно найти способы нахождения оптимальных решений. Получены общие способы решения игр такого класса (см. Г17-21] ), в виде функциональных уравнений, аналогичных уравнениям Беллмана. Однако даже простые функциональные уравнения могут быть решены только в очень редких случаях, даже с использованием больших ЭВМ. Основной целью работы является анализ оптимальных в некотором смысле решений функциональных уравнений Беллмана, применяемых для решения многошаговых игр с неполной информацией на предмет выявления стационарных решений. Существование стационарных оптимальных решений приводит к возможности решения задач в более узком классе допустимых управлении и значительно снижает затраты на их решение, позволяя в конечном счете построить все множество оптимальных управлений.

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

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

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

Первая глава посвящена бесконечношаговой игре с задержкой информации, предложенной Айзексом ( П] ) и названной им "корабль против бомбардировщика", частные случаи которой были исследованы другими авторами (см.Г 6] , [13] ).

В §§1-2 описана сама конфликтная ситуация и приведены различные способы ее формализации.

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

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

В §§1-2 описан вид исследуемых функциональных уравнений и приведены предварительные сведения.

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

В §§ 4-6 доказана теорема о существовании стационарной (марковской) оптимальной стратегии поведения и получен ряд следствий.

В третьей главе решается задача, поставленная в первой главе, на основе свойств решений, выявленных во второй главе.

В §§ 1-2 проверяются условия теоремы о существовании стационарных оптимальных стратегий поведения (для частного случая они получены в [ 6 ] , С 13 ] ).

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

Четвертая глава посвящена одной игре с бесконечным числом альтернатив.

В § I приведено описание задачи типа простое преследование на плоскости с возможностью выстрела у преследователя и континуальным числом альтернатив у убегающего.

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

В § 3 приведен конкретный пример игры и получены все оптимальные стратегии поведения.

Основные результаты диссертации заключаются в следующем:

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

2) В частном случае показано существование марковской стратегии поведения и выявлены причины, приводящие к существованию стационарной стратегии поведения.

3) Указан способ получения всего множества оптимальных стратегий поведения на основе существования оптимальной марковской стратегии поведения.

4) Предложен метод использования теоремы о существовании стационарной стратегии поведения, не смотря на некоторые неконструктивные условия.

Основные результаты диссертации опубликованы в работах [5] , Г 8 ] , Щ] .

Г л а в a I

БЕСКОНЕЧНОШАГОБАЯ ИГРА С ЗАДЕРЖКОЙ ИНФОРМАЦИИ

1. АйЗЕКС Р. Дифференциальные игры. М.: Мир, 1967, 479с.

2. ВОРОБЬЕВ Н.Н. Основы теории игр. Бескоалиционные игры. М.: Наука, 1984, 495 с.

3. БРУБДЗЗСХАЯ И.Н. Эквивалентность смешанных стратегий и стратегий поведения в счетной позиционной структуре.- В кн.: Позиционные игры /под ред. Н.Н.Воробьева и И.Н.Врублевекой. М.: Наука. Физматгиз. 1967, с. 246-250.

4. ДУБИНС Л.Э. Дискретная игра на уклонение от преследования. В кн.: Применение теории игр в военном деле. М.: Советское радио, X96I, с. 275-302.

5. ЗЕНКЕВИЧ Н.А., ОГЛОЕЯИН В.Л. а вопросу о динамических играх с запаздыванием информации. В сб.: Математические методы оптимизации и управления в сложных системах. Калинин, 1982, с. 60-68.

6. КАРЛИН С. Математические методы в теории игр, программирования и экономике. М.: Мир, 1964, 838с.

7. КОЛМОГОРОВ А.Н., ФОМИН С.В. Элементы теории функций и функционального анализа. М.: Наука, 1981, 543с.

8. ОГЛОЕЛИН В.Л. О свойствах оптимальных стратегий в одной динамической игре с запаздыванием информации. В сб.: Математические методы оптимизации и управления в сложных системах. Калинин, 1983, с. 67-77.

9. ПЕТРОСЯН Л.А. Дифференциальные игры преследования. Л.: изд-во ЛГУ, 1977, 222с.

10. ПЕТРОСЯН Л.А. Сигнальные стратегии и стратегии поведения в одном классе бескоалиционных позиционных игр. В кн.: По- 76 зиционные игры /под ред. Н.Н.Воробьева и Н.И.Врублевской. М.: Наука. Физматгиз. 1967, с. 221-229.

11. ПЕТРОСЯН Л.А., ТОМСКИЙ Г.В. дифференциальные игры с неполной информацией. Ирку тег:: изд-во Иркутского ун-та, 1984, 187 с.

12. ПЕТРОСЯН Л.А., ТОМСКИЙ Г.В. Динамические игры с полной ин-фюрмацией и их приложения к играм с неполной информацией.-Дифференциальные уравнения, т. 18, $ 4, с. 593-595.

13. СКАРФ Х.Э., 1ШШИ Л.С. Игры с неполной информацией. В кн.: Применение теории игр в военном деле. М.: Сов. радио, 1961, с. 256-274.

14. СЛОБОДИНСКАЯ Т.В. Верхние оценки значения игры в одном классе игр с неполной информацией. В кн.: Материалы Международной конференции - ТК-7. Новосибирск, 1974, с. 18-20.

15. СЛОБОДИНСКАЯ Т.В. Бескоалиционные дифференциальные игры преследования с задержкой информации. В кн.: Тезисы докладовШ Всесоюзной конференции по исследованиюопераций. Горький, 1978, с. 420-421.

16. СЛ0Б07ШШН Н.М. Теоремы существования для бесконечных позиционных игр. В сб.: Некоторые вопросы вычислительной и прикладной математики. Якутск, 1977, с. 47-51.

17. СЛОБОЖАНИН Н.М. О существовании ситуации равновесия в бесконечных позиционных играх П лиц.- Вопросы механики ипроцессов управления. Вып. 2. Управление динамическими системами. Л.: изд-во Ленингр. ун-та, 1978, с. 213-219.

18. СЛОБОЖАНИН Н.М. Обоснование одной гипотезы Л.А.Петросяна.-Вестн. Ленингр. ун-та, 1981, J' 13, с. II2-II4.

19. СЛОБОЖАНИН Н.М. 0 функциональных уравнениях одного класса многошаговых игр. Ред. ж. Вестн. Ленингр. ун-та. Сер. мат., мех., астрон. $19, Л., 1981, 14с.

20. СЛОБОЖАНИН Н.М. 0 существовании ситуации равновесия в бесконечных позиционных играх с неполной информацией.- В сб.: Многошаговые дифференциальные бескоалиционные и кооперативные игры и их приложения. Калинин, 1982, с. 135-140.

21. ЭДВАРДС Р. Функциональный анализ. М.: Наука, 1969, 1071с.Рис. 1