Решение одного класса иерархических дифференциальных игр: методы, алгоритмы, программы тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Осипов, Сергей Иванович

• Осипов, Сергей Иванович
• кандидат физико-математических наук
• 2007

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

Введение

1 Построение позиционных оптимальных стратегии Шта-кельберга в одной иерархической динамической игре двух лиц с аддитивной помехой

1.1 Общие замечания.

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

1.3 Основной результат.

1.4 Вычисление решений Штакельберга.

2 Алгоритм построения решений для иерархической игры Штакельберга в плоскости с цилиндрическими показателями игроков

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

2.2 Определение структуры решений.

2.2.1 Вспомогательные антагонистические игры Г1 и Г

2.2.2 Вспомогательная задача оптимального управления

2.3 Общее описание алгоритма.

2.3.1 Принципиальная схема алгоритма.

2.3.2 Алгоритм построения оптимальной траектории

2.3.3 Обсуждение геометрических конструкций, используемых при работе алгоритма

2.3.4 Плоские многоугольники: определения и обозначения

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

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

2.4.2 Описание алгоритма.

2.4.3 Краткое описание программы.

2.5 Алгоритм построения алгебраической суммы плоских многоугольников

2.5.1 Кинетический подход

2.5.2 Работы зарубежных авторов посвященные алгоритмам построения алгебраической суммы.

2.5.3 Алгоритм построения алгебраической суммы многосвязного и выпуклого многоугольников.

2.5.4 Этап "Обведение".

2.5.5 Этап "Выделение и сборка".

2.5.6 Отсев и упорядочение.

2.5.7 Алгоритм объединения многосвязных многоугольников

2.6 Программная реализация алгоритмов.

Численное решение одной иерархической дифференциальной игры двух лиц 102 3.1 Формулировка задачи.

3.2 Общее описание аналитического решения.

3.3 Общее описание алгоритма решения.

3.4 Результаты численного эксперимента

Введение диссертации (часть автореферата) на тему «Решение одного класса иерархических дифференциальных игр: методы, алгоритмы, программы»

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

Современный облик теории дифференциальных игр сформировался в значительной степени под влиянием работ отечественных и зарубежных математиков Н. Н. Красовского/1, 2/, Л. С. Понтрягина/3/, Р. Айзекса/4/, У. Флеминга. Крупный вклад в развитие теории дифференциальных игр внесли Э. Г. Альбрехт, М. Барди, В. Д. Батухтин, Е. Н. Баррон, Т. Башар, Р. Беллман, А. Брайсон, Н. Л. Григоренко, Р. В. Гамкрелидзе, В. И. Жуковский, М. И. Зеликин, Н. Калтон, А. Ф. Клейменов, А. Н. Красов-ский, А. В. Кряжимский, А. Б. Куржанский, Дж. Лейтман, П. Л. Лионе, А. А. Меликян, Е. Ф. Мищенко, М. С. Никольский, Г. Ольсдер, Ю. С. Осипов, А. Г. Пашков, В. С. Пацко, Н. Н. Петров, Л. А. Петросян, Г. К. Пожа-рицкий, Б. Н. Пшеничный, А. И. Субботин, Н. Н. Субботина, В. Е. Третьяков, В. Н. Ушаков, А. Фридман, Хо-Ю-Ши, А. Г. Ченцов, Ф. Л. Черноусько, А. А. Чикрий, С. В. Чистяков, А. Ф. Шориков, Р. Эллиот и многие другие.

Первые работы по статическим неантагонистическим играм относятся к периоду 30-50-х гг. двадцатого века и принадлежат таким авторам, как Дж. фон Нейман, О. Моргенштерн, Дж. Нэш, Г. фон Штакельберг. Принципиальным вопросом в неантагонистической игре является выбор понятия решения, отвечающего содержанию задачи и опирающегося на соответствующий выбор принципа оптимальности. Обычно рассматриваются следующие виды решений: равновесное по Нэшу/5/, решение по Штакельбергу/б/.

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

Неантагонистическим дифференциальным играм посвящены работы Т. Башара, Н. Н. Данилова, В. И. Жуковского, А. Ф. Клейменова, А. Ф. Ко-ноненко, Дж. Круза, В. Н. Лагунова, Дж. Лейтмана, С. В. Лутманова, О. А. Малафеева, Г. Олсдера, А. Ори, Л. А. Петросяна, А. А. Чикрия, С. В. Чистякова и многих других. Постановки задач, используемые методы и приемы их решения отличаются большим разнообразием, но общими являются вопросы определения понятия решения, теоремы существования решений, необходимые и достаточные условия оптимальности, методы построения решений. Многие понятия решений, введенные в статических играх, обобщаются на динамические игры. В частности, это относится к равновесному по Нэшу решению, решению по Штакельбергу. Кроме того, следует отметить, что большое число работ посвящено линейно-квадратичным играм.

