Задачи достижимости и синтеза управлений для гибридных систем тема автореферата и диссертации по математике, 01.01.02 ВАК РФ

Московский государственный университет имени М.В. Ломоносова

Задачи достижимости и синтеза управлений для гибридных систем

01.01.02 — дифференциальные уравнения

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

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

Точилин Павел Александрович

Москва 2008 г.

003461060

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

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

академик Куржанский Александр Борисович.

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

профессор Григоренко Николай Леонтьевич; доктор физико-математических наук, профессор Гусев Михаил Иванович.

Ведущая организация — Санкт-Петербургский государственный университет.

Защита состоится 2009 года в 15.30 на заседании дис-

сертационного совета Д 501.001.43 при Московском государственном университете имени М.В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМиК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ.

Автореферат разослан " 19 2009 г.

Ученый секретарь

диссертационного совета, профессор .^ЪЛ-Ьп/! Е.В.Захаров

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

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

Гибридные системы часто встречаются в различных прикладных задачах из таких областей знания, как автомобилестроение [17], авиастроение, робототехника [10], электроэнергетика, обеспечение безопасного движения в пространстве [18], [19], на суше [15], [21], на воде и др. Математическая модель гибридной системы возникает каждый раз, когда необходимо исследовать взаимодействие среды, непрерывно изменяющейся в соответствии с некоторыми физическими законами, и управляющих элементов, срабатывающих в дискретные моменты времени. Примерами таких комплексов могут служить электронные системы автоматического управления самолетом, либо автомобилем, системы автоматического регулирования температуры, влажности в помещении и др. Возможности подобных систем проявляются шире, чем обычных.

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

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

О

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

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

Задача достижимости состоит в построении множества достижимости гибридной системы, содержащего всевозможные состояния, в которые можно перейти ири помощи допустимых управляющих воздействий из фиксированного в заданный начальный момент времени состояния (или множества таковых). К задачам достижимости примыкают задачи верификации, в которых необходимо узнать, может ли анализируемая система попасть в одно из "нежелательных" состояний, либо, напротив, попасть во множество "желательных" состояний. Такая постановка задачи может быть обусловлена, например, прикладными проблемами обеспечения безопасного функционирования системы. Задачи достижимости и верификации для гибридных систем рассматривались в работах Е.А. Асарина, А.Б. Куржанского, J. Lygeros, S. Sastry, С. Toralin, Р. Varaiya и других авторов.

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

Для решения задачи синтеза может быть использована теория позиционного управления H.H. Красовского [3], [4], [5], а также перекликающиеся с ней методы динамического программирования [9]. Для решения задачи синтеза при этом полезен поиск позиционных управлений, удерживающих траекторию внутри системы слабо инвариантных множеств (попятных множеств достижимости, множеств разрешимости), образующих трубку разрешимости [13] (стабильный мост [5]) и т.н. По найденным слабо инвариантным множествам можно построить синтез с требуемыми свойствами, опираясь на метод экстремального прицеливания, [4].

Применению методов динамического программирования для решения задач управления гибридными системами посвящены работы М. Branicky, М. Borkar, S. Mitter [11], J. Lygeros, С. Tomlin, S. Sastry [16] и другие.

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

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

1) Исследована структура прямого и попятного множества достижимости гибридной системы. Приведены описания указанных множеств в виде попеременных суперпозиций операторов простой структуры, а также в виде множеств нулевого уровня специальных функций цены. Для этих функций методами выпуклого анализа выведены выражения, которые можно использовать для их численного расчета. Получены уравнения типа ГамильтонагЯкоби-Беллмана, которым должны удовлетворять указанные функции. Предложены численные методы построения множеств достижимости при помощи аппарата эллипсоидального исчисления, произведены расчеты для конкретных примеров систем.

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

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

Научная новизна работы. Полученные результаты являются новыми.

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

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

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

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

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

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

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

Апробация работы. Результаты работы были представлены в виде докладов на научно-исследовательских семинарах кафедры системного анализа факультета ВМиК МГУ (рук. академик Куржанский A.B.), а также на следующих конференциях:

• международная конференция студентов и аспирантов по фундаментальным наукам "Ломоносов-2005" (Москва, МГУ, апрель 2005 г.);

