В статье приводится краткий обзор задач, которые естественно возникают при планировании траектории движения объекта в условиях наблюдения за ним наблюдателями и, с другой стороны, при оптимальном размещении наблюдателей для сопровождения движущегося объекта. При планировании маршрута движения объекта в условиях наблюдения за ним со стороны других объектов-наблюдателей возникают экстремальные задачи построения маршрута с различными критериями [1]. С другой стороны, представляют интерес задачи оптимального размещения наблюдателей для сопровождения движущегося объекта. В работе предполагается наличие у объекта скоростного средства поражения, что заставляет наблюдателя для обеспечения безопасности придерживаться определенной тактики движения. Приведена характеризация оптимальной траектории, минимизирующей максимум видимости объекта при движении по траектории. Для задачи оптимизации интегрального критерия рассмотрен эффективный численный метод построения оптимального маршрута, основанный на модификации алгоритма Дейкстры.
Пусть G
T0 = ft( ) 2 X : 0 1; t(0) = t ; t(1) = t g:
множество видимых из t точек пространства, s(t) = = Xn v(t) S G тень множества G (при освещении из точки t), s(t) ее замыкание, (t; M ) расстояние от точки t до множества M .
Объект имеет возможность поразить наблюдателя посредством миниобъекта, способного двигаться в Xn G прямолинейно с большой скоростью. Таким образом, свобода движения наблюдателя f ограничена: он должен находиться вблизи множества s(t). Рисунок 1 иллюстрирует описываемую постановку задачи. Рис. 1: Задача о наиболее скрытом маршруте объекта t при наличии враждебных наблюдателей fi (показаны черными точками), которые вынуждены находиться недалеко от теневого множества s(t). Кружками показаны угловые точки множества G, которые играют важную роль в решении задачи Задача объекта t состоит в выборе траектории Tb из класса T непрерывных траекторий T = ft( ) : 0 1; t(0) 2 V ; t(1) 2 V g
Ye ; для которой max min (t; s(t)) = min (t; s(t)):
T 2T t2T t2Tb Наряду с (1) представляет интерес задача максимизации интегрального функционала: max T 2T
Z (t( ); s(t( ))) d (1) (2) на некотором естественном подклассе T траекторий из класса T.
Далее для простоты изложения, как правило, будем предполагать X = R2, оговаривая особо факты, справедливые и для X = R3. 3
Теневые точки и области влияния Точку x 2 G назовем теневой для t, если x 2 v(t) \ s(t);
(t; x) \ s(t) = ?: Далее предполагается, что граница bd G множества G является кусочно-гладкой: она может включать в себя конечное число прямолинейных отрезков и конечное число участков строгой выпуклости (фактически, конечное число точек перегиба), что важно для построения алгоритмов поиска оптимальной траектории.
Будем рассматривать точки x локальной выпуклости границы. Для каждой из них существует окрестность O(x) и прямая L; x 2 L, такие, что множество G T O(x) лежит по одну сторону относительно L. Точка локальной выпуклости называется угловой, если величина угла между односторонними касательными прямыми в этой точке удовлетворяет неравенству 0 < < . Множество угловых точек границы G обозначим через A (рис. 2). Максимальный по включению связный гладкий участок выпуклости границы множества G (участок, состоящий из гладких точек локальной выпуклости), будем обозначать через C (см. рис. 2). Итак, C гладкая выпуклая связная кривая без концевых точек. Совокупность таких участков границы обозначим через C.
Рис. 2: Граница множества G: угловые точки a; a0; a00 и выпуклый участок C Теневыми точками могут быть только угловые точки и точки из C 2 C. Для иных точек x 2 bd G любая прямая, содержащая x, содержит точки из G в любой окрестности O(x). Пусть t 62 G. Рассматривая множество точек на границе bdG, видимых (освещенных) из точки t, с учетом ограниченности G и связности дополнения XnG, можно установить (см. [2, теорема 1 для многогранного G]), что справедлива Лемма 1 Для любой точки t 62 G множество теневых точек непусто.
На примере, показанном на рисунке 3, для позиции t имеются две теневые точки. В дальнейшем будем обозначать множество ближайших к x точек из множества M Для точки s 2 bd G обозначим
X.
Рис. 3: Теневые точки
PM (x) = fy 2 M : kx yk = (x; M )g Te(s) = t 62 G : t 2 v(s); s 2 s(t) ;
T (s) = ft 62 G : s 2 Ps(t)(t)g замыкание множества точек t 62 G, для которых s является ближайшей теневой точкой. Если a 2 A угловая точка, то Te(a) является дополнением до XnG объединения угла при a и вертикального к нему угла (рис. 4i). Если c 2 C 2 C, то множество Te(c) непусто и лежит на касательной к дуге C прямой в точке c (рис. 4ii).
Для гладкого выпуклого участка C 2 C определим множества (рис. 4iii)
Te(C) = [ Te(c); c2C
T (C) = [ T (c):
c2C (i) (ii)
(iii) Рис. 4: Построение областей Te(a) и Te(C) Определим множество S = A S C, его элементы s 2 S будем называть вершинами. Множество S предполагается конечным. Для вершин s и точек x 2 T (s) введем “расстояние” 8 >> kx (x; s) = < kx > > : sk; если s = a 2 A; x 2 Te(a); ck; если s = C 2 C; c 2 C; x 2 Te(c); +1; если t 2= Te(s): (3) Принадлежность объекта множеству T (s) означает его близость к вершине s, где может присутствовать наблюдатель. По этой причине T (s) можно назвать “областью влияния” вершины s. Предпочтительным для объекта является месторасположение на общей границе смежных множеств T (s) и T (s0). Важно, что по определению этих множеств точки общей границы B(s; s0) = T (s) T T (s0) равноудалены от s и s0 по расстоянию (3). При поиске этих границ учитывается линейчатая структура множеств Te(s) (коническая при s 2 A, а при s 2 C совокупность интервалов на касательных прямых к дуге C) и используется решение следующих задач о построении границ между 1) T (a) и T (a0) (a; a0 2 A), 2) T (a) и T (C) (a 2 A; C 2 C), 3) T (C) и T (C0) (C; C0 2 C).
1) В случае многоугольного G множество T (a) является многоугольником, а в области, где Te(a) T Te(a0) 6= 6= ?, множества T (a); T (a0) разграничивает прямая L, ортогональная отрезку [a; a0] и содержащая точку (a + a0)=2. Так что ka zk = kz a0k (z 2 L) (рис. 5i).
2) Точки z границы между T (a) и T (C), попавшие в область Te(a) T Te(C) определяются так, что ka zk = = kz ck, где c 2 C точка касания дуги C с прямой, содержащей точку z (рис. 5ii).
3) Точка z границы между T (C); T (C0), попавшая в область Te(C) T Te(C0), есть пересечение прямых, касающихся дуг C; C0 в точках c 2 C; c0 2 C0 таких, что kc zk = kz c0k.
Граница раздела B(s; s0) указанных множеств может иметь сложную форму даже для множества простого вида (см. рис. 5ii).
(i)
(ii) Рис. 5: Примеры границ, разделяющих области влияния В работе [2] доказано следующее утверждение. Лемма 2 Пусть X = Rn и G–многогранник, тогда если X = R2, то [ T (a) = Xn G.
T (a) T T (a0) = ? для любых a; a0 2 A; a 6= a0;
a2A Замечание. Если X = R2, то утверждения леммы 2 можно распространить на случай, когда G не обязательно многогранник, следующим образом: [ T (s) = Xn G.
T (s) T T (s0) = ? для любых s; s0 2 S; s 6= s0; s2A Отметим, что в условиях леммы 2 множество
T0 = (Xn G)n [ T (a) a2A также является многогранником. Легко показать, что в случае X = Rn (n > 2) множество (4) может быть непустым.
На рисунке 6 показан пример построения областей влияния угловых точек для случая, когда G – многогранник. Для того чтобы не загромождать рисунок, заштрихованы области влияния только для двух точек “1” и “2”.
Рис. 6: Пример построения областей влияния угловых точек для случая, когда G – многогранник 4
Характеризация наилучшей траектории Решая задачу (1), объект t должен проследовать из V до V , максимизируя внутри коридора Y = Ye n(V S V ) наименьшее расстояние до вершин s 2 S, поскольку в них, возможно, присутствуют наблюдатели. Далее будет удобно на границе коридора Y выделить левую границу Yl и правую Yr относительно движения от t к t по оптимальной траектории, содержащейся в Y . Указанные границы берут свое начало на границе шара V и заканчиваются на границе шара V . Необходимо указать все точки из Y , которые должны лежать на оптимальной для задачи (1) траектории. По замечанию к лемме 2 коридор заполнен множествами T (s).
Пусть s 2 S,
Te(s) \ Y 6= ?;
Te(s) \ Yl 6= ?;
Te(s) \ Yr 6= ? (4) (5) и Ys более далекая по расстоянию (s; x) от s граница Yl или Yr. Обозначим через S1 множество вершин, удовлетворяющих условию (5). В связи с вершиной s рассмотрим задачу
M (s) = (s; Ys) = min (s; y); y2Ys и пусть P = PYs (s) множество ближайших к s по расстоянию точек из Ys. Любая траектория T 2 T пересекает любой отрезок, соединяющий s с точками из P. В случае малости величины (s; Ys) траектория Tb должна содержать множество P (рис. 7a).
Теперь возьмем пару вершин s; s0 2 S с противоположных сторон коридора Y (расстояния (s; Y ); (s0; Y ) достигаются на разных сторонах Yl; Yr границы Y ), для которых Q = Te(s) T Te(s0) 6= ? и Q T Y 6= ?. Множество таких пар вершин обозначим через S2. Тогда любая траектория T 2 T пересекает любую двузвенную ломаную, соединяющую точку x из Q с s и s0 (с точкой a, если s = a 2 A, а если s 2 C 2 C, то с точкой c 2 C, для которой x 2 Te(c)).
(a) (b) (c) Рис. 7: К доказательству теоремы: три случая расположения теневых точек относительно коридора Y В связи с парой таких вершин возникает задача Предположим, что общая граница
M (s; s0) = max min x2Q
(s; x); (s0; x) :
B(s; s0) = z : (s; z) = (s0; z) множеств T (s); T (s0) не пересекается с Q, и пусть вершины s и Q лежат по одну сторону от B(s; s0) (рис. 7b). Очевидно, что максимум (7) доставляет точка P = P(s; s0) 2 Q, для которой (s; P) = max (s; x) < (s0; P) = min (s0; x)
x x и M (s; s0) = (s0; P). При малой величине M (s; s0) точка P = P(s; s0) должна лежать на Tb. Здесь важно отметить, что P 2 bd Te(s), поэтому вершина s не является теневой для точки P. Оптимальная траектория Tb лишь касается границы bd Te(s) в точке P и в окрестности O(P) этой точки не пересекается с внутренностью множества Te(s). Но Tb пересекается в окрестности O(P) с внутренностью множества Te(s0).
Теперь предположим, что множество Q = Q T B(s; s0) непусто. Тогда задача сводится к эквивалентным задачам
M (s; s0) = max min x2Q
(s; x); (s0; x) M (s; s0) = min (s; x); x2Q
M (s; s0) = min (s0; x);
x2Q (6) (7) и множество точек P(s; s0), доставляющих минимум, в случае малости M (s; s0) обязано лежать на Tb (рис. 7c).
Случай бо´льшего числа вершин, лежащих по разные стороны от Y , рассматривать не надо, так как добавление новых вершин сужает множество Te(s) T Te(s0) и общую границу B(s; s0) и, значит, не уменьшает величину M (s; s0).
Сформулируем результат, подробное доказательство которого можно найти в [3]. Обозначим
M = min n min M (s); s2S1
min (s;s0)2S2
M (s; s0)o: Теорема. Имеет место равенство
Z i qi = kt a(Bi)k dt max min (t; s(t)) = M: T 2T t2T (t; s(t)) > M 8 t 2 Tb; и множества P(s); P(s; s0) лежат на Tb для всех s 2 S1 и (s; s0) 2 S2; доставляющих минимум в (8): Итак, анализ положения всех вершин s 2 C таких, что Te(s) T Y 6= ?, позволяет найти величину (9) и набор точек P = P(s) S P(s; s0), через которые проходит каждая оптимальная траектория Tb задачи (1). В силу леммы 1 для любой точки t 2 Tb найдется вершина s = st 2 C, для которой t 2 T (st). Поэтому любая точка траектории Tb удовлетворяет неравенству (t; s) > (t; st) > M 8 s 2 C: 5
Алгоритм построения наилучшей траектории для случая многогранного G Траектория, определяемая приведенной выше теоремой, имеет свободу вне множества P . Естественно желание объекта, насколько возможно, отдалить траекторию от вершин a 2 A XnY вне указанного множества. В связи с этим рассмотрим задачу (2) максимизации интегрального функционала. Ясно, что без дополнительных ограничений на класс T траекторий величина (2) не ограничена.
Как отмечалось, “коридор” заполнен связными компонентами B множеств вида T (a) T Y . В рассматриваемом случае каждая из них является многогранником. Совокупность этих компонент обозначим через N = fBg. Естественно потребовать, чтобы часть траектории T 2 T, попавшая в компоненту B T (a) T Y , располагалась по возможности дальше от вершины a, что фактически однозначно определяет траекторию на B.
Второе требование порядок посещения траекторией компонент B. Введем на N частичный порядок по величине расстояния d(t ; B), здесь d(t ; x) означает минимум длин кривых, содержащихся в Y и соединяющих точку t с x 2 B. Построим всевозможные связные строго возрастающие цепочки B = fB1; B2; : : : ; BN g; t 2 B1; t 2 BN ; d(t ; Bi) < d(t ; Bi+1); i = 1; : : : ; N 1; (10) где номер N зависит от цепочки. Будем рассматривать только такие траектории TB 2 T, которые посещают множества из цепочки по очереди, в соответствии с введенным порядком.
На каждой компоненте B = B(a) T (a) \ Y (B 2 N ) выделим “дальнюю” от вершины a часть = (bd B) = (bd B) (a) границы bd B компоненты B следующим образом.
Найдем угол с вершиной a наименьшего раствора, содержащий компоненту B(a). Две точки на сторонах этого угла, наиболее удаленные от a, разбивают bd B на две части: ближнюю к a и дальнюю от вершины a часть B = (bd B) .
Для каждой цепочки B (10) траектория TB строится из фрагментов “дальних” границ i = (bd Bi) (Bi T (a); a = a(Bi)) с весом (8) (9) (11) и при необходимости из отрезков, принадлежащих bd(a\) (см. [2, предложение 3]) с нулевым весом. Вес QB траектории TB определяется как сумма весов qi.
При введенных требованиях на класс траекторий T из T задача (2) сводится к задаче max QB
B поиска оптимального пути на направленном графе R, вершинами которого являются множества B 2 N с весом (11), а пути определяются цепочками (10).
Ниже представлена модификация алгоритма Дейкстры, которая позволяет найти маршрут при дополнительном ограничении на угол между смежными ребрами пути, тем самым обеспечить дополнительное требование гладкости пути.
Пусть построенный выше граф R состоит из множества вершин V = fuig и множества E = f(u; v)g ориентированных ребер. Рассмотрим на графе R = (V; E) множество путей (10) с дополнительным ограничением:
Az(ui 1; ui; ui+1) < max; 0 < i < m; где Az(ui 1; ui; ui+1) – угол между ребром (ui 1; ui) и ребром (ui; ui+1), max – максимальный допустимый угол поворота.
От классической задачи поиска оптимальных путей в графе сформулированная задача отличается наличием ограничения на угол поворота смежных ребер. Непосредственно алгоритм Дейкстры такое ограничение не может обеспечить. Для его учета необходимо исходный граф преобразовать таким образом, чтобы в нем остались только пути, в которых выполняется заданное ограничение. Это можно сделать переходом к так называемому реберному графу, в котором ребра исходного графа становятся вершинами, а вершины переходят в ребра, возможно, в несколько. Реберный граф позволяет получить точное решение поставленной задачи, однако практическая реализация алгоритма Дейкстры на нем предъявляет высокие требования к объему хранимой информации. Это связано с тем, что количество ребер и вершин в новом графе значительно, иногда на несколько порядков, больше, чем в исходном. Для снижения требований к объему хранимой информации был разработан модифицированный алгоритм Дейкстры, который включает в себя построение вспомогательного графа, в котором количество вершин больше количества вершин в исходном графе в заранее заданное число раз.
Рисунок 8 иллюстрирует результат работы предложенного алгоритма. Для решения задачи рассмотрим модифицированный граф G0 = (V 0; E0).
Пусть NL – параметр модифицированного графа – число слоев в этом графе. Множество вершин V 0 в рассматриваемом графе есть объединение NL слоев, начальной и конечной вершин:
V 0 = V1 [ : : : [ VNL;
Vi = V nft ; t g: Для каждого i-го слоя на единичной сфере задано основное направление ALi, определяющее конус направлений ребер, входящих в вершины этого слоя. Угловой размер конуса составляет 2 =NL. Множество ребер E0 можно представить в виде:
E0 = E1 [ : : : [ ENL; где
Ei = f(u; v) : u 2 Vj; v 2 Vi; Az(A(u; v); ALi) < =NL; Az(ALj; ALi) < max; j = 1 : : : NLg: Здесь Az(A(u; v); ALi) – угол между направлением вектора (u; v) и направлением ALi. Содержательный смысл множества Ei состоит в том, что это есть множество ребер, входящих в вершины i-го слоя, исходящих из вершин слоев, близких к i-му по основному направлению.
Рассмотрим некоторую вершину vi 2 Vi и все ребра, входящие в эту вершину: E(vi) = f(u; vi)g. Данное множество ребер будет состоять из следующих непересекающихся подмножеств: E(vi) = E(vi)1 [ : : : [ E(vi)NL;
E(vi)j = f(u; vi) : u 2 Vj; vi 2 Vi; Az(A(u; vi); ALi) < =NL; (u; vi) 2 Ejg: При увеличении числа слоев NL, вследствие выполнения условия Az(A(u; v); ALi) < =NL, количество ребер в каждом из множеств E(v)j будет уменьшаться до тех пор, пока в нем останутся ребра с единственным направлением. В результате для ребра (u; v) условие Az(ALj; ALi) < max будет эквивалентно Рис. 8: Пример построения маршрута предложенным алгоритмом условию Az(A(s; u); A(u; v)) < max, где (s; u) – любое ребро из E0, входящее в вершину u. Таким образом, каждому набору ребер из E, входящих в одну и ту же вершину из V и имеющих одинаковое направление, будет соответствовать одна вершина из V 0. Тогда результат алгоритма Дейкстры на модифицированном графе G0 = (V 0; E0) будет совпадать с результатом алгоритма Дейкстры на подграфе реберного исходному графу.
Предложенный алгоритм решает задачу об оптимальном пути, и его асимптотическая сложность есть O(V 2) [4]. Благодарности
Работа выполнена (в частности алгоритм п. 5, предложенный В.Б. Костоусовым) при частичной поддержке комплексной программы ФНИ УрО РАН (проект 15-16-1-14). Лемма 2 содержится в работе [2], выполненной за счет гранта Российского научного фонда (проект 14-11-00702). Список литературы [1] V.I. Berdyshev, V.B. Kostousov. Extremal problems and navigation models over geophysical fields.
Ekaterinburg: UB RAS, 2007 (in Russian). = В.И. Бердышев, В.Б. Костоусов. Экстремальные задачи и модели навигации по геофизическим полям. Екатеринбург: УрО РАН, 2007. [2] V.I. Berdyshev. On the problem of tracking a moving object by observers. Proc. Steklov Inst. Math. Suppl., 289(1):54–63, 2015. [3] V.I. Berdyshev. A moving object and observers in R2 with piecewise smooth shading set. Tr. Inst. Mat. Mekh. (Ekaterinburg), 21(4):95–101, 2015 (in Russian). = В.И. Бердышев. Движущийся объект и наблюдатели в R2 с кусочно-гладким затеняющим множеством. Труды Института математики и механики УрО РАН, 21(4):95–101, 2015. [4] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms. 3rd ed. MIT Press and McGraw-Hill, 2009.
Extreme problems in planning the route of the moving ob ject under observation
Vitalii I. Berdyshev1;2, Victor B. Kostousov1 1 – Krasovskii Institute of Mathematics and Mechanics (Yekaterinburg, Russia) 2 – Ural Federal University (Yekaterinburg, Russia) Keywords: planning the route, optimal route, geometrical observability, Dijkstra’s algorithm.
The article provides a brief overview of the challenges that naturally arise when planning the trajectory of the object under observation for it by the other observers and, on the other hand, for optimal placement of observers for tracking a moving object.