Среди перечисленных авторов существенное влияние на текущее исследование и его методологию оказали работы А. Ф. Кононенко, Л. А. Петросяна и А. Ф. Клейменова. Например, для игры двух лиц

А. Ф. Кононенко/7/ устанавливает необходимые условия существования по Нэшу решения в классе позиционных стратегий. Там же устанавливаются достаточные условия, которые почти совпадают с необходимыми. В этой же работе описана структура равновесных по Нэшу решений, использующих идею Ю. Б. Гермеера о применении стратегий наказания. Структура решений основана на совместном выборе игроками взаимовыгодной траектории, реализуемой с помощью программных управлений, и на применении позиционных стратегий наказания в случае отклонения игрока от выбранной траектории. При этом факт отклонения партнера каждый игрок устанавливает по информации о текущем фазовом векторе системы. Теорема о достаточных условиях фактически является теоремой существования равновесных по Нэшу решений.

Очень важным является условие динамической устойчивости решений в неантагонистической игре, введенное Л. А. Петросяном/8/.

В работах А. Ф. Клейменова/9/ получены следующие результаты, послужившие теоретическим фундаментом предлагаемой диссертации: 1) необходимые, а также достаточные условия существования решения по Штакельбергу, 2) описание решения по Штакельбергу в терминах решений нестандартной задачи оптимального управления.

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

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

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

Методы исследования. Исследования проводятся в рамках подхода, разрабатываемого в научной школе Н. Н. Красовского по оптимальному управлению и дифференциальным играм. Оптимальные стратегии в играх Штакельберга строятся на основе решений соответствующих нестандартных задач оптимального управления/9/. Алгоритмы программ основываются на дискретном представлении времени, а множеств из Я? — в виде многоугольников на плоскости, к которым применяются теоретико-множественные операции: объединения, пересечения, алгебраической суммы. Некоторые алгоритмы, используемые в диссертации, опираются на разработки В. Н. Ушакова и В. С. Пацко и их учеников. Научная новизна.

1. Найдено аналитическое решение одной иерархической динамической игры Штакельберга двух лиц с помехой.

2. Разработан алгоритм, построения численных решений для линейных игр Штакельберга с цилиндрическим показателями качества управления игроков.

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

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

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

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

Положения, выносимые на защиту:

1. Найдены решения двух вариантов одной игры Штакельберга, динамика которой описывается уравнением простых движений при наличии помехи.

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

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

Структура, объем и содержание. Диссертация состоит из введения, трех глав и списка литературы. Общий объем диссертации составляет 128 страниц, библиография включает 65 наименований, иллюстративный материал насчитывает 15 рисунков.

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

1. Красовский Н. Н. Управление динамической системой.— М.: Наука, 1985. - 520 с.

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

3. Понтрягин Л. С. Линейные дифференциальные игры преследования // Мат. Сб.- 1980.- Т. 112, № 3.- С. 307-330.

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

5. Нэш Д. Бескоалиционные игры // Матричные игры. — М.: Физматгиз, 1961.-С. 205-221.

6. Stackelberg Н. V. The Theory of Market Economy. — Hodge: London, 1952.

7. Кононенко А. Ф. О равновесных позиционных стратегиях в неантагонистических дифференциальных играх // Докл. АН СССР. — 1976.— Т. 231, № 2.-С. 285-288.

8. Петросян Л. А. Устойчивость решений в дифференциальных играх со многими участниками // Вестн. ЛГУ. — 1977. — № 19. — С. 46-52.

9. Клейменов А. Ф. Неантагонистические позиционные дифференциальные игры. — Екатеринбург: Наука. Уральское отделение, 1993. — 185 с.

10. Вайсблат П. В., Клейменов А. Ф. Решение одной иерархической дифференциальной игры двух лиц // Управление с гарантированным результатом. 1987. - С. 15-27.И. Krasovskii N. N., Subbotin A. I. Game-Theoretical Control Problems.— Springer-Verlag: N.Y, 1988.

11. Клейменов А., Осипов С. И. Построение позиционных оптимальных стратегий в одной иерархической динамической игре // Устойчивость и нелинейные колебания. — Свердловск, 1988. — С. 35-45.

12. Kleimenov A., Osipov S. Stackelberg positional strategies in a two-person hierarchical differential game with disturbance // 10th Int. Symp. on Dynamic games and Applications, St-Petersburg. — 2002. — Vol. 1. — Pp. 421426.

