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

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

О

ООЗОБ265Н

Осипов Сергей Иванович

РЕШЕНИЕ ОДНОГО КЛАССА ИЕРАРХИЧЕСКИХ ДИФФЕРЕНЦИАЛЬНЫХ ИГР (МЕТОДЫ, АЛГОРИТМЫ, ПРОГРАММЫ)

05 13 18 — математическое моделирование, численные методы и комплексы программ

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

Екатеринбург — 2007

003062658

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

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

профессор

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

Официальные оппоненты доктор физико-математических наук,

профессор

Сергей Владимирович Чистяков

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

Алексей Станиславович Лахтин

Ведущая организация Удмуртский государственный университет

Защита состоится 2007г в ч 00

мин на засе-

дании диссертационного совета К 212 286 01 при Уральском государственном университете им А М Горького по адресу 620083, г Екатеринбург, пр Ленина 51 , комн 248

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

Автореферат разослан " 2007г

Ученый секретарь диссертационного совета доктор физико-математических наук, профессор

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Объект исследования и актуальность темы Объектом исследования предлагаемой диссертации является один класс неантагонистических дифференциальных игр, а именно — иерархических позиционных дифференциальных игр

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

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

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

1Красовский К Н , Субботин А И Позиц юнные дифференциальные игры М Наука, 1474

-Красовский ^ F Управление динамической системой М Наука, 19S5

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

^Айзеке Р Дифференциальные игры М Мир 1%7

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

6Von Stackelberg Н The theory of the market ecoromy London Hodt;e, 1452

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

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

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

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

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

8Петросян JI А Устойчивость решений в дифференциальных играх со многими участниками //

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

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

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

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

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

Вести ЛГУ 1977 Л» 1<> С 40-52

дКлейменов а Ф Неантагонистрческпе позиционные дифференциальные игры Екатеринбург Наука Урал отд , 1903

задач оптимального управления9 Алгоритмы программ основываются на дискретном представлении времени, а множеств из В? — в виде многоугольников на плоскости, к которым применяются теоретико-множественные операции объединения, пересечения, алгебраической суммы Некоторые алгоритмы, используемые в диссертации, опираются на разработки В Н Ушакова и В С Пацко и их учеников Научная новизна

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

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

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

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

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

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

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

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

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

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

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

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

Обоснованность и достоверность результатов подтверждается восемью основными публикациями по теме диссертации

Апробация работы Основные результаты диссертации обсуждались и докладывались

1 на Всесоюзной школе "Оптимальное управление Геометрия и анализ", Кемерово, 1988,

2 на VII Всесоюзной конференции "Управление в механических системах", Свердловск, 1990,

3 на Международном симпозиуме "Dynamic Games and Applications", Санкт-Петербург, 2002,

4 на Международном семинаре ИФАК "Control Applications of Optimization", Вышеград, Венгрия, 2003,

5 на Международной научной конференции "Устойчивость, управление и моделирование динамических систем", Екатеринбург, 2006

6 на научных семинарах отдела динамических систем ИММ УрО РАН, Екатеринбург,

7 на научных семинарах кафедры теоретической механики Уральского государственного университета,

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении дается общая характеристика работы, приводятся историко-библиографические сведения, описывается содержание диссертации по главам

Глава 1 состоит из четырех разделов

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

Раздел 1 2 содержит математическую постановку задачи, формализацию игры, основанную на формализации и результатах теории антагонистических дифференциальных игр в соответствии с подходом4

Динамика процесса управления описывается скалярным уравнением

х = и + о, я [¿о] = то, < а, а > 0, (1)

где и — управление игрока 2, V — помеха, время I е [¿о,^], 0 < А* < А < А* Параметр А — выбирается игроком 1

Показатели качества первого и второго игроков соответственно

