Траектория объекта, наиболее удаленная от наблюдателей

Abstract

В статье рассматривается задача построения траектории движущегося объекта, которая наиболее удалена от группы наблюдателей. Задача рассматривается на плоскости. Особенность постановки заключается в предположении о том, что объект имеет ненулевую площадь и при движении должен соблюдать геометрические ограничения. Подробно описывается алгоритм построения оптимальной траектории.

-

[ Vh(t) \ B = ?;

Y = [ Vr(t); t2T0 замыкание множества A. где r = r(t) = inf kt bk. Из условий построения траектории T0 следует, что r(t) > h 8t 2 T0. Центральная b2B точка t объекта движется внутри коридора

Yh = [ Vr h(t): Предполагается, что Vr(t ) T Vr(t ) = ?.

Множество непрерывных траекторий

T = ft( ) : 0 6 6 1; t(0) = t ; t( 1 ) = t g

Yh обозначим через T.

Пусть @Y граница коридора Y и = (@Y )n(Vr(t ) S Vr(t )). В силу условий задачи множество разбивается на две непересекающиеся части: левую l и правую r по отношению к направлению движения по траектории T0 от точки t к точке t .

Аналогично, пусть @Yh – граница коридора Yh и E = (@Yh)n(Vr h(t ) S Vr h(t )). Множество E разбивается на две непересекающиеся части: левую часть El и правую Er по отношению к объекту, движущемуся от t к t по T0.

Предполагается, что задан конечный набор наблюдателей S = fSg, S 2= Y (Y обозначает внутренность множества Y ). Ради простоты будем считать, что S . Каждый наблюдатель S имеет фиксированный конус обзора K(S) объединение с S выпуклого открытого конуса при вершине S. Пересечение K(S) с Y может состоять из нескольких связных компонент. В дальнейшем через KY (S) обозначается компонента, содержащая S. Для любого S конус K(S) таков, что каждая траектория T 2 T пересекается с KY (S). Ради простоты будем считать, что Vh(t ) T KY (S) = ?, Vh(t ) T KY (S) = ? для любого S. Множество наблюдателей, принадлежащих l или r, будем обозначать через Sl, Sr, соответственно.

Определим ¾расстояние¿ h(t; S) от точки t 2 Yh до наблюдателя S (с учётом конуса наблюдения) следующим образом: Определим ¾расстояние¿ h(S; T ) от траектории T 2 T до наблюдателя S:

h(t; S) = minf (x; S) : x 2 Vh(t)g; где (x; S) = (kx Sk при x 2 KY (S),

+1 при x 2= KY (S).

h(S; T ) d=ef minf h(t; S) : t 2 T g: Задача объекта th состоит в выборе траектории Tb из класса T непрерывных траекторий для которой

T = ft( ) : 0 6 6 1; t(0) = t ; t( 1 ) = t g

Yh; M = M(S) d=ef max minf h(S; T ) : S 2 Sg = minf h(S; Tb) : S 2 Sg:

T 2T Рисунок 1 иллюстрирует описываемую постановку задачи.

Как правило, задача ( 1 ) имеет неединственное решение. В этом случае представляет интерес задача поиска среди гладких траекторий T решений задачи ( 1 ) траектории с минимальной длиной: где t0( ) – производная функции t( ).

min T 2T Рис. 1: Задача о наиболее удаленном от наблюдателей траектории объекта th. Наблюдатели S (показаны черными точками) 3

Характеризация наилучшей траектории Введём следующие обозначения для множеств (рис. 2): Рис. 2: К определению множества G G (S) d=ef ft : h(t; S) < g, где > 0: Рассмотрим частные случаи задачи ( 1 ).

I. Введём величины Определим множества:

A(S) d=ef (minf : G (S) T El 6= ?g; если S 2 Sr; minf : G (S) T Er 6= ?g; если S 2 Sl;

M = min A(S):

S2S Q (S) d=ef (G (S) T El; если S 2 Sr;

G (S) T Er; если S 2 Sl;

S2S Так же как для случая точечного объекта, рассмотренного в [1], для случая объекта th справедливо следующее утверждение (рис. 3). Рис. 3: Пример задачи о наиболее удалённой от наблюдателей траектории в условиях предложения 1 Предложение 1 Пусть набор наблюдателей S таков, что KY (Sl) T KY (Sr) T Yh = ? для любых Sl 2 Sl и Sr 2 Sr. Оптимальная траектория Tb 2 T характеризуется свойствами: Q(S) Tb,

h(S; Tb) > M для всех S 2 S.

Любая траектория T 2 T, удовлетворяющая условию 8S h(S; T ) > M , является оптимальной. II. Пусть S = fSl; Srg – пара наблюдателей такая, что KY (Sl) T KY (Sr) T Yh 6= ? (рис. 4). Рассмотрим множество точек, удалённых от двух наблюдателей не более, чем на величину :

Q (Sl; Sr) = G (Sl) \ G (Sr) \ Yh: Введём величину:

A(Sl; Sr) d=ef (+1; minf : Q (Sl; Sr) 6= ?g; иначе.

если 8 : Q (Sl; Sr) = ?, Можно показать, что в этом случае справедливо следующее утверждение, характеризующее оптимальную траекторию. Предложение 2 В случае II имеет место равенство

M(S) = minfA(Sl; Sr); A(Sl); A(Sr)g: Искомая оптимальная траектория в задаче ( 1 ) составлена из части границы множества G (S) :

= M(S), и дополнена частью границ El или Er соответСтрогая характеризация оптимальной траектории задачи ( 1 ) в случае произвольного расположения наблюдателей будет рассмотрена в дальнейших исследованиях. Однако, в следующем разделе представлен численный алгоритм, приближенно решающий задачи ( 1 ), ( 2 ), когда граница задана в виде простой ломаной линии без самопересечений. 4

Алгоритм построения наилучшей траектории Для решения задачи ( 2 ) воспользуемся алгоритмом Дейкстры [2] построения кратчайшего пути в графе. Для этого следует определить неориентированный граф (т.е. множества вершин и рёбер), в котором данный алгоритм будет искать кратчайший путь.

В качестве множества вершин примем объединение множества вершин описываемой ниже двумерной прямоугольной сетки с постоянным шагом и пары точек начального и конечного положения объекта. Пусть задан шаг сетки > 0, h.

Пусть граница задана в виде простой ломаной линии без самопересечений, fpi( ) = (xi( ); yi( )) : i = 0; :::; N 1g последовательность концевых точек отрезков этой линии.

Тогда размеры сетки вычисляются следующим образом:

Nx = 1 + Ny = 1 + maxfxi( )g maxfyi( )g minfxi( )g ; minfyi( )g : Множество вершин графа определим так:

C = (Cx

Cy) [ft ; t g; Cx = fxk : xk = k Cy = fyk : yk = k + minfxi( )g; k = 0; :::; Nx + minfyi( )g; k = 0; :::; Ny 1g; 1g: В качестве множества рёбер U возьмём все пары вершин fci; cjg из множества C, удовлетворяющие условию отрезок fci; cjg не должен пересекать ¾запретную¿ область, которую образуют h-окрестность границы и множества GM (S); S 2 S: В качестве веса ребра возьмём его длину: w = jjci Величина M вычисляется так: cjjj.

M = minfA(Sl; Sr); A(Sl); A(Sr) : Sl; Sr 2 Sg: Для определения того факта, что отрезок ребра не пересекает ¾запретную¿ область, строится множество ¾запретных¿ вершин Cb Cx Cy и применяется алгоритм Брезенхэма для растеризации отрезка [3].

Пусть Bresenham(fci; cjg) подмножество вершин на сетке Cx Cy, отмечаемых при растеризации отрезка fci; cjg алгоритмом Брезенхэма (рис. 5).

Тогда множество рёбер графа определим так:

U = ffci; cj; wg : ci; cj 2 C; ci 6= cj;

Bresenham(fci; cjg) \ Cb = ?; w = jjci

cjjjg: Рис. 5: Пример того, как с помощью алгоритма Брезенхэма определяется факт пересечения ребра fci; cjg с множеством ¾запретных¿ вершин Cb Далее построим множество ¾запретных¿ вершин Cb. Обозначим Li( ) множество точек, принадлежащих отрезку ломаной линии :

Li( ) =

ft : t = pi 1( ) k + pi( ) (1 (ft : t = pN 1( ) k + p0( ) (1 k); k 2 [0; 1]g; если i = 0,

иначе. k); k 2 [0; 1]g; Пусть r(t; X) минимальное евклидово расстояние от точки t 2 R2 до точек множества X R2: r(t; X) = xi2nXf jjt xjj: Обозначим Cb(Li( )) множество точек сетки, лежащих в окрестности радиуса h Li( ): " отрезка ломаной

Cb(Li( )) = ft : t 2 Cx Cy; r(t; Li( )) < h "g; ( 3 ) где величина " 2 ( ; 2 ) должна обеспечить прохождение траектории между ¾запретными¿ областями (рис. 6).

Обозначим H (S) множество точек, принадлежащих конусу наблюдения K(S) наблюдателя S и лежащих на расстоянии меньше от вершины конуса:

H (S) = ft : t 2 K(S); r(t; S) < g: Обозначим через Cb(S) множество точек сетки, лежащих в окрестности радиуса h " границы множества HM (S):

Cb(S) = ft : t 2 Cx Cy; r(t; @HM (S)) < h "g: Множество ¾запретных¿ вершин определим как объединение введёных выше множеств (см. рис. 6): (4) Cb = [ Cb(Li( )) [ Cb(S):

i S2S Предложенный алгоритм решает задачу об оптимальном пути, и его асимптотическая сложность есть O(jCj2) [2]. На рис. 7 представлен пример построения предложенным алгоритмом оптимальной траектории в задаче ( 2 ) для случая большого количества наблюдателей. Благодарности

Работа выполнена при частичной поддержке комплексной программы ФНИ УрО РАН (проект 15-16-114). Рис. 6: Пример множества ¾запретных¿ вершин Cb, показанных чёрным цветом. Можно видеть полученный в результате выбора " (см. ( 3 ), (4)) зазор между множествами Cb(S), который обеспечивает возможность решения задачи

Рис. 7: Пример построения маршрута предложенным алгоритмом Список литературы The farthest from observers tra jectory Alexander A. Popov, Victor B. Kostousov, Vitalii I. Berdyshev Krasovskii Institute of Mathematics and Mechanics (Yekaterinburg, Russia) Keywords: planning the route, optimal route, geometrical observability, Dijkstra’s algorithm.

The article considers the problem of constructing a moving object trajectory which is the farthest from the group of observers. The problem is considered on the plane. The peculiarity of the problem statement lies in the assumption that the area of object not equal to zero and, when moving, it must comply with geometric constraints. The algorithm for optimal trajectory constructing is described.

References

[1] V.I. Berdyshev . A moving object in R2 and a group of observers . Tr. Inst. Mat. Mekh. (Ekaterinburg) , 22 ( 4 ): 87 - 93 , 2016 (in Russian). = В.И. Бердышев . Движущийся в R2 объект и группа наблюдателей . Труды Института математики и механики УрО РАН , 22 ( 4 ): 87 - 93 , 2016 .

[2] T.H. Cormen , C.E. Leiserson , R.L. Rivest , C. Stein . Introduction to Algorithms. 3rd ed. MIT Press and McGraw-Hill , 2009 .

[3] D.F. Rogers . Procedural Elements for Computer Graphics . McGraw-Hill , 1985 .