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

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

КОРНЕВ Дмитрий Васильевич

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

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

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

- I 2015

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

005561724

005561724

Работа выполнена на кафедре вычислительной математики Института математики и компьютерных наук ФГАОУ ВПО «Уральский федеральный университет имени первого Президента России Б.Н.Ельцина».

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

Лукоянов Николай Юрьевич.

Официальные оппоненты: Петров Николай Никандрович, доктор физико-

математических наук, профессор, ФГБОУ ВПО «Удмуртский государственный университет», заведующий кафедрой дифференциальных уравнений математического факультета.

Ухоботов Виктор Иванович, доктор физико-математических наук, профессор, ФГБОУ ВПО «Челябинский государственный университет», заведующий кафедрой теории управления и оптимизации математического факультета.

Ведущая организация: ФГБОУ ВО «Московский государственный университет имени М.В.Ломоносова».

Защита состоится 23 сентября 2015 г. в 12:30 на заседании диссертационного совета Д 212.285.25 на базе ФГАОУ ВПО «Уральский федеральный университет имени первого Президента России Б.Н.Ельцина» по адресу: 620000, г. Екатеринбург, пр. Ленина, 51, зал заседаний диссертационных советов, комн. 248.

С диссертацией можно ознакомиться в библиотеке и на сайте ФГАОУ ВПО «Уральский федеральный университет имени первого Президента России Б.Н.Ельцина», http://dissovet.science.urfu.ru/news2/ .

Автореферат разослан " IЧ-" авг^О^в- 2015 г. Ученый секретарь

диссертационного совета, ,

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

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Степень разработанности темы исследования. Теория дифференциальных игр активно развивается начинал с середины XX века. Становление этой теории в первую очередь связано с работами Н.Н. Красовского, JI.C. Понтрягина, Б.Н. Пшеничного, R. Isaacs, W.H. Fleming и A. Friedman.

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

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

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

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

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

3Krasovskii A.N., Krasovskii N.N. Control under Lack of Information. — Berlin etc. : Birkhauser, 1995. - P. 322.

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

Рассматриваемые задачи различаются следующими условиями:

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

Задача 2. Седловой точки в маленькой игре может не быть. Задача формализуется в дифференциальную игру в классах смешанных стратегий3'5,6.

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

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

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

Теоретическая значимость. Линейно-выпуклые позиционные дифференциальные игры, соответствующие задачам 1 и 2, изучались, в частности, в работах H.H. Красовского3, А.Н. Красовского5,6 и Н.Ю. Лукоянова7,8, одна-

4Красовский А. Н. О позиционном минимаксном управлении // Прикладная математика и механика. — 1980. — Т. 44, №4. — С. 602-610.

5Красовский А. Н. Построение смешанных стратегий на основе стохастических программ // Прикладная математика и механика. — 1987. — Т. 51, №2. — С. 186-192.

6Красовский А. Н. Синтез смешанных стратегий управления. — Свердловск : Изд-во Урал, ун-та, 1988. — С. 151.

7Лукоянов Н. Ю. К вопросу вычисления цены дифференциальной игры для позиционного функционала // Прикладная математика и механика. — 1998. — Т. 62, №2. — С. 188-198.

вЛукоянов Н. Ю. О построении цепы позиционной дифференциальной игры // Дифференциальные уравнения. — 2001. — Т. 37, №1. — С. 18-26.

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

Для решения задачи 3 в диссертации были развиты конструкции выпуклых сверху оболочек, которые идейно восходят к стохастическому программному синтезу2. Последние изначально были разработаны для задач без интегральных ограничений3'5,7,8. Для задач с интегральными ограничениями подобные построения рассматривались ранее9'10'11, но для терминальных показателей качества. Постановок, которые бы объединяли в себе геометрические и интегральные ограничения на управляющие воздействия в сочетании с нетерминальным показателем качества рассматриваемой в диссертации структуры, ранее не исследовалось. В связи с этим, доказательство существования цены и седловой точки в соответствующей дифференциальной игре, а также разработка и обоснование разрешающей процедуры, доведенной до численного метода, представляют теоретический интерес.

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

Методология и методы исследования. Диссертация выполнена в рамках концепции позиционных дифференциальных игр. Численные методы решения задач 1 и 2 основаны па процедуре7, ядром которой является попятное построение выпуклых сверху (вогнутых) оболочек вспомогательных программных функций. Решение задачи 2 использует численный метод решения задачи 1 для вспомогательной модели-поводыря1'3'5'6.

9Локпгоп М. Д. О дифференциальных играх с интегральными ограпичепиями на управляющие воздействия // Дифференциальные уравнения. — 1992. — Т. 28, №11. — С. 1952-1961.

10Лукояпов Н. Ю. К задаче конфликтного управления при смешанных ограничениях // Прикладная математика и механика. — 1995. — Т. 59, Х*6. — С. 955-964.

