Пусть объект t движется внутри заданного коридора Y при наличии группы S враждебных наблюдателей S 2= Y , каждый из которых имеет фиксированный конус обзора K(S). Решается задача поиска наиболее удаленной от S траектории объекта при условии, что кратность покрытия Y конусами K(S) не превосходит двух. Пусть Y R3 “коридор”, являющийся замкнутой окрестностью гладкой траектории, соединяющей фиксированные точки t 6= t : при этом граница @Y гомеоморфна сфере. В коридоре Y движется объект t. Совокупность траекторий вида (1), содержащихся в Y , обозначим через T. Множество будем называть секущим, если с ним пересекается каждая траектория из T. Имеется набор S = fSg неподвижных недружественных наблюдателей S 2= Y . Каждый из них снабжен фиксированным выпуклым открытым конусом наблюдения K(S) с вершиной S, который является секущим множеством. Секущую связную компоненту пересечения K(S)\Y , ближайшую к S, обозначим через KY (S). Определим расстояние от S до точки t 2 Y следующим образом: и введем уклонение траектории T 2 T от S Весовой коэффициент d = d(S) зависит от возможностей наблюдателя и далее полагается равным единице. Задача объекта - поиск траектории T 2 T, доставляющей максимум Множество таких траекторий обозначим через T . Сторона, обеспечивающая наблюдение, размещает наблюдателей так, чтобы величина (3) оказалась по возможности малой. Задача (3) для пространства R2 рассматривалась в [1] (см. также [2]). В данной работе предполагается, что кратность покрытия области Y совокупностью множеств KY (S) не более двух.
(
T0 = ft( ) : 0 6
6 1; t(0) = t ; t(
M = M(S) d=ef maxfM(S; T ) : T 2 Tg:
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 International Youth School-conference ¾SoProMat-2017¿, Yekaterinburg, Russia, 06-Feb-2017, published at http://ceur-ws.org
Случай одиночного наблюдателя Пусть в S единственный наблюдатель S, тогда
M = max minf (S; t) : t 2 T g:
T 2T Поведение траектории T 2 T в зоне обзора наблюдателя S удобно отслеживать по точкам пересечения T с плоскостями H некоторого семейства H = H(S) = fHg секущих плоскостей. В качестве H в данном случае можно взять, например, семейство плоскостей H, содержащих S, точку t = t( ) 2 T0 и нормаль в точке t = t( ) к поверхности, образованной лучами fS + (t( 0) S) : > 0g, для точек на траектории T0 из окрестности точки t. Обозначим
M (S) = min maxf (S; y) : y 2 H \ KY (S)g;
H2H H = H (S) множество плоскостей, реализующих минимум в (5), PS;H множество точек из H \KY (S), доставляющих максимум в (5), и PS = fPS;H : H 2 H g. Пусть отображение H ! PS;H непрерывно по Хаусдорфу. Имеет место
PS;H
8 H 2 H ; (t; S) > M (S) 8 t 2 T \ KY (S); является оптимальной. 3
Поиск оптимальной траектории при наличии двух наблюдателей Пусть S пара наблюдателей. Для заданного S определим “левую” L(S) и “правую” R(S) части границы @KY (S): движущаяся от t к t точка t 2 Y сперва встречается с L(S) и затем с R(S) при выходе из KY (S). Границы L(S); R(S) являются секущими. Для пары S = fS1; S2g обозначим
K = KY (S1) \ KY (S2);
Kb (S) = Y \ conv (S [ K); где conv выпуклая оболочка множества, и определим “углы”: \L = \L(S1; S2) множество точек из Y , лежащих слева от R(Si) (i = 1; 2); \R = \R(S1; S2) множество точек из Y , лежащих справа от L(Si) (i = 1; 2).
Пусть K 6= ?. Пару S = fS1; S2g назовем четной, если оба множества Kbi = Kb (Si) (i = 1; 2) лежат в одном из углов \L или \R, и нечетной, если эти множества лежат в разных углах.
3.1. Рассмотрим случай четной пары S = fS1; S2g. Пусть Kbi \L(S) (i = 1; 2), L(S1) \ L(S2) 6= ?. Конические поверхности Q1 = L(S2) \ KY (S1); Q2 = L(S1) \ KY (S2) являются выпуклыми. Из точки S1 видна Q1, но не видна Q2. Из точки S2 видна Q2, но не видна Q1. Дуга = (S1; S2) = Q1 \ Q2 не видна из точек S1 и S2. Пересечение 1 = Q1 \ @Y состоит из соединенных посредством двух дуг 01; 010, которые видны из S1, но не видны из S2. Аналогично определим пару дуг 2 = 02 [ 020. Предполагая, что (рис. 1) (S1; 1) > (S2; 2); (6) траектории T от точки t до t и конечный участок от KY (S2) до t траектории принадлежат дополнению Y n(K(S1) [ K(S2)) и поэтому не видны из S1; S2. Для построенной траектории T имеем
M(S; T ) = minf (S1; (S1; S2)); M (S2)g: Существует > 0 такое, что при условии (Si; K(Sj)) > ; (i; j 2 f1; 2g; i 6= j) траектория T является оптимальной. В случае равенства в соотношении (6) оптимальной, в зависимости от величины M (S1), может оказаться траектория, построенная с использованием дуг 02; 020. Справедлива Теорема 2. Если S
четная пара, то M(S) = max minf (S1; (S1; S2)); M (S2)g; minfp(S2; (S2; S1)); M (S1)g : (7) Для численного решения задачи важно отметить, что представленная здесь траектория T строится из фрагментов дуг L(S) \ @Y; R(S) \ @Y и траектории T (S) (см. теорему 1).
3.2. Пусть пара нечетная, Kb1(S1) \L; Kb2(S2) \R. Тогда PS1 \R; PS2 \L, и если, в простейшем случае, траектории T (Si) (i = 1; 2), реализующие максимум в (4), удовлетворяют условию T (Si) \ K(Si) \ K = ?, то
M(S) = minfM (Si) : i = 1; 2g: (8) 4
О расположении наблюдателей В случае нечетной пары объект имеет возможность удаляться от наблюдателей к противоположной стенке коридора Y . Особенно просто в этом убедиться, сравнивая соотношения (7) и (8). Поэтому сторона, обеспечивающая наблюдение, предпочитает использовать четные пары наблюдателей. При наличии большого числа наблюдателей целесообразно располагать их вокруг коридора Y , формируя четные пары. Пары, для которых ([S1; S2] \ Y ) K, не рассматриваются.
Набор S наблюдателей группируют в два блока Si (i = 1; : : : ; n); Sj (j = 1; : : : ; m) таких, что Ki =
Ki \ Ki0 = ? (i 6= i0); Kj \ Kj0 = ? (j 6= j0); Ki упорядочены (слева направо) по i; Kj упорядочены по j; 8 i 9 j : Ki \ Kj 6= ?; 8 j 9 i 9 j : Ki \ Kj 6= ?; множество [i;j (Ki [ Kj) связно; если Ki \ Kj 6= ?; i 6= j; то fSi; Sjg 9 > > > > > > > = (9) 4.1
Жадный алгоритм построения траектории Рассмотрим произвольную пару Si; Sj, для которой Ki \ Kj 6= ?. Для нее в соответствии с п. 3.1 (переобозначим в нем S1 на Sj, S2 на Si) определены поверхности Qi = L(Sj) \ Ki, Qj = L(Si) \ Kj, дуга ji = Qi \ Qj, невидимая из точек Si; Sj, и две пары дуг Дуги каждой пары соединены дугой ji. Из первой пары выделим дугу (Si; Sj), на которой реализуется максимум
m(Si; Sj) d=ef maxf (Si; ( i)0); (Si; ( i)00)g = (Si; (Si; Sj)): Из второй пары выделим дугу (Sj; Si), доставляющую максимум
m(Sj; Si) d=ef maxf (Sj; 0j); (Sj; 0j0)g = (Sj; (Sj; Si)): Пусть множества Kb (S1); Kb (S1) принадлежат углу \L(S1; S1). Набор S построен так, что если для пары Si; Sj выполнено условие KY (Si) \ KY (Sj) 6= ?, то оба множества Kb (Si); Kb (Sj) принадлежат углу \L(Si; Sj). Построим участок траектории T , соединяющий первую пару K(S1); K(S1) с последней парой. Допустим, m(S1; S1) > m(S1; S1). Включим в T дугу (S1; S1) и ее продолжение в сторону от S1 по дуге L(S1) \ @Y до первой встречи с конусом K(Si1), для которого выполняется неравенство m(Si1; S1) < m(S1; Si1). Пусть t1 начальная точка построенного участка траектории, t02 конечная точка этого участка, t1 2 L(S1) \ L(S1), t02 2 L(Si1) \ L(S1). Пересечение L(Si1) \ KY (S1) состоит из двух дуг, и одна из них (S1; Si1). Если t02 2 (S1; Si1), то положим t2 = t02. Если дуга (S1; Si1) лежит на противоположной от t02 стороне коридора, то удлиним построенный участок траектории, присоединив к нему дугу (S1; Si1) (см. п. 3.1). Один конец дуги точка t02. Другой ее конец обозначим через t2. На этом завершается построение участка T (t1; t2) траектории T от t1 до t2. Далее, рассуждая аналогично, присоединим к T (t1; t2) дугу (S1; Si1) и ее продолжение по L(Sl1) \ @Y в сторону от Si1 до первой встречи с конусом K(Sj1), для которого выполняется неравенство m(Sj1; Si1) < m(Si1; Sj1), и т. д. Если на некотором шаге возникнет равенство m(Sj; Si) = m(Si; Sj), то продолжение траектории можно осуществить двумя способами: присоединением любой из дуг (Si; Sj), (Sj; Si). Пусть построен участок T (tq 1; tq) траектории и точка tq принадлежит последней паре fSi; Sjg. Включим в T один из отрезков (Si; Sj); (Sj; Si) и завершим построение T на участке от tq до t в соответствии с п. 3.1.
В процессе построения T , при предположении m(S1; S1) > m(S1; S1), последовательно задействованы дуги
(S1; S1); (S1; Si1); (Si1; Sj1); (Sj1; Si2); (Si2; Sj2); : : : ; правила выбора которых указаны выше. Имеет место
Теорема 3. Пусть набор S удовлетворяет условиям (9). Для построенной в п. 4:1 траектории T выполняется соотношение:
M > M(S; T ) = minfm(Si; Sj); m(Sj; Si)g; где минимум берется по всем парам наблюдателей, перечисленным в (10). Неравенство (11) является точным на классе наборов S, удовлетворяющих условиям (9).
На рис. 2 приведен упрощенный вариант траектории T (изображена жирными дугами и точками). На ней не отражен случай, когда объект “перескакивает” по дуге на противоположную сторону коридора Y , а также случай неоднозначного продолжения траектории по одной из дуг (Si; Sj); (Sj; Si). (10) (11) Рис. 2: Пример траектории Благодарности
Работа выполнена при частичной поддержке Программы Президиума РАН “Математические задачи современной теории управления”. Список литературы The most concealed R3-tra jectory Vitalii I. Berdyshev Krasovskii Institute of Mathematics and Mechanics (Yekaterinburg, Russia)
Let an object move inside of a corridor Y R3. There is a set S of rival observers S 62 Y ; each of them has a fixed view cone K(S). We assume that multiplicity of covering of corridor Y by the K(S) does not exceed two. The problem of finding the most remote from S trajectory T Y is solved.