автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Численное построение решений в классе неантагонистических позиционных дифференциальных игр

На правах рукописи

Кувшинов Дмитрий Рустамович

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

05.13.18 - Математическое моделирование, численные методы и комплексы

программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

2 1 ОКТ Ш

Екатеринбург - 2010

004610981

Работа выполнена на кафедре механики и математического моделирования ГОУ ВПО "Уральский государственный университет им. А. М. Горького".

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

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

Анатолий Федорович Клейменов

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

Виктор Иванович Ухоботов

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

Андрей Федорович Шориков

ГОУ ВПО "Удмуртский государственный

университет"

. 10„ ок^р^ 2010 г_ в 4500

Защита состоится « *-» ^ 1Ч'"Л'Г А '¿иИ) г. в Э — на заседании диссертационного совета Д 212.286.10 при ГОУ ВПО "Уральский государственный университет им. А. М. Горького по адресу: 620000, г. Екатеринбург, пр. Ленина 51, комн. 248.

С диссертацией можно ознакомиться в научной библиотеке ГОУ ВПО "Уральский государственный университет им. А. М. Горького".

Автореферат разосла

2010 г.

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

А? ^

доктор физико-математических наук, профессор ' В. Г Пименов

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

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

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

Современный облик теории дифференциальных игр сформировался в значительной степени под влиянием работ отечественных и зарубежных математиков Р. Айзекса1, Н. Н. Красовского2,3, Л. С. Понтрягина4, У. Флеминга.

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

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

1 .4 <1<гк< Р .Деффс^еншмлмп.'е ш р|,: М.: Мир. 1967.

' К/шсовский Я. II., Суббчпчш И. ГЬттционные дифференциальные игры. М.: Наука. 1974. ' Красмаг.кий Я. Н. Управление динамической системой. М.: Наука, 1985. ' [[ошп Л, С. ЛинеГтые л мф(|х '¡мч ч ¡налы I ыо ;1 г ¡л .1 преследования /./ Мат гГ) 19811. Т. 112, С. .1117 МО.

риваются равновесное решение по Нашу' и решения по Штакельбергу6.

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

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

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

Среди работ перечисленных авторов существенное влияние на методологию текущего исследования оказали работы А. Ф. Кононенко, Л. А. Петросяна и А. Ф. Клейменова. Так, для игры двух лиц А. Ф. Кононенко' устанавливает необходимые условия существования решения по Нэшу в классе позиционных стратегий. Там же устанавливаются достаточные условия, почти совпадающие с необходимыми. В этой же работе описана структура равновесных по Нэшу решений, использующих идею Ю. Б. Гермейера о применении стратегий наказания. Структура решений основана на совместном выборе игроками взаимовыгодной траектории, реализуемой с помощью программных управлений, а также на применении позиционных стратегий, составляющих седловую точку во вспомогательных антагонистических играх, в случае отклонения игрока от выбран' H.wi Дж. Б<''Ки.!.:пш>'( и г'1 г .и ■ игры // Матричные игры. М.: Фи!\1.п[ И1. 19G1. С. 20")-221.

И. von Stnckdbery The Thro.' v of [!;<■ ,\Jai h't Economy. Lomkm: Hodga ]902.

7 Кононенко .4. Ф О рапнптгных пщицН' »n :i t.r\ стр;т'П<>|Х и ш'гш'пшжистических дифференциальных играх Ц Докл. АН СССР. 197«. Т. '231, ,\»2. С. 285-Ш.

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

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

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

На этой основе С. И. Осиновым10 был разработан численный алгоритм построения решений по Штакельбергу в линейной игре двух лиц с цилиндрическими терминальными показателями качества.

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

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

Пг.трасян Л. .4. ^'с-гойчино.':':!, ¡»-(пений и дифференциации,]* играх со многими участниками // Вестник ЛГУ. 1977. .4*19. С. 46-52.

н Кл':йл1?но<1 А. Ф. Н"антагониг: и'1'.ч ы:с пичиционние диффе1>сн1|,и;1льние игры. Екатеринбург: Наука. 1993.

<)(пп<1>1 С. И. О реализации алгоритма построения решений для класса иерархических игр Шта-кельберга // Автоматика и телемеханика. 20! 17 .VII. С. 195-208.

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

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

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

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

в статье А. М. Тарасьева, В. Н. Ушакова и А. П. Хрипунова11.

Разработанный в диссертации алгоритм нахождения равновесных по Нэ-шу решений является развитием идеи, заложенной при разработке алгоритма С. И. Осипова10 построения решений Штакельберга.

Программная реализация опирается на парадигму обобщенного программирования в рамках языка программирования С++. Проектирование основано на идиоме «концепт-модель» и использовании политик для отделения концептуально-независимых компонент12.

Научная новизна.

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

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

3. Алгоритм численного построения решений Штакельберга разработан для более общей постановки, чем в оригинальной работе10.

4. Создана программная реализация разработанных алгоритмов в виде расширяемой библиотеки программных компонент с применением современных подходов к проектированию программных комплексов.

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

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

11 Тариа^ч .4. М.. Ушпкон В. II., Хрпгцрыв А. П. Об одном вычислительном алгоритме )к'Ш<;ния игровых -вдач у[;р;п:л('|:ня . Прикда'тан математик;! и механика. 1987. Т. 51. С. 216-222.

^ Алскглпдресжу А. Современное проектирование на С' ^ М , СПб.; Киев: Пчддгги.гкнй дом «Вильяме*. 21)02.

управляемых систем, которые могут быть использованы независимо от основного алгоритма.

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

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

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

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

1. Международная научная конференция «Устойчивость, управление и моделирование динамических систем», Екатеринбург, УрГУПС, 15-17 ноября, 2006.

2. The Second International Conference "Game Theory and Management", Gradúate School of Management, St. Petersburg State University, 26-27 июня, 2008.

3. International Joint Conferences on Computer, Information, and System Sciences, and Engineering (CISSE), 5-13 декабря, 2008.

4. 40-я Всероссийская молодежная школа-конференция «Проблемы теоретической и прикладной математики», Екатеринбург, 26-30 января, 2009.