11Лукоянов Н. Ю. О задаче конфликтного управления при смешанных ограничениях на управляющие воздействия // Дифференциальные уравнения. — 1995. — Т. 31, №9. — С. 1473-1482

12Бердышев Ю. И. Об одной задаче последовательного сближения нелинейной управляемой системы третьего порядка с группой движущихся точек // Прикладная математика и механика. — 2002. - Т. 66, №5. - С. 742-752.

Чтобы получить разрешающую процедуру в задаче 3, вводится вспомогательная переменная, характеризующая ресурсные запасы управления, проводится дополнительная оптимизация10'11 по расходу ресурсов, и применяются построения7, учитывающие нетерминальную структуру показателя качества. Обоснование процедуры, а вместе с тем и существования цены и оптимальных стратегий в соответствующей дифференциальной игре, опирается на введение вспомогательной модели; доказательство близости2 движений исходной системы и модели; доказательство и- и «-стабильности11 системы вспомогательных величин, построенных для модели; переход к предельным конструкциям, дающим необходимые оценки. Оптимальные стратегии строятся методом экстремального сдвига на сопутствующие точки2,3.

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

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

Степень достоверности результатов, апробация результатов. Результаты диссертации обсуждались на семинаре кафедры вычислительной математики Института математики и компьютерных наук Уральского федерального университета, на семинаре отдела динамических систем Института математики и механики им. Н.Н.Красовского УрО РАН и представлялись в докладах на Международной конференции «Алгоритмический анализ неустойчивых задач» (Екатеринбург, 2011), 42-ой и 43-ей Всероссийских молодежных школах-конференциях «Современные проблемы математики» (Екатеринбург, 2011, 2012), 3-ей и 4-ой традиционных Всероссийских молодежных летних школах «Управление, информация и оптимизация» (Яропо-лец, 2011, Звенигород, 2012), Всероссийской паучной конференции с международным участием «Математическая теория управления и математическое моделирование» (Ижевск, 2012), 15-th IFAC Workshop on Control Applications of Optimization (Rimini, Italy, 2012), 6-ой Международной конференции «Кол-могоровские чтения. Общие проблемы управления и их приложения» (Тамбов, 2013), 39-th International Conference Applications of Mathematics in Engineering and Economics (Созополь, Болгария, 2013), XII Всероссийском совещании по проблемам управления (Москва, 2014), 19-th IFAC World Congress (Cape Town, South Africa, 2014), Международной конференции «Динамика систем и процессы управления» (Екатеринбург, 2014), Международном ссми-

наре «Теория управления и теория обобщенных решений уравнений Гамильтона-Якоби» (Екатеринбург, 2015).

Публикации. Основной материал диссертации опубликован в работах [1-4, 6-14]. Для разработанного в рамках диссертации программного комплекса получено свидетельство о государственной регистрации [5].

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В главе 1 рассматривается антагонистическая дифференциальная игра, в которой динамическая система описывается уравнением

х = Л(£)х + /(£,и,и), £0 ^ £, г < х €М", иеНсГ-, 11 '

Здесь х — фазовый вектор; £ — время; точка над символом обозначает производную по времени; матрица-функция А(1) и вектор-функция /(£, и, у) непрерывны; и и V — управляющие воздействия первого и второго игроков. Моменты времени £о и $ зафиксированы, £, — момент начала процесса управления, и и V — компактные множества.

Предполагается, что выполнено условие седловой точки в маленькой игре:

1шптах(г,«)) = титт(/,/(г,и,и)), I € £о ^ (2)

иеи иеУ иеи

где символ (•, •) обозначает скалярное произведение векторов.

Допустимы измеримые по Борелю реализации управлений игроков = {«(0 б О, и ^ £ < <9} и = 6 V, £, < £ < 1?}.

В пространстве перемепных (£, х) определяется компактное множество Ко возможных позиций2 рассматриваемой динамической системы. Под движением х[£»[•]$], порожденным из позиции (£,,2.) 6 Ко, £» < -д, допустимыми реализациями и [£»[-]^) и понимаем абсолютно непрерывную функ-

цию (х(£) е М", £, ^ £ г?, х(£„) = х„}, которая при почти всех £» < £ ^ $ вместе с и = и{£) и V = 1>(£) удовлетворяет уравнению (1). При этом множество Ко таково, что справедливо включение (£,х(£)) £ Ко, £» ^ £ ^ 1?.

Пусть для i = 1,..., N заданы моменты времени оценки качества движения х[£,[•]г?]: £0 < ^ < < д, г = 1,..., N — 1, = 1?, по-

стоянные матрицы Д размерности й{ х п (1 ^ <и ^ п), целевые векторы

Ci € Rn и нормы ßi(li,...,lN) G К, {li,...,ljf) (E x ...RdОбозначим h(t) = min{i = 1 ,...,N: ■ßt^ t}, to t ^ Показатель качества, оценивающий движение a:[i,[-]i?], имеет вид

тИа^]) = - %)),... - . (з)

