научная статья по теме АЛГОРИТМ КУСОЧНО-ЛИНЕЙНОЙ АППРОКСИМАЦИИ ГРАНИЦЫ МНОЖЕСТВА ДОСТИЖИМОСТИ Автоматика. Вычислительная техника

Текст научной статьи на тему «АЛГОРИТМ КУСОЧНО-ЛИНЕЙНОЙ АППРОКСИМАЦИИ ГРАНИЦЫ МНОЖЕСТВА ДОСТИЖИМОСТИ»

Автоматика и телемеханика, № 3, 2015

( 2015 г. А.Ю. ГОРНОВ, д-р техн. наук (gornov@icc.ru), Е.А. ФИНКЕЛЬШТЕЙН (finkel@icc.ru) (Институт динамики систем и теории управления СО РАН, Иркутск)

АЛГОРИТМ КУСОЧНО-ЛИНЕЙНОЙ АППРОКСИМАЦИИ ГРАНИЦЫ МНОЖЕСТВА ДОСТИЖИМОСТИ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 , г с одинаковыми для всех подсистем ограничениями (