5. САО'09, IFAC Workshop on Control Applications of Optimisation, University of Jyváskylá, Agora, Finland, 6-8 мая, 2009.

6. Всероссийская конференция «Динамические системы, управление и нано-мехэника», Ижевск, УдГУ, 24-28 июня, 2009.

7. Международная конференция «Актуальные проблемы теории устойчивости и управления», Екатеринбург, ИММ УрО РАН, 21-26 сентября, 2009.

Содержание работы

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

Глава 1 состоит из шести разделов и содержит теоретический материал, служащий фундаментом разрабатываемых алгоритмов.

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

х =/,({,х,и)+ /2({,х,у), х(£0) = Хо, (1)

где х € К" — фазовый вектор, и 6 Р С К'' — управление первого игрока, V 6 <3 С К'' — управление второго игрока. Терминальные показатели качества игроков заданы функциями а, : К" >->■ К. Приведены базовые определения (чистой позиционной стратегии, законов управления игроков, движений). Перечислены основные условия, наложенные на систему, выполнение которых подразумевается в дальнейшем.

В разделе 1 2 рассматриваются антагонистические дифференциальные игры Г,-, динамика которых описывается уравнением (1). В игре Г,- игрок г максимизирует свой выигрыш <т;(х(г?)), а игрок (3 — г) ему противодействует При сделанных предположениях в играх Г,, г — 1,2, существуют непрерывные цены и универсальные оптимальные стратегии, которые используются в дальнейшем при описании структуры решения.

В разделе 1.3 дано определение равновесного по Нэшу решения игры (/У-ре-шения). .'У-решение характеризуется тем свойством, что игрок, уклоняющийся в одиночку от отслеживания этого решения, не может увеличить свой выигрыш. Приводятся необходимые, а также достаточные условия, которым удовлетворяют траектории, порожденные Л'-решениями. Эти условия сформулированы в терминах решений нестандартной задачи управления, в которой требует-

ся, чтобы функции цены ^■¿(¿,х(/.))1 г = 1,2, вычисленные вдоль траектории, при Ь = $ достигали максимума. Приводится структура позиционных стратегий, доставляющих Лг-решения. Основу этих стратегий составляют решения упомянутой нестандартной задачи управления, которые определяют //-траектории. При выходе позиции изе-трубки, построенной вдоль //-траектории, вследствие уклонения одного из игроков от отслеживания траектории предусматривается наказание уклониста с помощью оптимальной стратегии е соответствующей антагонистической игре Гг-

Раздел 1.4 содержит определение неулучшаемого равновесного по Нэшу решения (Р"-решения). При переходе от Р*-решения к любому другому /"-решению строгое увеличение выигрыша одного из игроков возможно лишь при строгом уменьшении выигрыша другого.

Раздел 1.5 содержит определение решений по Штакельбергу ^¿-решений, i = 1,2). 5;-решение определяется при введении дополнительных предположений: игрок называемый лидером, объявляет свою стратегию другому игроку до начала игры, а игрок (3 — ?*), называемый ведомым, зная стратегию игрока г, выбирает рациональную стратегию из условия максимизации своего выигрыша. Приводятся условия на траектории, порожденные ^¿-решениями. Они сформулированы в терминах решений нестандартной задачи оптимального управления, в которой лидер максимизирует показателытДх^)) на траекториях, вдоль которых функция цены ведомого 7¿-¡(1, х(0) при I = '(9 достигает максимума. Такие траектории в работе называются допустимыми.

Заметим, что решения того или иного типа, доставляющие обоим игрокам одни и те же значения выигрыша, в работе считаются эквивалентными.

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

Глава 2 состоит из семи разделов и содержит описание алгоритмов построения решений в неантагонистических играх.

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

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

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

В алгоритмах построения решений всех рассматриваемых типов можно выделить две части. Первую часть алгоритма составляет решение задачи поиска концов траекторий, удовлетворяющих условиям в нестандартных задачах (оптимального) управления. Вторую часть, названную в диссертации Т-алгоритмом, составляет решение задачи восстановления траектории по ее конечной точке. Эта вторая часть по сути не зависит от того, решение какого типа требуется найти, но связана с первой частью понятием множества незапрещенных позиций (каждому результирующему концу траектории соответствует свое множество незапрещенных позиций), которое приводится ниже Заметим, что в случае поиска решений по Нэшу первая часть состоит в построении набора точек, приближающего множество концов Л^-траекторий. В таком случае возможен либо прогон второй части для всех полученных точек с тем, чтобы получить аппроксимацию множества Л'-траекторий, либо выбор некоторых из них в соответствии с каким-то критерием.

Таким образом, первая часть алгоритма определяется типом искомых решений. Предлагаются три варианта: 5-алгоритм (поиск конечной точки 5;-траекто-рии), Р-алгоритм (построение аппроксимации множества концов всехР'-траекто-рий) и ^-алгоритм (построение аппроксимации множества концов всехЛ'-траек-торий).

Введем следующие дифференциальные позиционные игры сближения-уклонения Гу, / = 1,2, с € К, с динамикой (1). В игре Г,-' цель игрока г состоит в приведении фазового вектора х(г?) на множество

в то время, как другой игрок препятствует ему. В соответствии с теоремой об альтернативе-' из теории антагонистических позиционных дифференциальных игр получаем, что для всех позиций (£,х), попавших внутрь максимального стабильного моста И7,', в игре Г'/ справедливо условие -,((., х) > с; в то же время для позиций, лежащих вне моста И'-' или на его поверхности, справедливо усло-

вне 7,(£,x) ^ с. что позволяет использовать известные процедуры2'3,11 построения максимальных стабильных мостов в качестве составной части предлагаемых алгоритмов.

Множество незапрещенных позиций строится как множество всех позиций, через которые проходят траектории системы, исходящие из позиции (£о,Хо) и не проходящие через внутренность максимального стабильного моста HJ' (в случае ^-алгоритма) или объединения мостов WpUW.p (в случае Р- и N-алгоритмов), для некоторых значений с, е.), c-j. Работа S-, Р- и jV-алгоритмов состоит в переборе этих значений и выборе конечных точек (при t = il) искомых траекторий из строимых множеств незапрещенных позиций.

Кроме общего случая динамики (1), в диссертации рассматривались игры с динамиками

X = /о (t,x) + A(£,x)u + B(f,x)v, (2)

X = /oft, x) 4- fi(t, u) + f2(t, v). (3)