Полагаем, что существуют четные по ц нормы р) € К, (k, /i)el4x К, для которых справедливы равенства ..., lN) = а. (Z,, /¿¿+1(7i+1,..., lN)), i = 1,..., ЛГ — 1. Тогда7 показатель качества (3) является позиционным.

Цель первого игрока — доставить показателю (3) как можно меньшее значение. Цель второго противоположна цели первого.

Под чистой стратегией U первого игрока понимаем произвольную функцию U = {U{t,x,e) <Е U, (t,x) е К0, £ > 0}, где в — параметр точности2.

Законом управления Ы первого игрока называем тройку (U,e,As), где Ai — разбиение отрезка времени [i„,

As = {tj:t1 = tm, 0 < tj+i — tj ^ 5, j = l,...,к, tk+i=ti}. (4)

Из заданной позиции (tt,x*) £ К0 закон U в паре с допустимой реализацией v[t*[-]i?) формирует движение ж[•])?] системы (1) следующим образом:

i(t) = A(t)X(t) + f(t,Uj>v{t)), Uj = l/(tj, X{tj),£), tj^t< tJ+1, j = l,...,k, x(ti) = x,.

Гарантированный результат закона U определяется равенством Y{U\tt,xt) = sup тММ-М)-

Оптимальным гарантированным результатом первого игрока будет ru(i,,a:,) = inf lim sup lim sup ГШ — {U,E,&s)\t„xt).

и i-»0 As

Для С > 0 закон управления U^ называем С-оптимальным, если Г(£/с; t„xt) ^ Ги(£„ z.) + С

По аналогичной схеме с понятными изменениями для второго игрока определяются оптимальный гарантированный результат Г„(£„, х,) и ("-оптимальные законы управления V^.

Из результатов H.H. Красовского3 и А.Н. Красовского4 вытекает, что оптимальные гарантированные результаты игроков совпадают, определяя цену дифференциальной игры (1)-(3): Г0(г„х.) = ru(i„x„) = Г„(г„х,).

Глава 1 посвящена численному методу для нахождения цены r0(i,,x») и построения ("-оптимальных законов управления игроков. Разработанный численный метод базируется на следующей процедуре7.

Для отрезка времени управления [£„ г?] фиксируем разбиение As = {¿j}^1 вида (4) такое, что i?f £ i = h(t,), ..., JV. Обозначим

tm

тп) = J техпйп (тп, Ф(г?, т)/(т, u, w)) dr, m £ Rn, j = 1,..., k, ti

где Ф(t,r) — матрица Коши для уравнения х = Л(£)х. Попятно по шагам разбиения Дг определяем множества Gf(tt) векторов m £ R" и скалярные функции <pf(t,,m), тп £ Gf(tt). Пусть j - к + 1, тогда

GtM = ™ = 0}, ^+1(t.,m) = 0, (5)

Gi+1%) = {m: m = Z>JZ, I £ Rd", ^ 1}, </^+1(i„m) = -(m,cw).

Если 1 ^ j ^ к, тогда

G+(i.) = G;+1(i.), m) = conc [^(i., •)] M, (6)

Gi ('•)

где

i>j{t*,m) = AV>j(i„m) + <pj+1(tt,m), тп £ G+(ft), и далее, когда tj < 1JA(ty))

= Gj(t,), <pj(t„ тп) = <p~j (tt,m),

иначе, когда t, = г?/,, Л = Л(£_,),

G7(t.) = {m: m = i/m. + tfjDjf,

i/ > 0,/ e < l,m, 6 G+(i,)}, (7)

тп) = max [fvt(t„ m.) - (I, Dhch)].

(l/jijm.JIm J

Здесь символ т обозначает транспонирование; ¡J*N{-) и a"h{-) — нормы, сопряженные к /jjv(■) и <тЛ(-); символ сопсц [V"(0] обозначает выпуклую сверху (вогнутую) оболочку функции -ф(-) = {ф(тп), m £ С} на множестве G, то есть минимальную из вогнутых функций, мажорирующих 0(т) при т £ G; максимум в (7) вычисляется по всем таким тройкам (и,1,тп,), что и ^ 0, I £ Rd\ cr*(Z, г/) 1, m, £ G+(t.) и при этом итп, + Фт(г>,„ = тп.

Для х £ R" и j = 1,..., к + 1 рассмотрим величины

ef(t„x)= maх |(m,$(i),ij)i)+^(i„m)]. (8)

meGf(t,) J

Известно7, что величина х„) приближает цену r0(f,, х,) игры (1)-(3). На основе этих величин методом экстремального сдвига на сопутствующие точки2,3 удается построить ^-оптимальные законы управления игроков.

Численный метод, разработанный на базе описанной выше процедуры, опирается на «пиксельное» представление компактных множеств, когда они

