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

кандидата физико-математических наук
Ладейщиков, Александр Николаевич
город
Екатеринбург
год
2013
специальность ВАК РФ
05.13.18
Диссертация по информатике, вычислительной технике и управлению на тему «Некоторые задачи игрового управления»

Автореферат диссертации по теме "Некоторые задачи игрового управления"

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

ЛАДЕЙЩИКОВ Александр Николаевич

НЕКОТОРЫЕ ЗАДАЧИ ИГРОВОГО УПРАВЛЕНИЯ

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

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

21 ' ЮЯ 2013

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

005538995

005538995

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

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

профессор Красовский Андрей Николаевич

Официальные оппоненты: Ченцов Александр Георгиевич, доктор физико-

математических наук, член корреспондент РАН, ФГБУН институт математики и механики имени Н.Н.Красовского, главный научный сотрудник отдела управляемых систем

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

Ведущая организация: ФГБОУ ВПО «Челябинский государственный

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

Защита состоится » ЪЬ^Я 2013 г. в 41 ^^часов на заседании

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

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

Автореферат разослан УЬЛ 2013 г.

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

В.Г.Пименов

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

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

A.В.Мезенцева, Е.Ф.Мищенко, М.С.Никольского, Г.Олсдера, Ю.С.Осипова,

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

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

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

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

доставляющие некоторые величины р°, которые можно было бы назвать по определению ценой игры. Большинство таких конструкций базируется на предельном переходе по величине У от подходящих многошаговых процедур или от подходящих стохастических игр для систем с исчезающим шумом. В работах Н.Калтона, А.В.Кряжимского, А.И.Субботина, А.Г.Ченцова, Р.Эллиота развиты конструкции, где стратегии

(квазистратегии) формализуются как операторы, которые определяют отклик в текущий момент t одного из игроков на историю действий его противника вплоть до этого момента времени t. В работах Н.Н.Красовского, Э.Роксина предложены аксиоматические определения стратегий, движений и соответствующих игровых задач управления. В работах Н.Ю.Лукоянова, М.С.Никольского, Ю.С.Осипова, Ф.Л.Черноусько, B.C. Шишмакова рассматривались задачи игрового управления, в которых один из игроков получает информацию о положении системы с постоянным запаздыванием. В работах В.Г.Болтянского, Р.В.Гамкрелидзе, А.Н.Красовского,

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

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

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

управления при решении модельного примера с применением численных методов и составления комплекса (пакета) программ для ЭВМ.

Методы исследования. Основным методом исследования является метод экстремального сдвига на сопутствующие точки'. Предложенные численные алгоритмы реализованы автором в виде программы на языке Pascal2.

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

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

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

'Krasovskii A.N., Krasovskii N.N. Control Under Lack of Information. Boston: Birkhauser, 1994.

2Красовский A.H., Ладейщиков A.H. Программа для реализации алгоритма оптимального позиционного управления и вычисления цены антагонистической дифференциальной игры // а. с. 2013618708 РФ 17.09.2013; заявитель и правообладатель ФГАОУ ВПО «УрФУ имени первого Президента России Б.Н.Ельцина». - № 2013616912; заявл. 01.08.2013.

В третьей главе разработан специальный комплекс (пакет) программ для ЭВМ для решения конкретных задач в игровой постановке такого типа с использованием численных методов [3].

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

Основные результаты диссертации.

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

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

дифференциальных игр.

Разработан комплекс (пакет) программ для решения нелинейных дифференциальных игр.

Апробация работы. Основные результаты диссертации докладывались и обсуждались на конференциях: 14-ой, 15-ой отчетной научно-практической

7

конференции молодых ученых УГТУ - УПИ (Екатеринбург - 2008, 2009), 4-ой научно-практической конференции молодых специалистов, аспирантов и студентов "Информационно-математические технологии и экономическое моделирование" (Екатеринбург - 2010), 19-ой Международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2012» (Москва - 2012), 5-ой Всероссийской научно-технической конференции «Безопасность критичных инфраструктур и территорий», 20-ой Международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2013» (Москва - 2013), на научных семинарах кафедры вычислительной математики ФГАОУ ВПО «УрФУ имени первого Президента России Б.Н.Ельцина» и отдела управляемых систем ФГБУН «Институт математики и механики имени H.H. Красовского».