x = A(t)x + B(t)u + C(t)v, (4)

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

Раздел 2.2 посвящен алгоритмам численного построения множеств позиционного поглощения (являющихся максимальными стабильными мостами в рассматриваемых постановках задач).

Во-первых, это И'*-алгоритм из статьи11, используемый для динамик (1), (2). Формально его можно представить в виде следующей попятной процедуры

W?N = Mf,

v€Q u£(->

= У { x £ К" | x + h(fi(t, x, u) + /-¿(t, x, v)) = w }.

weir

Во-вторых, это W+-алгоритм, получаемый из И'"-алгоритма путем адаптирования последнего к динамике (3).

¡{'"'"-алгоритм основан на применении операций алгебраической суммы и

геометрической разности:

"I.v = Mf,

Wij = { x(w, tj-1. hj) I hj = tj+! -tj, we W[J+l © (-hjF.itj)) 9 hjFzfa) } ,

*(w,t,/i) = {хбГ | x + h/0(i,x) = w}, F,{t) = {Mt, u) 1 u 6 P }, F2(t) = { /2(i, v) | v g Q }.

В разделе 2.3 описаны Р-алгоритм и алгоритмы построения множеств неза-прещенных позиций (построенные по аналогии с И"- и И^-алгоритмами).

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

Алгоритм представлен в виде внешнего цикла, поочередно выбирающего целевые выигрыши то первого, то второго игроков, и внутреннего цикла, ищущего максимальный выигрыш одного игрока при фиксированном выигрыше другого игрока методом, напоминающим метод простых итераций. Далее приведен ЛА-алгоритм.

Внешний цикл. Будем считать, что известны с■ ~ '/¿(t, хо). Эти значения можно получить, например, в ходе вычисления S,-решений 5-алгоритмом.

1. Пусть 5д' (г = 1,2) — значения шагов, используемые при переборе значений выигрышей игроков. Начальные значения целевых выигрышей/?' = с*.

2. Пусть К = 0 — строимый набор концов Д/-траекторий.

3. Пусть flagi — flayi — continue. — флаги действия внешнего цикла (варианты значений: continue, supplement, stop).

4. Для г = 1,2, если flag, / stop, то (/¿ш/;,х') := ВнутреннийЦикл(/,д').

5. Если flay] = stop A flag-t — stop, либо стдх'-) < д1 А ^(х1) < д2, то переход к п. 8.

6. Для г = 1,2:

• если /Zap, = supplement, то

- пополним К -ф= х',

- для 1 ^ s < — найдем X*— концы А/-траекторий, доставляющих выигрыши c-i = д' и сз_,- = <тз_;(х*) — aSg3~'. построив соответствующую этим значениям выигрышей Д/-трубку

и взяв X;s = G'e"C2 Л М^1 П М?, пополним К <= Х[„

• если flag; ф stop, то изменим д' :— д1 + 6д'.

7. Повтор с л. 4.

8. Возвращаем К, выход.

Внутренний цикл. Пусть зафиксированы индекс игрока г и значение выигрыша с, игрока г. На дМ¿' можно выбрать точку х', доставляющую наибольший выигрыш игроку (3 — г), обозначим с|..,(с,) = аз-;(х') = max гг)..,(х).

1. Пусть задан параметр точности е'х. Положим х' = х', с3_; ~ гЪ-/(с,:). Построим мост Wj*.

2. Если = 0, то возвращаем (stop, любая точка).

3. Если Xy £ то возвращаем (continue, любая точка).

4. Строим мост WJ3;/, предварительно добавляя вершину х' в границу аппроксимации целевого множества ЭМ^'.

5. Если хо G Wто возвращаем (supplement, х')

6. Строим множество незапрещенных позиций G'1'1-, используя W'' и Wijt'/. Положим D := G$',0i П W;;.,.

7. Если D ^ 0, то

• выберем х" = argmax<73_,-(x);

xgD

• если |oj_j — о"з-/(х'»)| < i'x, то возвращаем (supplement,х'^);

• с-з-i : = C73_i(x'); х' :— х'„ повтор с п. 4;

8. Иначе возвращаем (stop, любая точка) — останов внешнего цикла для игрока i.

В разделе 2.5 описан алгоритм построения решений по Штакельбергу.

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

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

Глава 3 состоит из трех разделов и посвящена программной реализации разработанных алгоритмов.

В разделе 3.1 описан общий подход к построению библиотеки программных компонентов, характерный для современных библиотек на языке С++.

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

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

Глава 4 состоит из двух разделов и содержит два примера численного расчета.

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

+ ¿(0)=£о, £(0) = (о-

Пусть зафиксированы ограничения на выбор управлений игроками: ||и|( ^ |М! ^ V. Каждый из игроков стремится привести систему в конечный момент

игры I = $ как можно ближе к своей целевой точке а'1' (г = 1,2). После применения замены2 рассматривается система второго порядка.

x = (tf-t)(u + v), х(0) = х<, = & H-tfÇo-

Поскольку случай ц = — 1 рассматривался аналитическими методами9, то это дает возможность определить погрешность численного решения. В диссертации приведена погрешность вычисления концов Р*-траекторий для одного набора параметров.

Для иллюстрации работы /V-алгоритма были выбраны следующие значения параметров игры: тЭ = 2. целевые точки игроков а'1' = (—2.5,4.5), а'2) = (3.5,3.5), £„ = (-0.5, -0.5), = (0.5,0.25). Отсюда получаем х0 = (0.5,0). Использовалось разбиение временного отрезка с постоянным шагом 0.005. Были выбраны шаги 5g1 = 5д2 = 0.08.

На рис. 1 и 2 приведены результаты численного расчета для значений д = 1.3, и — 0.7. На рис. 1 черными точками показана аппроксимация множества концов всех Л/-траекторий, на рис. 2 представлено отображение этого множества в плоскость (/,,/,) значений выигрышей игроков. Серой ломаной и на рис. 1, и на рис. 2 соединены (и таким образом выделены) концы Р"-траекторий. Кроме того, на рис. 1 приведены пять Р'-траекторий (в координатах (^ь^з). полученные интегрированием управлений, вычисленных при расчете траекторий в координатах {х\,х2))- Параметр точности t^ был выбран равным 5 • Ю-"1. Кроме того, на каждом шаге построения множества незапрещенных позиций производилось прореживание контуров с удалением ребер длиной менее 10

Второй пример (раздел 4.2) описывается нелинейной динамикой

. xi + 2

X} ----¿'1 4- Х'2 + и +

j.'i + 1

. -t-. + 2

Х-> = X]--Х2 + OU + V,

XI + 1

xq = (3,2).

Ограничения на управления игроков: |и| ^ 1, |и| 1.

Цели игроков состоят в максимизации следующих показателей:

/!(«(•)• v(0) = ffi(x(U)) = -1 - 0.02iï(tf) + + Л2(1У)),

/,(«(■),■(.•(■)) = a2(x(J)) - - 1 - 0.02«(tf) + ln(.;'i(¿!) + x2(i))).

Уравнения движения и показатели игроков взяты из статьи Красовского Н. А , Тарасьева А. М.13, однако там решалась другая задача и, к тому же, на полубесконечном интервале времени

Параметры точности: шаг по времени /г. — 2 • 10~3, минимальная длина ребра 4 -10 , длина ребра ломаной, аппроксимирующей линию уровня показателя качества 0.2, шаги по выигрышам бдд = 6до = 0.045, ¿(¿¡ц = = 3 • Ю-3, критерий останова внутреннего цикла е^ = = 2 • 10~3.

На рис. 3 показано множество концов допустимых траекторий, полученных при поиске ¿^-решения (конец ¿^-траектории отмечен символом ,$1). На рис. 4 показано множество концов ДГ-траекторий, серой ломаной соединены (и таким образом выделены) концы Р*-траекторий. На рис. 5 представлено отображение этого множества в плоскость (/ь/з) значений выигрышей игроков.

1:1 Крлсовскнй И .4,. Тарасмш .4. Л/. Поиск точек максимума векторного критерия с декомпотици-онными свойствами Труди МММ 5/рО РАН. 21109. Т. 15 >4. С.107-182

• \

: : -Ч

Л

3.5 3.0 2.J 2.0 1.5

Рис. 2. Вьгш-рышм на /V-решениях, (i = 1.3. и — 0.7.

Рис. 3. Множество концов 5.-допустимых траекторий.

\ /

/

2 • 3

Рис. 4. Множество концов Л'-траекторий.

Рис. 5. Выигрыши на Лг-решспиях.

Основные результаты

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

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

2. Разработан алгоритм, строящий только неулучшаемые равновесные по Нэшу решения с меньшими затратами машинного времени и памяти (по сравнению с алгоритмом из п. 1).

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

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

Список публикаций

Основные результаты диссертации опубликованы в следующих работах.

Статьи, опубликованные в ведущих рецензируемых научных журналах и изданиях, определенных ВАК:

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

2. Кувшинов Д. Р. Алгоритм численного построения решений по Нэшу в позиционной дифференциальной игре двух лиц. // Вестник Удмуртского ун-та. — 2009, № 3 (Математика. Механика. Компьютерные науки). — С. 81-90.

3. Клейменов А. Ф, Кувшинов Д. Р., Осипов С. И. Численное построение решений Нэша и Штакельберга в линейной неантагонистической позиционной дифференциальной игре двух лиц. // Труды И ММ УрО РАН. Том 15 № 4. - Екатеринбург: 2009. - С 120-133.

Другие публикации:

5. Кувшинов Д. Р. Демонстрация численного алгоритма построения решения Штакельберга для класса неантагонистических дифференциальных игр на примере задачи, имеющей аналитическое решение. // Устойчивость, управление и моделирование динамических систем: Сб. научн. трудов под нзучн. ред. Г. А. Тимофеевой. Материалы Международн. научн. конференции (15-17 нояб., 2006). - Екатеринбург: УрГУПС. - №54 (137). - 2006.

- С. 50.

6. Kleimenov A. F., Osipov S. /., Kuvshinov D. R. Numerical Construction of Nash and Stackelberg trajectories in a linear positional differential game. // Межд. Конф. «Дифференциальные уравнения и топология», поев. 100-летию со дня рождения Л.С.Понтрягина (17 — 22 июня 2008). Тез. докл. — М.: 2008.

- С. 259.

7 Kleimenov A. F., Osipov S. /., Kuvshinov D. R. Numerical Construction of Nash Trajectories in a Two-Person Non Zero-sum Linear Positional Differential Game. // The 2nd Int. Conf. "Game Theory and Management". Abstracts. / Ed. by L. A. Petrosjan, N. A. Zenkevich. - St.-Petersburg: 2008. - Pp. 98-101.

8. Кувшинов Д. P. Численное построение нэшевских решений в линейной позиционной дифференциальной игре двух лиц. // Тез. докл. 40-й Всероссийской молодежной шк.-конф. «Проблемы теоретической и прикладной математики» (26 - 30 янв. 2009). - Екатеринбург: 2009. - С. 236-240.

9. Kleimenov A. F., Osipov S. /., Kuvshinov D. R. A Numerical Construction Algorithm of Nash and Stackelberg Solutions for Two-Person Non-Zero Sum Linear Positional Differential Games. // CAO'09, IFAC Workshop on Control Appl, of Optimisation (May 6 - 8, 2009). Abstracts / Univ. of Jyvaskyla. — Agora, Finland: 2009. - Pp. 28-29.

10. Kleimenov A. F., Osipov S. I., Kuvshinov D. R Nash and Stackelberg Solutions Numerical Construction in a Two-Person Nonantagonistic Linear Positional Differential Game. // Contributions to Game Theory and Management. Vol. II The Second Int. Conf. "Game Theory and Management" (June 26-27, 2008), St.Petersburg, Russia. Collected papers. / Ed. by L.A. Petrosjan and N.A. Zenkevich. - St.Petersburg: 2009. - Pp. 205-219.

11. Kuvshinov D R. Nash Trajectories Numerical Construction in a Two-Person Non-zero Sum Nonlinear Positional Differential Game. // The 3rd Int. Conf. "Game Theory and Management" ( June 24 — 26, 2009). Abstracts. / Ed. by L.A. Petrosjan and N.A. Zenkevich. — St.Petersburg: 2009. - Pp. 146-149.

12. Кувшинов Д P Алгоритм численного построения решений по Нэшу в позиционной дифференциальной игре двух лиц. //Тез. докл. Всероссийской конф. «Динамическиесистемы, управление и наномеханика» (24-28 июня, 2009). - Ижевск: 2009. - С. 42.

13. Клейменов А. Ф, Кувшинов Д. Р., Осипов С. И. Численное построение решений в неантагонистической дифференциальной игре двух лиц. // Тез. докл. Международн. конф. «Актуальные проблемы теории устойчивости и управления» (21-26 сент., 2009). — Екатеринбург: 2009. — С 84-86.

14. Kleimenov А. F., Osipov S. I., Kuvshinov D. R. A Numerical Construction Algorithm of Nash and Stackelberg Solutions for Two-person Non-zero Sum Linear Positional Differential Games. // Innovations and Advances in Computer Sciences and Engineering. Ed. by T. Sobh. — Springer Netherlands: 2010. — Pp. 249-254.

Введение.

Список обозначений.

Глава 1. Сведения из теории неантагонистических дифференциальных игр.

1.1. Система и траектории.

1.2. Вспомогательные антагонистические игры.

1.3. Равновесное по Нэшу решение.

1.4. Неулучшаемое равновесное по Нэшу решение.

1.5. Решение по Штакельбергу.

1.6. Реализация согласованных ломаных Эйлера, порожденных решениями игры.

Глава 2. Теоретические основы численных алгоритмов и их описание

2.1. Общая идея

2.2. Аппроксимация множеств уровня функции цены антагонистической дифференциальной игры.

2.2.1. И/*-алгоритм

2.2.2. 1У+-алгоритм.

2.3. Неулучшаемые решения по Нэшу.

2.3.1. Внешний цикл.'

2.3.2. Внутренний цикл.

2.3.3. Множество незапрещенных позиций.

2.4. Решения по Нэшу.

2.5. Решение по Штакельбергу.

2.5.1. Внешний цикл.

2.5.2. Множество незапрещенных позиций.

2.6. Восстановление траектории.

2.7. Алгоритмы вычислительной геометрии.

2.7.1. Теоретико-множественные операции.

2.7.2. Алгебраическая сумма.

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

3.1. Общий подход.

3.2. Струкура программной реализации.

3.2.1. Элементы геометрии.

3.2.2. Система.

3.2.3. Задачи и методы решения.

3.2.4. Алгоритмы

3.2.5. Внешний цикл Р-алгоритма.

3.3. Поддержка параллельных вычислений.

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

4.1. Пример 1.

4.1.1. Модельный пример: ц= ь>.

4.1.2. Случай \х ф и.

4.2. Пример 2.

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

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

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

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

Современный облик теории дифференциальных игр сформировался в значительной степени под влиянием работ отечественных и зарубежных математиков Р. Айзекса [1], Н. Н. Красовского [25, 26, 82, 83], Л. С. Понтрягина [42], У. Флеминга.

Крупный вклад в развитие теории дифференциальных игр внесли Э. Г. Альбрехт, М. Барди, В. Д. Батухтин, Е. Н. Баррон, Т. Башар, Р. Беллман, А. Брайтон, Н. Л. Григоренко, Р. В. Гамкрелидзе, В. И. Жуковский, М. И. Зеликин,

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

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

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

Неантагонистическим дифференциальным играм посвящены работы X. Абу-Кандила (Н. Abou-Kandil), Т. Башара (Т. Basar), Н. Н. Данилова, В. И. Жуковского, В. В. Захарова, П. Кардалиге (P. Cardaliaguet), А. Ф. Клейменова, А. Ф. Ко-ноненко, Дж. Круза (J. В. Cruz), В. Н. Лагунова, Дж. Лейтмана (G. Leitmann), С. В. Лутманова, О. А. Малафеева, Г. Олсдера (G. J. Olsder), А. Ори (A. Haurie), Л. А. Петросяна, А. А. Чикрия, С. В. Чистякова, Г. Янка (G. Jank) и других. Необходимо также упомянуть работы М. Фальконе (М. Falcone) и его сотрудников

66, 70] по численным алгоритмам в дифференциальных играх и Д. В. Камзолкина по приближенному вычислению функции цены [15].

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

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

Важным является условие динамической устойчивости решений в неантагонистической игре, введенное Л. А. Петросяном [41].

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

На этой основе С. И. Осиповым [36, 37] был разработан численный алгоритм построения'решений по Штакельбергу в линейной игре двух лиц с цилиндрическими терминальными показателями качества.

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

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

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

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

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

Заметим, что алгоритмы численного решения антагонистических позиционных дифференциальных игр, используемые в предлагаемых алгоритмах построения решений для неантагонистических игр, были разработаны в научных коллективах, руководимых В. Н. Ушаковым и В. С. Пацко. В частности, был использован алгоритм построения множества позиционного поглощения в антагонистической игре с нелинейной динамикой, предложенный в статье А. М. Тарасьева, В. Н. Ушакова и А. П. Хрипунова [51].

Разработанный в диссертации алгоритм нахождения равновесных по Нэшу решений, является развитием идеи, заложенной при разработке алгоритма С. И. Осипова [36] построения решений Штакельберга.

Программная реализация опирается на парадигму обобщенного программирования в рамках языка программирования С++, проектирование основано на идиоме «концепция-модель» и использовании политик для отделения концептуально-независимых компонент [2, 47, 91].

Научная новизна.

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

2. Алгоритм численного построения решений Штакельберга разработан для более общей постановки, чем в оригинальной работе [36].

3. Создана программная реализация разработанных алгоритмов в виде расширяемой библиотеки программных компонент с применением современных подходов к проектированию программных комплексов.

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

Разработанная программная реализация включает в качестве составных компонент ряд других алгоритмов, в частности, алгоритмы построения решений по Штакельбергу, построения множеств; позиционного поглощения в антагонистической дифференциальной игре, построения множеств достижимости, которые могут быть использованы независимо от основного алгоритма. Предусмотрен обобщенный интерфейс (в рамках парадигмы обобщенного программирования, языка С++) для подключения библиотек алгоритмов вычислительной геометрии, служащих фундаментом разрабатываемых алгоритмов построения решений в позиционных дифференциальных играх. '

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

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

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

2. Предложен алгоритм, строящий только неулучшаемые равновесные по Нэ-шу решения с меньшими затратами машинного времени и памяти (по сравнению с алгоритмом из п. 1).

3. Разработана программная реализация алгоритмов построения равновесных по Нэшу решений и решений Штакельберга в виде расширяемой библиотеки программных компонент (классов-шаблонов и функций-шаблонов) с применением современных подходов к проектированию программных комплексов.

4. Показана работоспособность разработанных алгоритмов и их программных реализаций на расчете двух примеров, один из которых ранее изучался аналитическими методами в [16].

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

1. Международная научная конференция «Устойчивость, управление и моделирование динамических систем», Екатеринбург, УрГУПС, 15 - 17 ноября, 2006.

2 The Second International Conference "Game Theory and Management", Gradúate School of Management, St. Petersburg State University, 26 - 27 июня, 2008.

3. International Joint Conferences on Computer, Information, and System Sciences, and Engineering (CISSE), 5-13 декабря, 2008.

4. 40-я Всероссийская молодежная школа-конференция «Проблемы теоретической и прикладной математики», Екатеринбург, 26 - 30 января, 2009.

5. САО'09, IFAC Workshop on Control Applications of Optimisation, University of Jyvaskyla, Agora, Finland, 6-8 мая, 2009.

6. Всероссийская конференция «Динамические системы, управление и наноме-ханика», Ижевск, УдГУ, 24 - 28 июня, 2009,

7. Международная конференция «Актуальные проблемы теории устойчивости и управления», Екатеринбург, ИММ УрО РАН, 21 - 26 сентября, 2009.

Публикации. Основные материалы диссертации опубликованы в 13 работах [19-21, 27-30, 77-81, 85].

В совместных работах [20, 21, 77-81] А. Ф. Клейменову принадлежит постановка задачи, алгоритм построения равновесных по Нэшу решений, основанный на решении последовательности вспомогательных биматричных игр, названный в работах БМ-процедурой (в диссертацию он не был включен), и общее руководство исследованием; в этих же работах С. И. Осипову принадлежит алгоритм построения решений Штакельберга и первая его программная реализация. Кроме того, в [21] Череповым А. С. была проведена предварительная работа по программной реализации алгоритма.

Совместная работа [19], по сути резюмирующая весь цикл работ, содержит обзор алгоритма построения решений Штакельберга С. И. Осипова и ВМ-процедуру А. Ф. Клейменова. Остальные результаты статьи, включая алгоритм построения равновесных по Нэшу решений и вариант для неулучшаемых равновесных по Нэшу решений, получены автором.

Отметим, что в работах 2008 и 2009 годов использовалась программная реализация, созданная полностью автором диссертации на языке С++, с учетом опыта, полученного при работе над результатами, представленными в [21, 27].

В [27] представлены результаты, полученные после перехода на библиотеку GLU в качестве библиотеки алгоритмов вычислительной геометрии.

Работы [28-30, 85] посвящены алгоритму построения равновесных по Нэшу решений, заявленному как основной результат диссертации, при этом работа [29] является основной.

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

Заключение

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

Представляют интерес дальнейшие теоретические изыскания в следующих направлениях.

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

• Увеличение числа игроков сверх двух. Возможно, удастся использовать разработанные алгоритмы как основу для новых алгоритмов с большим числом игроков.

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

Решение подобных задач требует создания новых подходов к построению решений.

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

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

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

Разработанную автором диссертации библиотеку программ (названную GDGT — «Geometrical Differential Game Template Library»1), рассмотренную в главе 3, предполагается разместить на одной из основных площадок разработчиков открытого программного обеспечения в Интернете, а именно SourceForge.net или Google Code, сделав ее доступной по лицензии семейства MIT [87], в соответствии с которой допускается свободное использование ПО без ограничений, включая неограниченное право на использование, копирование, изменение, добавление, публикацию, распространение и сублицензирование.

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

1 Букв, «библиотека шаблонов геометрических дифференциальных игр

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

2. Александреску А. Современное проектирование на С++. — М.; СПб.; Киев: Издательский дом «Вильяме», 2002. — 336 с.

3. Альбрехт Э. Г. Об экстремальных стратегиях в нелинейных дифференцц^ альных играх // Прикл. математика и механика. — 1986.— Т. 50, № 3.—-С. 339-345.

4. Боресков А. В., Харламов А. А. Основы работы с технологией С1ЮА. — ]у . ДМК Пресс, 2010. 232 с.

5. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. — 2 изд. — М.; СПб.: Издательство Бином — Невский Диалект, 1998. 560 с.

6. Буч Г., Рамбо Дою., Джекобсон А. Язык 11МЬ. Руководство пользователя. 2 изд. М.: ДМК Пресс; СПб.: Питер, 2004. - 432 с.

7. Вайсблат П. М., Клейменов А. Ф. Решение одной иерархической дифферец. циальной игры двух лиц // Управление с гарантированным результатом. — Свердловск, 1987. С. 15-27.

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

9. Вержбицкий В. М. Основы численных методов: учебник для вузов. — 2 изд. — М.: Высшая школа, 2005. — 840 с.

10. Данилов Н. Н. Решение задачи динамической устойчивости в кооперативной дифференциальной игре с побочными платежами // Прикладная математика и механика. — 1989. —■ Т. 53, вып. 1. — С. 45-59.

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

12. Использование видеокарт для вычислений, http: / /www. gpgpu. ru/.

13. Камзолкин Д. В. Численный метод приближенного вычисления функции цены для задачи оптимального управления с терминальным функционалом // Вычислительные методы и программирование — 2004. Т. 5, № 2. -С. 121-132.

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

15. Клейменов А. Ф. О решениях в неантагонистической позиционной дифференциальной игре // Прикладная математика и механика, — 1997.— Т. 61, № 5. С. 739-746.

16. Клейменов А. Ф. Различные типы решений в позиционной неантагонистической дифференциальной игре // Вестник Тамбовского ун-та. Серия Естественные и технические науки. — 2007. Вып. 4. — С. 464-466.

17. Клейменов А. Ф, Кувшинов Д. Р., Осипов С. И. Численное построение решений Нэша и Штакельберга в линейной неантагонистической позиционной дифференциальной игре двух лиц // Труды Института математики и механики УрО РАН. 2009. - Т. 15, № 4. - С. 120-133.

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

19. Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа, — 7 изд. — М.: Физматлит, 2004. — 572 с.

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

21. Красовский Н. А., Тарасьев А. М. Поиск точек максимума векторного критерия с декомпозиционными свойствами // Труды Института математики и механики. 2009. - Т. 15, № 4. - С. 167-182.

22. Красовский Н. Н. Управление динамической системой. Задача о минимуме гарантированного результата. — М.: Наука, 1985.— 520 с.

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

24. Кувшинов Д. Р. Алгоритм численного построения решений по Нэшу в позиционной дифференциальной игре двух лиц // Тез. докл. Всероссийской конференции «Динамические системы, управление и наномеханика». — Ижевск: 2009.- С. 42.

25. Кувшинов Д. Р. Алгоритм численного построения решений по Нэшу в позиционной дифференциальной игре двух лиц // Вестник Удмуртского университета (Математика. Механика. Компьютерные науки).— 2009. — № 3.— С. 81-90.

26. Кувшинов Д. Р. Численное построение нэшевских решений в линейной позиционной дифференциальной игре двух лиц // Тез. докл. 40-й Всероссийской молодежной шк.-конф. «Проблемы теоретической и прикладной математики». Екатеринбург: 2009.- С. 236-240.

27. Лагунов В. Н. Игры преследования и введение в теорию игр. — Тверь: Изд-во Твер. гос. ун-та, 1993. — 146 с.

28. Мейерс С. Эффективное использование STL. — СПб.: Питер, 2003.— 224 с.117

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

30. Осипов С. И. Алгоритм построения алгебраической суммы невыпуклого 0д носвязного и выпуклого многоугольников // Проблемы теоретической и Прикладной математики. — Свердловск: ИММ УНЦ АН СССР, 1989. — С. 11—12

31. Осипов С. И. О реализации алгоритма построения решений для класса иерар„хических игр Штакельберга // Автоматика и телемеханика. — 2007.11.-С. 195-208.

32. Осипов С. И. Решение одного класса иерархических дифференциальных игр (методы, алгоритмы, программы): дис. . кандидата физ.-мат. наук.—- Екатеринбург: УрГУ, 2007. 128 с.

33. Пахотинских В. Ю., Ушаков В. Н. Аппроксимация стабильных мостов в дифференциальных играх с ограничениями на фазовый вектор // Изв. Уральского гос. ун-та. 2002. - Т. 26, № 5. - С. 158-169.

34. Петров Н. Н. Об одной задаче группового преследования с фазовыми ограничениями // Изв. вузов. Математика. — 1994. — № 4. — С. 24-29.

35. Петросян Л. А. Дифференциальные игры преследования. — Л.: Издат. Ленинградского ун-та, 1977. — 222 с.

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

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

38. Понтрягин Л. С., Болтянский В. Г., Гамкрелидзе Р. В., Мищенко Е. Ф. Математическая теория оптимальных процессов. — М.: Физматгиз, 1961. — 391 с.

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

40. Саттер Г. Решение сложных задач на С++. — М.; СПб.; Киев: Издательский дом «Вильяме», 2002.— 400 с.

41. Система автоматической генерации документации из исходного кода Doxy-gen. http: //www. stack. nl/~dimitri/doxygen/.

42. Страуструп Б. Язык программирования С++, — 3 изд. — СПб.; М.: Невский Диалект — Издательство Бином, 1999. — 991 с.

43. Субботин А. И. Минимаксные неравенства и уравнения Гамильтона-Яко-би. М.: Наука, 1991. - 216 с.

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

45. Тан К. Ш., Стиб В.-Х., Харди И. Символьный С++: Введение в компьютерную алгебру с использованием объектно-ориентированного программирования. 2 изд. - М.: Мир, 2001. - 622 с.

46. Тарасьев А. М., Ушаков В. Н., Хрипунов А. П. Об одном вычислитеа^ЬНОм алгоритме решения игровых задач управления // Прикладная математика и механика. 1987. - Т. 51, № 2. - С. 216-222.

47. У хоботов В. И. Дифференциальная игра с простым движением // ву зов. Математика. — 1991. — № 8. — С. 69-72.

48. Ушаков В. П. К задаче построения стабильных мостов в дифференци^ЛЬНО£игре сближения-уклонения // Изв. АН СССР. Техн. кибернетика. — 1980.4. С. 29-36.

49. Ушаков В. П., Хрипунов А. П. О приближенном построении решений в игровых задачах управления // Прикладная математика и механика. — 1997.1. Т. 61, № 3. С. 413-421.

50. Хайрер Э., Ваннер Г. Решение обыкновенных дифференциальных уравнений Жесткие и дифференциально-алгебраические задачи. Пер. с англ. — М.: Мир 1999.- 685 с.

51. Хлопин Д. В. Пошаговая аппроксимация и конструктивные движения в задачах оптимизации // Проблемы теоретической и прикладной математики: Труды 40-й Всероссийской молодежной конференции. — Екатеринбург: ИММ УрО РАН, 2009. С. 271-275.

52. Чистяков С. В. Элементы динамической теории классических кооперативных игр // Численные и качественные методы прикладной математики (вопросы механики и процессов управления, вып.23). — СПб.: Изд-во С.-Петерб. ун-та, 2004. С. 14-40.

53. Шориков А. Ф. Минимаксное оценивание и управление в дискретных динамических системах. — Екатеринбург: Изд-во Урал, ун-та, 1997. — 242 с.

54. Abou-Kandil H. Solution of N-person Stackelberg games with nearly cooperating leaders // International Journal of Control — 1987. — Vol. 45, no. 3. — Pp. 1043-1050.

55. Agarwal P. K., Flato E., Halperin D. Polygon decomposition for efficient construction of Minkowski sums // Computational Geometry: Theory and Applications. —2002.-Vol. 21.- Pp. 39-61.

56. Bardi M., Dolcetta I. C. Optimal Control and Viscosity Solutions of Hamil-ton-Jacobi-Bellman Equations. — Boston: Birkhâuser, 1997. — 570 pp.

57. Basar T., Olsder G. J. Dynamic Noncooperative Game Theory. — Philadelphia, PA: SIAM, 1999.- 536 pp.

58. Boolean Operations on 3D Selective Nef Complexes: Data Structure, Algorithms, and Implementation / M. Granados, P. Hachenberger, S. Hert et al. // Proc. of the 11th Annu. European Sympos. Algorithms (ESA'03).— Budapest: 2003,— September. — Pp. 654-666.

59. Boost C++ Libraries, http://www.boost.org/.

60. Cardaliaguet P., Plaskacz S. Existence and uniqueness of a Nash equilibrium feedback for a simple non-zero-sum differential game // Int. J. Game Theory. —2003.- Vol. 32.- Pp. 33-71.

61. Carlini E., Falcone M., Ferretti R. An efficient algorithm for Hamilton-Jaco-bi equations in high dimensions // Computing and Visualization in Science.—2004. Vol. 7. - Pp. 15-29.

62. Chen C. I., Cruz J. B. Stackelberg solution for two person games with biased information patterns // IEEE Trans. Automat. Contr.— 1972. — AC-17, N. 6.— Pp. 791-798.

63. Computational Geometry: Algorithms and Applications / M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf. — 2 edition. — Berlin: Springer-Verlag, 2000. — 367 pp.

64. Computational Geometry Algorithms Library, http: / /www. cgal. org/.

65. Falcone M. Numerical Methods for Differential Games via PDEs // International Game Theory Review. 2006. - Vol. 8, no. 2. - Pp. 231-272.

66. Guibas L. J., Ramshaw LStolfi J. A Kinetic Framework for Computational Geometry // In. Proc. 24th Annu. IEEE Sympos. Found. Computer Science. — 1983.-Pp. 100-111.

67. Hansen E., Walster G. W. Global Optimization Using Interval Analysis.— 2 edition. N.Y., Basel: Marcel Dekker, Inc., 2004. — 492 pp.

68. Hoffmann C. M. Geometric and solid modeling: an introduction. — San Francisco: Morgan Kaufmann Publishers Inc., 1989. — 338 pp.

69. International Standard ISO/IEC-14882: Programming Languages — C++ / ISO/IEC. 2 edition. - 2003. - October 15. - 786 pp.

70. Jank G., Kun G. Optimal control of disturbed linear-quadratic differential games // European Journal of Control. — 2002. — Vol. 8(2). — Pp. 152-162.

71. Kleimenov A. F., Osipov S. /., Kuvshinov D. R. Numerical Construction of Nash and Stackelberg trajectories in a linear positional differential game // Me^fl.

72. Конф. «Диф. уравнения и топология», поев. 100-летию со дня рождения Л.С.Понтрягина. Тезисы докладов. — М.: 2008. — С. 259.

73. Krasovskii A. N., Krasovskii N. N. Control under Lack of Information. — Berlin: ■ Birkháuser, 1995. 322 pp.

74. Krasovskii N. N., Subbotin A. I. Game-Theoretical Control Problems.— NY. Berlin: Springer-Verlag, 1988. — 517 pp.

75. Kumkov S. S., Patsko V. S., Shinar J. On level sets with "narrow throats" in linear differential games // International Game Theory Review. — 2005. — September. — Vol. 7, no. 3. Pp. 285-312.

76. Melikyan A. A. Generalized Characteristics of First Order PDEs: Applications in Optimal Control and Differential Games. — Boston: Birkhäuser, 1998. — 310 pp.

77. MIT License, http://opensource.org/licenses/mit-license.php.

78. Myers N. C. Traits: a new and useful template technique // C++ Report.— 1995. — June, http: //www. cantrip. org/traits. html.

79. Nef polyhedra in 3-dimensional space, http://www.win.tue.nl/~phachenb/ Nef/.

80. Ramkumar G. D. An Algorithm to Compute the Minkowski Sum Outer-face of Two Simple Polygons //In Proc. 12th Annu. ACM Symos. Computational Geometry.- 1996,- Pp. 234-241.

81. Siek J., Lumsdaine A. Concept Checking: Binding Parametric Polymorphism in C++ // First Workshop on C++ Template Programming, Erfurt, Germany.— 2000. — October 10. http://oonumerics.org/tmpw00/.

82. The OpenGL Graphics System Utility Library (Version 1.3) / N. Chin, C. Frazier, P. Ho et al.; Ed. by J. Leech; Silicon Graphics, Inc.— 1998. — November 4.— 42 pp.

83. Tolwinski B., Haurie A., Leitmann G. Cooperative equilibria in differential games // J. Math. Anal. AppL- 1986. Vol. 119.- Pp. 182-202.94. von Stackelberg H. The theory of the market economy. — London: William Hodge, 1952. — 328 pp.

84. Zakharov V. Game theory approach in communication networks // OASIS: Distributed Search System in the Internet — 1999.