покрываются равномерной конечной е-сетью, и все точки множества, входящие в окрестность радиуса е с центром в одном из узлов сети, отождествляются с этим узлом-пикселем. Таким образом, компакты G^(U) представляются в виде конечных мпожест G^ С Rn пикселей т. Все функции хранятся в табличном виде. Функции от времени представляются в виде массивов значений в точках разбиения Ag. Функции ip^(t„,m), т £ G*(£«), представляются в виде ассоциативных массивов = {(т, <р*(т)): in € Gf}. Для нахождения необходимых значений функции Диспользуются пиксельные аппроксимации U и V компактов U и V с размерами пикселей, характеризуемыми параметрами Дц и Ду. В (6) выпуклая сверху оболочка ip = concg [?/>(■)] табулированной функции ф = ip(rn), т € G С R", аппроксимируется сверху опорными гиперплоскостями с фиксированным набором нормалей, в качестве которого используется семейство векторов, лежащих на единичной (п-)-1)-мерной полусфере, параметризуемое углами ф{, г = 1,..., п, пробегающими отрезок [0, тг] с равномерным шагом Аф. Сначала по набору нормалей находим функции опорных гиперплоскостей к подграфику функции ~ф. Затем для каждой точки т 6 G ищем минимум их значений в этой точке и значение concg [V»(-)] (rn) полагаем равным найденному минимуму. В пересчете (7) значения и ^ 0 берутся с равномерным шагом Аи\ вектора I € H.d'1 перебираются с равномерным по всем координатам шагом Д;; для вектора т (mi,..., тп) € R71 соответствующий ему пиксель т находится при помощи покоординатного преобразования inj = Ат round(т;/Дт), г = 1,... ,п.

Получена оценка алгоритмической сложности данного численного метода. Утверждение 5.5. Итоговое время Т приближенного вычисления величины ej~(£»,x») (8) составляет

где Ли, Ау, Аф, Ад, А;, \и и д.* — подходящие константы, определяемые по системе (1) и показателю качества (3).

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

Г X! = 12 + _п</^,9_4

\±а = —0,52! — 0,05x2 + Ъ(Ь)и, Ю-г.-и - % ^

х = (хь Х2) 6 К2, и е {-1, о, 1}, V е {-1, о, 1},

где

{1,5 + 1,5 cos2тг(< - 0,5), если t € [0,5; 1,5],

1,5 + 1,5 cos 2тг(£ - 2,5), если t е [2,5; 3,5],

3 иначе,

c(t) = I ССЛИ t G 1,4] U [2'6; 3'41 \ 0,3 иначе,

задано начальное условие

х, = х(0) = (ij(0), тг(0)) = (1,0)

и показатель качества

i=i

где

(10)

(И)

С1 = (0, -1), с2 = (-1,0), с3 = (0,1), С4 = (1,0).

В численных построениях использовались равномерное разбиение As отрезка времени управления [0,4] с диаметром 6 = 0,001 и значение параметра точности е = 0,005. Для пиксельных представлений были выбраны значепия параметров Ат = А/ = Д„ = 0,01, Аф = 7г/200.

В этой задаче множества <?+(£,) оставались неизменными, когда tj находилось в рамках одного из полуинтервалов [0,1), [1,2), [2,3), [3,4). Пиксельное представление соответствующих множеств Gj~(£») приведено на рис. 1.

S.ljJ

Рис. 1: Пикселыгае представление множеств в примере 6.1.

Найденное численпо значение велпчипы х,), приближающее цену

Г0(£,, х,) игры (9)—(11), составило 1,131. Ниже приводятся результаты трех симуляций процесса управления в этой игре.

1. Управляющие воздействия игроков формировались построенными численно С-оптимальными законами Щ и Реализовалось значение показателя качества 7(1' = 1,112 и

2. Управление первого игрока формировалось законом Щ, управляющие воздействия второго назначались случайным равновероятным образом. Реализовалось значение показателя качества 7^) = 0,408 < ж»),

3. Управляющие воздействия первого игрока назначались случайным равновероятным образом, а управление второго формировалось законом . Реализовалось значение показателя качества 7® = 4,996 > е]~(£,,х„).

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

л \

/ / г" -А. у

