=Paper=
{{Paper
|id=Vol-1662/opt1
|storemode=property
|title=Экстремальные задачи планирования маршрута движущегося объекта в условиях наблюдения(Extreme problems in planning the route of the moving object under observation)
|pdfUrl=https://ceur-ws.org/Vol-1662/opt1.pdf
|volume=Vol-1662
|authors=Vitalii I. Berdyshev,Victor B. Kostousov
}}
==Экстремальные задачи планирования маршрута движущегося объекта в условиях наблюдения(Extreme problems in planning the route of the moving object under observation)==
https://ceur-ws.org/Vol-1662/opt1.pdf
Экстремальные задачи планирования маршрута
движущегося объекта в условиях наблюдения
В.И. Бердышев1,2 В.Б. Костоусов1
bvi@imm.uran.ru vkost@imm.uran.ru
1 – ИММ УрО РАН (Екатеринбург)
2 – УрФУ (Екатеринбург)
Аннотация
В статье приводится краткий обзор задач, которые естественно воз-
никают при планировании траектории движения объекта в услови-
ях наблюдения за ним наблюдателями и, с другой стороны, при
оптимальном размещении наблюдателей для сопровождения дви-
жущегося объекта.
1 Введение
При планировании маршрута движения объекта в условиях наблюдения за ним со стороны других
объектов-наблюдателей возникают экстремальные задачи построения маршрута с различными критери-
ями [1]. С другой стороны, представляют интерес задачи оптимального размещения наблюдателей для
сопровождения движущегося объекта. В работе предполагается наличие у объекта скоростного средства
поражения, что заставляет наблюдателя для обеспечения безопасности придерживаться определенной так-
тики движения. Приведена характеризация оптимальной траектории, минимизирующей максимум види-
мости объекта при движении по траектории. Для задачи оптимизации интегрального критерия рассмотрен
эффективный численный метод построения оптимального маршрута, основанный на модификации алго-
ритма Дейкстры.
2 Постановка задачи
Пусть G — ограниченное, может быть несвязное множество с кусочно-гладкой границей в X = Rn
◦
(n = 2, 3), являющееся замыканием открытого множества G, и такое, что X\G связно. Множество G
T ◦
препятствует видимости и движению. Точки x, y ∈ X видимы одна для другой, если [x, y] G= ∅. В
◦
X движутся объект t 6∈ G и наблюдатели fi 6∈G, враждебные по отношению к t. Объект движется из
окрестности V∗ = VR (t∗ ) точки t∗ в окрестность V ∗ = VR (t∗ ) точки t∗ (где VR (t) – открытый шар с
центром в t радиуса R > 0), V∗ V ∗ = ∅, (V∗ V ∗ ) G = ∅, внутри заданного “коридора” Ye , Ye G = ∅,
T S T T
являющегося окрестностью заранее рассчитанной непрерывной траектории
T0 = {t(τ ) ∈ X : 0 ≤ τ ≤ 1, t(0) = t∗ , t(1) = t∗ }.
Будем предполагать, что в окрестностях V∗ , V ∗ наблюдателей нет.
Copyright c by the paper’s authors. Copying permitted for private and academic purposes.
In: A.A. Makhnev, S.F. Pravdin (eds.): Proceedings of the 47th International Youth School-conference “Modern Problems in
Mathematics and its Applications”, Yekaterinburg, Russia, 02-Feb-2016, published at http://ceur-ws.org
32
n T ◦ o
Пусть v(t) = x ∈ X : [x, t] G= ∅ — множество видимых из t точек пространства, s(t) =
S
= X\ v(t) G — тень множества G (при освещении из точки t), s(t) — ее замыкание, ρ(t, M ) — рас-
стояние от точки t до множества M .
Объект имеет возможность поразить наблюдателя посредством миниобъекта, способного двигаться в
◦
X\ G прямолинейно с большой скоростью. Таким образом, свобода движения наблюдателя f ограничена:
он должен находиться вблизи множества s(t). Рисунок 1 иллюстрирует описываемую постановку задачи.
Рис. 1: Задача о наиболее скрытом маршруте объекта t при наличии враждебных наблюдателей fi (пока-
заны черными точками), которые вынуждены находиться недалеко от теневого множества s(t). Кружками
показаны угловые точки множества G, которые играют важную роль в решении задачи
Задача объекта t состоит в выборе траектории Tb из класса T непрерывных траекторий
T = {t(τ ) : 0 ≤ τ ≤ 1, t(0) ∈ V∗ , t(1) ∈ V ∗ } ⊂ Ye ,
для которой
max min ρ(t, s(t)) = min ρ(t, s(t)). (1)
T ∈T t∈T t∈Tb
Наряду с (1) представляет интерес задача максимизации интегрального функционала:
Z
max∗ ρ(t(τ ), s(t(τ ))) dτ (2)
T ∈T
на некотором естественном подклассе T∗ траекторий из класса T.
Далее для простоты изложения, как правило, будем предполагать X = R2 , оговаривая особо факты,
справедливые и для X = R3 .
3 Теневые точки и области влияния
Точку x ∈ G назовем теневой для t, если
\ \
x ∈ v(t) s(t), (t, x) s(t) = ∅.
Далее предполагается, что граница bd G множества G является кусочно-гладкой: она может включать в
себя конечное число прямолинейных отрезков и конечное число участков строгой выпуклости (фактически,
конечное число точек перегиба), что важно для построения алгоритмов поиска оптимальной траектории.
Будем рассматривать точки x локальной выпуклости границы.
T Для каждой из них существует окрест-
ность O(x) и прямая L, x ∈ L, такие, что множество G O(x) лежит по одну сторону относительно L.
Точка локальной выпуклости называется угловой, если величина α угла между односторонними касатель-
ными прямыми в этой точке удовлетворяет неравенству 0 < α < π. Множество угловых точек границы G
обозначим через A (рис. 2).
33
Максимальный по включению связный гладкий участок выпуклости границы множества G (участок,
состоящий из гладких точек локальной выпуклости), будем обозначать через C (см. рис. 2). Итак, C —
гладкая выпуклая связная кривая без концевых точек. Совокупность таких участков границы обозначим
через C.
Рис. 2: Граница множества G: угловые точки a, a0 , a00 и выпуклый участок C
Теневыми точками могут быть только угловые точки и точки из C ∈ C. Для иных точек x ∈ bd G любая
◦
прямая, содержащая x, содержит точки из G в любой окрестности O(x). Пусть t 6∈ G. Рассматривая мно-
жество точек на границе bdG, видимых (освещенных) из точки t, с учетом ограниченности G и связности
дополнения X\G, можно установить (см. [2, теорема 1 для многогранного G]), что справедлива
Лемма 1 Для любой точки t 6∈ G множество теневых точек непусто.
На примере, показанном на рисунке 3, для позиции t имеются две теневые точки.
Рис. 3: Теневые точки
В дальнейшем будем обозначать
PM (x) = {y ∈ M : kx − yk = ρ(x, M )}
— множество ближайших к x точек из множества M ⊂ X.
Для точки s ∈ bd G обозначим
Te(s) = t 6∈ G : t ∈ v(s), s ∈ s(t) , T (s) = {t 6∈ G : s ∈ Ps(t) (t)}
— замыкание множества точек t 6∈ G, для которых s является ближайшей теневой точкой.
Если a ∈ A — угловая точка, то Te(a) является дополнением до X\G объединения угла при a и верти-
кального к нему угла (рис. 4i). Если c ∈ C ∈ C, то множество Te(c) непусто и лежит на касательной к дуге
C прямой в точке c (рис. 4ii).
Для гладкого выпуклого участка C ∈ C определим множества (рис. 4iii)
[ [
Te(C) = Te(c), T (C) = T (c).
c∈C c∈C
34
(i) (ii) (iii)
Рис. 4: Построение областей Te(a) и Te(C)
S
Определим множество S = A C, его элементы s ∈ S будем называть вершинами. Множество S предпо-
лагается конечным. Для вершин s и точек x ∈ T (s) введем “расстояние”
kx − sk, если s = a ∈ A, x ∈ Te(a),
ρ(x, s) = kx − ck, если s = C ∈ C, c ∈ C, x ∈ Te(c), (3)
+∞, если t ∈/ Te(s).
◦
Принадлежность объекта множеству T (s) означает его близость к вершине s, где может присутствовать
наблюдатель. По этой причине T (s) можно назвать “областью влияния” вершины s. Предпочтительным
для объекта является месторасположение на общей границе смежных множеств T (s) и T (s0 ). Важно, что
по определению этих множеств точки общей границы B(s, s ) = T (s) T (s ) равноудалены от s и s0 по
0 0
T
расстоянию (3). При поиске этих границ учитывается линейчатая структура множеств Te(s) (коническая
при s ∈ A, а при s ∈ C — совокупность интервалов на касательных прямых к дуге C) и используется
решение следующих задач о построении границ между
1) T (a) и T (a0 ) (a, a0 ∈ A),
2) T (a) и T (C) (a ∈ A, C ∈ C),
3) T (C) и T (C 0 ) (C, C 0 ∈ C).
1) В случае многоугольного G множество T (a) является многоугольником, а в области, где Te(a) Te(a0 ) 6=
T
6= ∅, множества T (a), T (a0 ) разграничивает прямая L, ортогональная отрезку [a, a0 ] и содержащая точку
(a + a0 )/2. Так что ka − zk = kz − a0 k (z ∈ L) (рис. 5i).
T
2) Точки z границы между T (a) и T (C), попавшие в область Te(a) Te(C) определяются так, что ka − zk =
= kz − ck, где c ∈ C — точка касания дуги C с прямой, содержащей точку z (рис. 5ii).
3) Точка z границы между T (C), T (C 0 ), попавшая в область Te(C) Te(C 0 ), есть пересечение прямых,
T
касающихся дуг C, C 0 в точках c ∈ C, c0 ∈ C 0 таких, что kc − zk = kz − c0 k.
Граница раздела B(s, s0 ) указанных множеств может иметь сложную форму даже для множества про-
стого вида (см. рис. 5ii).
(i) (ii)
Рис. 5: Примеры границ, разделяющих области влияния
В работе [2] доказано следующее утверждение.
Лемма 2 Пусть X = Rn и G–многогранник, тогда
35
— множество T (a) является многогранником для любой a ∈ A,
◦ T ◦
— T (a) T (a0 ) = ∅ для любых a, a0 ∈ A, a 6= a0 ,
[ ◦
— если X = R2 , то T (a) = X\ G.
a∈A
Замечание. Если X = R2 , то утверждения леммы 2 можно распространить на случай, когда G не
обязательно многогранник, следующим образом:
◦ T ◦
— T (s) T (s0 ) = ∅ для любых s, s0 ∈ S, s 6= s0 ,
[ ◦
— T (s) = X\ G.
s∈A
Отметим, что в условиях леммы 2 множество
◦ [ ◦
T0 = (X\ G)\ T (a) (4)
a∈A
также является многогранником. Легко показать, что в случае X = Rn (n > 2) множество (4) может быть
непустым.
На рисунке 6 показан пример построения областей влияния угловых точек для случая, когда G – мно-
гогранник. Для того чтобы не загромождать рисунок, заштрихованы области влияния только для двух
точек “1” и “2”.
Рис. 6: Пример построения областей влияния угловых точек для случая, когда G – многогранник
4 Характеризация наилучшей траектории
Решая задачу (1), объект t должен проследовать из V∗ до V ∗ , максимизируя внутри коридора Y =
Y \(V∗ V ∗ ) наименьшее расстояние до вершин s ∈ S, поскольку в них, возможно, присутствуют наблю-
e S
датели. Далее будет удобно на границе коридора Y выделить левую границу Yl и правую Yr относительно
движения от t∗ к t∗ по оптимальной траектории, содержащейся в Y . Указанные границы берут свое начало
на границе шара V∗ и заканчиваются на границе шара V ∗ . Необходимо указать все точки из Y , которые
должны лежать на оптимальной для задачи (1) траектории. По замечанию к лемме 2 коридор заполнен
множествами T (s).
Пусть s ∈ S,
\ ◦ \ \
Te(s) Y 6= ∅, Te(s) Yl 6= ∅, Te(s) Yr 6= ∅ (5)
36
и Ys — более далекая по расстоянию ρ(s, x) от s граница Yl или Yr . Обозначим через S 1 множество вершин,
удовлетворяющих условию (5). В связи с вершиной s рассмотрим задачу
M (s) = ρ(s, Ys ) = min ρ(s, y), (6)
y∈Ys
и пусть P = PYs (s) — множество ближайших к s по расстоянию ρ точек из Ys . Любая траектория T ∈ T
пересекает любой отрезок, соединяющий s с точками из P. В случае малости величины ρ(s, Ys ) траектория
Tb должна содержать множество P (рис. 7a).
Теперь возьмем пару вершин s, s0 ∈ S с противоположных сторон коридора Y (расстояния
ρ(s, Y ), ρ(s0 , Y ) достигаются на разных сторонах Yl , Yr границы Y ), для которых Q = Te(s) Te(s0 ) 6= ∅ и
T
T ◦
Q Y 6= ∅. Множество таких пар вершин обозначим через S 2 . Тогда любая траектория T ∈ T пересекает
любую двузвенную ломаную, соединяющую точку x из Q с s и s0 (с точкой a, если s = a ∈ A, а если
s ∈ C ∈ C, то с точкой c ∈ C, для которой x ∈ Te(c)).
(a) (b) (c)
Рис. 7: К доказательству теоремы: три случая расположения теневых точек относительно коридора Y
В связи с парой таких вершин возникает задача
M (s, s0 ) = max min ρ(s, x), ρ(s0 , x) .
(7)
x∈Q
Предположим, что общая граница
B(s, s0 ) = z : ρ(s, z) = ρ(s0 , z)
множеств T (s), T (s0 ) не пересекается с Q, и пусть вершины s и Q лежат по одну сторону от B(s, s0 ) (рис. 7b).
Очевидно, что максимум (7) доставляет точка P = P(s, s0 ) ∈ 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 ∈ bd Te(s), поэтому вершина s не является теневой для точки P. Оптимальная траек-
тория Tb лишь касается границы bd Te(s) в точке P и в окрестности O(P) этой точки не пересекается с
внутренностью множества Te(s). Но Tb пересекается T в окрестности O(P) с внутренностью множества Te(s0 ).
∗ 0
Теперь предположим, что множество Q = Q B(s, s ) непусто. Тогда задача
M (s, s0 ) = max∗ min ρ(s, x), ρ(s0 , x)
x∈Q
сводится к эквивалентным задачам
M (s, s0 ) = min∗ ρ(s, x), M (s, s0 ) = min∗ ρ(s0 , x),
x∈Q x∈Q
37
и множество точек P(s, s0 ), доставляющих минимум, в случае малости M (s, s0 ) обязано лежать на Tb
(рис. 7c).
Случай бо́льшего числа вершин, лежащих по T разные стороны от Y , рассматривать не надо, так как
добавление новых вершин сужает множество Te(s) Te(s0 ) и общую границу B(s, s0 ) и, значит, не уменьшает
величину M (s, s0 ).
Сформулируем результат, подробное доказательство которого можно найти в [3].
Обозначим n o
0
M = min min1 M (s), min0 2
M (s, s ) . (8)
s∈S (s,s )∈S
Теорема. Имеет место равенство
max min ρ(t, s(t)) = M. (9)
T ∈T t∈T
Траектория Tb ∈ T является оптимальной в задаче (1) тогда и только тогда, когда
ρ(t, s(t)) > M ∀ t ∈ Tb ,
и множества P(s), P(s, s0 ) лежат на Tb для всех s ∈ S 1 и (s, s0 ) ∈ S 2 , доставляющих минимум в (8).
T ◦
Итак, анализ положения всех вершин s ∈ C таких, что Te(s) Y 6= ∅, позволяет найти величину (9) и
набор точек P ∗ = P(s) P(s, s0 ), через которые проходит каждая оптимальная траектория Tb задачи (1).
S
В силу леммы 1 для любой точки t ∈ Tb найдется вершина s = st ∈ C, для которой t ∈ T (st ). Поэтому
любая точка траектории Tb удовлетворяет неравенству
ρ(t, s) > ρ(t, st ) > M ∀ s ∈ C.
5 Алгоритм построения наилучшей траектории для случая многогранного G
Траектория, определяемая приведенной выше теоремой, имеет свободу вне множества P ∗ . Естественно
желание объекта, насколько возможно, отдалить траекторию от вершин a ∈ A ⊂ X\Y вне указанного
множества. В связи с этим рассмотрим задачу (2) максимизации интегрального функционала. Ясно, что
без дополнительных ограничений на класс T траекторий величина (2) не ограничена. T
Как отмечалось, “коридор” заполнен связными компонентами B множеств вида T (a) Y . В рассматри-
ваемом случае каждая из них является многогранником. Совокупность этих компонент обозначим через T
N = {B}. Естественно потребовать, чтобы часть траектории T ∈ T, попавшая в компоненту B ⊂ T (a) Y ,
располагалась по возможности дальше от вершины a, что фактически однозначно определяет траекторию
на B.
Второе требование — порядок посещения траекторией компонент B. Введем на N частичный поря-
док по величине расстояния d(t∗ , B), здесь d(t∗ , x) означает минимум длин кривых, содержащихся в Y и
соединяющих точку t∗ с x ∈ B. Построим всевозможные связные строго возрастающие цепочки
B = {B1 , B2 , . . . , BN }, t ∗ ∈ B1 , t ∗ ∈ BN , d(t∗ , Bi ) < d(t∗ , Bi+1 ), i = 1, . . . , N − 1, (10)
где номер N зависит от цепочки. Будем рассматривать только такие траектории TB ∈ T, которые посещают
множества из цепочки по очереди, в соответствии с введенным порядком.
На каждой компоненте B = B(a) ⊂ T (a) ∩ Y (B ∈ 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 )) с весом
Z
qi = kt − a(Bi )k dt (11)
γi
38
и при необходимости из отрезков, принадлежащих bd(a∠) (см. [2, предложение 3]) с нулевым весом. Вес
QB траектории TB определяется как сумма весов qi .
При введенных требованиях на класс траекторий T из T задача (2) сводится к задаче
max QB
B
поиска оптимального пути на направленном графе R, вершинами которого являются множества B ∈ N с
весом (11), а пути определяются цепочками (10).
Ниже представлена модификация алгоритма Дейкстры, которая позволяет найти маршрут при допол-
нительном ограничении на угол между смежными ребрами пути, тем самым обеспечить дополнительное
требование гладкости пути.
Пусть построенный выше граф R состоит из множества вершин V = {ui } и множества E = {(u, v)}
ориентированных ребер. Рассмотрим на графе 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 , E 0 ).
Пусть NL – параметр модифицированного графа – число слоев в этом графе. Множество вершин V 0 в
рассматриваемом графе есть объединение NL слоев, начальной и конечной вершин:
V 0 = V1 ∪ . . . ∪ VNL , Vi = V \{t∗ , t∗ }.
Для каждого i-го слоя на единичной сфере задано основное направление ALi , определяющее конус на-
правлений ребер, входящих в вершины этого слоя. Угловой размер конуса составляет 2π/NL . Множество
ребер E 0 можно представить в виде:
E 0 = E1 ∪ . . . ∪ ENL ,
где
Ei = {(u, v) : u ∈ Vj ; v ∈ Vi ; Az(A(u, v), ALi ) < π/NL ; Az(ALj , ALi ) < ∆φmax ; j = 1 . . . NL }.
Здесь Az(A(u, v), ALi ) – угол между направлением вектора (u, v) и направлением ALi .
Содержательный смысл множества Ei состоит в том, что это есть множество ребер, входящих в вершины
i-го слоя, исходящих из вершин слоев, близких к i-му по основному направлению.
Рассмотрим некоторую вершину vi ∈ Vi и все ребра, входящие в эту вершину: E(vi ) = {(u, vi )}. Данное
множество ребер будет состоять из следующих непересекающихся подмножеств:
E(vi ) = E(vi )1 ∪ . . . ∪ E(vi )NL , E(vi )j = {(u, vi ) : u ∈ Vj ; vi ∈ Vi ; Az(A(u, vi ), ALi ) < π/NL ; (u, vi ) ∈ Ej }.
При увеличении числа слоев NL , вследствие выполнения условия Az(A(u, v), ALi ) < π/NL , количество
ребер в каждом из множеств E(v)j будет уменьшаться до тех пор, пока в нем останутся ребра с един-
ственным направлением. В результате для ребра (u, v) условие Az(ALj , ALi ) < ∆φmax будет эквивалентно
39
Рис. 8: Пример построения маршрута предложенным алгоритмом
условию Az(A(s, u), A(u, v)) < ∆φmax , где (s, u) – любое ребро из E 0 , входящее в вершину u. Таким образом,
каждому набору ребер из E, входящих в одну и ту же вершину из V и имеющих одинаковое направление,
будет соответствовать одна вершина из V 0 . Тогда результат алгоритма Дейкстры на модифицированном
графе G0 = (V 0 , E 0 ) будет совпадать с результатом алгоритма Дейкстры на подграфе реберного исходному
графу.
Предложенный алгоритм решает задачу об оптимальном пути, и его асимптотическая сложность есть
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.
40
Extreme problems in planning the route of the moving object 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.
41