• VII международная конференция "Дискретные модели в теории управляющих систем" (Московская область, Покровское, март 2006 г.);

• 13-ая международная конференция но автоматическому управлению "Автоматика-2006" (Винница, Украина, сентябрь 2006 г.);

• конференция "Ломоносовские чтения" (Москва, МГУ, апрель 2008 г.);

• конференция "Тихоновские чтения" (Москва, МГУ, октябрь 2008 г.).

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

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

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

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

и«),г = 1,...,ЛГ, (1)

где в каждый момент времени активной является одна из указанных систем. Здесь хМ е С К"1 - вектор фазовых координат, и^ Е - управление. На управление и^ наложены геометрические ограничения: = ис\ь) €

ту

Дискретная составляющая модели гибридной системы содержит правила мгновенного перехода от одной системы дифференциальных уравнений (1) к другой - переключения системы. Переключение с г-ой системы (1) на другую может произойти лишь при определенных условиях, а именно, при € ¿>(г), где <?(г) С М"1 - пространственная область переключения. Множества ¿>(г) представляют собой конечные объединения гиперплоскостей и полос в пространстве Е"1.

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

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

5(<).

Функционирование дискретной составляющей гибридной системы при переключении и/или перестройке может быть описано уравнением:

{i+,x^i+\t + 0)} = R(t,x^(t-0),C,ud), (2)

где г~,г+ 6 {1,..., N} - номера систем дифференциальных уравнений (1) до и после переключения, t € [<o,ii], - Q),x(-i+\t + 0) £ Slr - векторы

фазовых переменных непосредственно до и сразу после перестройки, Ud 6 Кп<у - управляющий параметр, на значения которого наложено ограничение: Ud = ud{t,i~) е Vd(i~), где Vd(i~) - некоторое множество в пространстве

Управления ис могут быть взяты либо из класса программных управлений Wc,o(i0)£i) (тогда ис — u£\t) - функция времени, зависящая также от номера активной системы (1)), либо из класса позиционных управлений Ucj. В последнем случае ис является многозначным отображением Uc'1 = Uc\t,x) С Vi{t), зависящим от времени, вектора фазовых переменных и номера активной системы (1). При использовании многозначных позиционных управлений необходимо убедиться, что после подстановки таких управлений в уравнения системы будут получены дифференциальные включения, имеющие решения. Под решениями таких дифференциальных включений понимаются решения, определенные в монографии [8]. Однако, использование известной теоремы о существовании решения у полунепрерывного сверху, выпуклозначного, компактнозначного дифференциального включения, в данной работе невозможно. Вместо указанной теоремы из [8] в диссертации использован результат, приведенный в [22] и позволяющий работать с управлениями, приводящими к невыпуклозначным дифференциальным включениям.

При решении различных задач управления для гибридных систем ключевым является определение понятия позиции системы. В данной работе под позицией системы понимается четверка {t, х, г, в}, в которой t € [io, ii] - текущий момент времени, х EÜX~ вектор фазовых переменных, г € {1,..., N} -номер активной системы дифференциальных уравнений, в € [ta,t] - момент последнего произошедшего переключения или перестройки. Компонента в позволяет различать позиции системы непосредственно перед переключением и/или перестройкой и сразу после таковой. Определенная таким образом позиция системы позволяет формулировать принцип оптимальности в фор-

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

Частным случаем рассматриваемой модели гибридной системы, рассматриваемым в диссертации, является кусочно-линейная система с переключениями ([7J, [12J, [20J), в которой область фазового пространства Ох разбита гиперплоскостями на части Î)'1', каждой из которых поставлена в соответствие некоторая система линейных дифференциальных уравнений с управляющими параметрами. Уравнения из описания модели гибридной системы при этом являются линейными (то есть система имеет линейную структуру) по вектору фазовых переменных и управлению:

/,(*, «W) = + Bi{t)uf + G(t)v®. (3)

Здесь v^ = Vc\t) : [io,ii] —» Kn"c - фиксированная непрерывная функция, Ai(t) еС(МЛп*хп*),в,(г) 6C([fo,ii],Kn*xn^),Ci(i) eq^ti],®"^"-).

Ri(t,x,i,Ud) = j.Vud, если x e

R(t xi u) = i Kij^x + Mi№Ui + N*i ' если x 6 П(0 Л °(Л ' ' ' d- \ x , иначе

Здесь Vd = Vd(t,i) - фиксированное отображение, Kij(t) € R"1*"*, Aiy(i) € Rnxxn„d) 6 detKij(t) Ф 0, € Vd - выпуклое, компактное