1 I \ / ( \

\ \ 1 / //

//

V к/

-2 -1.5 -1 -0.5 0 0.5 1 1.5

Рис. 2: Траектории реализовавшихся движений в примере 6.1.

Глава 2 посвящена дифференциальной игре для системы (1) с показателем качества (3) без предположения о выполнении условия (2), когда цены в классах чистых позиционных стратегий 11(Ь,х,е) и У(Ь,х,е) может не существовать, и целесообразна формализация в классах смешанных стратегий3,5.

Поскольку компакты и и V могут быть приближены конечными множествами, далее полагаем, что О и V конечны изначально:

и = {ЫИ € И"»: г = 1,..., £}, V = {г/М еГ:« = 1 ,...,М}.

Обозначим

Г = 1

{я= {91,...,чм) <7, 3=0, з = 1,...,М, ¿®, = 1}.

5 = 1

Наряду с исходной системой (1) рассмотрим вспомогательную модель: ь м

г=1

у € К", р* € Р, я" е (2.

Подобно Ко определим компактное множество К\ Э Ко возможных позиций модели2. В процессе формирования управления первого игрока модель (12) играет роль поводыря1,3. Отметим, что модель (12) удовлетворяет условию седловой точки в маленькой игре.

Под смешанной стратегией и первого игрока понимаем тройку (Ри(-), Ри(:), «£(■)) измеримых по (х,у) функций:

ри = ри(1,х,у,е) €Р, р*и=р*и(их,у,е) € Р, я*и = д*(Ь,х,у,е) € О, £ £ [£0,1?], х € К", у е Еп, е > 0.

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

Из заданных позиций (Ь,,х*) е К0 системы (1) и (и, у,) € Кг модели (12) закон управления Ы — ({/, £, Д{) в паре с допустимой случайной реализацией

[<»[■]$) = {г>ш(£) е V, и ^ £ < •&, и € П} формирует случайное движение [■]!?]) комплекса (1), (12) следующим образом:

хы(£) = АЦ)хыЦ) +

уи{1) = Л(«)уы(0+

ь м

г=1 а=1

tj^t<tj+l, з = 1,...,к, = х,, уыЦг) = у,,

где £ О определяется в результате случайного испытания при условии

Здесь символ Р(... \...) обозначает условную вероятность. Кроме того, предполагается, что на каждом шаге ^ < £^+1 случайная реализация г*ш [£»[■]$)

является стохастически независимой от получаемой реализации и^ =

= Uuj, tj^t< tj+i, j = 1,..., к, шеП}:

РЫ*) е В I x„(tj), u^tj)) = p(vu(t) e в I x^tj), y^tj)), в с Y.

Для 0 < /3 < 1 гарантированный результат закона U определяем как

T{U-,tt,xt,yt\P) = sup min {а € R: P(7(:r [í,[.]tf]) < а) > р}. n«MW

Оптимальным гарантированным результатом первого игрока будет Г„ = inf limlimsuplim sup limsupTfW = (17, e, As);t„x,,y,: P).

и г-»о Iz.-y.l^r, As

Для С > о, 0 < /3 < 1 закон управления U^p первого игрока называем (С, /3)-оптималы1ым, если

г(^С,/з;У* = ж»; Р) < Гu(t„xt) + С-

По аналогичной схеме с понятными изменениями для второго игрока определяются оптимальный гарантированный результат Fv(tt,xt) и ((, /^-оптимальные законы управления

Известно3, что игра (1),(3) имеет цену r0(f,,z») = Г„(£,,х*) = rv(t,,xt).

Глава 2 посвящена численному методу для нахождения цены Г0(£„, х,) и построения (С, /3)-оптимальных законов управления игроков. Разработанный численный метод базируется на методе из главы 1, который применяется к вспомогательной дифференциальной игре (12), (3). На основе системы величин (8) при помощи экстремального сдвига на сопутствующие точки определяются стратегии U%s и обеспечивающие подходящую близость13 движений исходной системы (1) и модели (12), а также необходимые гарантии достигаемого значения показателя качества.

Теорема 10.1. Для любых чисел С>ОиО,5</3<1 найдутся такие число е* > 0 и функция 0(e) > 0, 0 < с ^ е*, что, каковы бы ни были начальная позиция (¿,,x.) € Ко, значение 0 < е ^ е* и разбиение As вида (4), i9¡ 6 As, i = h(t,),...,N, 5 < S(e), законы = (U^.e, As) и V¿s = (V¿,£,AS) будут (С, P)-оптимальными, и будет выполнено неравенство

\r0{U,xt)-ei(U,xt)\^C

13 Красовский А. А., Красовский А. Н. Нелинейная позиционная дифференциальная игра в классе смешанных стратегий // Математическая теория управления и дифференциальные уравнения: сб. статей к 90-летию со дня рождения академика Евгения Фроловича Мищенко, Тр. МИАН. - Т. 277. - 2012. - С. 144-151.

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

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

(1) , у,

К \ „УЧ ,

ц = и = 0 ^ I < I? = 2,

Рт

т2(<) ' т2(£)

а2т

г =--— +

К2\2и^ +

И2у' т2(Ь)'

(13)

и! ' соэгД1) — гД1' вти'1'

иР вт гД1' + и!1' сое г)'1'

(з,г) 6 М2 х К2, и = (и^У2') 6 ®2 х К2, V = (г;(1),г/„гО € К1 х К2 х К2, и<2>, V,, У* е {(1,0), (0,1), (-1,0), (0,-1)},

задано начальное условие

5(0) = (0,-2), ¿(0) = (2,0), г(0) = (—1,1), г(0) = (0,4) (14)

и показатель качества

7=ы*) - ы*))2+ы*) -

(15)

