Задачи управления для систем с эллипсоидальной динамикой тема автореферата и диссертации по математике, 01.01.02 ВАК РФ

Московский Государственный Университет им. М. В. Ломоносова Факультет вычислительной математики и кибернетики

Месяц Алексей Игоревич

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

Задачи управления для систем с

эллипсоидальной динамикой

01.01.02 — дифференциальные уравнения, динамические системы и оптимальное управление

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

11 НОЯ 2015

Москва 2015

005564544

005564544

Работа выполнена на кафедре системного анализа факультета вычислительной математики и кибернетики федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Московский государственный университет имени М. В. Ломоносова»

Научный руководитель: Куржанский Александр Борисович,

доктор физико-математических наук, академик РАН, заведующий кафедрой системного анализа

факультета ВМК МГУ имени М. В. Ломоносова. Официальные оппоненты: Лотов Александр Владимирович,

доктор физико-математических наук, профессор, главный научный сотрудник ФИЦ «Информатика и управление» РАН Тимофеева Галина Адольфовна, доктор физико-математических наук, профессор, заведующая кафедрой «Высшая и прикладная математика» в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Уральский государственный университет путей сообщения». Ведущая организация: федеральное государственное бюджетное учреждение науки «Институт проблем механики имени А. Ю. Ишлинского Российской Академии Наук» Защита состоится 23 декабря 2015 года в 15 часов 30 минут на заседании диссертационного совета Д. 501.001.43 при Московском государственном университете им. М. В. Ломоносова по адресу: 119991, г. Москва, ГСП-1, Ленинские ГЬры, МГУ, д.1, стр. 52, 2-й учебный корпус, ВМК, аудитория 685.

С диссертацией можно ознакомиться в Научной библиотеке Московского государственного университета им. М. В. Ломоносова по адресу: 119192, г. Москва, Ломоносовский проспект, д. 27

Автореферат разослан «^ » ^ г.

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

доктор физико-математических наук, профессор О* <4-/о/ у Е.В.Захаров

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

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

Изучение динамики трубок траекторий представляет собой одну из актуальных задач современной теории управления [11, 1]. Трубки траекторий возникают, например, при рассмотрении задачи достижимости, в которой требуется описать множество всех терминальных состояний, которые система может достичь к заданному моменту времени из множества начальных состояний, используя допустимые управления. Сопряженной к задаче достижимости является задача разрешимости — задача отыскания всех начальных состояний системы, стартуя из которых, система может при помощи допустимых управлений попасть в терминальный момент на заранее заданное целевое множество. При решении этих задач осуществляется переход от рассмотрения отдельных траекторий к анализу ансамблей траекторий, задающих многозначную динамику исследуемых систем. Для описания эволюции таких ансамблей необходим анализ трубок достижимости и разрешимости — многозначных отображений, сечения которых в каждый момент времени будут являться множествами достижимости и разрешимости соответственно. Изучением динамики подобных трубок занимается теория трубок траекторий. Построение трубок разрешимости позволяет конструировать синтезирующее управление с помощью метода экстремального прицеливания Н. Н. Красов-ского [12].

Задачи достижимости и разрешимости не являются задачами оптимиза-

ции, однако им можно поставить в соответствие задачи оптимизации, которые обеспечивают регулярные методы вычисления их решений. Эффективным общим подходом для решения таких задач является метод динамического программирования, разработанный Р. Беллманом [13] и опирающийся на гамиль-тонов формализм. В основе метода динамического программирования лежит понятие позиции системы. Позиция системы — это минимальный набор параметров, обеспечивающий выполнение принципа оптимальности, выраженного в виде полугруппового свойства для соответствующей функции цены. В простейшем случае позиция совпадает с парой {время, фазовый вектор}. Метод динамического программирования приводит к рассмотрению уравнений в частных производных типа Гамильтона-Якоби-Беллмана. Решение уравнений ГЯБ представляет собой ресурсоёмкую задачу даже для систем малой размерности, однако многочисленные практические задачи требуют рассмотрения подобных задач большой размерности [9]. Таким образом, возникает потребность в создании специальных методов и подходов для решения га-мильтоновых систем большой размерности.