о 1 = / \и2Щ(1т, (2)

и,

■9

(72 = + I\и2Щс1т (3)

1о

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

Рассматриваются два варианта игры В первом варианте лидер передает ведомому информацию о всей реализации помехи Во втором варианте

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

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

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

Используемая в задаче формализация9 основана на формализации и результатах общей теории позиционных антагонистических дифференциальных игр1 В первом варианте игры оба игрока применяют чистые позиционные стратегии Л — {A(i, с, г), U = {u(i,x, е), Д>(г)} Во втором варианте

— игрок 1 использует контрстратегии Л" = {\(t,x,u,s), f3i(e)}, а игрок 2 — чистые позиционные стратегии

Аналогично9 определяются законы управления первого и второго игроков Z(A,£i, Ai) и Z(U,S2, Л2) для варианта 1 и Z{A",ei,Ai), Z(U,s2, Дз)— для варианта 2 Закон управления игрока 2 и реализация помехи порождают ломаную Эйлера — траекторию системы (1)

Тогда гарантированные результаты первого и второго игроков в варианте 1 будут

Р^А, U, v[ ]) - lim inf ai(Z(A, e{, Д{), Z(U, 4, Д£), v[], tk0,4), (4)

А,—»со

при ef 0, fg to, 4 20, ¿(Af) < ДО*), если к-* oo, (5) АЛ, U, ]) = lira sup a2*(Z(Л, e}, Д*), Z(U, ek2, Д§), ], 4 xk0),

при условии (5)

Для варианта 2 — результат pi\Au,U, v[]) аналогичный варианту 1 (4), (5) и

pf\k\U) = sup hmSupa*2(Z(A\£k1,Ak1),Z(U,ek,A^,v[},4,xk0), >[]ev А-юо

при условии (5)

Выполнены следующие предположения

А. Игрок 1 (лидер) выбирает стратегию Л* (во втором варианте — контрстратегию Л"*) до начала игры и сообщает ее игроку 2

Б. Игрок 2 (ведомый), зная стратегию Л* (контрстратегию Л"*), действует рационально — выбирает стратегию U* из условия

U, v>[ ]) —■> mm у, для варианта 1

и из условия

pf\ku%U) mm и,

(2) ~ о

и условия невозрастания р>2 вдоль траектории для варианта I

Гарантированный результат лидера при объявлении им стратегии Л зависит от того, какую стратегию выберет ведомый из множества рациональных стратегий /vi(A, г>[]) Для второго варианта объявленной стратегии Л" при реализации помехи ?>[ ] соответствует множество рациональных стратегий Ко(Аи) Рассматриваются два случая

Случай 1, когда ведомый выбирает произвольную рациональную стратегию

^(Л^П) = inf £\a,u,v[]),

DfcAi(A,i [])

«[ ]) = mi Sf\A\ U, v[}),

О ьАДЛ")

Случай 2, когда ведомый выбирает стратегию, наилучшую для лидера (доброжелательный ведомый)

¿2(Л,г>П) = „ max „«(Л,(>[]), (6)

еР(Л,о[]) = max Л2)(Л«,С^[]) (7)

с/еА2(Л")

Задача 1,, (г = 1,2) Найти стратегию лидера Л]^ такую, что

е1'(Л1„г[]) = тах£>]г(Л,г>[ ]), г = 1, 2

Задача 2,, (г = 1,2) Найти контрстратегию лидера Л!>, такую, что

е?х(Л2,„»'[ ]) = тахе?'(Аи,г»[ ]), г= 1,2

Для первого варианта, пару стратегий (Лхд, [^д), где Лх 1 решает задачу 11, а 1/\ 1 € А'ДЛхд, ?;[ ]) назовем решением Штакельберга в дифференциальной иерархической игре, а пару стратегий (Л12, ^о), где Л^ решает задачу 12, а V12 доставляет максимум в (б), при Л — Л1 2, назовем решением Штакельберга в дифференциальной иерархической игре с доброжелательным ведомым Для второго варианта решения Штакельбега определяются аналогично, с понятными изменениями

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

Задача Зп (г = 1, 2) При фиксированной помехе ъ'[ ] найти кусочно-непрерывные функции и ^ < t < 1), доставляющие решение задачи

о

,™а>,(/ Чт)гг(т)(1т),

А( ) ч( ) Л

при условии (для г = 1)

« 1?

х(0) + / Л (тУ(т)с1т > + / А(г)М2(г)й?г, (8)

¿0

t <0,

при условии (для г = 2)

и Ь

Тг^ъ-ФО) + / А(г)гг(г)(/г > *&)) + ] *(т)и\т)<!т, (9)

