I»
Оглавление
1
Введение 4
1 О вычислении функции цены в некоторых классах нелинейных задач оптимального управления 14
1.1 Задача оптимального управления с терминальным функционалом............ 14
1.1.1 Постановка задачи.............................................. 14
1.1.2 Функция цены и обобщенное решение уравнения Гамильтона-Якоби-
Веллмана....................................................... 15
1.1.3 Представление значения функции цены с помощью экстремалей принципа максимума Понтрягина............................................. 16
1.1.4 Исследование решения вспомогательной задачи Коши............... 18
1.1.5 Метод приближенного вычисления функции цены ................... 21
1.1.6 Модифицированный метод приближенного вычисления функции цены. Приближенное решение задачи оптимального управления .... 26
1.1.7 Алгоритм приближенного вычисления функции цены для задачи оптимальное управления с терминальным функционалом ..................... 30
, 1.2 Задача оптимального управления с функционалом типа Больца............. 37
1.2.1 Постановка задачи.............................................. 37
1.2.2 Метод приближенное вычисления функции цены для задачи оптимального управления с функционалом типа Больца........................ 37
1.2.3 Модифицированный алгоритм. Приближенное решение задачи оптимального управления с функционалом типа Больца........................ 44
1.2.4 Гладкая аппроксимация задачи оптимальное управления с терминальным функционалом ................................................. 47
1.3 Задача оптимального управления с фиксированным правым концом........ 51
1.3.1 Постановка задачи.............................................. 51
1.3.2 Представление значения функции цены на основе экстремалей принципа максимума Понтрягина............................................. 51
1.3.3 Метод приближенное вычисления функции цены для задачи оптимального управления с фиксированным правым концом..................... 53
1 1.4 Задача быстродействия................................................. 57
1.4.1 Постановка задачи.............................................. 57
! 1.4.2 Представление значения функции цены для задачи быстродействия
на основе экстремалей принципа максимума Понтрягина............ 57
2
1.4.3 Метод приближенного вычисления функции цены для задачи быстродействия 58
1.4.4 Достаточные условия непрерывности функции цены в задаче быст-
* родействия........................................................ 62
2 Вычисление функции цены для конкретных задач оптимального управ-
' ления 64
2.1 Расчет тестовых примеров................................................. 64
2.1.1 Линейно-квадратичная задача....................................... 64
2.1.2 Задача быстродействия для модели ’’тележка”....................... 68
2.2 Расчет задач оптимального управления с неизвестной функцией цены .... 73
2.2.1 Модель ”РОСТ”..................................................... 73
2.2.2 Модель ’’хищник-жертва”........................................... 74
2.2.3 Модель физического маятника....................................... 76
2.2.4 Задача наискорейшего пространственного разворота твердого тела . . 78
3 О построении максимальных и-стабильных мостов для одного класса нелинейных дифференциальных игр сближения 80
3.1 Постановка задачи........................................................ 80
3.2 Дискретная по времени схема приближенного построения максимальных и-стабильных мостов........................................................... 81
3.3 Дискретная по времени, фазовым координатам и множествам управления схема приближенного построения максимальных и-стабильных мостов ... 83
3.4 Дифференциальные игры с фазовыми ограничениями........................... 91
4 Приближенное построение максимальных н-стабильных мостов для конкретных дифференциальных игр 94
4.1 Модельный пример......................................................... 94
4.2 Модель физического маятника............................................. 96
4.3 Модель ’’хищник - жертва”............................................... 97
4.4 Пример с фазовыми ограничениями......................................... 99
4.5 Модель трехколесной тележки на плоскости................................105
А Описание программной реализации метода приближенного построения максимальных ц-стабильных мостов 109
Литература 113
3
Введение
В диссертации рассматриваются два класса задач управления нелинейной динамической
* системой: задачи оптимального управления и задачи синтеза гарантирующих управлений в нелинейных дифференциальных играх. Важную роль при решении таких задач играет функция цены для задачи оптимального управления и множества, обладающие специаль-
* ным свойством стабильности, в игровой задаче управления.
Объектом исследования в первом классе задач управления являются динамические управляемые системы, описываемые на отрезке времени [to >7*] дифференциальным уравнением
x = f{x,u), (1)
где х € Rn - фазовая переменная, а управление и 6 Rp стеснено геометрическим ограничением и € Р С R?. Для системы (1) с начальным условием x(t0) = х0 рассматривается ряд задач оптимального управления со свободным правым концом и функционалом типа Больца, а также задачи с фиксированным правым концом х(Т) = Х| и функционалом типа Лагранжа или быстродействия. Подобные задачи часто возникают при исследовании математических моделей механики, экономики, биологии, фундаментальной медицины.
Функция цены в задаче оптимального управления каждой точке фазового пространства и начальному моменту времени ставит в соответствие оптимальное значение функционала, достижимое из этой точки как из начальной. Функция цены играет важную роль при решении задач оптимального управления в классе позиционных законов управления. Она является удобным носителем информации об оптимальном управлении, позволяющим рассчитывать его в реальном времени для реализовавшейся позиции.
Для вычисления функции цены в узлах пространственно-временной сетки разработан ряд методов, которые можно разделить на следующие две группы: методы, основанные на исследовании отдельных траекторий, и методы, основанные на исследовании всего множества траекторий.
К первой группе относятся методы, основанные на решении краевой задачи принципа максимума Поптрягина |33, 25] (Г.Л. Гродзовский, Ю.Н. Иванов, В.В. Токарев, H.H. Моисеев, Д. Брайсон, Хо Ю-ши, C.II. Аввакумов, Ю.Н. Киселев, М.В. Орлов и др.), градиентные методы в пространстве управлений |11| (Л.И. Шатровский, Т.М. Энеев, H.H. Моисеев, Р. Копп, X. Мойер, A.B. Балакришнан, Ф.П. Васильев и др.), метод последовательных приближений [55] (И.А. Крылов, Ф.Л. Черноусько, Н.В. Баничук, X. Келли, Р. Копп, X. Мойер и др.), методы, связанные с варьированием и перебором траекторий в пространстве фазовых координат [26] (H.H. Моисеев, B.C. Михалевич, Н.З. Шор, Ф.Л. Черноусько, Р.П. Федоренко и др.).
Ко второй группе относятся методы, основанные на получении уравнений Гамильтона-Якоби-Беллмана |8, 40], исследовании существования и единственности решения различных краевых задач для таких уравнений и построении разностных аппроксимаций для решения этих краевых задач.
В случае выполнения гипотезы о дифференцируемости функции цены для непрерывной управляемой системы, такие методы были предложены Р. Веллманом, H.H. Моисеевым [55, 25, 26] и др.
С другой стороны исследования конкретных задач оптимального управления показывают (Л.С.Понтрягин [33], Е.Ф.Мищенко и др.), что функция цены, как правило, дифференцируема не всюду и потому не является классическим глобальным решением уравне-
4
ния Гамильтона-Якоби-Беллмана. Таким образом, в этом случае, как и во многих других, где используются уравнения в частных производных (УЧП) первого порядка, возникает необходимость вводить понятие обобщенного решения, а также развивать теорию и методы построения таких решений.
Задачи, связанные с изучением негладких решений УЧП первого порядка, исследовались в работах Н.С. Бахвалова, JI. Эванса, У. Флеминга, И.М. Гельфанда, С.К. Годунова,
Э. Хопфа, H.H. Кузнецова, O.A. Ладыженской, П. Лакса, O.A. Олейник, Б.Л. Рождественского, A.A. Самарского, А.Н.Тихонова, А.Б. Куржанского, Н.С. Кружкова, A.A. Меликя-на, М.С. Никольского и др.
В начале 80-х годов М. Крэндалл и П.Л. Лионе ввели понятие вязкостного решения (viscosity solution (56]). Теория вязкостных решений продвинула исследования УЧП первого порядка и эллиптических уравнений. В рамках этой теории были доказаны теоремы существования и единственности для различных типов уравнений и краевых задач, а также изучены некоторые приложения к задачам управления и дифференциальным играм.
В конце семидесятых годов А.И Субботиным был предложен другой подход к построению обобщенных решений, который может быть рассмотрен, как неклассический метод характеристик. Следуя этому подходу, обобщенное решение (называемое минимаксным) должно быть инвариантно относительно потока, порождаемого так называемыми характеристическими дифференциальными включениями. Теория минимаксных решений изложена в работах А.И. Субботина (40, 41, 42]. В них получены теоремы существования и единственности таких решений, поставлены задачи численной аппроксимации минимаксных решений и решения на их основе задач оптимального управления и дифференциальных игр.
Развитие теории минимаксных решений, в том числе метода характеристик, для задач оптимального управления, предложено в работах H.H. Субботиной (44, 45, 46, 47, 57], в которых получено условие первого порядка, дополняющее принцип максимума Понтрягина до необходимых и достаточных условий оптимальности.
В работах А.М. Тарасьева, A.A. Успенского и В.Н. Ушакова предложены конечноразностные операторы для построения минимаксного решения уравнения Гамильтона-Якоби-Беллмана-Айзекса. Поскольку точное вычисление этих операторов является достаточно сложной задачей, авторами предложена их аппроксимация кусочно-линейными функциями с вершинами в узлах фиксированной сетки в фазовом пространстве (48). Расчеты конкретных задач, проведенные по этому методу, показали его эффективность.
В девяностых годах В.П. Масловым, В.Н. Колокольцовым и С.Н. Самборским в работах, базирующихся на идемпотентном анализе, была предложена друюя концепция обобщенною решения. Она основана на существенной модернизации классического подхода к определению обобщенного (слабого) решения в математической физике. С помощью этого подхода были развернуты исследования УЧП с выпуклым гамильтонианом и их приложений к задачам математической физики.
Вместе с тем разработка новых схем аппроксимации функции цены в задаче оптимального управления с заданной точностью, основанных, в частности, на совместном использовании обобщения классического метода характеристик Коши и необходимых условий оптимальности в форме принципа максимума Понтрягина, является актуальной.
Объектом исследования во втором классе задач управления являются динамические управляемые системы с неопределенными параметрами, описываемые на отрезке времени
5
[0,Т] дифференциальным уравнением
i = /(x,ti,v), (2)
где х G Я4 - фазовая переменная, управление и стеснено геометрическим ограничением и € Р С Rv, помеха v выбирается из множества Q С Ä7. Для этой системы с начальным условием х(0) = то рассматривается задача наведения траектории системы (2) на терминальное множество М С Я” в момент времени Т в классе позиционных управлений.
В работах H.H. Красовского и А.И. Субботина [20, 21, 43] введены конструкции стабильных мостов и показано, что если построен максимальный ц-стабильный мост W с [0, Г] х Яп в данной задаче, то задача наведения имеет решение в классе позиционных процедур управления для любой начальной точки (£о,^о) € W.
Для линейной дифференциальной игры при помощи альтернированного интеграла JI.C. Понтрягина [37, 34) решение задачи построения множества W сводится к интегрированию многозначных отображений. Исследованию этой задачи посвящены работы Е.Ф. Мищенко, А.Б. Куржанского, М.С. Никольского, Е.С. Половинкина, H.JI. Григоренко,
Н.Х. Розова, B.C. Пацко, В.И. Максимова, A.A. Чикрий и др.
В случае нелинейной управляемой системы для построения множества W используются операторные конструкции, исследованные в работах H.H. Красовского, А.И. Субботина, А.Б. Куржанского, Б.Н. Пшеничного, В.В. Остапенко, В.Н. Ушакова, H.H. Субботиной, A.A. Меликяна [20, 38, 52). В общем случае вычисление этих операторов представляет собой сложную задачу. Поэтому для практической реализации в вычислительных программах требуются дальнейшие аппроксимации этих операторов.
В работах А.М. Тарасьева, В.Н. Ушакова и А.П. Хрипунова [49, 50, 54) рассматривается аппроксимация операторов программного поглощения многогранниками, которые могут быть, вообще говоря, не выпуклыми. Данный метод эффективен для решения дифференциальных игр на плоскости. Но уже в трехмерном пространстве алгоритмы вычисления множеств, являющихся, например, пересечением не выпуклых многогранников, сложны и с трудом поддаются программированию.
Новым направлением в построении максимальных п-стабильных мостов являются сеточные методы. В этих методах в фазовом пространстве задается некоторая (обычно равномерная) сетка, в узлах которой и определяются операторы программного поглощения. Дискретизации подвергаются и другие элементы дифференциальной игры, такие как множества допустимых управлений игроков, временной интервал, терминальное множество. Данный метод с успехом применялся для построения областей достижимости нелинейных управляемых систем В.Н. Ушаковым [14). Также в работах Т.Х Бабалыева и А.П. Хрипунова [6] было рассмотрено применение сеточных методов для построения множеств позиционного поглощения для линейных по управлениям дифференциальных игр сближения.
Таким образом задача отыскания достаточных условий сходимости аппроксимаций и-стабильных мостов для нелинейных дифференциальных игр к идеальному и-стабильному мосту является актуальной.
В главе 1 диссертации исследуется задача аппроксимации функции цены в задачах оптимального управления. В разделе 1.1 рассматривается задача минимизации целевой функции вида
Ф(1(Т|«о,Хо, «(•))) -+ inf
«(•)€£/
б
на решениях системы (1). Функция цены V(t,x) ищется в заданной прямоугольной области |0,Т]хХ Ci?x R,x.
Известно, что при выполнении ряда условий, функция цены является обобщенным (в а минимаксном или вязкостном смысле) решением задачи Коши для уравнения Гамильтона-
Якоби-Беллмана
dV(t,x) , . /„ ч dV(t,x)\ л
—+ /=о
с краевым условием V(Tyx) = Ф(т). В случае, если функция V{tyx) является гладкой, для решения этой задачи применим классический метод характеристик, позволяющий свести решение задачи Коши для уравнения в частных производных к интегрированию системы обыкновенных дифференциальных уравнений, называемой характеристической. В общем случае функция цены может не являться гладкой, и для ее вычисления рассматривается обобщение метода характеристик, заключающееся в применении операции минимума при вычислении функции цены В точке (£q, Xq) в случае, если существует более одной характеристики, компонента х которых пересекает в момент <0 точку :г0.
Также используется тот факт [47), что для уравнения Гамильтона-Якоби-Беллмана характеристики Коши совпадают с экстремалями и коэкстремалями принципа максимума Понтрягина. Получаем представление значения функции цены как минимума целевой функции Ф(т(Т)) на всех допустимых парах (z(-)>u(’))> удовлетворяющих принципу максимума. Это представление является основой для разработки конструктивного метода аппроксимации функции цены. При этом при практическом применении описанного способа вычисления функции цены для построении соответствующих экстремалей принципа максимума требуется однозначное определение управления и*(ху ф)у максимизирующего функцию Гамильтона-Понтрягина Н(хуиуф). Кроме того необходимо исключить случай вырожденности принципа максимума, когда ему удовлетворяют все допустимые управления. В лемме 1.4 приводятся достаточные условия, при которых значение функции цены в точке (£о.£о) можно представить как минимум целевой функции на всех решениях некоторой вспомогательной задачи Коши для гамильтоновой системы
!х = /(т, и*(т, ф)) = F{xy ф)у ^
* - - - (- ^L, Jf* - (3)
х[Т)=хт,
ЯТ) =
проходящих через точку (*0>Яо)-
Таким образом лемма 1.4 по сути позволяет исходную задачу оптимального управления, являющуюся бесконечномерной задачей минимизации, свести к задаче конечномерной минимизации на некотором компактном множестве К С Rn. Мпожество К в данном случае является произвольной внешней аппроксимацией множества достижимости системы (1) из любой начальной точки (£о,Хо) € [0,Т] х X.
Далее на основе леммы 1.4 предлагается следующая аппроксимационная схема для приближенного вычисления функции цены.
На множестве [0,Т] х X задается равномерная сетка. Временной интервал [0,Т] разбивается на I одинаковых частей точками ту:
Т
О = т0 < т, < • • • < Ti = Т, ri+l - = j.
7
Каждый из отрезков [т“,т^],г = 1 ,...,п, определяющих множество X, разбивается на т одинаковых частей точками
III
Получаем на множестве [0,Т] х X равномерную сетку с узлами в точках
»^'21 * • •»^я)| к ~ • • • * к = 0,..., тп\ I — 1,..., п.
Эта сетка разбивает множество [О, Т] х X на прямоугольные ячейки
Я}0311—3»» = [^о-Ь^о] Х —х * * ’ * (^-1*^,1*
]\ — !»•••» ТЩ * = 1> • • • » 71.
Множество всех ячеек обозначим через
2 — {9тоо1,...апЬ'о = 1> • • • I к = 1»•• • > 771; 1 = 1,..., 71}.
Аналогично множеству X задается равномерная сетка на прямоугольном множестве К. Узлами сетки будут точки т]и^п = (77^,..., т£):
г. К * г < о Я < 1 2Я . ,
-Л+- = 77*, С т/2 < ... <г/^ = Я- 77Л+1 - 77^ = —, I = 1,...,71.
Множество всех узлов этой сетки обозначим через
М = {^1.-Зп У» = = 1,...,п}.
Для приближенного решения задачи Коши (3) в обратном времени предлагается использовать произвольный конечно-разностный метод с постоянным шагом ^ (при вычислении оценки погрешности аппроксимации рассматривался метод Эйлера).
Для каждой ячейки <7 определяется множество М{д) С N, представляющее собой множество всех точек 77 € А/*, для которых приближенное решение задачи Коши (3) с конечным условием х(Т) = 77 проходит через ячейку д.
Если множество А/(<7) не пусто, то минимальное значение функционала на этом множестве обозначается как
^(ч) = пнп Ф(т?). (4)
пеМ(я)
Аппроксимация функции цены определяется как кусочно-постоянная функция, принимающая постоянное значение в каждой ячейке q ^ Q■t равное IV(<7)
У{Ь,х) = ИД?), («,*)€*.
В теореме 1.1 приводятся достаточные условия для равномерной сходимости предложенной аппроксимационной схемы, состоящие из условий, налагаемых на исходную задачу оптимального управления, и условий согласования параметров т, /, к и з. Также в теореме приводится оценка погрешности аппроксимации, имеющая порядок О (Т) 4- О (|).
Далее в том же разделе исследуется возможность применения данного метода для вычисления некоторого программного управления, решающего поставленную задачу оптимального управления приближенно, то есть гарантирующего значение целевой функции
8
близкое к оптимальному. Для этого требуется для каждой ячейки g € Q запоминать то значение 77(g), на котором в формуле (4) достигается минимум. В дальнейшем гарантирующее управление вычисляется но формуле u(t) = <))> W (*(0»^(0) “ решение
задачи Коши (3) с краевым условием х(Т) = 77(g). В теореме 1.2 доказывается сходимость гарантированного результата к оптимальному.
В разделе 1.1.7 предлагается алгоритм для вычисления функции цены с заданной точностью. Приводится оценка сложности алгоритма по двум критериям: количеству операций, достаточных для достижения заданной точности, и по количеству ячеек множества Q. Первый критерий характеризует время работы алгоритма и, на первый взгляд, является основным. Но, так как в отличие от времени расчета физическая память компьютера всегда строго ограничена, то целесообразно рассматривать и второй критерий, характеризующий объем памяти, необходимой для хранения результатов вычислений.
Рассматриваются задачи минимизации указанных двух критериев при фиксированной погрешности вычислений. Показано, что при заданной величине погрешности е оба критерия имеют одинаковый порядок роста О
Также исследуется сходимость метода аппроксимации функции цены в случае, если не выполняются условия согласования параметров теоремы 1.1. В теореме 1.3 доказывается, что в ряде случаев сходимость может иметь место, даже если не выполняются условия согласования.
В разделе 1.2 рассматривается задача оптимального управления с функционалом типа Вольца, состоящим из терминальной и интегральной частей:
т
I{t0,x0lu{-)) = [ /о(т(<|^,^о,^(-)))и(0)^ + Ф(х(Т|<о,^о,^(-») -> inf .
J “(•)€£/
to
Для аппроксимации функции цены в этой задаче предлагается метод, являющийся развитием метода аппроксимации функции цены в задаче оптимального управления с терминальным функционалом.
В теореме 1.4 приводятся достаточные условия сходимости метода и оценка погрешности аппроксимации.
В разделе 1.2.4 на основе метода вычисления функции цены в задаче оптимального управления с функционалом типа Больца предлагается гладкая аппроксимация для задачи оптимального управления с терминальным функционалом в случае линейной по управлению системы вида
i = fi(x) +/2{х)и.
Рассматривается вспомогательная задача оптимального управления с функционалом вида
т
Ia{t0,xQ,u{-)) = а [ \\u{t)\\2dt + <l>{x{T\totx0,u{-)))-> inf ,
J «(•)€£/
*о
где а 6 R\ - параметр. В лемме 1.14 доказывается равномерная сходимость в области [О, Т] х X функции цены вспомогательной задачи к исходной при стремлении параметра и к нулю.
Данная аппроксимационная задача обладает свойством единственности и липшицево-сти максимизатора и*(х,ф), что позволяет существенно расширить круг решаемых задач
9
- Киев+380960830922