ИЗВЕСТИЯ РАИ. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2008, № 1, с. 5-11
УПРАВЛЕНИЕ В ДЕТЕРМИНИРОВАННЫХ СИСТЕМАХ
УДК 517.977
АЛГОРИТМ МЕТОДА СЕЧЕНИЙ И ПРОГРАММНЫЕ СРЕДСТВА
ДЛЯ ПОСТРОЕНИЯ МНОЖЕСТВ*
© 2008 г. О. В. Моржин, А. И. Тятшшкин
Иркутск, Институт динамики систем и теории управления СО РАН Поступила в редакцию 18.01.07 г.
Рассматривается метод сечений для построения множеств достижимости нелинейных управляемых систем с ограничениями на управление и состояние системы. Предлагаемые алгоритмы основаны на применении комплексов программ, функциональное наполнение которых содержит методы расчета оптимального управления при различных ограничениях на управление и фазовые координаты системы. Обсуждаются также вопросы многопроцессорной вычислительной технологии и приведены результаты численных экспериментов.
Введение. Проблема построения (оценивания) множеств достижимости (МД) для дифференциальных управляемых систем исследуется в работах многих специалистов как в детерминированном случае, так и в системах с неполной информацией [1-5]. При численном исследовании динамических свойств управляемой системы с помощью комплексов программ для расчета оптимального управления представляется также актуальной разработка многоме-тодной вычислительной технологии для построения и оценивания МД в нелинейных дифференциальных системах, которая ориентирована на многопроцессорные расчеты с применением технологии параллельных вычислений.
В данной статье представлены: 1) алгоритм метода сечений для построения МД, основанный на решении серии задач оптимизации программных управлений (ЗОПУ) с ограничениями на правом конце траектории; 2) вычислительная технология, ориентированная на многопроцессорные системы с параллельными вычислениями; 3) результаты эксперимента, показывающего эффективность алгоритма на примерах с различными особенностями.
В алгоритмах численного синтеза, основанных на принципе оптимальности Р. Беллмана, необходимо для каждого момента времени задавать ограниченные множества допустимых состояний системы. Дискретные аппроксимации этих множеств затем представляются в виде решеток, для каждого узла которых методом динамического программирования определяется условно оптимальное управление, переводящее систему в заданное конечное состояние.
Следовательно, на первом этапе алгоритмов численного синтеза необходимо определить гра-
* Работа выполнена при финансовой поддержке РФФИ (проекты < 05-01-00659, 07-01-90101).
ницы множества разрешимости управляемой системы для всех узлов заданной сетки по времени, т.е. построить интегральную воронку [6] как совокупность управляемых состояний системы на всем временном интервале. В алгоритмах, рассматриваемых в данной статье, для построения интегральных воронок используются комплексы программ, с помощью которых решается серия ЗОПУ в обратном времени, начиная с заданного конечного состояния. Результатом работы этих алгоритмов являются множества состояний управляемой системы, из которых она переводима в заданное конечное состояние при некотором допустимом управлении.
1. Постановка задачи. Рассмотрим управляемую систему:
х( г) = Дг, х(г), и(г)), (1.1)
X(гs) = е X?, и(г)е Р с Кт, г е Т = [ ггР], £(г, х(г))<0, я(г, х) = (g1 (г, х),..., gq(г, х)),
^ 1. Э )
г е Т,
х(гР) е Г. (1.4)
Здесь х(г) - вектор состояния, х(г) е Ян, и(г) -управление, и(г) е Ят, г е Т. Траекторию х(-) полагаем непрерывной и кусочно-дифференцируемой, функцию и(-) (программное управление) -кусочно-непрерывной, множество Р - выпуклым компактом в Ёт. Множество начальных состояний Х3, удовлетворяющее условию (1.3), предполагается компактным, и оно может быть одноточечным. Функции/(г, х, и) и я(г, х) предполагаются непрерывно-дифференцируемыми по совокупности переменных (х, и) и переменной х соответственно и кусочно-непрерывными по г, г > г3. Для каждой позиции {г?, х5} и любой допустимой (в смысле (1.2)) программы и(-) существует един-
ственная траектория x[t] = x(t, tS, xS | u(-)) системы (1.1), исходящая из состояния x(tS) = xS.
Требуется найти оптимальное позиционное управление u(t,x) [7, 8], обеспечивающее выполнение целевого критерия /(x(-), u(-)) —«- min при ограничениях (1.2)—(1.4) и с множеством XS, по предположению компактным. Целевое множество GS с Rn ("goal set") определяется из условия (1.4) и допустимых границ изменения фазовых координат в соответствии с прикладным смыслом модели.
Определение 1. Множеством достижимости Ж(б, tS, XS) в момент б > tS из позиции {tS, XS} называется объединение
Ж[б] = Ж (б, tS, Xs ) =
= U(x(б, ts, Xs|u(■):u(■ )e P, xs e Xs}
всех состояний x[6], достижимых в момент t = б в силу системы (1.1) из xS e XS при всех возможных управлениях u(t) e P, tS < t < tF, с учетом фазовых ограничений (1.3).
Определение 2. Трубкой достижимости (или интегральной воронкой) из позиции {tS, XS} называется многозначная функция Ж[б] = Ж(б, tS, Xs), б > ts.
Множества Ж[t] являются сечениями Ж[1] = = Ж^, tS, XS) трубок решений Ж(-, tS, XS) дифференциального включения x e F(t, x), t > tS, x(tS) = XS, где F(t, x) = ft, x, u )|u e P}.
Определение 3. Множеством разрешимости ^[б] = ^(б, tF, GS) системы в момент б называется множество состояний x e Rn, для каждого из которых существует управление u(t) e P, б < t < tF, переводящее систему (1.1) при условиях (1.3) из состояния x(6) = x в некоторое состояние x(tF) e GS ("попятные" МД [6]).
Если множество XS не задано, то его необходимо построить как множество разрешимости системы в момент времени б = tS.
Цель данной статьи - разработать алгоритмы и программные средства для построения множеств достижимости и разрешимости нелинейных управляемых систем, заданных условиями (1.1)—(1.4), и с помощью вычислительных экспериментов показать работоспособность предложенной технологии.
2. Алгоритмы метода сечений. Идея метода сечений для построения МД размерности n1, 2 < n1 < n заключается в следующем:
1) выполняется решение терминальных ЗОПУ с целью нахождения глобальных минимальных и максимальных значений n1 фазовых координат:
min ч max ч 7 Z
xk (tF), xk (tF), k e 1, n; тем самым определяются вершины параллелепипеда, включающего искомое МД, при этом фактическая размерность параллелепипеда 1 < | < n1, зависящая от управ-
ления и свойств множества XS, может оказаться меньшей n в том случае, когда для некоторых координат получим 0 < x,max (xF) — x,min (tF) < 5k, где 5k —
достаточно малое число, k e 1, n ;
2) в полученном параллелепипеде, имеющем размерность | (1 < | < n1, 2 < n1 < n), по тем из n1
фазовых координат, для которых x™ (tF) —
- x,min (tF) > 5k, производится разбиение с заданным шагом Axk > 5k, k e 1, n;
3) далее находим совокупность граничных точек МД, чтобы построить его контур. Для этого при фиксированных на сетке (n — 1) фазовых координатах минимизируется (а затем максимизируется) оставшаяся свободная фазовая координата
xk, k* e 1, n, если выполняется условие x™ (tF) —
- xkmin (tF) > Axxk (и так для каждой из | координат);
4) с целью проверки достижимости узлов сетки, введенной в полученном параллелепипеде, которые изнутри ограничены построенным точечным контуром МД, осуществляется решение серии ЗОПУ о переводе фазовой траектории из точек (или точки) множества XS в эту узловую точку (считается, что контур ограничивает изнутри некоторый узел сетки, не входящий в этот точечный контур, если по каждой координате имеются по две точки контура, образующие с этим узлом шаблон типа "крест").
Ограничимся МД размерностей 2 и 3, потому что для множества большей размерности рассматриваются проекции на 2- и 3-мерное пространство.
Алгоритм 1. Рассмотрим более подробно алгоритм построения на плоскости x1 х x2 точечного контура МД Ж(б, tS, XS).
1. Для системы (1.1)—(1.3) при n = 2, t e [tS, б], б < < tF, формулируются четыре ЗОПУ со свободным правым концом и соответственно с целевыми критериями: xx(6) —► min, xx(6) —► max, x2(6) —► min, x2(6) —► max. При этом требуется найти глобальное решение каждой ЗОПУ. Тем самым получаем минимальные и максимальные значения каждой
min max min max
координаты: x1 , x1 , x2 , x2 .
2. В прямоугольнике с вершинами в точках
min max min min max min max max
(x1 , x2 ), (x1 , x2 ), (x1 , x2 ) и (x1 , x2 ), содержащем искомое МД системы, вводится сетка по тем координатам, для которых 0 < 5k < Axk <
max min max min
< xk - xk , Axk = (xk — xk )/ Rk, где Rk — число разбиений вдоль оси xk, Rk > 1, k e 1, 2 .
r-f t—I 4 max min , ;; .
3. Если Axk < xk — xk , k = 1, 2 , то в цикле по j,
j = 0, R2, выполняется решение (R2 + 1) [задач]
ЗОПУ с целевым критерием xx(0) —► min относительно системы (1.1)—(1.3) с терминальным огра-
//л\ max »
ничением x2(0) = x2 — Axj пересчитываемым от задачи к задаче. Тем самым находится "левая" часть контура МД. Аналогично в цикле по j, j =
= 0, R2, выполняется решение (R2 + 1) ЗОПУ на максимум x1(ö) относительно системы (1.1)—(1.3) с указанным выше терминальным ограничением по координате x2. В итоге вычисляются координаты точек "правой" части контура МД.
4. Если Axk < x,max — хГ, k = 1, 2, то в цикле по
i, i = 0, Ri, находится решение каждой из (R1 + 1) ЗОПУ из серии с целевым критерием х2(0) —*- min относительно системы (1.1)—(1.3) при терминальном ограничении х1(б) = х™ - Ax1i. В результате определяются координаты точек "нижней" части контура МД. Из решения (R1 + 1) ЗОПУ в цикле
по i, i = 0, Rt, с целевым критерием х2(0) —»- max при том же терминальном ограничении (пересчитываемым для каждой ЗОПУ из серии) находятся координаты точек "верхней" части контура МД.
Замечание! Полученные в результате реализации алгоритма 1 точки образуют точечный контур МД. При этом некоторые точки могут вычисляться более одного раза: например, при вычислении точек "левой" и "нижней" частей контура МД. Точки, которые получаются на итерациях метода глобального решения ЗОПУ и удовлетворяют терминальному ограничению, но не доставляют глобального экстремума в задаче, могут быть также учтены. Если в алгоритме 1 условие
A Xk* < Xk*
max min
— xk * не выполняется только для од-
ной координаты k* е I, 2 , то вмест
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.