¿0 < ¿1 < <2 <

где т( ) — траектория уравнения (1), порожденная управлением и( ) и реализацией помехи г>[ ] из начальной позиции (¿сь^о)

В условиях (8), (9) фигурируют непрерывные функции цены1'2 71(£,х(£)), 72(^1,^(^1)) вспомогательных антагонистических игр Г^, соответственно, в которых ведомый стремится минимизировать свой показатель, а лидер ему противодействует

Пусть Л°( ) и и°( ), — решение З1 при фиксированной помехе г>[], а т°( ) — траектория (1), порожденная управлениями и°( ) и у[ ] из позиции (и,то) Рассматриваются стратегии и0 = {и°(1,х,£),$(е)}, где

\°«хе) = 'Л°(<) '

Х \{1)(Ь,х,г) , ||х-х°(0|| > £

(10)

и0

= I II О/ЛП ^ ' ( ^

1 произвольная , ||ж — х(ь)[| > £

¿0 < < < ,

, , ) —универсальная оптимальная стратегия лидера в игре Г^1', а функция /3?(е) выбрана так, чтобы обеспечить выполнение условия, что соответствующие ломаные Эйлера при условии ¿(Дг) < не выходят за пределы е-окрестности движения х°( )

Пусть Ао( ) и ио( ) — решение задачи Зо при фиксированной помехе г»[ ] Рассматривается контрстратегия = {Ао(/, х, и, г), (3{{е)} и стратегия Щ = {ь0{1,-с, £),$(£)}, где

Хп _ 1Л°(*) , \\п-А*)\\<е П9, " , ||и-ио(ОН>, ' (12)

= «о(0 , (13)

to<t<i} ,

Л^2-®х, и, г) — универсальная оптимальная стратегия лидера в игре Г®, а функция ) выбрана аналогично варианту 1

Справедливы следующие теоремы, определяющие структуру решения задач 1г и 2г

Теорема 1

Пусть для решения задачи 3i в условии (8) имеет место строгое неравенство для всех t G [¿о, тогда пара стратегий (Л°, U0) (10),(11) есть решение Штакельберга в иерархической дифференциальной игре Если же хотя бы при одном t G [¿Oj^) условие (8) выполняется со знаком равенства, то пара (Л°, £7°) (10),(11) есть решение Штакельберга в иерархической дифференциальной игре с доброжелательным ведомым Теорема 2

Пусть для решения задачи З2 А( ) и щ( ) в условии (9) имеет место строгое неравенство для всех t G тогда пара контрстратегия лидера

(Aq,Uq) (12),(13) есть решение Штакельберга в иерархической дифференциальной игре Если же хотя бы при одном t € [£о,$) условие (9) выполняется со знаком равенства, то пара (Ад, i/o) (12),(13) есть решение Штакельберга в иерархической дифференциальной игре с доброжелательным ведомым

В разделе 1 4 выписываются функции цены антагонистических игр Г.Р, Г,2', находятся решения задач Зг и тем самым, согласно теоремам 1 и 2, находятся решения задач 1 и 2

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

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

х = Ах + Bu + Cv, x[i0] = х0 (14)

Здесь время t G фазовый вектор х G Rn, A G [п X тг], В е [n х к],

С G [га X I] — постоянные матрицы Значения управляющих векторов и иг; первого и второго игроков ограничены условиями

«(0 € fi{t)P, v(t) е 7(i)Q, (15)

11 Крясовскчй А II Некоторое задачи игрового угравления Учеб пособие Свердловск УрГУ, 1984

где множества Р, <3 — выпуклые компактные многогранники в пространствах Г1А и И/ с конечным числом вершин, а /¿(^) = а + Ы, 7(/) = с + <й — скалярные линейные функции

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

Ь =01{та{д),хр[д)), (16)

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

к = <т2Ы<>) хв{4)) (17)