Структура множеств достижимости и разрешимости может быть очень сложной даже для простых систем. Для решения задач анализа динамики трубок до конца, то есть до практически реализуемых алгоритмов, применяется эллипсоидальное исчисление. В работах А. Б. Куржанского были построены параметризованные семейства эллипсоидальных трубок, позволяющие сконструировать внешние и внутренние оценки трубок достижимости и разрешимости для систем с неопределённостью [2]. Численные алгоритмы, осуществляющие построение таких оценок, реализованы в программном па-

кете Ellipsoidal Toolbox для вычислительной среды Matlab [8]. На основе полученных методами эллипсоидального исчисления внутренних оценок множества разрешимости можно строить синтезирующие управления методом эллипсоидального синтеза [2].

Таким образом, особый интерес представляют эллипсоидальные трубки, т.е. многозначные отображения, сечениями которых в каждый момент времени являются эллипсоиды. Невырожденный эллипсоид в Rn описывается двумя параметрами: центром q е R" и положительно определенной симметричной матрицей конфигураций, Q € Rnxn, Q = Q' > 0:

£ (q, Q) = {xe R": (х- q, Q~*(x - ?)) < 1},

или, эквивалентно,

£ {q, Q) = {x& Rn: (x, I) < (q, I) + y/{l,Ql), Для всех I 6 R"}.

Следовательно, уравнения, описывающие динамику эллипсоидальных трубок £ (q(t), Q(t)), также содержат две компоненты: векторную для q(t) и матричную для Q(t).

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

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

исследования поверхности морского дна и картографирования [15,16, 21, 22]. Кроме того, с помощью таких систем осуществляется моделирование поведения стай птиц или косяков рыб [14,16]. Решение задач группового управления широко востребовано на практике.

В работах [3, 4, 5] поставлена задача синтеза целевых управлений для группы агентов, которым необходимо достичь целевого множества, избегая столкновений друг с другом и внешними препятствиями, находясь при этом внутри виртуального эллипсоидального контейнера. Решение при этом строится в два этапа. Сначала рассчитывается виртуальное движение эллипсоидального контейнера, который, производя реконфигурацию, избегает столкновений с внешними препятствиями, после чего находятся синтезирующие управления для агентов внутри контейнера, для которых он служит внешним фазовым ограничением. Использование эллипсоидального контейнера позволяет гарантировать выполнение командного свойства для группы, которое заключается в двух условиях: условии непересечения зон безопасностей каждого из агентов и условия «близости» агентов друг к другу.

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

Задача управления системами с матричными фазовыми траекториями рассматривалась И. В. Чебуниным в работе [7]. В ней исследовалось мат-

ричное дифференциальное уравнение Риккати, которое часто встречается в теории управления:

P(t) = AP(t) + PA'(t) + Mit) - P{t)B'N(t)BP(t), P{tQ) = Po > 0, (1)

где P(t) G Rnxn - фазовая матрица, M(t) S Rnxn и N(t) E Rmxm - матричные управления. Требовалось найти пару {M(t),N(t)}, которая переводила бы систему в момент t\ в заданную положительно определённую матрицу Р*. В работе [7] были получены условия управляемости уравнения (1) для двух случаев: когда управление является произвольной симметричной матрицей и когда оно принадлежит к классу неотрицательно определённых матриц. Для решения задачи исследуемая система сводилась к векторной с помощью операции вытягивания матриц в вектора с использованием тензорного произведения Кронекера.

Матричные фазовые переменные также встречаются в задачах оптимизации наблюдений [26].

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

Научная новизна работы. Полученные результаты являются новыми. В работе рассмотрены новые задачи синтеза управления для систем с матричными траекториями. Работа продолжает исследования работ [7, 3, 4].

Теоретическая и практическая значимость. Работа носит, в основ-

7

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

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

Апробация работы. Результаты работы были представлены в виде докладов на следующих научных семинарах:

1. Семинар «Прикладные задачи системного анализа» под руководством академика А. Б. Куржанского на кафедре системного анализа факультета ВМК МГУ;

2. Семинар «Теория управления и динамика систем» под руководством академика Ф. Л. Черноусько в ИПМех РАН им. А. Ю. Ишлинского;

3. Семинар «Проблемы математической теории управления» под руководством члена-корреспонеднета С. М. Асеева и профессора М. С. Никольского в МИАН им. В. А. Стеклова;

4. Семинар отдела «Математическое моделирование экономических си-

8

стем» в ВЦ РАН им. А. А. Дородницына под руководством профессора И. Г. Поспелова.

Результаты работы были представлены на следующих международных конференциях:

1. Двадцатая международная конференция «Автоматика», Николаев, Украина (2013);

2. Пятьдесят вторая международная конференция IEEE Conference on Decision and Control, Флоренция, Италия (CDC 2013);

3. Двадцать первая международная конференция International Symposium on Mathematical Theory of Networks and Systems, Гронинген, Нидерланды (MTNS 2014).

Публикации. Основные результаты изложены в работах [29, 30, 32, 33], из которых две, [29, 30], опубликованы в журналах из списка ВАК.

Указанные работы выполнены в соавторстве с научным руководителем А. Б. Куржанским. Научному руководителю принадлежат постановки задач. Доказательства теорем и реализация вычислительных примеров принадлежат автору диссертации.

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

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

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

т = тя(ь) + + в{1)и{Г)В\ь), (Жо) = д0, (2)

где е Кпхп — матричная фазовая переменная, и € Етхт — матричное позиционное управление, (¿о — известное начальное положение системы. Задача рассматривается на фиксированном интервале времени [£о, в]. Требуется

минимизировать интегральный функционал на траекториях системы, в

ЧШ = I №, С}®), ЩЬ, (¡(Щ <И + ДО) - М, Б{Я{в) - М)>. (3)

«О

Здесь М, .0 = £>' > 0 — известные матрицы. Геометрические ограничения на значения управления отсутствуют.

Во втором разделе первой главы эта задача сводится, подобно работе [7], к векторной, используя операцию вытягивания матрицы по строкам в столбец, (•) : Жпхт М"т. Важным свойством операции вытягивания является возможность явной записи вытягивания произведения матриц: АВХ = (А ® В')Х, где ® означает операцию тензорного произведения. Оно позволяет переформулировать исходную задачу в векторном виде.

Полученная задача затем решается классическими методами динамического программирования [6, 18]. При этом вводится векторная функция цены:

= тт{Ф(Щ-)) | Щ0) = Щ.

