Институт математики и механики им. Н.Н. Красовского УрО РАН (Екатеринбург) Рассмотрена задача достижимости для линейных многошаговых управляемых систем, описывающих так называемое групповое движение, при котором объекты попарно не сближаются, но и не слишком отдаляются друг от друга. Условия группового движения приводят к невыпуклым фазовым ограничениям специального типа, в результате чего множества достижимости могут быть невыпуклыми и даже несвязными. Получающиеся трубки достижимости могут быть представлены в виде ветвящихся трубок, сечения которых являются выпуклыми политопами, а множества достижимости представимы в виде объединения вышеупомянутых сечений. В работе предлагаются некоторые алгоритмы построения внутренних полиэдральных оценок множеств достижимости в виде объединений параллелепипедов, построенных на основе “элементарных” параллелотопозначных оценок для результатов теоретико-множественных операций с параллелелотопами/параллелепипедами и полосами. Ключевые слова: множества достижимости; многошаговые системы; групповое движение; внутренние полиэдральные оценки.
можно более точных аппроксимаций (например, путем аппроксимации множеств политопами с большим количеством вершин и граней [12, 13]), но могущих потребовать большого объема вычислений, особенно для систем большой размерности. Упомянем, что кроме указанного выше гарантированного подхода к решению задач управления и оценивания в условиях неопределенности существует стохастический подход, при котором используются вероятностные характеристики неизвестных входных данных. Решения задач оценивания состояния линейных многошаговых систем при одновременном наличии детерминированных и случайных помех описано, например, в [14, 15]. Множества достижимости по начальным данным и их аппроксимации для стохастических систем рассматривались, например, в [16].
В настоящей работе рассматривается задача достижимости для линейных многошаговых управляемых систем, описывающих так называемое групповое движение. А именно, рассматривается конечное множество управляемых объектов при условии, что их траектории должны не слишком сближаться, но и не слишком отдаляться друг от друга. Мотивация задач такого рода вытекает из активно развиваемой в последнее время теории управления групповым движением (см., например, [5, 17–19]). Предполагается, что начальные состояния и управления объектов стеснены данными параллелепипедозначными ограничениями. Вышеупомянутые условия группового движения приводят к невыпуклым фазовым ограничениям специального типа, в результате чего множества достижимости могут быть невыпуклыми и даже несвязными. Получающиеся трубки достижимости могут быть представлены в виде ветвящихся трубок, сечения которых являются выпуклыми политопами, а множества достижимости представимы в виде объединения вышеупомянутых сечений [20]. В работе предлагаются некоторые алгоритмы построения внутренних полиэдральных оценок множеств достижимости в виде объединений параллелепипедов, построенных на основе “элементарных” параллелотопозначных оценок [9–11] для результатов теоретико-множественных операций с параллелелотопами/параллелепипедами и полосами.
Ниже используются следующие обозначения: Rn и Rn£m линейные пространства вещественных n-векторов и n£m-матриц соответственно; > знак транспонирования; kxk2 = (x>x)1=2 и kxk1 = max1·i·n jxij разные нормы вектора x = (x1; : : : ; xn)>; e = (1; 1; : : : ; 1)>; A = faijg = fa1; a2; : : : ang матрица с элементами aij и со столбцами aj (верхним индексом нумеруются столбцы, нижним компоненты векторов); 0 нулевая матрица (вектор) произвольной размерности; I единичная матрица; A = diag fAjg диагональная матрица A с блоками Aj на диагонали; det A определитель матрицы A; kAk = max1·i·n Pjm=1 jaijj норма матрицы A2Rn£m, индуцированная нормой kxk1; int X совокупность внутренних точек множества X ½ Rn; M (H) мощность (число элементов) конечного множества H; vol P объем параллелепипеда P . 2
Постановка задачи Предполагается, что система состоит из m подсистем с фазовыми координатами xj = (xj;1>; xj;2>)> 2 Rn, где n = n1 + n2, xj;1 2 Rn1, xj;2 2 Rn2, j = 1; 2; : : : ; m, и описывается соотношениями xj[k] = Aj[k] xj[k¡1] + Bj[k] uj[k]; k = 1; 2; : : : ; N; j = 1; 2; : : : ; m;
j
xj[0] 2 P0 ; uj[k] 2 Rj[k]; k = 1; 2; : : : ; N ; j = 1; 2; : : : ; m;
kxj;1[k] ¡ xl;1[k]k1 ¸ ¹; k = 0; 1; : : : ; N; j; l = 1; 2; : : : ; m; l > j;
kxj;1[k] ¡ xl;1[k]k1 · ¹; k = 0; 1; : : : ; N; j; l = 1; 2; : : : ; m; l > j:
(1)
(2)
(
Множеством достижимости (МД) Z[i] системы (1)–(
В [20] были исследованы некоторые свойства вышеупомянутых множеств достижимости и дано описание трубок достижимости в виде ветвящихся трубок. В настоящей работе рассматривается задача нахождения внутренних полиэдральных оценок для них с использованием “элементарных” параллелепипедозначных оценок для множеств.
Напомним некоторые упомянутые выше и используемые далее понятия. Называем множество P ½ Rn внутренней оценкой множества Q ½ Rn, если Q µ P .
Параллелепипедом P(p; P ; ¼) ½ Rn называем множество P = P(p; P ; ¼) = fx j x = p + Pin=1 pi¼i»i; j»ij · 1g, где p 2 Rn; P = fpig 2 Rn£n неособая матрица (det P 6= 0) со столбцами pi, kpik2 = 1 (приведенное условие нормировки в терминах евклидовой нормы может быть опущено с целью упрощения формул); ¼ 2 Rn, ¼ ¸ 0 (векторные неравенства понимаем покомпонентно). Можно сказать, что p центр параллелепипеда, P матрица ориентации, pi направления, ¼i величины его “полуосей”.
Параллелотопом P[p; P¹ ] ½ Rn называем множество P = P[p; P¹ ] = fxj x = p + P¹³; k³k1 · 1g, где p 2 Rn, а матрица P¹ = fp¹ig 2 Rn£r может быть особой и необязательно квадратной (r · n). Называем параллелотоп P невырожденным, если r = n и det P¹ 6= 0.
Полосой или m-полосой S = S(c; S; ¾; m) ½ Rn называем пересечение m гиперполос §i, где 1 · m · n m (здесь m не связано с числом подсистем в (1)): S = S(c; S; ¾; m) = T §i, где §i = §(ci; si; ¾i) = fx j jx>si ¡ i=1 cij · ¾ig. Здесь c 2 Rm; S = fsig 2 Rn£m матрица ранга m со столбцами si 2 Rn; ¾ 2 Rm, ¾ ¸ 0. Векторы §si определяют нормали к гиперплоскостям, ограничивающим гиперполосу §i.
Каждый параллелепипед это параллелотоп: P(p; P ; ¼) = P[p; P¹], P¹ = P diag f¼ig; каждый невырожденный параллелотоп это параллелепипед с P = P¹ diag fkp¹ik2¡1g, ¼i = kp¹ik2 или, иначе, с P = P¹, ¼ = e, где e = (1; 1; : : : ; 1)>. Известно также, что при m = n полоса превращается в параллелепипед (см. формулы в [8]).
Везде ниже считаем, что выполнено следующее предположение.
Предположение 1. Множества P0j = P(pj0; P0j; ¼0j) = P[pj0; P¹0j] ½ Rn и множества Rj[k] = P(rj[k]; Rj[k]; ½j[k]) = P[rj[k]; R¹j[k]] ½ Rnu в (2) это параллелепипеды; все матрицы Aj[k] неособые.
В следующем разделе приводится описание множеств достижимости и трубок достижимости рассматриваемых систем. Четвертый раздел посвящен алгоритмам построения искомых внутренних полиэдральных оценок. 3
Описание множеств достижимости и трубок достижимости Несложно видеть, что полная система может быть записана в виде: z[k] = A[k] z[k¡1] + B[k] u[k]; k = 1; 2; : : : ; N ; z[0] 2 P0;
u[k] 2 R[k]; k = 1; 2; : : : ; N ; z[k] 2 Y; k = 0; 1; : : : ; N: Здесь A[k] = diag fAj[k]g и B[k] = diag fBj[k]g блочные матрицы, составленные из матриц, фигурирующих в (1); параллелепипеды P0 = P[p0; P¹0] и R[k] = P[r[k]; R¹[k]] (записанные для простоты обозначений в виде параллелотопов) определяются множествами P0j = P[pj0; P¹j] и Rj[k] = P[rj[k]; R¹j[k]] из (2): 0 p0 = (p10>; p20>; : : : ; p0m>)>, P¹0 = diag fP¹0jg, r[k] = (r1[k]>; r2[k]>; : : : ; rm[k]>)>, R¹[k] = diag fR¹j[k]g; множество Y определяется нижними и верхними ограничениями из условий группового движения:
Y = Y· T Y^;
Y· = fz = (x1>; x2>; : : : ; xm>)> j kxj;1 ¡ xl;1k1 ¸ ¹; j; l = 1; 2; : : : ; m; l > jg;
Y^ = fz = (x1>; x2>; : : : ; xm>)> j kxj;1 ¡ xl;1k1 · ¹; j; l = 1; 2; : : : ; m; l > jg
и задает фазовые ограничения в системе (
Известно [3, § 18], что МД системы типа (
Рассмотрим, что представляет собой пересечение выпуклого множества Z(0) с Y.
Несложно заметить, что невыпуклое множество Y· представимо в следующем виде:
(
Заметим также, что нетрудно распространить результаты статьи на случай, где неравенства в условиях
группового движения (
Рис. 1: Пример множеств Z(0) = P0, Y·, Y^ и Y для случая m = 2, n1 = 1, n2 = 0
На рис. 1 дан пример для случая m = 2, n1 = 1, n2 = 0, показывающий, что может получиться в
Rm(n1+n2) при пересечении параллелепипеда Z(0) = P0 с множествами Y· и Y. Здесь Y· состоит из двух
8
x2 0
8
С учетом рекуррентных соотношений (
Утверждение 1. (См. [20]). Трубка достижимости Z[¢] системы (1)–(
Z =
S S 1·i1;:::;iJ ·n1 0·!1;:::;!J ·1
³Z(0) T ¡Y(1i1;!1) T Y(2i2;!2) T : : : T Y(JiJ ;!J )¢´ =
S S 1·i1;:::;iJ ·n1 0·!1;:::;!J ·1
J ³Z(0) T ¡ T °=1
Y(i°;!°)¢´; ° где J = m(m ¡ 1)=2, а объединения берутся по всевозможным индексам i1; i2; : : : iJ , изменяющимся от 1 до n1, и всевозможным индексам !1; !2; : : : !J , принимающим значения 0 и 1.
Замечание 1. Обозначим через Wh множества Wh = T°J=1 Y(°i°!°), которые мы “занумеровали” с помощью векторов типа
Z[0; H[0]] = P0 T (T°J=1 Y(i°[0];!°[0])) = P0 T Wh[0]; °
H[0] = [h[0]]; Z(0)[k; H[k¡1]] = A[k] Z[k¡1; H[k¡1]] + B[k] R[k]; k = 1; 2; : : : ; N ; H[k] = [H[k¡1]; h[k]] = [h[0]; h[1]; : : : ; h[k]]; k = 1; 2; : : : ; N ; h[k] = ((¡1)!1[k]+1i1[k]; (¡1)!2[k]+1i2[k]; : : : ; (¡1)!J [k]+1iJ [k])>; k = 0; 1; : : : ; N ; Z[k; H[k]] = Z(0)[k; H[k¡1]] T Wh[k]; k = 1; 2; : : : ; N ;
Wh[k] = TJ °
°=1 Y(i°[k];!°[k]); k = 0; 1; : : : ; N: При этом множества достижимости Z[k] представимы в виде объединения вышеупомянутых сечений: Z[k] = SH[k] Z[k; H[k]] (назовем эти сечения Z[k; H[k]] компонентами множеств достижимости), верхняя оценка числа которых дается большим числом L[k] = Kk+1, где K = (2n1)J , J = m(m ¡ 1)=2.
Таким образом, для каждой ветви Z[¢; H[¢]] на каждом k-м шаге сначала производятся операции линейного преобразования сечения и суммирования множеств, затем выбирается J штук n3-полос из тех, которые определяют множество Y, конструируется соответствующее множество Wh[k] и производится операция пересечения с ним. Индексы, определяющие эти полосы, запоминаются в последнем столбце h[k] матрицы H[k]. 1·j·m 1·k·N uj[k]2Rj[k] kBj[k]uj[k]k1. max max max
Описание ветвящейся трубки достижимости Z[¢] в форме с ветвями Z[¢; H[¢]] с использованием матриц H[k] отражает суть конструкций, но может быть не очень эффективно при компьютерной реализации. Заметим, что трубка Z[¢] может быть представлена как позиционное дерево, а именно, как K-арное дерево, так что степень каждого узла не превышает K (см., например, [22, часть VIII, разд. Б.5.3]).
Верхняя оценка числа получающихся таким образом ветвей и, соответственно, компонент МД дается очень большим числом L[k] = Kk+1 = (2n1)J(k+1). При некоторых предположениях (типа приведенного ниже предположения 2) эту оценку можно немного уменьшить. 2 3 4 5 6 Число пар объектов Рассмотрим вопрос о построении внутренних полиэдральных оценок множеств достижимости для случая группового движения.
В силу (
Пусть Q это ограниченный политоп, определяемый пересечением ¨ ¸ n + 1 гиперполос: Q = Tj¨=1§j, §j = §(cj; sj; ¾j) = fxj j (x>sj ¡ cjj · ¾jg, и пусть Q имеет непустую внутренность int Q. Внутренние параллелепипедозначные оценки P p¡¡;P ¡(Q) для Q с произвольным фиксированным центром p¡ 2 int Q и неособой матрицей ориентации P ¡ 2 Rn£n могут быть вычислены по явным формулам [10, 11]; p¡ и P ¡ выступают в роли параметров оценок. Один из возможных способов нахождения центра p¡ при выбранной матрице ориентации P ¡ это решение задачи максимизации объема оценки, т.е. нахождение: p¡ 2 Argmax fvol P p¡¡;P ¡(Q) j p¡ 2 Qg. Для численного решения может быть использован, например, симплексный метод Нелдера и Мида [23].
Некоторые примеры построения полиэдральных оценок трубок траекторий (для систем без условий группового движения) с использованием элементарных оценок приведены в [8–11].
Заменяя в рекуррентных соотношениях для нахождения МД результаты операций с множествами соответствующими элементарными оценками, рассмотрим ветвящуюся полиэдральную трубку с ветвями P¡[¢; H[¢]], где сечения P¡[k; H[k]] каждой ветви P¡[¢; H[¢]] удовлетворяют следующим соотношениям: (P0; если P0 µ Wh[0];
P p¡¡[H[0]];P ¡[H[0]](P0 T Wh[0]) в противном случае; P(0)¡[k; H[k¡1]] = P ¡¡[H[k¡1]](A[k] P¡[k¡1; H[k¡1]] + B[k] R[k]); k = 1; 2; : : : ; N ; H[k] = [H[k¡1]; h[k]] = [h[0]; h[1]; : : : ; h[k]]; k = 1; 2; : : : ; N ; H[0] = h[0]; P¡[k; H[k]] = (P(0)¡[k; H[k¡1]]; если P(0)¡[k; H[k¡1]] µ Wh[k];
P p¡¡[H[k]];P ¡[H[k]](P(0)¡[k; H[k¡1]] T Wh[k]) в противном случае; Wh[k] = T°J=1 Y(i°[k];!°[k]); k = 0; 1; : : : ; N: ° k = 1; 2; : : : ; N ; Здесь матрица H[k] = [h[0]; h[1]; : : : ; h[k]] = fh[·]gk·=0 2 RJ£(k+1) определяет “историю” построения ветви аналогично утверждению 1. Матричные функции ¡[¢] и P ¡[¢] и векторные функции p¡[¢], удовлетворяющие следующим условиям: ¡[H[k]] 2 Rmnu£mn, k¡[H[k]]k · 1, k = 0; 1; : : : ; N ¡1; P ¡[H[k]] 2 Rmn£mn, det P ¡[H[k]] 6= 0, k = 0; 1; : : : ; N ; p¡[H[k]] 2 Rmn; p¡[H[0]] 2 int (P0 T Wh[0]); p¡[H[k]] 2 int (P(0)¡[k; H[k¡1]] T Wh[k]), k = 1; 2; : : : ; N , представляют собой допустимые параметры оценок.
Утверждение 2. Если ветвящаяся полиэдральная трубка P¡[¢] такова, что ее ветви P¡[¢; H[¢]]
удовлетворяют рекуррентным соотношениям (
SH[k] P¡[k; H[k]] µ Z[k]; k = 0; 1; : : : ; N:
Верхняя оценка числа непустых множеств в объединении (
Опять получается, фактически, K-арное дерево, где K = (2n1)J , J = m(m ¡ 1)=2. Вычисление всех ветвей полного K-арного дерева [22, часть VIII, разд. Б.5.3] может быть практически невозможно для m > 2, n1 > 1 и не очень малых значений высоты дерева (равной k + 1 на шаге k). Предлагается строить не всю систему ветвей P¡[¢; H[¢]], а зафиксировать некоторое число L и строить не более L внутренних трубок (ветвей P¡[¢; H[¢]]), оставив при k = 0 не более L параллелотопов P¡[0; H[0]], а затем последовательно оставляя на каждом k-м шаге из потенциально возможных L ¢ K трубок не более L штук, а именно, те, которые имеют большие (по сравнению с другими) объемы сечений параллелепипедов P¡[k; H[k]].
При этом строится система L параллелепипедозначных трубок P(®)¡[¢], ® = 1; 2; : : : ; L, вычисление
которых можно описать соотношениями типа использовавшихся в [10]:
P(®);(0)¡[k] = P ¡¡(®)[k¡1](A[k] P(®)¡[k] + B[k] R[k]); k = 1; 2; : : : ; N;
(
Введем следующие обозначения. Пусть f (h) функция аргумента h, принимающего значения из
некоторого непустого конечного множества H, которое имеет мощность (число элементов) M (H) = K ¸
L ¸ 1. Записью H~ = argmax(L) ff (h) j h 2 Hg будем обозначать процедуру нахождения множества
H~ = fh~1; h~2; : : : h~Lg таких L элементов множества H, которые дают наибольшие, по сравнению с другими,
значения функции f . А именно, при K > L упорядочим все значения f (h) при h 2 H по величине: f (h¯1 ) ¸
f (h¯2 ) ¸ : : : ¸ f (h¯L ) ¸ f (h¯L+1 ) ¸ : : : ¸ f (h¯K ). Если выполнено строгое неравенство f (h¯L ) > f (h¯L+1 ),
то полагаем H~ = argmax(L) ff (h) j h 2 Hg = fh~1; h~2; : : : h~Lg = fh¯1 ; h¯2 ; : : : h¯L g; множество H~ определяется
однозначно. Если же f (h¯L ) = f (h¯L+1 ), то либо просто полагаем H~ = fh¯1 ; h¯2 ; : : : h¯L g, либо находим
индексы K1 и K2, такие что 1 · K1 · L < K2 · K и f (h¯K1 ) = f (h¯K1+1 ) = : : : = f (h¯K2 ), причем K1
таков, что либо K1 = 1, либо f (h¯K1¡1 ) > f (h¯K1 ), а K2 таков, что либо K2 = K, либо f (h¯K2 ) > f (h¯K2+1 );
из векторов h¯K1 ; h¯K1+1 ; : : : h¯K2 случайным образом выбираем L ¡ (K1 ¡ 1) штук и вносим их в H~ после
внесения туда h¯1 ; h¯2 ; : : : h¯K1¡1 (которое выполняется при K1 > 1). При K = L просто полагаем H~ = H.
Далее в качестве H будем рассматривать множество всевозможных векторов h типа (
(1) Все H~(®)[k] = H (® = 1; 2; : : : ; L, k = 1; 2; : : : ; N ), т.е. берутся наибольшими возможными. При этом K~ [k] = K; для больших значений m объем вычислений может оказаться слишком большим.
(2) Все множества H~(®)[k] (® = 1; 2; : : : ; L, k = 1; 2; : : : ; N ) одноточечные, определяемые равенствами
~(®)[k] = h~®. При этом K~ [k] = 1 и в результате вычислений будут найдены “стационарно расположенные”
H
внутренние оценки компонент множеств достижимости, т.е. те оценки, которые лежат в зафиксированных
вначале и не меняющихся от шага к шагу множествах.
На k-м шаге для перехода от P(®);(0)¡[k] к P(®)¡[k] для каждого ® 2 f1; 2; : : : ; Lg строится K~ [k] штук
множеств P(®;¯)¡[k] = P p¡(®;¯)¡[k]];P (®;¯)¡[k](P(®);(0)¡[k] T Wh¯ ), где индекс ¯ 2 f1; 2; : : : ; K~ [k]g пробегает
множество значений, позволяющих перебрать все элементы множества H~(®)[k] возможных (допускаемых
алгоритмом) на k-м шаге значений векторов h¯ типа (
P(±)¡[k] = P(®±¤[k];¯±¤[k]))¡[k]; ± = 1; 2; : : : ; L;
h(±)[k] = h¯±¤[k]; ± = 1; 2; : : : ; L:
При этом, очевидно, может получиться, что для построенного таким образом сечения P(±)¡[k] имеем ®±¤ 6= ±
(т.е. требуется смена нумерации трубок), и может быть, что не все значения ®¤; ®2¤; : : : ; ®L¤ различны
(какие1
то трубки “оборвались”, а какие-то “разветвились”). Поэтому, чтобы остаться в рамках описания трубок
с помощью соотношений (
P(±)¡[·] = P(®±¤[k])¡[·]; · = 0; 1; : : : ; k ¡ 1; h(±)[·] = h(®±¤[k])[·]; · = 0; 1; : : : ; k ¡ 1; ± = 1; 2; : : : ; L: Следствие 3. Пусть трубки P(®)¡[¢], ® = 1; 2; : : : ; L, построены описанным выше способом. Тогда внутренними оценками для множеств достижимости Z[k] будут служить объединения параллелепипедов P(®)¡[k]: S0·®·L P(®)¡[k] µ Z[k], k = 0; 1; : : : ; N .
Заметим, что при численной реализации вычисления трубок P(®)¡[¢] на компьютере вместо работы с L массивами, содержащими описания вышеупомянутых трубок, эффективнее использовать указатели и структуры типа дерево (чтобы для двух трубок с одинаковыми начальными участками “историй” соответствующие участки хранились в одном экземрляре).
Ввиду большого объема требуемых вычислений может быть полезно проводить их на многопроцессорном вычислительном комплексе. В качестве простейшего способа распараллеливания (вообще говоря, не самого эффективного с точки зрения получения трубок с наибольшими объемами сечений) можно предложить простейшую “процессорную ферму”, когда “рабочие” процессоры рассчитывают отдельные системы внутренних параллелепипедозначных трубок (каждый не более L штук аналогично тому, как описано выше), и операция argmax(L) применяется к трубкам, рассчитываемым только на этом процессоре.
Численная верификация предложенных алгоритмов является предметом дальнейшей работы. Благодарности Список литературы Работа выполнена при частичной финансовой поддержке РФФИ (Проект 15-01-02368a). [1] A.B. Kurzhanski, I. V´alyi. Ellipsoidal Calculus for Estimation and Control. Boston: Birkh¨auser, 1997. [2] A.B. Kurzhanski, P. Varaiya. Dynamics and Control of Trajectory Tubes: Theory and Computation.
(Systems & Control: Foundations & Applications, Book 85). Birkh¨auser Basel, 2014. систем при групповом движении. Вестник ЮУрГУ. Серия: Вычислительная математика и ин-форматика, 5(1):13–23, 2016. URL: http://vestnik.susu.ru/cmi/article/view/3888/4226 (Дата обращения 25.12.2016).
On internal estimates for reachable sets of discrete-time systems describing multi-agent motion
Elena K. Kostousova Krasovskii Institute of Mathematics and Mechanics (Ekaterinburg, Russia)
Abstract. The reachability problem for linear discrete-time control systems which describe so called multiagent motion is considered. Namely, we consider a finite set of control subsystems under a condition that the trajectories of the subsystems should be pairwise not very close to and not very far away from each other. The conditions of multi-agent motion lead to nonconvex state constraints of special type. As a result the reachable sets can be nonconvex and even disconnected. Corresponding reachable tubes may be presented in the form of branching trajectory tubes whose cross-sections are convex polytopes; the reachable sets may be presented in the form of unions of the mentioned cross-sections. In the paper, there are proposed some algorithms for constructing internal polyhedral estimates for the reachable sets in the form of unions of parallelepipeds, which are constructed on the base of primary parallelotope-valued estimates for results of set operations with parallelotopes/parallelepipeds and zones.
Keywords: reachable sets, discrete-time systems, multi-agent motion, internal polyhedral estimates.