множество.

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

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

В пункте 1.2.1 введено понятие множества достижимости для гибридной системы, а также поставлена задача построения указанного множества. Под множеством достижимости X(t,tç,,iQ, Хй) в момент времени t € [¿о, будем понимать множество всех точек £ € в которые можно перевести траекторию системы из начальной многозначной позиции {¿о^сь^о}-

Множество достижимости гибридной системы X(t, ¿о, ¿о, До) имеет ветвящуюся структуру. Можно выделить семейство множеств X(t,to,io>Xo\ip)

простой структуры, образующих в объединении множество достижимости. Здесь ф - вектор-параметр семейства, содержащий информацию о последовательных перестройках и переключениях. Каждая такая ветвь может быть представлена в виде альтернированной суперпозиции операторов однократного переключения или перестройки г,] е {1,...,IV} я операторов непрерывного перехода г 6 {1,

Известно [8], что множество достижимости линейной системы обыкновенных дифференциальных уравнений, построенное из выпуклого, компактного начального множества ЛгЬ, является выпуклым и компактным. В случае с гибридной системой с линейной структурой это, вообще говоря, неверно. Однако, каждая ветвь множества достижимости из построенного семейства является выпуклым, ограниченным множеством.

В разделе 1.2 также приведены постановки задач верификации: для заданной многозначной начальной позиции {¿о, Ц, <%} необходимо определить, какое из следующих соотношений выполняется (для фиксированного Ь € [¿о, либо сразу для всех £ £ [¿о, ¿1]):

*(<,*о,»о,*о)ПМ=0, (4)

Х(!М,Хо)ПМфЬ (5)

Ли*о,»о,«*о)С М. (6)

Здесь М - это некоторое множество точек в фазовом пространстве, попадания в которые необходимо избежать (в случае с задачей (4)), либо, напротив, в которые необходимо попасть (в задачах (5) и (б)).

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

с\{Х(^0,г0,Х0\ф)) = {хеПх: < 0}.

Данная функция является решением уравнения Гамильтона-Якоби-Беллмана

min DV(t,a#)(-l, ~Ai0(t)x - Bk(t)uc - Ck(t)v™(t)) + d2(x, C) = 0,

«cST'io (i)

t € [io.il],a; 6 fix- (7)

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

В терминах функций цены могут быть решены задачи верификации (пункт 1.2.6). На основании информации о ветвящейся структуре множества достижимости разработаны методы аппроксимации как всего множества достижимости, так и каждой его ветви в отдельности (пункт 1.2.7). Указанные методы используют технику эллипсоидальной аппроксимации [13], [14] и позволяют получать внешние или внутренние оценки множества достижимости в виде объединений эллипсоидов, либо в виде объединений пересечений семейств эллипсоидов. В данной работе подробно разобран случай с внешними эллипсоидальными аппроксимациями. Приведены примеры построения аппроксимаций множеств достижимости для конкретных гибридных систем. Таким образом, задачи достижимости и верификации для гибридных систем удалось решить полностью, вплоть до реализации соответствующих численных методов.

Во второй главе диссертации рассматривается задача синтеза управлений для гибридной системы. Раздел 2.1 посвящен исследованию структуры слабо инвариантного множества, построение которого является первым этапом решения задачи синтеза. Под слабо инвариантным множеством W(i, ii, Лх) (множеством разрешимости или стабильным мостом) гибридной системы понимается множество таких пар (х*,г*) (х* е Qx, i* € {1,..., N}), для которых гибридная система может быть переведена на отрезке времени [i,ii] из начальной точки х*, при начальной активной системе дифференциальных уравнений (1) с номером г* в целевое множество Х\.

Ветвящаяся структура слабо инвариантного множества схожа со структурой множества достижимости гибридной системы. Слабо инвариантное

'Здесь Df(x)(y) - производная функции /(•) в точке х по направлению у.

множество W(t,U,Xi) является, вообще говоря, несвязным. Оно иредстави-мо в виде объединения выпуклых, ограниченных множеств W(t, ¿1, <%i|io, ф), параметризованных номером ¿о изначально активной системы дифференциальных уравнений, а также параметром ф, содержащим информацию о последовательных переключениях и перестройках. Множество W(t, t\, A\|io, ф) может быть представлено в виде суперпозиции операторов однократного переключения или перестройки i,j е {1,...,./V} и операторов непрерывного перехода W^, г € {1, ...,N}.

Задачу построения слабо инвариантного множества можно свести к задаче минимизации квадрата расстояния от конца траектории до целевого множества Х\. Для этой задачи введены функции цены V(t, x\io,i>), связанные со множествами W(t, ti, Xi\io, ф) следующими соотношениями:

W(t,tu Xi\io,il>) = {х е Пх : V{t,x\ц,ф) < 0} flintГГ(г0,£),

где О*(г'о, С) - некоторое компактное множество, зависящее от ф. В случае гибридной системы с линейной структурой для функций цены методами выпуклого анализа получены выражения, пригодные для расчета. Продифференцировав функции цены из полученных соотношений, могут быть также выведены уравнения Гамильтона-Якоби-Беллмана. Из тех же соотношений получаются формулы для пересчета значений функций цены при переключениях и/или перестройках - граничные значения для уравнений Гамильтона-Якоби-Беллмана.

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

Обозначим через J{x,i) множество номеров систем (1), на которые потенциально может переключиться траектория гибридной системы во время следующего, ближайшего переключения, если в некоторый момент времени t x{t) = х, i(t) = i. Пусть ty(t,ti,i\J(x,i)) - множество всех значений пат раметра ф, при которых первое переключение может произойти только на одну из систем дифференциальных уравнений (1) с номером j € J{x,i).

Рассмотрим некоторую сетку по параметру t € [io,ii]:

{Cm}m=l : Ci = to < Сг < ... < Crc-1 < с» = h (8)

(здесь n - некоторое фиксированное натуральное число). Зафиксируем некоторую позицию {t, x,i, в}, в которой не может произойти переключение или

перестройка, причем Ь 6 [(т, Ст+1) для некоторого номера т. Введем следующие вспомогательные обозначения:

,х\г,-0): ф € > £,,1+1}

(тх - момент времени ближайшего переключения или перестройки),

Ф^А]^.®.*) = 6 Ф(М1,№,г)) : У(1,х\иф) =