Используя свойства произведения Кронекера, устанавливается, что для векторной задачи можно получить явные формулы для оптимального управления и для параметров функции цены в терминах решения соответствующих уравнений Риккати. Решения этих уравнений оказываются записаны в покомпонентном виде, и встаёт вопрос о возвращении от них к первоначальным матричным обозначениям. Иными словами, если исходная задача формулировалась в операциях умножения, сложения и транспонирования матриц, то можно ли полученный ответ записать в этих же операциях? В третьем разделе первой главы доказывается, что, вообще говоря, это возможно не всегда. Указывается класс систем, для которых такой переход возможен. А именно, доказывается, что это возможно тогда и только тогда, когда параметры системы T(t) и B(t) удовлетворяют следующему соотношению:

T(t) + T'(t) = v(t)I, B(t)B'(t) = v{t)I, t € M],

где fi(t), v(t) — произвольные скалярные функции.

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

В первом разделе второй главы вновь рассматривается линейно-квадратичная задача (2), (3), но теперь её решение строится без выхода из класса матриц. Для этого, отталкиваясь от идей тензорного анализа [23], во втором разделе второй главы предлагается специальная форма записи действия линейных операторов над матричными пространствами. Как известно, действие линейного оператора над R" однозначно определяется заданием образа базиса пространства. Если эти образы «склеить», то получится матрица