Система (13) рассматривалась при параметрах ах = 0,2; К\ = —40; Аг = 0,5; N1 = 4; Р = -4; а2 = 0,4; К2 = -25; Л2 = 0,4; И2 = 6; т{(Ь) = т.о+ехр^Л^], г = 1,2; тлю = 1; тгго = 1В численных построениях использовались равномерное разбиение Д^ отрезка времени управления [0,2] с диаметром <5 = 0,01 и значение параметра точности £ = 0,05. Для пиксельных представлений были выбраны значения параметров Дт = Д; = Д„ = 0,01, Аф = 7г/500.

Найденное численно значение величины приближающее цену

Г0(4,, I,) игры (13)—(15), составило 0,279. Ниже приводятся результаты трех симуляций процесса управления в этой игре, выполненных по той же схеме, что и в примере 6.1, с применением построенных численно законов и У^р вместо законов Щ и У^. В симуляциях реализовались, соответственно, следующие значения показателя (15):

v(1)

= 0,272 и еГ (и, х,), 7(2) = 0 < е^ (г„ х.),

7'

(3)

8,843 >

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

Г 2 ,S2 2

-1

-2

Г2,«2 2

1

О

-1

-2

/ \

\

\ \

(16)

-1 -0.5 0 0.5 г1(Я1 -1 -0.5 0 0.5 n,Sl Рис. 3: Траектории реализовавшихся движений в примере 12.2.

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

Движение динамической системы описывается уравнением

х = A(t)x + B(t)u + C(t)v, t0 ^ t, sj £ < ■в, ier, и e Rnu, v e Rn".

Здесь x — фазовый вектор; t — время; A(t), B(t), C(t) — непрерывные матрицы-функции; и — управляющее воздействие; v — воздействие неконтролируемой помехи. Моменты времени t0 и i) зафиксированы, tt — момент начала процесса управления. Далее задача формализуется в дифференциальную игру, управление трактуется как первый игрок, а помеха как второй.