Для текущей позиции {Ь,х,(,0} непрерывную компоненту управления определим следующим образом:

+ С^Ц))'): ф е Ф 1<т+1А1а,х,г)} < о|.

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

Дискретная составляющая управления - это отображение

где <ша. 6 {!,..., И}, гл е {0,1}, е Рб,{г). Индекс ыа определяет номер системы (1), на которую необходимо переключиться, величина определяет, имеет ли место перестройка, а параметр щ влияет на выбор позиции системы сразу после перестройки.

Все три части дискретной составляющей управления могут быть определены на основании сравнения функций цены У(Ь,х\1,ф) при различных ф, соответствующих разным ситуациям: есть переключение, но нет перестройки; есть перестройка, но нет переключения; нет ни перестройки, ни переключения; имеет место перестройка с переключением.

Раздел 2.2 завершается доказательством теоремы, утверждающей, что при некоторых ограничениях на области переключений £(г), при малом диаметре разбиения {(т} построенный синтез решает задачу попадания траектории в целевое множество Хх с заданной точностью. То есть гарантируется попадание траектории во множество Л,1+Вг(0), где величина г > 0 стремится к нулю при стремлении к нулю диаметра разбиения {Ст}-

В третьей главе диссертации рассмотрены два примера моделей гибридных систем: на плоскости и в трехмерном пространстве.

Первый пример - математическая модель движения бильярдного шара в треугольной области на плоскости. Гибридный характер в данной модели проявляется в сочетании движения шара по плоскости, закон которого формализуется при помощи системы дифференциальных уравнений, а также моментальных соударений шара с границами области. Такие соударения моделируются при помощи оператора переключений и перестроек, построенного на основе известной гипотезы Ньютона [2]. В исследуемой системе возможно появление так называемого эффекта Зенона, когда за конечное время на траектории системы происходит бесконечное число переключений или перестроек. В разделе 3.1 приводятся достаточные условия отсутствия такого эффекта. Кроме того, раздел 3.1 посвящен исследованию квазипериодических и асимптотически квазипериодических траекторий гибридной системы, для которых последовательности векторов фазовых переменных в моменты переключений являются периодическими, либо стремятся к таковым с ростом времени. В пункте 3.1.3 приведен алгоритм поиска начальных позиций системы, из которых исходят квазипериодические, либо асимптотически квазипериодические траектории.

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

• Задача 1. Для заданной начальной позиции необходимо определить, существует ли такое управление, которое переводит траекторию в М.

• Задача 2. Для заданной начальной позиции (¿о,£о) необходимо определить наименьшее значение Г > Ьо, для которого существует такое управление, которое переводит траекторию в М. к моменту I*.

• Задача 3. Для заданной начальной позиции (io, zo) необходимо определить наименьшее количество перестроек к* S Z+, для которого существует управление, переводящее траекторию в М, причем на траектории происходит не более к* перестроек.

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

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

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

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

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

[1] Беллман Р. Динамическое программирование. М.: Изд-во иностр. литературы, 1960.

[2] Козлов В.В., Трещев Д.В. Биллиарды. Генетическое введение в динаг мику систем с ударами. М.: Изд-во МГУ, 1991.

[3] Красовский H.H. Теория управления движением. М.: Наука, 1968.

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

[5] Красовский H.H., Субботин А.И. Позиционные дифференциальиые игры. М.: Наука, 1974.

[6] Куржанский A.B. Управление и наблюдение в условиях неопределенности. М.: Наука, 1977.

[7] Куржанский А.Б., Варайя П. Задачи динамики и управления в гибридных системах // Труды международного семинара "Теория управления и теория обобщенных решений уравнений Гамильтона-Якоби". Екатеринбург: Изд-во Уральского университета, 2005. с.26-33.

[8] Филиппов А.Ф. Дифференциальные уравнения с разрывной правой частью. М.: Наука, 1985.

[9] Bellman R., Kalaba R. Dynamic programming and modern control theory. New York: Academic Press, 1965.

10] Branicky M.S., Hebbar R. Fast marching for hybrid control. // Proceedings of the 38th IEEE Conference on Decision and Control. 1999.