Публикации. Материал диссертации опубликован в 2 статьях в рецензируемых научных журналах, определенных ВАК [1-2], в монографии [6], в тезисах докладов. На разработанный комплекс программ имеется свидетельство о государственной регистрации программ для ЭВМ [3]. Список основных публикаций автора приведен в конце автореферата.

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

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

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

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

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

Рассматривается объект, движение которого описывается дифференциальным уравнением

х = А(/)х + В(0и + С(0у, ta<t<û, us Р, veQ.

Здесь х - п -мерный фазовый вектор, t время, t0 и г? зафиксированы, A(f), В(/), С(/) - кусочно-непрерывные матрицы -функции, и - г -мерный и v - s -мерный векторы ( и - управление, v -помеха). Все векторы трактуются как векторы-столбцы. В (1) Р <z Rr и Q с R'- ограниченные замкнутые множества векторов, т.е. - компакты.

Показатель качества у для процесса {^t'oN^l; "(ЛИ*?]; v(ta[-]û]}={x[t], ta<t<ê-, u[t], t0<t<é; »[/], t0<t<â} имеет вид

1>

а

Здесь х - некоторый фиксированный и-мерный вектор, символ |/| обозначает евклидову норму вектора /; ?>(/)и?У(0 суть заданные кусочно-непрерывные функции, <р^)> а, }/(/)> /3, а > 0, /? > 0.

Рассматривается задача об управлении по принципу обратной связи на минимакс заданного критерия У (2) при дефиците информации о действующих динамических помехах. Кроме того, информация о состояниях идет с запаздыванием и еще с искажением. Текущая информация о фазовых состояниях х[/] объекта (1) при г >/„ + А , где й>0 величина запаздывания, используется в виде п -мерного вектора х"[г]

Начальное фазовое состояние х[*0] = х0 объекта также сообщается с искажением. Обозначим

В таком случае в качестве достаточного информационного образа У[<], на основании которого целесообразно формировать оптимальную стратегию управления и0((,У,е) выбирается совокупность компонент определяемых параметрами системы (1), критерия качества 7 (2) и величинами (3),(4). В рассматриваемой задаче величина оптимального гарантированного результата для состояния {/,, У [/, ]} называется величина

(3)

х,

0 ~ Х0 ^

(4)

Ри (t., Y [ /. ]) = inf limI lireI sup p (Vs = {u (■), e, A ,}, /,, Y [ ]), (5)

u(-) e->0 S-*О Д^ V-7

Для построения величины (5) используется метод стохастического программного синтеза3. Устанавливается, что величина оптимального гарантированного результата (5) удовлетворяет условию и -стабильности4. Стратегия и°(/,У,е) называется оптимальной универсальной, если она гарантирует результат (5) и для любой возможной позиции работает по одному и тому же алгоритму. Для построения оптимальной стратегии u°(t, Y, е) используется метод экстремального сдвига на сопутствующие элементы, который в данной работе трансформируется к следующему виду.

В момент времени е Аг в некоторой окрестности ЛТД?,.] информационного состояния находится сопутствующая точка Z°[/J

удовлетворяющая условию

Pi (t,,Z0 [/,])= nun paAt.„Z) (6)

После этого выбором вектора управления «°['(] = u°(in Y[t,], е) е Р осуществляется экстремальный сдвиг состояния к сопутствующему

состоянию Z°[t,].

Устанавливается, что построенная таким методом стратегия u"(t, Y, е) является оптимальной универсальной стратегией.

Основным результатом первой главы является следующая теорема:

3 Красовский H.H., Третьяков В.Е. Стохастический программный синтез для позиционной дифференциальной игры //Докл. АН СССР. 1981. 259. №1.

4Красовский H.H. Управление динамической системой. Москва: Наука 1985.

Теорема 1.2 Построенная чистая стратегия управление и"(■) = и"(!,У, е) является оптимальной универсальной стратегией для рассматриваемой задачи конфликтного управления для динамической системы (I) с критерием качества процесса управления у (2). При этом

стратегия и"(•) = У, е) строится как экстремальная к функции оптимального гарантированного результата У).

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

Результаты первой главы опубликованы в работе [1].

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

{м°(-) = м°(/,д:,£), V0(■) = V^>(t,x,e)} рассматриваемой антагонистической дифференциальной игры. Решение задачи базируется на методе экстремального сдвига на сопутствующие точки. Оптимальные стратегии м°(-) = и0(/,*,£) и У°(-) = строятся как экстремальные к

функции цены игры Р°((,х) . При этом цена игры для любой возможной позиции {?, х) строится известным методом верхних выпуклых оболочек', вытекающим из метода стохастического программного синтеза3. Существенную роль при решении поставленной задачи играют некоторые виртуальные (компьютерные) модели, играющие роль поводыря (лидера) для реального конфликтно-управляемого х - объекта.

Рассматривается объект, описываемый векторным нелинейным дифференциальным уравнением

х = /^,х,и, V), Г0<Г<г?, не Р, ье£>, (7)

где х - п -мерный вектор, 7 - время, начальный и конечный моменты времени ^ и 13 зафиксированы, и -5-мерный вектор управления, V - Г-мерный вектор помехи, Р и б - компакты.

Функцию / полагаем непрерывной по х, и, V ив каждой ограниченной области в пространства {*} удовлетворяющей условию Липшица по х с константой : т.е.

, (8) <ьг и(2)-*0) ,

'Krasovskii A.N., Krasovskii N.N. Control Under Lack of Information. Boston: Birkhausen 1994.

3 Красовский H.H., Третьяков В.Е. Стохастический программный синтез для позиционной дифференциальной игры // Докл. АН СССР. 1981. 259. №1.

где х(,) е G, /=1,2.

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

= {x[t], t„<t <т)} объекта (7), реализации управления ы[/,[ ]г?)= {и[/]е Р, /,</<г?} и реализации помехи

v[i,[-]^) = {w[/]e ß, i, <t<r)} следующего вида