Предполагается, что функция о^ Я2 -> Я' — непрерывная, а а^ Я" —» Я — гладкая и вогнутая

Предполагается, что игрокам известны уравнения динамики системы, ограничения на управляющие множества, показатели качества управления, момент окончания игры и фазовый вектор в любой момент игры Это позволяет формализовать действия игроков в классах чистых позиционных стратегий Аналогично главе 1 формализуются законы управления, движения и гарантированные результаты игроков Первый игрок — лидер объявляет свою стратегию до начала игры, а второй игрок — ведомый, выбирает свою стратегию из условия рациональности

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

Структура стратегий, доставляющих решение Штакельберга, по сути дела описана в главе 1 (см стр 12 автореферата) Основная идея этой структуры состоит в том, что оба игрока стремятся согласованно обеспечить нахождение текущей позиции игры в пределахг-трубки, построенной вокруг оптимальной траектории Таким образом, построение решения Штакельберга сводится

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

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

В диссертации предлагается следующий алгоритм построения решений последней задачи, основанный на приведении динамической системы к системе конечно-разностных уравнений для сетки по оси времени (tt,t — 0, ,п), и использовании методов вычислительной геометрии для приближенного построения границ сечений D(f,) G R2 множества допустимых траекторий плоскостями it — const,

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

Финальное множество D(v>) аппроксимируется совокупностью его приближенных "дуг", получаемых в результате работы алгоритма Сопоставление рисунков 1 (а) и 1 (Ь), а также рисунков 2 (а) и 2 (б) дает наглядное представление о том, как дуги, получающиеся в результате работы алгоритма, "заполняют" соответствующие множества D(il)

Для построения каждой дуги сначала с помощью попятной процедуры12

12Ясакова Е Л , Логунова Г В , 171 ЦК о В С Построение стабильных мостов в линейной дифферен-

Рис 1

приближенно вычисляются сечения стабильного моста в задаче сближения-уклонения1,2 с лебеговым множеством, границей которого является одна из линий уровня функции 02(3") = с

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

Алгоритм построения трубки достижимости предполагает выполнение следующих операций, повторяющихся для каждого момента времени Пусть сечение трубки достижимости (текущий многоугольник) построено для момента i, Далее строится множество достижимости системы в следующий момент времени для которого начальными состояниями являются точки текущего многоугольника Затем полученное множество достижимости пересекается13 с дополнением сечения моста для момента tl+1 Результирующий многоугольник и будет сечением трубки достижимости для момента tl+1 На последнем шаге вершины сечения трубки достижимости, лежащие на границе последнего сечения моста, берутся в качестве искомой дуги

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

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

t = U

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

циатьной игре с фиксированным моментом окончания / / Алгоритмы и программы решения линейных дифференцральных игр Свердловск УНЦ АН СССР, 19S4 С 127-158

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

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

Глава 2 состоит из б разделов Раздел 2 1 содержит математическую постановку задачи и ее формализацию Раздел 2 2 содержит определение структуры решений и включает два подраздела Подраздел 2 2 1 содержит формулировку вспомогательной антагонистической игры Го Подраздел 2 2 2 содержит формулировку вспомогательной задачи нестандартного оптимального управления

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

Раздел 2 4 содержит описание процедуры построения моста для игры сближения-уклонения с лебеговым множеством показателя качества управления второго игрока, состоит из 3 подразделов Подраздел 2 4 1 содержит постановку задачи Подраздел 2 4 2 содержит описание алгоритма Подраздел 2 4 3 содержит краткое описание реализации

Раздел 2 5 содержит описание алгоритма построения алгебраической суммы многоугольника общего вида и выпуклого, состоит из 7 подразделов Подраздел 2 5 1 содержит описание теории "кинетического подхода", служащей теоретическим основанием предлагаемому алгоритму Подраздел 2 5 2 содержит сравнительный анализ предлагаемого алгоритма с известными алгоритмами Подраздел 2 5 3 содержит общее описание алгоритма построения алгебраической суммы многоугольников, а последующие четыре раздела де-

тализируют этапы этого алгоритма Подраздел 2 5 4 содержит описание этапа "обведение" Подраздел 2 5 5 содержит описание этапа выделения контуров, содержащих границу результирующего многоугольника Подраздел 2 5 6 содержит описание этапа выделения границы результирующего многоугольника Подраздел 2 5 7 содержит описание операции объединения многосвязных многоугольников

Раздел 2 6 содержит краткое описание программной реализации Поскольку вспомогательных алгоритмов, являющихся частями алгоритма построения решений Штакельбрга довольно много, причем отдельные процедуры алгоритмов12,13 разрабатывались различными коллективами авторов, в разное время и для разных платформ, то объединение их в рамках одной программы оказалось чрезвычайно трудоемкой задачей Среднестатистические затраты только на программирование и отладку одной логики алгоритмов (без учета интерфейсных модулей) составляет не менее 1 7 человеко-лет Кроме того, алгоритм предъявляет высокие требования к объему оперативной памяти и быстродействию вычислительной системы, поэтому его практическая проверка, в определенной степени сдерживалась скоростью развития средств программирования и вычислительной техники

Параметров, оказывающих влияние на работу алгоритма, довольно много, что затрудняет оценку его погрешности, особенно, если иметь в виду вычислительную погрешность Можно выделить две группы таких параметров 1) параметры точности представления геометрических объектов (точка, отрезок, ломаная) и 2) технологические параметры, определяющиеся характеристиками вычислительного комплекса (память, быстродействие, операционная система) Это представляет определенную трудность при управлении программным комплексом, реализующим алгоритм

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