Ill Branicky M.S., Borkar V.S., Mitter S.M. A unified framework for hybrid control: model and optimal control theory. // IEEE transactions on automatic control, 43/1 p.31-45, 1998.

121 Johansson M. Piecewise linear control systems. Lecture Notes in Control and Information Sciences. N284. Springer, 2003.

131 Kurzhanski А.В., Valyi I. Ellipsoidal Calculus for Estimation and Control. SCFA. Boston: Birkhauser, 1997.

141 Kurzhanski А.В., Varaiya P. Ellipsoidal techniques for reachability analysis. Part I: External approximations. Part II: Internal approximations. Box-valued constraints // Optimization methods and software. 2002. V.17. p.177-237.

151 Lygeros J., Godbole D.N., Sastry S. Verified hybrid controllers for automated vehicles // IEEE transactions on automatic control, 43/4 p.522-539, 1998.

161 Lygeros J., Tomlin C., Sastry S. Controllers for reachability specifications for hybrid systems // Automatica, V. 35., p.349-370. 1999.

171 Santis E., Benedetto M.D., Pola G. Digital idle speed control of automotive engines: a safety problem for hybrid systems // Nonlinear Analysis, V.65. 2006. N9, p. 1705-1724.

181 Santis E., Benedetto M.D., Gennaro S., Innocenzo A., Pola G. Critical observability of a class of hybrid systems and application to air trafic management // Lecture Notes in Control and Information Sciences. N337. Springer, 2006.

