Автоматика и телемеханика, № 3, 2015
( 2015 г. А.Ю. ГОРНОВ, д-р техн. наук (gornov@icc.ru), Е.А. ФИНКЕЛЬШТЕЙН (finkel@icc.ru) (Институт динамики систем и теории управления СО РАН, Иркутск)
АЛГОРИТМ КУСОЧНО-ЛИНЕЙНОЙ АППРОКСИМАЦИИ ГРАНИЦЫ МНОЖЕСТВА ДОСТИЖИМОСТИ1
Дается краткий обзор теоретических работ и подходов к оценкам множеств достижимости управляемых систем. Предлагается алгоритм кусочно-линейной аппроксимации границы множества достижимости, основанный на решении специальной задачи оптимального управления по критерию максимума объема соответствующей оценки множества достижимости. Приводятся результаты вычислительных экспериментов.
1. Введение
Для исследования экстремальных свойств динамических систем традиционно используются методы теории оптимального управления. Однако решение задачи оптимального управления (ЗОУ), как правило, дает лишь точечную информацию об исследуемой управляемой системе. В практических приложениях зачастую этого недостаточно, необходимо знать также нелокальное поведение системы, ее предельные возможности, поведение оптимальных решений при различных оптимизируемых функционалах. Для получения информации такого типа известен ряд теоретических подходов, основанных на исследовании свойств и геометрии множества достижимости (МД) (см., например, [1-3]). В этих же работах рассматриваются вопросы исследования интегральных воронок управляемых систем — динамики МД. Методика дифференциальных включений для исследования управляемых систем была предложена достаточно давно [4], однако ее практическое применение сдерживается слабостью численных методов, обычно сводящихся к задаче построения оценок МД, внутренних или внешних. Для линейных систем предложено множество подходов и методов аппроксимации МД, разработаны многочисленные алгоритмические подходы [5]. Однако в целом проблема численного оценивания МД нелинейных динамических систем к настоящему времени не может считаться решенной.
Факторами, осложняющими процесс разработки алгоритмов аппроксимации МД в нелинейном случае, являются, по мнению авторов, следующие: рост сложности геометрии МД с увеличением интервала времени; плохая обусловленность возникающих вычислительных задач; многоэкстремальность вспомогательных задач оптимизации, следующая из невыпуклости МД для нелинейных систем; вычислительная неустойчивость.
Теоретические результаты, направленные на конструирование вычислительных методов построения внутренних и внешних аппроксимаций МД
1 Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных исследований (проекты № 12-01-00193_а и № 14-01-31296-мол_а).
нелинейных управляемых систем, развивались в последние годы в работах ряда авторов [2, 3, 5, 7-21]. Было предложено несколько принципиально различных подходов к построению численных процедур. Методы, основанные на эллипсоидальных конструкциях [2, 7], обладая рядом универсальных свойств, к сожалению, в случае существенно невыпуклых множеств пока позволяют получать только грубые оценки. Подходы, основанные на достаточных условиях оптимальности, глубоко исследованные в [6], были использованы для решения ряда сложных задач, в том числе прикладных. Методы эйлерова типа («пиксельные методы» [8]) предполагают использование априорно заданных сеток в фазовом пространстве и проецирование на них аппроксимаций МД в процессе расчетов. Этот тип методов наиболее хорошо изучен теоретически и наиболее полно оснащен конструктивно. По мнению многих специалистов (см., например, [8]), методы эйлерова типа на сегодня являются единственным надежным инструментом аппроксимации МД нелинейных систем. Методы, основанные на уравнении границы интегральной воронки [3], пока разработаны только для систем с гладкой границей и не применимы к задачам с параллелепипедными ограничениями. Интересный класс методов, основанных на полиэдральных аппроксимациях, исследуется в [22, 23]. Методы стохастических аппроксимаций [24], привлекательные в теоретическом аспекте, основаны на принципе Монте-Карло и состоят из алгоритмов генерации аппроксимативных точек и алгоритмов отсечения неинформативной информации. Методы такого типа просты в реализации, но, к сожалению, не всегда позволяют конструировать достаточно устойчивые вычислительные схемы. Методы [25] используют идею об аппроксимации границы МД многогранниками и максимизации объема тел, ими ограничиваемых.
В работе предлагается алгоритм вариационного типа и связанная с ним вычислительная технология аппроксимации МД нелинейной управляемой системы на плоскости, основанная на решении специальной ЗОУ по критерию максимума объема соответствующей оценки МД. Для решения аппроксимативной ЗОУ используется поисковый метод конечномерной оптимизации туннельного типа [26], основанный на дискретизации непрерывного управления.
2. Метод аппроксимации
Задача приближенного представления МД распадается на две: первая — задача эффективного вычисления точек МД и вторая — геометрическая задача представления многомерной фигуры, каковой является МД, с помощью проекций. Авторы располагают реальными возможностями проектирования либо на оси, либо на плоскости (двумерное подпространство). Эта задача в простейшем частном случае является предметом инженерной графики (начертательной геометрии [27]), а в общем случае может представлять собой сложную независимую проблему [28], которая не является предметом данного исследования. Предлагаемый алгоритм дает возможность строить аппроксимации проекций МД на плоскость.
Рассматривается управляемая система следующего вида:
(1) ж = /(ж(г),и(г),г), г е у = ^(ж(^)), ж(г0) = ж0, и е и,
где х — состояние, и — управление, у — выход. Функции / предполагаются непрерывно дифференцируемыми, и — выпуклое и компактное. Предположим, что выход системы двумерный, у = (у1,у2), и поставим задачу аппроксимации МД в плоскости выходов. В рассматриваемом двумерном случае задача аппроксимации МД может быть сведена к задаче максимизации площади фигуры, ограничиваемой правильным кусочно-линейным контуром -замкнутой ломаной линией без самопересечений.
Для решения этой задачи строится вспомогательная ЗОУ (называемая аппроксимативной), которая включает набор повторяющихся систем (1) с независимыми управлениями.
Сконструируем управляемую систему из N подсистем
(2) ¿з = /(*,■(*),и,-(*),*), Хз(1 о) = х°, г € [io.ii], г>з(г) € и, ] = МУ,
каждая подсистема соответствует одной вершине аппроксимирующего контура.
Размерность рассматриваемой системы, таким образом, равна пЫ : Zi(t), г = 1 ,пМ. Для каждой подсистемы определен свой собственный набор управлений ы(Ь),1 , г с одинаковыми для всех подсистем ограничениями ({/); размерность управлений общей системы rN. В качестве максимизируемого функционала рассматривается «функционал объема» (в данном случае -площади), построенный по стандартной формуле площади невыпуклого многоугольника.
Объем (в двумерном случае — площадь) фигуры, ограниченной контуром, можно вычислить по следующей формуле:
Му) = 0,5
N
+ уЫ^ЖУМ) - у?-1(*1))
3=1
Такой подход вычисления площади фигуры применим только для правильных контуров. В случае наличия в контуре самопересечений в формуле появляются слагаемые с различными знаками и применение ее становится некорректным.
Проблемами на этом пути являются возможное возникновение в процессе расчетов «вырожденных контуров» — контуров с самопересечениями, контуров с неравномерными длинами звеньев, контуров с немонотонной нумерацией звеньев и др.
При отсутствии дополнительных требований к аппроксимирующему контуру в процессе варьирования управлений появляются звенья произвольно большого размера, что «выгодно» с точки зрения увеличения ограничиваемой контуром площади, но приводит к очень грубой аппроксимации границы МД на некоторых участках. Для преодоления этой проблемы вводится «функционал равномерной аппроксимации», штрафующий за существенно различный размер звеньев контура:
N
31 (у) = ^ (Ь(уз(¿1) - у,--1(^)) - )2,
3=1
где Цуз - уз-1) = у/(у) - у]_1)'2 + (у2 - у2_1)2 - длина ¿-го звена, 5Г =
= ^г {ЦУ]{11) - Уj-l(tl))) — средняя длина звена по контуру, у0 = ум -условие замкнутости контура.
С целью обеспечения правильности контура вводится функционал штрафа за самопересечения. Рассмотрим два отрезка, принадлежащих контуру,
Ы^Ь, (У1к-1,У2к-1)] и [(у),у2), (ylj-l,y2j-l)], к = ].
Для того чтобы выяснить, содержит ли контур самопересечения, необходимо для каждой пары несмежных отрезков проверить, лежат ли концы одного по одну сторону от прямой, соединяющей концы второго, или по разные.
Если один из отрезков горизонтальный (у^ = у^-к или ук = ук-к), то достаточно найти знак выражения (ук — yк)(Ук-1 — ук). Положительный будет свидетельствовать об отсутствии пересечений, отрицательный — о наличии. В общем случае соответствующий вывод можно сделать на основе знака выражения
[(у1-! — у ь у 1-1 — Уfc), (у] — у1, у2 — у !)] [(у й-1 — у I у 1-1 — у 2)> (у]-1 — у ь у2-1 — у1)] ,
где квадратные скобки означают косое (псевдоскалярное) произведение.
N
Определим = ^ Рк)j•,
1
„ 1, если отрезки с номерами к и 7 пересекаются;
где Рк ,j = < п
I 0 в противном случае.
Проверка на самопересечения может не выявить некоторые особенности, которые можно охарактеризовать касанием (попаданием в малую окрестность) точек, по индексам удаленных друг от друга. Для преодоления этой особенности введем функционал, штрафующий за наличие в контуре подобных свойств, т.е. при каждом выполнении условия ^(у^ — у+ (у2 — у2)2 < е
для |г — 7| > 2 к минимизируемому функционалу добавляется штраф фиксированного размера, который при этом домножается на весовой коэффициент.
N
Определим = ^^ О к ,j,
k,j=1
где О к л- =
1, если вершины с номерами к и 7 попадают в круг радиуса е; 0 в противном случае.
3. Аппроксимативная задача оптимального управления и алгоритм ее решения
Аппроксимативная ЗОУ для рассматриваемой системы 2 в сформулированных терминах может быть поставлена так:
7о(г>) ^ тах при условиях Л(и)=0, 7к(«) = 0, 7а(и)=0.
Рассмотренная вспомогательная ЗОУ имеет размерность nN, где n — размерность исходной системы,
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.