7{x[ttimu[t,[-mv[tt[-]if)) = tf (9)

= Jсу(/,*[/], u{t], v[t])dt + ç{x[d]). t.

Здесь функция О) непрерывна по t, X, и, V и удовлетворяет условию (8) при замене символа / на СО , а функция <р непрерывна по х.

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

min max {(/• f {t, x,u, v) ) + y • û)(t, x, u,v)} =

KP " '

(10)

= max min {(/• /(/, x, u,v))+ y ■ a>(t,x, u,v)},

vgQ ueP '

где / - любой n -мерный вектор, У - любой скаляр, символ (/•/(/, x,M,t>)) - обозначает скалярное произведение в пространстве R".

Для дифференциальной игры для х - объекта (7) с функционалом У (9) рассматривается вспомогательная дифференциальная игра-2 для расширенной х = { х, хл+1} - системы

* = /(>, Х,и, V),

(П)

хп+1 =со{Г,х,и,ь), иеР, 1>€0, /0</<г?

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

г = у{х[а-т)=<р(х[13])+хп+№1 (12)

где Зс[а-]|*]= {?[/]= {*[*], *„+,[/]}, t,<t<б}.

Функционал (12) является позиционным5. А именно, позиционньш функционалом (критерием качества) называется функционал от движения *['.[•]«?]= {*[']={*[']> *п+1[']Ь х -объекта,

который можно представить в виде

Г&[*.[■]&]) = а), («)

где

5 Красовский А.Н. О позиционном минимаксном управлении // Прикл. математика и механика. 1980. Т. 44. Вып. 4.

и функция ]> &) , при фиксированном отрезке движения

х [ [" ] t* ] непрерывна и не убывает по ОС .

В случае функционала [']*?]) (13) имеем

= а = = + (15)

С использованием метода экстремального сдвига на сопутствующие точки {/., vv°[/J} доказывается следующее утверждение:

Лемма 2.1. Дифференщюльная игра-2 для X -системы (11) с

позиционным функционалом Y (12) имеет цену

р\(t, х) = х ) = х ) и седловую точку {u\.) = u\t,X,£),v\-) = v\t,X,£)) .

При доказательстве Леммы 2.1 также используется метод6'7, обеспечивающий отслеживание реального X -объекта (11) и его виртуальной (компьютерной) w -модели:

w = f(t, w, u„V,), wK^=a(t,w,u„vt), u,e P, v,eQ (16)

В рассматриваемом случае этот метод трансформируется в следующие утверждения:

6Krasovskii A.N., Choi Y.S Stochastic Control with the Leaders-Stabilizers. IMM Ural Branch of RAS.Ekaterinburg.Russia. 2001.