И

линейного оператора. В работе проводится аналогичная процедура для матричных операторов.

Действие произвольного линейного оператора Л б С (Цпхп,Мтхт) на базисе матричного пространства, А = и предлагается понимать под аналогом матрицы оператора в векторном случае. Эти объекты в дальнейшем называются представлениями матричных операторов. В данном разделе также строятся правила нахождения представления произведения операторов и представления сопряженного оператора, а также исследуется их взаимосвязь с классической теорией операторов.

Ключевым моментом при этом построении является указание способа сведения задачи нахождения представления произведения операторов к матричному умножению. Пусть заданы представления двух операторов, А = = и В = и пусть ¡{1,з) — произвольное взаимно од-

нозначное отображение множества индексов (г,г,.?' = 1,2,... ,тг, в номера 1,2,..., тг2, а д{г,^ — множества (р, д), р, д = 1,..., т, в номера 1,..., т2. Тогда любому представлению Б = {Г>у}£,-=1) е Мтхт, можно поставить во взаимно однозначное соответствие матрицу

Показывается, что для произведения операторов будет справделиво

о о о

С = АВ.

Таким образом, нахождение п2 • к2 коэффициентов представления оператора С = ЛВ сводится к нахождению коэффициентов матрицы С размера к2 X п2, получающейся как произведение матриц А и В размеров к2 х ш2

12

и m2 х n2 соответственно. Данная формула полезна при реализации вычислительных алгоритмов для матричных операторов, поскольку она позволяет организовывать хранение представлений операторов в памяти согласованно с имеющимся в распоряжении алгоритмом умножения матриц. Данный подход особенно актуален при использовании параллельных вычислений, так как он позволяет применять известные алгоритмы для нахождения произведения матриц, имеющие хорошую алгоритмическую сложность [27, 28]. Более того, имея конкретный алгоритм умножения матриц, можно подобрать под него специальный способ хранения матриц представлений операторов, эффективный именно для этого алгоритма.

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

V(t0, Q0) = тт{Щи(-)) \ Q(t0) = Q0},

и соответствующая производная в уравнении ГЯБ будет уже матричной производной, понимаемой в смысле Фреше.

Кроме того, в этом разделе задача рассматривается при наличии дополнительных фазовых ограничений,

Л2_ < (Q,Q) < А2, 0<А_<А+,

где А_, А+ — известные константы. Эти неравенства ограничивают возможный размер эллипсоида с матрицей конфигураций Q(t) шарами радиусов А_

13

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

В четвертом разделе второй главы проводится сравнение вычислительной сложности методов из первой и второй глав по числу арифметических операций, требуемых при вычислении формул, полученных разными способами. Пусть имеется алгоритм умножения матриц порядка п с числом умножений /(п). Пусть /(п) = 0(па), а € (2,3]. Решение задачи в обоих способах разбивается на два этапа: нахождение в обратном времени параметров квадратичной формы функции цены, определяемых матрицами правой части системы, и нахождение по заданной начальной позиции ¿о, (¿о оптимальной траектории в прямом времени, рассчитывающее управление по найденным на первом этапе параметрам. Доказывается, что:

1. Оба алгоритма имеют одинаковое число умножений порядка п2а на этапе нахождения функции цены;

2. Операторный алгоритм позволяет найти оптимальное управление за число умножений порядка п4, а метод с вытягиванием — за п2а.

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

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

14

ности действий:

1. Записать исходную задачу в операторном виде;

2. Найти представления операторов, входящих в задачу;

3. Решить операторную задачу (её решение аналогично решению векторной задачи);

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

В третьей главе эта схема решения через запись матричных операторов применяется для решения нескольких задач с геометрическими («жёсткими») ограничениями на управление.

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

(и(г), и(ь)) ^ м2 для всех г е [г0,0], (4)

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

м = {<Э : (<2(е) - М, Б(С}(9) - М)) < 1},