[19] Tomlin С., Pappas G., Sastry S. Conflict resolution for air traffic management: a study in multiagent hybrid systems. IEEE transactions on automatic control, N43/4. p.509-521, 1998.

[20] Van der Schaft A., Schumacher H. An introduction to hybrid dynamical systems. Lecture Notes in Control and Information Sciences. N251. Springer, 2000.

[21] Varaiya P. Smart cars on smart roads: problems of control // IEEE Transactions on Automatic Control. N38/2. p.195-207, 1993.

[22] Veliov V. Stability-like properties of differential inclusions // Set-Valued Analysis. 5/1. p.73-88. Springer, 1997.

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

[23] Точилин П.А. Построение множества разрешимости для линейной гибридной системы // Материалы Междунар. конференции студентов и аспирантов по фундаментальным наукам "Ломоносов-2005", секция "Вычислительная математика и кибернетика", Москва, 2005. с.71-72.

[24] Точилин П.А. О построении множества разрешимости для гибридной системы с линейной структурой // Сборник статей молодых ученых факультета ВМиК МГУ, выпуск 2. М.: Издательский отдел факультета ВМиК МГУ, 2005. с.84-95.

[25] Точилин П.А. Анализ гибридных систем 2-го порядка // Труды VII международной конференции "Дискретные модели в теории управляющих систем", М.: МАКС Пресс, 2006. с.367-373.

[26] Точилин П.А. Анализ гибридной системы второго порядка с линейной структурой // Вестник Московского университета. Серия 15: Вычислительная математика и кибернетика. N1. М.: 2008. с.26-33.

[27] Куржанский А.Б., Точилин П.А. Слабо инвариантные множества гибридных систем// Дифференциальные уравнения. 2008. т. 44, N11. с.1523-1533.

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

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано к печати 29.12.2008 г. Формат 60x90 1/16. Усл.печ.л. 1,0. Тираж 100 экз. Заказ 8007. Тел. 939-3890. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

Содержание

Перечень основных обозначений.

Введение.

1 Достижимость и верификация в гибридных системах.

1.1 Гибридная система.

1.1.1 Описание модели.

1.1.2 Классы допустимых управлений.

1.1.3 Траектория гибридной системы.

1.1.4 Дополнительные ограничения на параметры системы.

1.1.5 Кусочно-линейная система с переключениями.

1.2 Множество достижимости и задача верификации.

1.2.1 Постановка задачи.

1.2.2 Дискретная история траектории гибридной системы.

1.2.3 Свойства множества достижимости.

1.2.4 Решение задачи верификации.

1.2.5 Метод динамического программирования. Функции цены.

1.2.6 Решение задачи верификации с помощью функций цены.

1.2.7 Об эллипсоидальной аппроксимации множества достижимости.

1.2.8 Примеры построения аппроксимации множества достижимости.

2 Задача синтеза управлений для гибридной системы.

2.1 Слабо инвариантное множество.

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

2.1.2 Функции цены для слабо инвариантного множества.

2.2 Решение задачи синтеза управлений при помощи функции цены.

2.3 Об эллипсоидальной аппроксимации слабо инвариантного множества.

3 Примеры.

3.1 Пример в К2. Моделирование движения бильярдного шара.

3.1.1 Описание математической модели.

3.1.2 Эффект Зенона.

3.1.3 Квазипериодические траектории.

3.2 Пример в Ж3. Задача управления шариком, скачущим на вращающейся плоскости.

3.2.1 Описание математической модели.

3.2.2 Задача управления траекторией гибридной системы.

3.2.3 Функции цены и уравнения Гамильтона-Якоби-Беллмана.

3.2.4 Оптимальное управление.

3.2.5 Примеры.

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

Гибридные системы часто встречаются в различных прикладных задачах из таких областей знания, как автомобилестроение [65], авиастроение [4], робототехника [33], электроэнергетика [69], обеспечение безопасного движения в пространстве [37], [66], [70] на суше [56], [75], на воде и др. Математическая модель гибридной системы возникает каждый раз, когда необходимо исследовать взаимодействие среды, непрерывно изменяющейся в соответствии с некоторыми физическими законами, и управляющих элементов, срабатывающих в дискретные моменты времени. Примерами таких комплексов могут служить электронные системы автоматического управления самолетом, либо автомобилем, системы автоматического регулирования температуры, влажности в помещении и др. Возможности подобных систем проявляются шире, чем обычных.

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