Допустимы измеримые по Борелю реализации управлений игроков и[М-]0) = {u(t) G R"u, t, ^ t < 0} и u[i,[.]0) = {«(t) 6 R"-, U < t < которые удовлетворяют геометрическим и интегральному ограничениям:

l|u(i)||„ ^ Au, ||w(i)||. ^ A,, U <£<t?; /а(т)||и(т)||вА- < p.. (17)

i.

Здесь || • ||„ и || • ||„ — нормы в R"» и R"»; Au, A„ — задапные постоянные; a(r) — скалярная, положительная, непрерывная на [i0, Щ функция.

Дополнительно к фазовому вектору х системы (16) вводится переменная р, изменение которой описывается уравнением

р=-a(i)||w||u, p(£,)=pt,

(18)

и которая оценивает запас ресурса управления. Тогда интегральное ограничение из (17) переписывается в виде фазового ограничения: 0 ^ р ^

В пространстве переменных (£, х, р) определяется компактное множество К0 возможных позиций расширенной системы (16), (18). Под движением [■]■!?] исходной системы, порожденным из позиции (£«,х*,р,) е К0, £» < 1?, допустимыми реализациями и [£„[■]'?) и г? [-]г?), понимаем абсолютно непрерывную функцию {х(£) еМ", -< £ ^ 1?, х(£„) = х,}, которая при почти всех £, £ ^ г? вместе с и — и(£) и V = г/(£) удовлетворяет уравнению (16). При этом множество Ко определяется так, что имеет место включение

(£,х(£),р(£)) е К0, р(£) = р. - / а{т)\\и{т)\\и(1т, и ^ £ ^ 1?.

г.

Показатель качества, оценивающий движение х[£,[•]г?], имеет вид (3). Задача первого игрока (управления) — доставить показателю (3) как можно меньшее значение. Цель второго игрока (помехи) противоположна. Под стратегией I/ первого игрока понимаем произвольную функцию

и ={£/(£,Х,р,е) £Г", ||с;(£,х,р,£)||и ^ Лц, (£,х,р) е Ко, е > 0}.

Из заданной позиции (£», ж„, />,) е Ко закон управления Ы = {II, е, Д^) в паре с допустимой реализацией V [£»[•]!?) управления второго игрока формирует движение (х[£»[•]$],/э[£*[•]$]) расширенной системы (16), (18) как решение пошаговых уравнений

х(£) = Л(£)х(£) + В(£К+С(£)«(«), , < , . , ■ , ,

при начальном условии х(£1) = х„, р{1\) — р,. Величина щ назначается законом Ы по правилу

О, если 0 ^ р(£,) < /аМНиЗМт, . и*, иначе,

Гарантированный результат закона 1А определяется равенством

Т{Ы-,и,х,,р<)= йир 7(х[£,[-]1Я).

„[ЦЮ

Оптимальным гарантированным результатом первого игрока будет Ги(£4,х«, р,) = тГНтзирИтяирГЧ^ = (С/, е, Д^);£„,х»,р»),

и е->0 д4

Стратегию Щ, на которой достигается инфимум, называем оптимальной.

и,- =

Для С > 0 закон управления Щ называем (^-оптимальным, если

T(WC; tr, х„ р„) ^ ru(i„ х„ р.) + С-

По аналогичной схеме с понятными изменениями для второго игрока определяются оптимальный гарантированный результат Г„(£,, ж,, р„), оптимальные стратегии V& и ^-оптимальные законы управления Vf.

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

Для отрезка времени управления [f., фиксируем разбиение As = вида (4) такое, что t?j eAs,i = h(tm), ...,N. Для р. ^ 0 и j = 1,..., к через Щ{р„) обозначим множество всех измеримых функций u[tj[-]tj+1) = {u(i) е R"", tj ^ t < ij+i} таких, что

INOII« < A», tj^t<tj+1, f a(r)||U(r)||udr < p„

а через fj — множество измеримых функций v[ij[']f_,+1) = {v(t) € Rn", tj < t < tj+1}, удовлетворяющих условию

IKOIIv^A», tj^t<tj+1. Пусть m € Rn, p ^ 0, обозначим

Arpj(tt,m,p) = minmax / (ш, Ф(0, т)(В(т)и,(т) + C(r)u,(r)))dr. i 'j tj

Попятно по шагам разбиения As определяем множества Gf(t*) векторов m € R" и скалярные функции y>*(i„m,p), m е Gf(tt), р ^ 0. Определяющие соотношения аналогичны процедуре (5)-(7). Отличие состоит в том, что в (6) функция ipj(t,, •) задается теперь равенством

■ф^и, тп, р) = min [Аф,(и, тп,р- р') + tpj+1(tt,m, р% m € Gj(tt), р ^ 0,

Rj(t*,p) = {p - max[0,p - Au f a(r)dr] < p' sj p},

tj

при этом овыпукление производится по m е Gj (t,) при каждом 0 < р < р,. Для х £ R", р > 0 и j — 1,..., к + 1 рассмотрим величины

ef{t„x,p;As)= шах [(т,Ф(г?,^)х) + <pf(tr,m,p)]. (19)

m€G.- (t*)

Оказывается, что для всякой последовательности разбиений Д^, 5/. —> 0 при к -> оо, существуют пределы

c±(tt,xf,p^) = lim ef(t*,x„pt; Д,,J, (20)

которые являются равномерными по (i*,x«,pt) € /Го и не зависят от выбора последовательности разбиений Ask.

Лемма 16.4. Для любого числа £ > 0 существует число 5* > 0 такое, что, каковы бы ни были позиция (£,, х„, р.) 6 К0 и разбиение Ag вида (4), i% 6 As, i = h(tt),..., N, 5 ^ 6", будут выполнены неравенства

|e±(tt,x„p*) - ef(tt,xt,pt;As)| «S

На основе предельных величин (20) методом экстремального сдвига на сопутствующую точку определяются стратегии Щ и У^. Теорема 16.1. В задаче (16)—(18), (3) имеют место равенства

е~(£„х,,р,) = Ги(£„х„р.) = I\{и,х.,р,), (и,х„р„) е Ко-

Стратегии Щ и являются оптимальными.

Из теоремы 16.1 и леммы 16.4 следует, что величина е^(£»,х„,р»; Д^) из системы величин (19) с измельчением разбиения As приближает оптимальные гарантированные результаты Ги(£,,х,,р,) = Г„(£,,х»,р*). Кроме того, по системе величин (19) методом экстремального сдвига на сопутствующие точки удается построить ("-оптимальные законы управления игроков.

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

Пример 18.2. Движение динамической системы описывается уравнением

Гх> = + к = и= 0 <£<^ = 2,

( х2 = -0,5x1 — 0,05х2 + 6(£)и,

х = (хьх2) е К2, «еК1, не К1, _ / 2 + 2 соэ 27г(£ — 0,5), если £ 6 [0,5; 1,5], (21)

14 иначе,

Г 0,3, 1 0,1

n(t\ - } J'3' если 1 е t°'6; 1>41 Щ) " Ь> иначе,

на реализации управлении игроков наложены ограничения

2

|u(t)| ^ 1, \v(t)\ «Л о < t < 2; / \u(T)\d,T < р. = 1, (22)

о

заданы начальное условие

х, = (х1(0),12(0)) = (0,5, 0,1), (23)

и показатель качества

7(® [и[•]*]) = + М1) - 0,5|2 + |ц(2) + 0,512 + |х2(2)|2. (24)

В численных построениях использовались равномерное разбиение Д^ отрезка времени управления [0,2] с диаметром 5 — 0,01, значение параметра точности £ — 0,05 и подходящие значения параметров пиксельных представлений. Найденное численно значение величины (£,,, ж,, р*), приближающее оптимальные гарантированные результаты игроков, составляющих цену дифференциальной игры (21)—(24), составило 0,702.

В результате проведения симуляции процесса управления, когда управляющие воздействия игроков формировались построешшми численно С-опти-мальными законами, реализовалось значение показателя качества (24) 7 = 0,731 и е^" (<», х,, р,). Реализация движения, полученная в симуляции, приведена на рисунке 4.

X

0,5

0

-0,5 -1

-1,5

0 0,5 1 1,5 г

Рис. 4: Реализация движения в примере 18.2.

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

Работа выполнена при поддержке Программ Президиума РАН «Математическая теория управления» (проект 09-П-1-1015) и «Динамические системы и теория управления» (проект 12-П-1-1002), грантов РФФИ (проекты 11-01-12088-офи-м-2011, 14-01-31319-мол_а, 12-01-31247-мол_а).

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

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

1. Корнев Д. В. О численном решении позиционных дифференциальных игр с нетерминальной платой // Автоматика и телемеханика. — 2012. — №11. — С. 60-75.

2. Корпев Д. В., Лукоянов Н. Ю. О численном решении дифференциальных игр с нетерминальной платой в классах смешанных стратегии // Вестник Удмуртского Университета. Математика. Механика. Компьютерные науки. — 2013. — №3. — С. 34-48.

3. Корпев Д. В. Об одном численном методе решения позиционных дифференциальных игр в смешанных стратегиях // Вестник Тамбовского университета. Серия: естественные и технические науки. — 2013. — Т. 18, №5-2. — С. 2556-2558.

4. Корнев Д. В., Лукоянов Н. 10. К задаче управления на минимакс позиционного функционала при геометрических и интегральных ограничениях на управляющие воздействия // Труды Института математики и мехапики УрО РАН. — 2015. — Т. 21, №2. — С. 87-101.

5. Корпев Д. В. Свидетельство о государственной регистрации программы для ЭВМ №2015614531 «-Программный комплекс для решения позиционных дифференциальных игр с нетерминальной платой». Федеральная служба по интеллектуальной собственности (Роспатент). Зарегистрировано 20.04.2015.

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

6. Komev D., Lukoyanov N. On Numerical Solving of Differential Games with Nonterminal Payoff // 15th IFAC Workshop on Control Applications of Optimization. — Vol. 15. — International Federation of Automatic Control, 2012. — P. 71-76.

7. Kornev D., Lukoyanov N. On Numerical Solution of Differential Games in Classes of Mixed Strategies // Proceedings of the 19th IFAC World Federation of Automatic Control, 2014. — P. 1550-1555.

8. Корнев Д. В. К вопросу о программной реализации решения дифференциальной игры с нетерминальной платой // "Современные проблемы математики", Труды 42-й Региональной молодежной конференции. — Екатеринбург: УрО РАН, 2011. — С. 34-37.

9. Корпев Д. В., Лукоянов Н. Ю. Численные методы решения линейных позиционных дифференциальных игр с нетерминальной платой // "Алгоритмический анализ неустойчивых задач", Тезисы докладов Международной конференции, посвященной памяти В. К. Иванова. — Екатеринбург: ИММ УрО РАН, 2011. — С. 248.

10. Корнев Д. В. О численном решении дифференциальных игр с нетерминальной платой // "Современные проблемы математики", Тезисы Международной (43-й Всероссийской) молодежной школы-конференции. — Екатеринбург: Институт математики и механики УрО РАН, 2012. — С. 136-138.

11. Корнев Д. В. Об одном численном методе решения задач конфликтного управления // Известия Института математики и информатики УдГУ. — 2012. — №1 (39). — С. 67-68.

12. Корнев Д. В. О численном решении дифференциальных игр на минимакс позиционного функционала в классах смешанных стратегий // Динамика систем и процессы управления: тез. докл. Междунар. конф., посвящ. 90-летию со дня рождения акад. H.H. Красовского. — 2014. — С. 111-113.

13. Корпев Д. В. Об оптимизации гарантии при интегральных ограничениях на управляющие воздействия и нетерминальном показателе качества // Труды XII Всерос. совещ. по проблемам управления (ВСГГУ-2014). — 2014. — С. 2059-2070.

14. Корнев Д. В., Лукоянов II. Ю., К задаче динамической оптимизации гарантии при геометрических и интегральных ограничениях на возможности управления // Теория управления и теория обобщенных решений уравнений Гамильтона-Якоби: Тез. докл. II Междунар. семинара, посвященного 70-летию со дня рождения акад. А.И. Субботипа. Екатеринбург, Россия, 1-3 апреля 2015 г. — Екатеринбург: ИММ УрО РАН, УрФУ, 2015. - С. 94-95.

Подписано в печать 08.07.2015. Формат 60x90 1/16 Бумага офсетная. Усл. печ. л. 1,5. Тираж 125 экз. Заказ № 295. Отпечатано в типографии ИПЦ УрФУ 620000, Екатеринбург, ул. Тургенева, 4