13. Клейменов А. Ф., Осипов С. И. Численный метод решения одного класса иерархических дифференциальных игр двух лиц // Оптимальное управление. Геометрия и анализ. — Кемерово, 1988. — С. 12.

14. Осипов С. И. Алгоритм построения алгебраической суммы невыпуклого односвязного и выпуклого многоугольников // Проблемы теоретической и прикладной математики. — Свердловск, 1989.— С. 11-12.

15. Осипов С. И. Об одном алгоритме построения решений иерархической дифференциальной игры двух лиц. — // VII Всесоюзная конференция. Управление в механических системах. — Свердловск. — 1990.— С. 8081.

16. Осипов С. И. Численное построение решений одного класса иерархических линейных дифференциальных игр на плоскости // Устойчивость и нелинейные колебания. — Свердловск, 1991.— С. 73-78.

17. Kleimenov A., Osipov S. Computation of Stackelberg trajectories in a class of linear differential games on pane // ICM Millenium Lectures on Games, Edt. by L. Petrosyan and D. Yeung,.— Berlin: Springer-Verlag, 2003.— Pp. 391-396.

18. Осипов С. И. О реализации алгоритма построения решений для класса иерархических игр Штакельберга // Устойчивость, управление и моделирование динамических систем: Сб. научн. трудов. — Екатеринбург: УрГУПС, 2006. С. 60-61. - № 54 (137).

19. Численное решение одной иерархической дифференциальной игры двух лиц / А. Ф. Клейменов, С. И. Осипов, А. С. Черепов, Д. Р. Кувшинов // Известия Уральского государственного университета. (Математика и механика. Вып. 10. ). — 2006. — № 46. — С. 160-170.

20. Krasovskii A. N., Krasovskii N. N. Control under Lack of Information.— Birkhauser: Berlin, 1995.