По-видимому, в силу чрезмерной широты охвата, не следует концентрироваться на поисках удовлетворительной универсальной модели гибридной системы и устоявшейся системы обозначений, используемых при её описании. Тем более, что каждый класс моделей гибридной системы был, как правило, мотивирован конкретными видами прикладных задач. Различные представления для моделей гибридных систем приведены, например, в [10], [25], [32], [41], [42], [54], [59], [60], [74].

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

Среди классических задач теории управления, поставленных для гибридных систем, значительные результаты были получены в решении задач стабилизации [34], [42], [64], [68], а также в ряде задач оптимального управления. Данным вопросам посвящены работы M.S. Branicky, М. Johansson, S. Sastry. Стоит отметить работу [32], в которой для решения задачи оптимального управления гибридной системой были выведены квазивариационные неравенства для специально сконструированной функции цены. В работах ,Т. Lygeros [36], [37] рассматриваются задачи управления для стохастических гибридных систем.

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

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

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

Задачи достижимости и верификации для гибридной системы рассматривались, в частности, в работах Е. Асарина, J. Lygeros, С. Tomlin и др.: [10], [55], [57], [65], [72]. В работах [27], [29] для их решения были применены геометрические методы. В работе [10] предложены схемы, основанные на разработанном ранее эллипсоидальном исчислении [45], [47]. Применение данной техники позволит построить для гибридных систем конструктивную теорию, направленную на решение задач достижимости и верификации "до конца", т.е. до практически реализуемого алгоритма.

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

Один из методов решения задач програмлтого управления для обычных, негибридных систем опирается на принцип максимума JI.C. Понтрягина [15], при помощи которого могут быть получены необходимые условия оптимальности. Принцип максимума может быть применен в обобщенной формулировке и для гибридных систем [77]. В отсутствии возмущений значение критерия оптимальности при позиционных стратегиях совпадает со значением, полученным при программных управлениях. Однако, при наличии возмущений одних программных управлений уже недостаточно. В таком случае нужны позиционные управления, найденные, например, путем использования методов динамического программирования [1], а также теория, разработанная для негибридных систем H.H. Красовским [б], [7], [8]. Задача синтеза может быть также сформулирована как задача поиска такого позиционного управления, которое удерживает траекторию внутри системы слабо инвариантных лтоо/сеств (попятных множеств достижимости, множеств разрешимости), образующих трубку разрешимости [45] (стабильный мост [8]) и т.п. По найденным слабо инвариантным множествам можно построить синтез с требуемыми свойствами, опираясь на метод экстремального прицеливания, [7].

Применению методов динамического программирования для решения задач управления гибридными системами посвящены работы [28], [32], [33], [43] [57], [67], [71] и другие.

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

В первой главе диссертации рассматривается задача построения множества достижимости для гибридной системы, а также задачи верификации. В разделе 1.1 описывается математическая модель гибридной системы, используемая в следующих разделах и главах. Эта модель включает в себя непрерывную и дискретную составляющие. Непрерывная составляющая системы представлена совокупностью N систем обыкновенных дифференциальных уравнений: и«) ,/ = 1,.,ЛГ, (1) где в каждый момент времени активной является одна из указанных систем. Здесь .т^ £ £1Х С М"* - вектор фазовых координат, 6 Кп"с - управление. На управление и^ наложены геометрические ограничения: и^ = и^^) £

Дискретная составляющая модели гибридной системы содержит правила мгновенного перехода от одной системы дифференциальных уравнений (1) к другой - переключения системы. Переключение с г-ой системы (1) на другую может произойти лишь при определенных условиях, а именно, при £ <5(г), где 5(г) С М71* - пространственная область переключения. В данной работе всюду считается, что множества с?(г) представляют собой конечные объединения гиперплоскостей и полос в пространстве К"-".

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