Рассматривается задача управления плоским движением материальной

точки массы т, находящейся под действием двух сил ^ и F2 При этом сила поворачивается на угол </? В формировании сил участвуют два игрока Первый игрок осуществляет выбор силы а второй игрок —силы а также угла поворота силы первого игрока Указанная задача рассматривалась в статье10 как иерархическая дифференциальная игра, там же получено ее аналитическое решение

В данной задаче множество £>(¿0, в зависимости от исходных значений задачи может иметь два типа первый тип изображен на рис 1, второй — на рис 2 Вид аналитическое решение обозначено литерой (а), численного решения — (б) Вычисления производились с 64-битной точностью и следующими значениями параметров 500 шагов по времени, 512 вершин сечения моста, 64 вершины точечного множества достижимости, минимальная длина ребра 10~4, минимальное значение синуса угла при вершине и максимальное отклонение дуги от радиуса последнего сечения моста - 10~5 Средняя относительная погрешность составила 0 0065 в первом варианте и 0 056 во втором

При сравнении аналитических и численных результатов выяснилось, что в аналитических формулах, описывающих границу множества достижимости £>(■$) в статье10 , имеется неточность В диссертации приводится уточненное аналитическое описание границы множества -0(1?)

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

Глава 3 состоит из четырех разделов Раздел 3 1 содержит формулировку задачи Раздел 3 2 содержит общее описание аналитического решения Раздел 3 3 содержит общее описание алгоритма решения Раздел 3 4 содержит результаты численного эксперимента

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ Таким образом в диссертации были получены нижеперечисленные результаты

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

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

3 На основе вышеупомянутого алгоритма реализован комплекс программ /7, 8, 9/

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

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

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

[2] Kleimenov А , Osipov S Stackelberg positional strategies in a two-person hierarchical differential game with disturbance 10th Int Symp on Dynamic games and Applications, St-Petersburg, VI 421-426, 2002

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

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

[5] Осипов С И Об одном алгоритме построения решений иерархической дифференциальной игры двух лиц // VII Всесоюзная конференция Управление в механических системах — Свердловск, 1990 С 80-81

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

[7] Kleimenov А , Osipov S Computation of Stackelberg trajectories in a class of two-person linear differential games with terminal players' payoffs and polygonal constraining for controls In IFAC Workshop on Control Applications of Optimization, Preprints, Elsevier Science Ltd, Oxford, 2003 pp 201-205

[8] 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, Springer-Verlag, Berlin, 2003 pp 391-396

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

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

Введение

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 рисунков.

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.