21. Клейменов А. Ф. К теории иерархических дифференциальных игрдвух лиц.- Свердловск, 1985,- 67 е.- (Препр./ УНЦ АН СССР. ИММ;.

22. Красовский А. Н. Некоторые задачи игрового управления: Учеб. пособие.— Свердловск: Уральский госуниверситет, 1984. — 99 с.

23. Колмогоров А. #., Фомин С. В. Элементы теории функций и функционального анализа. — М.: Наука, 1976.

24. Субботин А. И., Ченцов А. Г. Оптимизация гарантии в задачах управления. М.: Наука, 1981. - 288 с.

25. Алгоритмы и программы решения линейных дифференциальных игр. Свердловск: ИММ УНЦ АН СССР, 1984. - 296 с.

26. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение: Пер. с англ. М.: Мир, 1989. - 478 с.

27. Пшеничный Б. Н., Сагайдак М. И. О дифференциальных играх с фиксированным временем // Кибернетика. — 1970. — Т. 2. — С. 54-63.

28. Пономарев А. П. Оценка погрешности численного метода построения альтернативного интеграла Понтрягина // Вестник Московского университета. Сер. Выч. мат. и кибернетика. — 1978. — Т. 15, № 4. — С. 37-43.

29. Guibas L. J., Ramshaw L., Stolfi J. A kinetic framework for computational geometry // Proc. 24th Annu. IEEE Sympos. Found. Comput. Sci. — 1983.-Pp. 100-111.

30. Schapira P. Operations on constructible functions // Journal of Pure and Applied, Algebra1991.- Vol. 12.- Pp. 83-93.

31. Ramkumar, G. D. Tracings and their convolution: Theory and applications: Ph.D. thesis / Stanford University. — Dept. Comput. Sci., Stanford Univ. Stanford, CA, 1998.-March.

32. Lee I.-K., Kim M.-S., Elber G. Polynomial/rational approximation of Minkowski sum boundary curves // Graphical Models and Image Processing. 1998. - March. - Vol. 60, no. 2. - Pp. 136-165.

33. Bajaj C., Kim M.-S. Generation of configuration space obstacles: The case of moving algebraic curves // Algorithmica.— 1989.— Vol. 4, no. 2.— Pp. 157-172.

34. Gritzmann P., Sturmfeld B. Minkowski addition of poly topes: Computational complexity and applications // SIAM J. Discrete Math. — 1993.— Vol. 6. Pp. 246-269.

35. Guibas L. J., Sharir M., Sifrony S. On the general motion planning problem with two degrees of freedom // Discrete Comput. Geom. — 1989. — Vol. 4. — Pp. 491-521.

36. The complexity of a single face of a Minkowski sum. / S. Har-Peled, T. M. Chan, B. Aronov et al. // Proc. 7th Canad. Conf. Comput. Geom. 1995. - Pp. 91-96.

37. Кнут, Д. Е. Искусство программирования для ЭВМ. Т. 3: Сортировка и поиск. — М.: Мир, 1978. — 844 с.

38. Milenkovic V. J. Robust polygon modeling // Comput. Aided. Design.— 1993.-Vol. 25, no. 9.

39. Milenkovic V. J. Practical methods for set operations on polygons using exact arithmetic // Proc. 7th Canad. Conf. Comput. Geom.— 1995.— Pp. 55-60.

40. Milenkovic V. J. Shortest path geometric rounding. — Manuscript. — 1995.

41. Hobby J. Practical segment intersection with finite precision output.— Manuscript. — 1994.

42. Леонов M. В., Никитин А. Г. Эффективный алгоритм, реализующий замкнутый набор булевых операций над множествами многоугольников на плоскости. — Новосибирск, 1997. — (Препр./ СО РАН. Ин-т Систем Информатики; 46).

43. Risler J.-J. Placement of curved polygons: Report 91-2.— Laboratoire de Mathematiques, Ecole Normale Superieure, UA 762 du CNRS: LEMENS, 1991.

44. Gritzmann P., Sturmfeld B. Minkowski addition of polytopes: Computational complexity and applications. // SIAM J. Discrete Math. — 1993. — Vol. 6. Pp. 246-269.

45. Kaul A., O'Connor M. A., Srinivasan V. Computing Minkowski sums of regular polygons. // Proc. 3th Canad. Conf. Comput. Geom.— 1991. — Pp. 74-77.

46. Kaul A., O'Connor M. A. Computing Minkowski sums of regular polyhe-dra.: Report RC 18891 (82557) 5/12/93. Yorktown Heights, NY 10598: IBM T.J. Watson Research Center, 1992.

47. Guibas L. J., Seidel R. Computing convolutions by reciprocal search // Discrete Comp. Geom. 1987. - Vol. 2. - Pp. 175-193.

48. Chan T. M. A simple trapezoid sweep algorithm for reporting red/blue segment intersections. // Proc. 3th Canad. Conf. Comput. Geom. — 1994. — Pp. 263-268.

49. Fmke U., Hinrichs K. Overlaying simply connected planar subdivisions in linear time // Proc. 11th Annu. ACM Sympos. Comput. Geom. — 1995. — Pp. 119-126.

50. Edelsbrunner H. Algebraic decompositions of non-convex polyhedra // Proc. 36th Annu. IEEE Sympos. Found. Comput. Sei. 1995,- P. Unknown.

51. Ramkumar G. D. An algorithm to compute the Minkowski sum outer-face of two simple polygons // Proc. 12th Annu. ACM Sympos. Comput. Geom. 1996.-Pp. 234-241.

52. Bäsch J., Guibas L. J., Ramkumar G. D. Reporting red-blue intersections between two sets of connected line segments // Proc 4th Annu. European Sympos. Algorithms. — Vol. 1136 of Lecture Notes Comput. Sei — Springer-Verlag, 1996. Pp. 302-319.

53. Polyhedral tracings and their convolution / J. Bäsch, L. J. Guibas,G. D. Ramkumar, L. Ramshaw // Proc. 2nd Workshop on Algorithmic Foundations of Robotics. — 1996.

54. Вахрушев В., Тарасьев A. M., Ушаков В. Н. Алгоритм построения пересечения и объединения множеств на плоскости / / Управление с гарантированным результатом. — Свердловск: ИММ УНЦ АН СССР, 1987. — С. 28-36.

55. Bentley J. L., Ottmann Т. A. Algorithms for reporting and counting geometric intersections // IEEE Transactions on Computers.— 1979. — no. 2. Pp. 643-647.

56. Computer Graphics: Principles and Practice. / J. D. Foley, A. V. Dam, S. Feiner, J. Huges. — Addison-Wesley, Reading, MA, 1990.

57. Weiler K. Polygon comparison using a graph representation // Comput. Graph. 1980. - Vol. 14, no. 3. - Pp. 10-18.

58. Weiler K., Atherton P. Hidden surface removal using polygon area sorting // Comput. Graph. 1977,- Vol. 11, no. 2. - Pp. 214-222.

59. Schutte K. Knowledge Based Recognition of Man Made Objects: Ph.D. thesis / University of Twente. — 1994.

60. Schutte K. An edge labeling approach to concave polygon clipping.— Manuscript. — 1995.

61. Брукс Ф. Мифический человеко-месяц или как создаются программные системы. — М.: Символ-Плюс, 2006. — 304 с.

62. Proc. 7th Canad. Conf. Comput. Geom. — 1995.