7Красовский A.H., Ладейщиков A.H. Некоторые задачи игрового управления. Екатеринбург: УрГСХА, 2012.

Лемма 2.2. Пусть заданы позиция {(,, х,} для X -объекта (11), позиция { t,, w,} для W -модели (12) и число £ > О. Тогда можно указать число > 0 такое, что если векторы и0 и У,0 определены из условий

max {(s, /О,, x,,u°,v)) + yt Ü)(t,,x,,u°,v)} =

veQ » '

= min max {(s,f(t„x„u, v) ) + yt co(tt,xt,u,v)},

usP vcQ 4 '

(17)

min {( j. f(t„ u„ v?))+y, ü)(t„w„u„v?)} = = max min {(st /(/,, w„ ut, «,)) + y, a>(t,,w,,ut,vt)},

u.eß u.eP 4 '

где s, =x, -w„ yt = *(n+D* -w((I+1)„ то при t, <(< t, + S (e)

действие «°[ f,[ •] О = { u°[ t ] = M°, t,<t<tt + S ( £ ) } « иаре с любым действием V[ [ ' Ю . и действие [["]0 = { [О = > t, < t < t, + 6 {£)} в паре с любым действием и„[/,[•]/] породят из позиций {t,,x,} и {I., н\} движения

*[i.[-]/*]={Jc[/], tt<t<t'} и

= {*,</<*"}, длякоторых:

X(t,x[tl w[t]) = A(t„x„w.) + e(t-t.) (18)

Здесь Л ( /, х, w) функция вида:

Л(/, Зс, й) = |х-й|2ехр {-2 Гс(/-/„)}, (19)

где = 2/,с ; где . постоянная Липшица из (8).

Лемма 23. Формулируется аналогично лемме 2.2 при взаимной замене символов и и V, Р и

Наряду с позиционной дифференциальной игрой-2 относительно расширенной {х = { х, Хп+1}} рассматривается некоторая дифференциальная игра-3, отличающаяся от игры-2 лишь тем, что стратегии в этой игре-3 определяются как функции и ((, х, £ ) и и (/,*,£), то есть как чистые позиционные стратегии для исходной дифференциальной игры для х - объекта (7) с функционалом у (9).

Доказывается следующая

Лемма 2.4. Рассматриваемая дифференциальная игра-3 имеет цену р° х ) = х) и седловую точку {м°() = «0 х, £),

V0(•) — V0х, £)} , складывающуюся га экстремальных стратегий ие(-) = ие(1,х = {х,х11+1 =0},£) и д'(-) = и°«,х = {х,хп+1=0},£).

Устанавливается, что в выражении функции цены игры р\ х )

координата х^, входит аддитивно, поэтому принимая хш = 0 построение

седловой точки {м•) = и°((, х, б), У°(-) = 1>°(/, х, £)} методом экстремального сдвига остается прежним.

Основным результатом второй главы является приведенное выше оригинальное и конструктивное доказательство следующего утверждения.

Теорема 23. Рассматриваемая дифференциальная игра для системы (7) с функционалом (9) имеет цену х) =

(и + 1) 0}) и седловую точку {и (•), V (•)} , складывающуюся из экстремальных универсальных стратегий Ъе(■) = %'х = {х,х^=Щ,Е) и Ье(-) = Ье{1,х = {х,хм — 0},

Результаты второй главы опубликованы в работе [2].

В третьей главе теоретические результаты иллюстрируются на решении модельного примера. Рассматривается движение материальной точки с единичной массой в горизонтальной плоскости {д{,д2} под действием управляющей силы и={их,и2} и силы помехи и = {и,,1>2} на фиксированном отрезке [ (0, г? ] времени процесса управления. Уравнение движения объекта в форме второго закона Ньютона имеет вид

4 = и + Ь, t0<t<tf, (20)

где д - двумерный вектор, и и V - векторные управляющие воздействия, удовлетворяющие условиям

\и |= (и,2 + и22УА < ц,

(21)

где // и т] заданные числа.

Рассматривается задача об управлениях и и V , которые соответственно минимизируют и максимизируют величину

у= ](и-ь )А+\д[&]\,

I.

где («•» ) = м,и1+м2У2, к[г?]|=(9,2[г?] + ?22[г?])Й. t0<tt<д.

Рассматриваемая задача формализуется в антагонистическую дифференциальную игру двух лиц для х - объекта:

(23)

х3 = м, + У,, х4 = и2 + v1.

где х1 = д{, х7 = с функционалом 7 :

у = |<и-и >Л + (*2[г?] + д:2[г?])Х- (24)

Для рассмотренного Зс = { д;, хл+1} -объекта добавляем нелинейную компоненту

Л5 = ( И + V ) = М,1»[ + «2и2. (25)

В таком случае функционал У (12) принимает вид

В соответствии с результатами из второй главы, рассматриваемая дифференциальная игра для системы (23) с критерием качества У (24) имеет седловую точку { м°( •) = м°(г, х, £ ), V0(•) - V0(t, х, £)} и цену

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

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

Результаты третьей главы опубликованы в работе [2]. На разработанный комплекс (пакет) программ для ЭВМ для реализации алгоритма оптимального позиционного управления и вычисления цены антагонистической дифференциальной игры получено авторское свидетельство [3].

Публикации по теме диссертации

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

1. Красовский А.Н., Ладежциков А.Н. Об одной задаче конфликтного управления при неполной запаздывающей информации II Математическая теория игр и ее приложения. 2011. Т. 3. вып. 2. С.18-36.

2. Красовский А.Н., Ладейщиков А.Н. Задача игрового управления при дефиците информации II Математическая теория игр и ее приложения.

2012. Т. 4. вып. 2. С.57-70.

3. Красовский А.Н., Ладейщиков А.Н. Программа для реализации алгоритма оптимального позиционного управления и вычисления цены антагонистической дифференциальной игры // а.с. 2013618708РФ17.09.2013; заявитель и правообладатель ФГАОУ ВПО «УрФУ имени первого Президента России Б.Н.Ельцина». - № 2013616912; заявл. 01.08.2013.

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

4. Ким A.B., Красовский А.Н., Глушенкова В.В., Ладейщиков А.Н. Управление ВИЧ моделями II Российский иммунологический журнал.

2013.Т. 7 (16). №. 2-3.

5. Красовский А.Н., Ладейщиков А.Н. Оптимизация гарантии в задачах управления механическими системами II Аграрный вестник Урала. 2012.№12 (104).С. 18-21.

6. Красовский А.Н., Ладейщиков А.Н. Некоторые задачи игрового управления. Екатеринбург: УрГСХА, 2012. С.128.

7. Красовский А.Н., Ладейщиков А.Н. Об одной задаче отслеживания движений виртуальной динамической модели движениями реального динамического объекта И Тез.докл. 14-ой Всероссийской научно-практической конференции молодых ученых УГТУ - УПИ. Екатеринбург. 2008.

8. Красовский А.Н., Ладейщиков А.Н. Об отслеживании движения виртуальной модели движением реального движущегося объекта // Тез.докл. 15-ой Всероссийской научно-практической конференции молодых ученых УГТУ - УПИ. Екатеринбург.2009.

9. Красовский А.Н., Ладейщиков А.Н. Об одной задаче отслеживания движений динамического материального объекта и его виртуальной модели II Тез.докл. 4-ой научно-практической конференции молодых ученых "Информационно-математические технологии и экономическое моделирование". Екатеринбург. 2010.

10. Ладейщиков А.Н. Задача игрового управления при дефиците информации II Тез.докл. 19-ой Международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2012». Москва. 2012.

11. Ладейщиков А.Н. Некоторые задачи оптимального игрового управления/1 Тез.докл. 5-ой Всероссийской научно-технической конференции «Безопасность критичных инфраструктур и территорий». Новоабзаково. 2012.

12. Ладейщиков А.Н. Задача игрового управления при неполной запаздывающей информации // Тез.докл. 20-ой Международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2013». Москва. 2013.

Подписано в печать 06.11.2013. Формат 60x84 1/16 Бумага офсетная. Усл. печ. л. 1,4 Тираж 120 экз. Заказ № 2748.

Отпечатано в типографии ИПЦ УрФУ 620000, Екатеринбург, ул. Тургенева, 4

Текст работы Ладейщиков, Александр Николаевич, диссертация по теме Математическое моделирование, численные методы и комплексы программ

Федеральное государственное автономное образовательное учреждение Высшего профессионального образования «Уральский федеральный университет имени первого Президента России Б.Н. Ельцина»

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

04201451182

г/

ЛАДЕЙЩИКОВ Александр Николаевич

НЕКОТОРЫЕ ЗАДАЧИ ИГРОВОГО УПРАВЛЕНИЯ

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

комплексы программ.

ДИССЕРТАЦИЯ

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

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

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

Оглавление

Введение 4

1. Задача конфликтного управления при неполной запаздывающей информации 11

1.1. Движение объекта............................................................................11

1.2. Критерий качества процесса управления......................................15

1.3. Информационный образ..................................................................16

1.4. Стратегия и закон управления. Движение, порожденное законом управления........................................................................19

1.5. Движение информационной У-системы........................................22

1.6. Запаздывание информации............................................................23

1.7. Вспомогательный критерий качества............................................27

1.8. Постановка задачи для у*................................................................28

1.9. Программный стохастический синтез............................................31

1.9.1. Движение виртуальной 1 -модели......................................31

1.9.2. Программный экстремум......................................................35

1.10. Оптимальная стратегия. Экстремальный сдвиг..........................38

2. Задача игрового управления при дефиците информации 43

2.1. Движение нелинейного объекта..................................................43

2.2. Показатель качества........................................................................45

2.3. Постановка задачи для первого игрока........................................46

2.4. Постановка задачи для второго игрока........................................52

2.5. Седловая точка. Цена игры............................................................57

2.6. Дифференциальная игра - 2..........................................................60

2.6.1. Позиционный функционал. Существование

решения в дифференциальной игре - 2............................67

2.6.2. Виртуальная w-модель-лидер............................................69

2.6.3. Сопутствующие точки. Экстремальные стратегии üe(-),Öe(') ......................................................................70

2.7. Дифференциальная игра - 3..........................................................74

2.7.1. Экстремальные стратегии ие (•) , Vе (•)........................80

2.7.2. Существование решения в дифференциальной

игре-3......................................................................................82

2.8. Существование решения исходной дифференциальной

игры....................................................................................................84

3. Моделирование одной задачи игрового управления 86

3.1. Модельный пример........................................................................86

3.2. Численный эксперимент................................................................92

3.3. Алгоритм управления......................................................................94

3.3.1. Алгоритм для м(-) = м°(-) и v(-) = u°(-)......................94

3.3.2. Алгоритм для и(-) = и°(-) и ......................97

3.3.3. Алгоритм для и и(-) = и°(-)......................100

3.4. Программа реализации алгоритма управления........................103

3.4.1. Программа для и(-) = и°(-) и и(-) = о°(-)....................103

3.4.2. Программа для и(-) = и°(0 и ....................106

3.4.3. Программадля и и(-) = и°(-)....................108

Список литературы 112

Введение

Задачи игрового управления, вызванные в свое время практическими задачами, обрели в последние годы форму строгой теории, развивающейся в рамках общей математической теории управления движением. В настоящее время эти задачи рассматриваются в теории дифференциальных игр. При этом усилия многих исследователей в этой области направлены не только на выяснение формальной структуры дифференциальной игры как математически идеализированного предмета, ной на поиски таких подходов к решению задач, которые могли бы привести к результатам, отвечающим возможным запросам практики. Такому становлению и развитию дифференциальных игр способствовали работы Р. Айзекса [1], Л.С. Понтрягина [36, 43 - 46], H.H. Красовского [20 -26, 79], В.Д. Батухтина [67], В.Г. Болтянского [3, 45], Р.В. Гамкрелидзе [45, 76], Н. Калтона [72], А.Н. Красовского [7-9, 78, 79], A.B. Кряжимского [27, 80], A.B. Куржанского [28], Н.Ю. Лукоянова [33], A.A. Меликяна [60], З.Ф. Мищенко [35, 36, 45, 46], М.С. Никольского [37, 38], Ю.С. Осипова [39, 80], H.H. Петрова [41], Л.А. Петросяна [42], Б.Н. Пшеничного [47 - 49], И. Роксина [81], А.И. Субботина [23, 51, 52], H.H. Субботиной [51, 53], В.Е: Третьякова [19, 24, 25, 26, 55], В.И. Ухоботова [56, 82]В.Н. Ушакова [57], В. Флеминга [73], А. Фридмана [74, 75], Ю.Хо [77], А.Г. Ченцова [52, 58], Ф.Л. Черноусько [59, 60], A.A. Чикрия [61], А.Ф.Шорикова [65], Р. Эллиота [72], и других авторов.

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

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

В связи с этим в теории дифференциальных игр остается еще ряд невыясненных вопросов принципиального характера о существовании оптимальных решений в той или иной форме синтеза управляемой системы по принципу обратной связи. Известны трудности, связанные с непосредственной формализацией дифференциальных игр на основе отождествления стратегий с такими управлениями - функциями от текущих позиций, которые удовлетворяли бы стандартным теоремам о существовании решений соответствующих дифференциальных уравнений. Эти трудности вызвали к жизни обобщенные формализации дифференциальных игр, которые рассматривались в ряде работ [1, 7, 23, 41, 42, 60, 62, 67, 72-74, 79] упомянутых выше авторов. Были развиты

формальные процедуры, доставляющие некоторые величины р°, которые можно было бы назвать по определению ценой игры. Большинство таких конструкций базируется на предельном переходе по величине У от подходящих многошаговых процедур или от подходящих стохастических игр для систем с исчезающим шумом. В работах [27, 52, 58, 72] развиты конструкции, где стратегии (квазистратегии) формализуются как операторы, которые определяют отклик в текущий момент I одного из игроков на историю действий его противника вплоть до этого момента

времени t. В работах [21, 81] предложены аксиоматические определения стратегий, движений и соответствующих игровых задач управления. В работах [37, 39, 59, 64] рассматривались задачи игрового управления, в которых один из игроков получает информацию о положении системы с постоянным запаздыванием. В работах [3, 21, 23, 35, 36, 39, 43, 46, 48, 59, 76, 79] разработана стройная формальная модель игрового управления, делающая акцент на одну из двух противоположных задач, из которых можно составить дифференциальную игру. Эта модель позволила выяснить принципиальные вопросы строения дифференциальных игр. В то же время на основе этой модели оказалось возможным разработать методы построения разрешающих управлений для важных игровых задач сближения и уклонения.

Основой для формализации позиционной теории антагонистических дифференциальных игр послужила известная теорема об альтернативе H.H. Красовского и А.И. Суботина [23].

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

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

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

В первой главе для конфликтно управляемой динамической системы, описываемой обыкновенным векторным линейным уравнением, в игровой постановке, рассматривается задача об оптимальном управлении по принципу обратной связи, при неполной информации о динамической помехе и при запаздывающей неточной информации о значениях фазовой переменной, характеризующей текущее состояние системы. Критерий качества процесса управления у задается в виде функционала от движения объекта и реализации управляющих воздействий и помех. Задача на минимакс критерия качества решается в классе чистых стратегий в рамках концепции дифференциальных игр, разработанной в Свердловске (ныне Екатеринбурге). При решении рассматриваемой в первой главе задачи используется метод программного стохастического синтеза [19, 26, 55] и метод экстремального сдвига на сопутствующие точки [8, 79]. Устанавливается оптимальная стратегия управления.

Основным результатом первой главы является следующая

Теорема 1.2 Построенная чистая стратегия управления и°(■) = и0(?,У,£) является оптимальной универсальной стратегией для задачи конфликтного управления для линейной динамической системы с рассматриваемым критерием качества процесса управления УПри этом стратегия и°{-) = и0(/,У,б) строится как экстремальная к функции оптимального гарантированного результата Ри (') = Ри (*> гДе У = ~ информационный элемент (образ),

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

стратегии и°((,У,е) величина б > О есть некоторый параметр точности [7, 66]. Он не является информационной переменной, выбирается и фиксируется нами до или в момент начала решения задачи, участвует в построении оптимальной стратегии методом экстремального сдвига [8, 9] на элементы (точки), сопутствующие информационному образу У = / и влияет на точность решения задачи.

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

Результаты первой главы опубликованы в работе [11].

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

и(-) = и(-) = и^,х,е), соответственно, первого и второго

игроков. То есть в данном случае в качестве информационного образа используется текущая позиция х), т.е. пара - момент времени t и значение х = хУ\ фазового вектора конфликтно-управляемого х-объекта. Фигурирующая в выражениях для стратегий игроков величина 8 > 0, выбирается здесь самостоятельно, каждым из игроков, то есть £ = £и для стратегии и^,х,е) первого игрока, вообще говоря, не совпадает с параметром точности £ = £0 для стратегии и^,х,е). Эти параметры, как и в задаче из первой главы, не являются информационными переменными, участвуют в конструировании оптимальных стратегий и°(-) = и°^,х,£) и и°(•) = о®(1,х,б) , и влияют только на точность решения задачи первым и вторым игроком. Устанавливается существование цены р°^,х) и позиционной седловой

точки {и0(-) = и0У,х,£), и°(-) = *,£■)} рассматриваемой антагонистической дифференциальной игры. Основным новым элементом предложенным в диссертационной работе и рассматриваемым в этой главе является оригинальное доказательство теоремы существования оптимальных решений. А именно, в рассмотрение вводятся две вспомогательные дифференциальные игры-2 и 3. В дифференциальной игре-2 рассматривается вспомогательный критерий качества у, который является позиционным [8, 9]. Тогда для некоторого вспомогательного х -объекта устанавливается существование цены игры седловой

точки {и°(-) = и°((,х,£), и°(-) = и°(г,х,£)}. Переходя к

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

стратегий и°(-) = и°^,х,е) и и0(•) = и°^,х,е). Устанавливается существование седловой точки

{и°(') = и°(1,х = {х,хп+1=0},8), и°(-) = и°^,х = {х,хп+1=0},£)} и

цены игры р1^,х) = р\(¿,х). Далее доказывается, что цена

дифференциальной игры-3: Рз((,х = {х, хп+х = 0}) равна цене исходной дифференциальной игры для х - объекта с критерием качества у .

Решение задачи базируется на методе экстремального сдвига на сопутствующие точки. Существенную роль при решении поставленной задачи играют некоторые виртуальные (компьютерные) модели, играющие роль поводыря (лидера) [78] для реального конфликтно управляемого объекта.

Основным результатом второй главы является следующая Теорема 2.3. Дифференциальная игра для рассматриваемой нелинейной конфликтно-управляемой динамической системы с заданным критерием качества У имеет цену

р (/, *) = х = {х, х{

п+1) 0}) и седловую точку

{и0 (•) = и0 и°(-) = , складывающуюся из

экстремальных стратегий ие(-) = ие(1,х = {х,хп+1= 0},£г) и

ие{-) = Vе{$, х = {х, хп+1 = 0}, ё).

Результаты первой главы опубликованы в работе [12].

Подчеркнем, что все стратегии, построенные в первой и второй главе, являются универсальными [23], то есть работают по одному и тому же правилу, начиная с любого текущего момента времени I = 1 ,...,к в схеме управления по принципу обратной связи.

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

Результаты третьей главы опубликованы в работе [12]. На разработанный комплекс (пакет) программ для ЭВМ для реализации алгоритма оптимального позиционного управления и вычисления цены антагонистической дифференциальной игры получено авторское свидетельство [13].

Теоретические результаты, приведенные в диссертации, базируются на работах авторов [7- 19, 78, 79].

Апробация работы. Основные результаты диссертации докладывались на конференциях: 14-ой, 15-ой отчетной научно-практической конференции молодых ученых УГТУ - УПИ (Екатеринбург, 2008, 2009), 4-ой научно-практической конференции молодых специалистов, аспирантов и студентов "Информационно-математические технологии и экономическое моделирование" (Екатеринбург, 2010), 19-ой Международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2012» (Москва, 2012), 5-ой Всероссийской научно-технической конференции «Безопасность критичных инфраструктур и

территорий», 20-ой Международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2013» (Москва, 2013), на научных семинарах кафедры вычислительной математики ФГАОУ ВПО «УрФУ имени первого Президента России Б.Н.Ельцина» и отдела управляемых систем ФГБУН «Институт математики и механики имени H.H. Красовского».

Публикации. Материал диссертации опубликован в 2 статьях в рецензируемых научных журналах, определенных ВАК [11-12], в монографии [14], в тезисах докладов. На разработанный комплекс программ имеется свидетельство о государственной регистрации программ для ЭВМ [13].

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

Глава 1

ЗАДАЧА КОНФЛИКТНОГО УПРАВЛЕНИЯ ПРИ НЕПОЛНОЙ ЗАПАЗДЫВАЮЩЕЙ ИНФОРМАЦИИ

1.1 Движение об