2. ТЕРРАЙН
В простейшей модели движение РМС задается в террайне - ограниченной прямоугольной рамкой области с препятствиями, непрозрачными для измерителя и непреодолимыми для МР. Для простоты препятствия представляют собой многоугольники с углами в вершинах в 90 и 270, стороны которых параллельны граничной рамке и длина каждого отрезка принимает целочисленное значение (в соответствии с шагами по осям этой координатной системы). Подобные модели активно разрабатывались и анализировались в ИПМ [15] и других исследовательских организациях. Более сложная модель формируется в виде совокупности элементарных террайнов и классов ситуаций в них. Далее в работе рассматривается только террайн.
Отрезок [a,b] называется касательным, если: 1) он максимален для данного террайна, т.е. в направлении из a в b b является максимально удалённой видимой из a точкой (и наоборот, в направлении из b в a a является самой удаленной видимой из b точкой); 2) на интервале (a,b) есть как граничные точки, так и внутренние точки террайна.
Отрезок [c,d] называется выходным, если: 1) [c,d] строго входит в некоторый касательный отрезок; 2) c и d являются граничными точками террайна; 3) интервал (c,d) состоит только из внутренних точек террайна. Если выходной отрезок [c,d] строго входит в касательный отрезок, [a,b] а точка x расположена на этом касательном отрезке и не принадлежит указанному выходному отрезку, [c,d] называется наблюдаемым в точке x выходным отрезком.
Вершины препятствий, расположенные на интервале касательного отрезка, называются замыкающими вершинами.
Ориентация замыкающей вершины определяется тем, по какую сторону от касательного отрезка расположены содержащие замыкающую вершину граничные отрезки препятствий. Если ориентации двух замыкающих вершины, расположенных на одном касательном отрезке, различны, то на касательном отрезке имеет место ситуация типа «двойной замок». Сказанное иллюстрирует рис.1.
Рис. 1 Основные понятия теории террайнов.
V есть область в граничной рамке, исключая внутренние точки препятствий П1 и П2. Точки x и y, а также x и z видимы одна из другой, а точки z и y - нет. [a1, b1] и [a2, b2] являются касательными отрезками; [p1, b1] - выходной отрезок, наблюдаемый в точке x, этот выходной отрезок входит в dV(x); pi, i=1,2,3,4 - замки на указанных касательных отрезках. На [a2,b2] наблюдается ситуация "двойной замок" и этот касательный отрезок является классом видимости.
Пусть V - заключенная в рамку область допустимых положений МР (который представляется точкой). Две точки x,y видимы одна из другой (что записывается как x~y), если отрезок [x,y] не пересекает препятствий (но может их касаться).
Отношение видимости является отношением толерантности, т.е. оно рефлексивно, симметрично, но в общем случае не транзитивно. Историческая справка об отношении толерантности приведена в Приложении 1.
В общем случае террайн
Ter = < V , , , ~, [...]>,
где
V - носитель террайна,
(x,y) - исходная евклидова метрика,
(x,y) - вторая основная непрерывная метрика, удовлетворяющая отношению (x,y) (x,y) (обычно выбирается длина геодезической, т.е. кратчайшего пути, не пересекающего препятствий),
“~” - основное отношение толерантности (отношение видимости), которое может быть определено по схеме (x~y)<=>((x,y)=(x,y)),
[...] - индуцированные на основе указанных выше метрик и толерантности другие метрики и толерантности [15].
Всегда предполагается, что число препятствий в террайне и число вершин препятствий конечны.
Наряду с традиционным понятием границы множества M в террайнах большую роль играет свободная граница множества M - dM. Она определяется как подмножество таких точек x "обычной границы", что в сколь угодно малой окрестности x найдутся точки y из носителя террайна V, которые не входят в замыкание M.
Отличие от "обычной границы" в том, что там все y, не входящие в замыкание M, могут принадлежать препятствию. dV(x) - множество, через которое МР может покинуть V(x) - видимую окрестность x (т.е. множество всех точек, видимых из x). Видимая окрестность множества V(M) понимается как объединение видимых окрестностей всех точек множества.
Справедливо
Утверждение 2.1 [15]:
(1) V(M)=V(dM)
(2) dV(x) состоит из всех выходных отрезков, наблюдаемых в точке x.
(3) dV(M) в общем случае состоит из выходных отрезков или участков выходных отрезков, наблюдаемых из точек множества M.
Конечное множество A называется навигационным, если V(A)=V.
Конечное множество M называется магистральным, если
(1) M является навигационным множеством;
(2) если x, y - элементы M, то существует путь из x в y в виде ломаной, все вершины которого суть элементы M.
Магистральное множество задает определенный магистральный граф, при движении по которому можно выйти в визуальную окрестность любой точки террайна.
Здесь путь понимается как последовательность точек, в которой любые две соседние точки видимы друг из друга.
3. ЯДРА И КЛАССЫ ВИДИМОСТИ
Рис. 3. Атлас классов: (a,b) - связные классы, (c,d,e) - несвязные.
Ядра и классы видимости являются основными структурными образованиями на террайне [15,16].
Ядром видимости называется максимальная область, для каждой точки которой видимая окрестность одна и та же.
Утверждение 3.1.
Если в любой точке террайна наблюдаются два выходных отрезка, которые входят в разные касательные отрезки, т.е. неколлинеарны, то в таком террайне отсутствуют нетривиальные (т.е. состоящие более чем из одной точки) ядра видимости.
Утверждение следует из теоремы, доказанной в [16], о представлении ядер видимости. Атлас возможных типов ядер видимости представлен на рис.2. Здесь изображены:
(2a): "Веер" ядер у вершины p. Каждое ядро - полуинтервал, одно из граничных точек террайна (второго типа), остальные из внутренних точек террайна (первого типа), с граничной точкой террайна- концом полуинтервала.
(2b): Ядро первого типа - интервал.
(2c): Усеченное ядро первого типа - отрезок - с граничной точкой террайна - одним из концов отрезка.
(2d): Усеченное ядро первого типа - отрезок, состоящее из внутренних точек террайна.
(2e): Невырожденное ядро второго типа, состоящее из одного или нескольких интервалов (случай несвязного ядра) граничных точек террайна.
(2f): Усеченное ядро второго типа, представляющее собой отрезок, входящий в состав граничного отрезка террайна.
(2g): Разбиение ядра второго типа из-за ситуации типа "двойной замок".
(2h): Ситуация типа "цепь": между компонентами несвязного ядра второго типа находятся ядра первого типа.
Классом видимости называется максимальная область, все точки которой видимы одна из другой. Это понятие, также как и понятие класса толерантности в общем случае [17, 18], является аналогом понятия клики на конечном графе.
Класс видимости может быть связным или несвязным множеством. Нетрудно видеть, что несвязный класс видимости может быть гомоморфно отображен на полный граф.
Справедливы следующие теоремы.
Теорема 3.1. (О связных классах видимости)
Связный класс видимости является выпуклым многоугольником, или (в вырожденном случае) касательным отрезком, на котором наблюдается ситуация типа двойной замок. Если такой класс является выпуклым многоугольником, то каждая его сторона либо (а) входит в состав некоторого граничного отрезка препятствия, либо (б) на этой стороне расположены хотя бы одна замыкающая вершина, а если таких замыкающих вершин несколько, то ориентация их всех одинакова; при этом хотя бы одна сторона многоугольника удовлетворяет условию (б).
Теорема 3.2. (О несвязных классах видимости)
Несвязный класс видимости состоит из конечного числа l?3 связных непересекающихся компонент M1,...,Ml, каждая из которых может быть либо точкой, либо отрезком, либо выпуклым многоугольником. При этом существует n?l(l-1)/2 связных классов видимости K1,...,Kn таких, что каждая компонента Mi является пересечением mi этих связных классов, где 2?mi?l-1.
Рис. 3. Атлас классов: (a,b) - связные классы, (c,d,e) - несвязные.
Доказательство теорем приведено в [16]. Рис. 3,4 иллюстрируют вышесказанное. На рис.4 приведены примеры характеристик несвязного класса.
Рис. 4. (f, g, h) - иллюстрация характеристик несвязного класса:
l-число связных компонент,
n-число "образующих" классов,
- число "одиночных" компонент,
mi - число компонент в i-ом "пучке"
Если понятие ядра видимости является более "экзотическим" (ядро видимости, как несложно заметить, имеет меру нуль, поскольку располагается на некотором касательном отрезке), то понятие класса видимости имеет более богатый спектр приложений. Покрытие террайна конечным числом классов или предклассов видимости используется для представления среды в виде графа районов [16], которые и могут выявляться на основе такого покрытия. Эти же покрытия применяются для навигационных вычислений. Наличие несвязных классов видимости свидетельствует о существовании специфической конфигурации для групп роботов, получившей в работах [16, 19] название "райского сада". Любую задачу выбора пути можно решить с точностью до класса видимости.
Следует особо отметить, что в районе расположения ядер группа МР может совершать маневры типа "движение в ядре", когда в каждый момент времени роботы находятся в одном из ядер (при этом они могут продвигаться вперед к подцели движения), а поля зрения у МР будут совпадать.
4. ОБОСНОВАНИЕ АЛГОРИТМОВ ВЫБОРА ПУТИ
Пусть МР обладает возможностью фиксировать точки некоторого магистрального множества M и осуществлять к ним передвижение, а также опознавать целевую точку. Тогда задача выбора пути между произвольными точками террайна x и y сводится к задаче построения такого пути по магистральному графу, вершинами которого являются элементы M и, возможно, точки x и y. Ребра графа при этом определяются на основе отношения видимости. При этом известные алгоритмы выбора маршрута по известному графу модифицируется с учетом того, что МР в каждый момент времени может находиться в единственной вершине (или двигаться по ребру) итеративно строящегося в процессе решения задачи путевого графа, являющегося подграфом магистрального [11].
Под задачей о достижении целевой точки для одного МР понимается упорядоченная тройка m=(Ter,b,g), где Ter - некоторый террайн, b - точка начала движения, g - целевая точка. При этом b,gV, т.е. являются допустимыми точками террайна.
Задача называется тривиальной, если [b,g]V, т.е. начальная и целевая точки видимы одна из другой. В дальнейшем будут рассматриваться только нетривиальные задачи.
Террайн Ter предполагается линейно связным, т.е. для любой задачи m=(Ter,b,g) на нем существует путь из b в g. Более того - существует путь, представимый ломаной.
Путь ph есть последовательность точек террайна (ломаная) ph={s0,s1,…,sn} такая, что [si,si+1 ]V, i=0,..n-1 (при этом точки не обязаны быть различными). Последовательность ph называется решением задачи m, если s0=b, sn=g.
Точки si, i>0 называются подцелями, а n есть информационная длина пути (число звеньев ломаной).
Под задачей информационного обхода понимается сбор информации обо всем носителе террайна V, который является ограниченной областью. Если для задачи m задана недостижимая целевая точка g, то естественно за достаточный промежуток времени МР решит задачу информационного обхода.
При формулировке задачи для РМС вместо b определяется B - множество, характеризующее расположение МР РМС в начальный момент времени.
Управление движением РМС в общем случае строится следующим образом. Пусть xi(tk) - положение i-го МР в момент времени tk. Тогда такт работы системы управления (СУ) РМС при решении рассматриваемых задач заключается в выборе подцелей движения для элементов РМС из множества dV(x1(t1),x1(t2),..,x1(tn),..,xm(t1),xm(t2),..,xm(tn)). Это множество будем обозначать через Wn; оно представляет собой открытую границу множества положений всех подцелей, пройденных элементами РМС к моменту n.
Ниже приводится схема шага (последовательность операций управления в процессе реализации одного шага) централизованного управления последовательного (ЦУПос) для решения задач достижения целевой точки и информационного обхода. (Капитаном здесь называется центр управления РМС).