Функционирование дискретной составляющей гибридной системы при переключении и/или перестройке может быть описано уравнением: 0)} = 0),г-,«Д (2) где г-,г+ € {1,., ./V} - номера систем дифференциальных уравнений (1) до и после переключения, I 6 [¿о, /]], —0), ¿'^(¿+0) 6 - векторы фазовых переменных непосредственно до и сразу после перестройки, иа € МПц<г - управляющий параметр, на значения которого наложено ограничение: и^ = г ) £ 'Ра{г ). где 'Ра{г )-некоторое множество в пространстве Е'1"^.

Управления ис могут быть взяты либо из класса программных управлений ¿1) тогда ис = и^(¿) - функция времени, зависящая также от номера активной системы (1)), либо из класса позиционных управлений ¿4,/. В последнем случае ис является многозначным отображением а^ = и^ (¿, х) С зависящим от времени, вектора фазовых переданных и номера активной системы (1). При использовании многозначных позиционных управлений необходимо убедиться, что после их подстановки в уравнения системы будут получены дифференциальные включения, имеющие решения (в смысле, определенном в монографии [22]) Использование известной теоремы о существовании решения у полунепрерывного сверху, выпуклозначного, компактнозначпого дифференциального включения, в данной работе невозможно. Вместо указанной теоремы из [22] в работе использован результат, приведенный в [76] и позволяющий работать с управлениями, приводящими к невыпуклозначным дифференциальным включениям.

При решении различных задач управления для гибридных систем ключевым является определение понятия позиции системы. В данной работе под позицией системы понимается четверка {£, х,г,в}, в которой / Е [¿сь ¿1] — текущий момент времени, х Е - вектор фазовых переменных, / € {1,., А"} - номер активной системы дифференциальных уравнений, в € [¿о, ~ момент последнего произошедшего переключения или перестройки. Компонента в позволяет различать позиции системы непосредственно перед переключением и/или перестройкой и сразу после таковой. Определенная таким образом позиция системы позволяет формулировать принцип оптимальности в форме полугруппового свойства для функций цены, используемых для решения задач управления методами динамического программирования.

Частным случаем рассматриваемой модели гибридной системы является кусочно-линейная система с переключениями ([74], [42], [10]), в которой область фазового пространства Их разбита гиперплоскостями на части каждой из которых поставлена в соответствие некоторая система линейных дифференциальных уравнений с управляющими параметрами. Уравнения из описания модели гибридной системы при этом являются линейными по вектору фазовых переменных и управлению: „СО) = + + (3)

Здесь (¿) : [¿о, —»• Мп"с - фиксированная непрерывная функция,

АОО € € С([*о,*1],Кп*хп"с),С'.(*) € С([*о,и]ЛпМс), х, I, иа) = з^щ, если х £ . . { Кф)х + ^/i7(í)г¿f^ + , если х £ П® п гьх [ь, х, г, ив.) — л х , иначе

Здесь — Vd.it,г) - фиксированное отображение, £ МГ1жХ,г;с, е ЕПхХПг'.г, Ш.ПхХП"<1, с^ ф 0, щ £ Та - выпуклое, компактное множество. Часть результатов в данной работе получена при предположении, что исследуемая гибридная система является кусочно-линейной системой с переключениями. Используется также более слабое предположение о линейной структуре гибридной системы, когда уравнения из описания модели являются линейными, но нет никаких ограничений, связанных с разбиением фазового пространства на области

Основные результаты, приведенные в данной диссертации:

• Исследована ветвящаяся структура прямого и попятного множеств достижимости для гибридной системы с линейной структурой без неопределенности. Приведены описания указанных множеств в виде попеременных суперпозиций операторов простой структуры, а также в виде множеств нулевого уровня специальных функций цены. Для этих функций методами выпуклого анализа выведены выражения, которые можно использовать для их численного расчета. Кроме того, получены уравнения типа Гамильтона-Якоби-Беллмана, которым должны удовлетворять указанные функции. Предложены численные методы расчета множеств достижимости, основанные на использовании аппарата эллипсоидального исчисления. Проведены расчеты аппроксимаций множеств достижимости для нескольких примеров гибридных систем.

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

• Для конкретного примера гибридной системы на плоскости исследованы возможности появления эффекта Зенона, а также квазипериодических или асимптотически квазипериодических траекторий.

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

Заключение