где, как и ранее, М, О = Б' > 0 — известные матрицы. Рассматривается задача разрешимости — задача построения множества разрешимости для системы,

\У(1-1иМ) = {<5 е Кпхп: ЗЯи т.ч. ($1 - - М)) < 1,

э [/(•), удв. (4), т.ч. = 15

п = <

Задача решается методом динамического программирования через сведение её к параметрическому семейству линейно-квадратичных задач. Вводится функция цены,

У{Ь 0,д0) = шт тах Ф(^,<Эо, «о,/?(•). ^0)

Щ-) {ао,/»(•)}£"

где

в

Ф(*0, Яо, ао, Р, и) = а0 {СЦ9) - М, ЯДО) -М))+\Щ- <[/(*), щ)) Л>

J Д <0

в

{<*<,,£(•)} : а0>0, > 0, а0 + | 0(*)<Й = 1

Показывается, что искомое будет множеством уровня функ-

ции цены:

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

Ш{А)= У 5(0,(2) СГ.

Множество Ш (Л) позволяет получить наглядное представление о множестве А, при этом имея размерность п, в то время как само А при этом является -мерным. Далее в этом разделе выводятся свойства множества Ш (Л) в случае выпуклости А:

1. Если А выпукло, то и 9JÎ (А) выпукло;

2. Если р (L, А) — опорная фунция матричного множества A, L € то p(l,m(A)) = y/p{lV,A), I е Ж";

3. Ж (conv{^, V2.....Vv}) = conv{£ (0, Vi), £ (0,V2),..., £ (0, VN)};

4. m(Br(Q0)) = £(0,Q0 + rI).

Кроме того, в этом разделе приводится численный алгоритм построения множеств ЭЯ (Л) на практике.

В третьем разделе третьей главы приводится пример применения предложенных методов для построения множества разрешимости, описанного во втором разделе.

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

Q(t) = T(t)Q(t) + Q(t)T'(t) + B(t)U{t)B'(t), Q(to)e£(Qo,Q0), U(t)e£(P(t),P(t)),

где Qo = Q'o > 0 —известная матрица, P(t) = P(t)' > 0 — известная матричная функция, Q°, V(t) — известные положительно определённые операторы в пространствах матриц. Эта задача рассматривается, как и ранее, на фиксированном временном интервале [i0, б]. Ставится задача построения эллипсоидальной (в пространстве матриц) оценки множества достижимости для такой системы. Во втором подразделе эта оценка строится по аналогии с векторным случаем [2] с учетом формул для представлений, полученных во второй главе. Выводятся явные формулы для центра и оператора конфигура-

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

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

В пятом разделе третьей главы полученные результаты применяются для решения задачи реконфигурации эллипсоидального контейнера. Эта задача происходит из теории группового управления [4, 5]. В ней матрич-нозначное движение задаёт виртуальный эллипсоидальный контейнер, который выступает в качестве эталонного движения для группы объектов. Ему требуется, осуществляя необходимое для того изменение своей формы, переместиться из начальной позиции, избегая столкновения с препятствиями, на заранее заданное целевое множество. В разделе приводится пример построения решения задачи реконфигурации эллипсоидального контейнера на плоскости при наличии двух препятствий. При этом контейнер должен удовлетворять геометрическим ограничениям:

Вх_ (д(«)) С £ („(4), <2(ф С Вх+ (?(«)), 0 < А_ ^ А+.

Эти ограничения означают, что в контейнер можно вписать шар радиусом А_ и что он всегда содержится в шаре А+ с центрами, совпадающими с центром

18

контейнера. Динамика центра контейнера задаётся уравнением Я = и{£), д(г0) = ?о> Шо) = «о.

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

1. Определяются гиперплоскости Н\ ¿ = 1,2, заключающие между собой область фазового пространства, содержащую препятствия, и трансвер-сальные им "Щ, г = 1,2, задающие между собой область С для движения контейнера, свободную от препятствий.

2. Строится множество Т\ возможных состояний центра для перехода на область С, и для каждого состояния г 6 7\ строится Ох (г) — множество допустимых матриц конфигураций контейнера. При этом любую пару (д, С)) из Т\ х 0\{г) можно соединить допустимой траекторией с начальной позицией (5о,<Эо)-

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

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

5. Строится множество Гг позиций центра и порождённое им множество 02(г), обладающее тем свойством, что для любой пары (д, £?) из Гг х

xC>2(z) найдётся точка в целевом множестве, которую можно соединить допустимой траекторией с (q,Q).

6. Решается задача синтеза управления для центра контейнера с целевым множеством Тч-

7. Решается задача синтеза управления для матрицы конфигураций с целевым множеством Оъ(г), где z — терминальная позиция центра из предыдущего шага;

8. Решаются задачи синтеза управлений для центра с целевым множеством М..

Множества Oi(z) строятся с помощью множеств вида Приводится

вычислительный пример.

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

Для осуществления разбиения контейнера £ (q0, Q0) на два эллипсоида, £ (?ь Qi) и £ (172, Q2), с внешним и внутренним ограничениями А!,, на собственные значения, соответственно, рассматривается следующая задача:

vol £ (qi, Qi) + vol £ (q2, Q2) max, BxL(qi)C£(qi,Qi), ¿ = 1,2, £(qi,Qi)CBK(qi), г = 1,2,

Ы£(Яь Ох) П Ы£(д2, Яз) = 0,

где через уо1£ (<7, О) обозначается объём эллипсоида1 £ (д, О).

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

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

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

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

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

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

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

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

[1] А. В. Kurzhanski and P. Varaiya, Dynamics and Control of Trajectory Tubes: Theory and Computation, Birkhauser, Boston, 2014.

[2] A.B. Kurzhanski and I. Vdlyi. Ellipsoidal Calculus for Estimation and Control, Birkhauser, Boston, 1997.

[3] Kurzhanski A.B., Varaiya P. On synthesizing target controls under obstacle and collision avoidance // Journal of Franklin Institute. 2010. February. V. 347, № 1. Pp. 130-145.

[4] Куржанский А. Б. Задача управления групповым движением. Общие соотношения // Доклады Российской Академии наук. Т. 426, №1. С. 20-25 (2009).

[5] Куржанский А. Б. О задаче группового управления в условиях препятствий // Труды института математики и механики РАН, Т. 20, №3, С. 166-179 (2014).

[6] Kurzhanski А.В., Varaiya P. Dynamic Optimization for Reachability Problems // Journal of Optimization Theory and Applications, V. 2, P. 227-251 (2001).

[7] Чебунин И.В. Условия управляемости для уравнения Риккати // Дифференциальные уравнения. 2003. Т. 39, № 12. С. 1654-1661.

[8] Kurzhanskiy A. A. and Varaiya, P. Ellipsoidal Toolbox.

http://systemanalysisdpt-cmc-msu.github.io/ellipsoids/

[9] Куржанский А. В., Дарьин A. H. Параллельный алгоритм вычисления инвариантных множеств линейных систем большой размерности при неопределённых возмущениях // Журнал вычислительной математики и математической физики. 2013. Том 53, №. 1. С. 47-57.

[10] Kurzhanski А.В., Varaiya P. Optimization of Output Feedback Control Under Set-Membership Uncertainty // Journal of Optimization Theory and Applications. 2011. V. 151. Pp. 11-32.

[11] Kurzhanski A.B. and Filippova, T.F., On the theory of trajectory tubes: a mathematical formalism for uncertain dynamics, viability and control // Advances in Nonlinear Dynamics and Control. Progress in Systems and Control Theory, vol. 17, pp. 122-188 (1993).

[12] N.N. Krasovskii and A.I. Subbotin, Game-Theoretical Control Problems, Springer, New York, 1988.

[13] Беллман P. Динамическое программирование. M.: ИЛ, 1960.

[14] R. Olfati-Saber, "Flocking for multi-agent dynamic systems: algorithms and theory," IEEE Trans. Automatic Control, vol.51, No. 3, 2006, pp. 401-420.

[15] Group Coordination and Cooperative Control / Eds. K.Y, Pettersen, J.T. Gravdahl, H. Nijmeijer. Berlin: Springer-Verlag, 2006.

[16] Cooperative Control / Eds. V. Kumar, N. Leonard, A.S. Morse. Berlin: Springer-Verlag, 2004.

[17] A.I. Subbotin, Generalized Solutions of First-Order PDE's. The Dynamic Optimization Perspective, SCFA, Boston, 1995.

[18] W. H. Fleming and H. M. Soner, Controlled Markov Processes and Viscosity Solutions, Springer-Veriag, New York, 1993.

[19] Clarke F.H., Ledyaev Y.S., Stern R.J., and Wolenski P.R., Nonsmooth Analysis and Control Theory, Springer, New York (1998).

[20] Lions P.-L. General solutions of Hamilton- Jacobi Equations, Pitman, London (1982).

[21] O.Junge, S.Ober-Bloebaum, "Optimal reconfiguration of formation flying satellites," IEEE Conference on Decision and Control and European Control Conference ECC, Seville, Spain, 2005, pp.66-71.

[22] Р.И. Козлов, H.H. Максимкин, Л.В. Киселев. Устойчивость конфигураций группового движения автономных поводных роботов в условиях неопределенности // Подводные роботы и робототехника. Т. 5, №19, С. 40-46 (2010).

[23] Рашевский П. К. Риманова геометрия и тензорный анализ. М.: Наука, 1967.

[24] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004.

[25] Steeb W.-H. Problems and solutions in introductory and advacned matrix calculus. London: World Scientific, 2006.

[26] René Boel and Jan H. van Schuppen, "Control of the observation matrix for control purposes," in: Proceedings of the 19th International Symposium on Mathematical Theory of Networks and Systems, Budapest, Hungary, 2010, pp. 1261-1268.

[27] Strassen V. Gaussian Elimination is not Optimal // Numerische Mathematik. 1969. №13, P. 354-356.

[28] Coppersmith D., Winograd S. Matrix multiplication via arithmetic progressions // Journal of Symbolic Computation. 1990. №9. P. 251-280.

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

[29] Куржанский А. В., Месяц А. И. Оптимальное управление эллипсоидальными движениями // Дифференциальные уравнения. 2012. Т. 48. №12. С. 1525-1532.

[30] Куржанский А. В., Месяц А. И. Управление эллипсоидальными траекториями. Теория и вычисления // Журнал вычислительной математики и математической физики. 2014. Т. 54. №3. С. 404-414.

[31J Месяц А.И. Управление эллипсоидальными траекториями // Материалы XX международной конференции «Автоматика», Николаев, Украина, стр. 63-64, 2013.

[32] Kurzhanski А.В., Mesyats A.I. Ellipsoidal motions for applied control: from theory to computation // Proceedings of the 52nd IEEE Conference on Decision and Control, Florence, Italy, pp. 5816-5821, 2013.

[33] Kurzhanski A.B., Mesyats A.I. The Mathematics of Team Control // Proceedings of the 21st International Symposium on Mathematical Theory of Networks and Systems, Groningen, Netherlands, p. 1755-1758, 2014.

Напечатано с готового оригинал-макета

Подписано в печать 19.10.2015 г. Формат 60x90 1/16. Усл.печ.л. 1,0. Тираж 100 экз. Заказ 253.

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8(495)939-3890/91. Тел./факс 8(495)939-3891.