Научная работа: Логический подход к проектированию алгоритмов информационного обеспечения мобильных систем. Основные понятия

1. Организация Капитаном согласованного общего осмотра на текущих позициях и формирование текущей открытой границы dV(x₁(t_n),..,x_k(t_n))=U_n

2. Формирование полной открытой границы dV(x₁(t₁),..,x₁(t_n),...,x_k(t₁),..,x_k(t_n))=W_n

3. Выделение на W_n множества выходных отрезков {_i}

4. Выбор элемента системы для шага из условия , здесь G - целевая конфигурация точек, ch - оценочная функция расстояния от выходного отрезка до целевой точки.

5. Реализация шага элементом.

Процесс активации группового шага информационного обхода в режиме централизованного управления параллельного (ЦУПар) следующий. (Предполагается террайн типа изображенного на рис. 5: помещение с «коридорами», «комнатами» и «дверьми»).

1. Выбор Капитаном Ведущего группы и передача ему задания на шаг.

2. Расстановка Ведущим приоритетов в группе.

3. Выполнение группой маневра "продвижение через дверь".

4. Построение группы псевдоядром видимости (т.е. видимые окрестности положений элементов группы отличаются незначительно).

5. Проведение элементами группы осмотра дальнего плана.

6. Проведение Ведущим согласованной интерпретации объектов дальнего плана и активация у каждого из элементов группы процесса информационного слежения.

7. Сообщение от Ведущего к Капитану.

8. Выбор Капитаном подцелей движения на шаге.

9. Построение Ведущим плана реализации подцелей на шаге.

10. Запуск шага.

Рис.5 Лабиринтоподобный террайн

Следует отметить то обстоятельство, что в режиме ЦУПар достижение текущих подцелей реализуется одновременно всеми элементами РМС. При этом осуществляется синхронизация по окончанию шага: шаг считается завершенным, когда все МР достигли своих подцелей.

Корректность определения алгоритмов достижения целевой точки и информационного обхода обосновывается следующей теоремой [20].

Теорема 4.1:

Пусть для алгоритма, реализующего ЦУПос, на шаге выбирается подцель из W_n. Тогда данный алгоритм сходится за конечное число шагов для любой задачи достижения целевой точки на данном террайне.

Следствие:

Алгоритм ЦУПос решения задачи информационного обхода сходится за конечное число шагов.

Теорема 4.2:

Пусть для алгоритма, реализующего ЦУПар, на шаге выбираются подцели из W_n. Тогда данный алгоритм сходится за конечное число шагов для любой задачи достижения целевой точки на данном террайне.

Следствие:

Алгоритм ЦУПар решения задачи информационного обхода сходится за конечное число шагов.

Подробно организация информационного обхода для РМС с малым радиусом действия информационной системы рассмотрена в [21].

5. СТРУКТУРНЫЕ ХАРАКТЕРИСТИКИ СРЕДЫ

Как уже было сказано выше, основной структурной моделью среды является магистральный граф. Террайн тоже может рассматриваться как граф с континуумом ребер и вершин.

Поэтому характеристики сложности террайна могут рассматриваться как характеристики сложности графа.

Диаметром террайна называется максимальное число в минимальном по числу звеньев пути между любыми двумя точками террайна. Эта характеристика является аналогом диаметра графа.

Навигационное множество называется независимым, если ни одной точки из него нельзя удалить без того, чтобы множество не перестало быть навигационным.

Число элементов в независимом навигационном множестве называется навигационным числом.

Нетрудно видеть, что для нетривиального террайна существуют минимальное и максимальное навигационные числа. Навигационное множество является аналогом доминирующего множества на графе, а навигационное число - аналогом числа доминирования (рис. 6).

Навигационные базисы (независимые навигационные множества)

_min=2 _max=4

Рис.6. Навигационные множества

Рассмотрим свойства магистрального графа. Порядок группы автоморфизмов этого графа является мерой его симметрии. Вместе с тем, сама группа автоморфизмов дает описание симметрии для ситуаций типа «ирония судьбы» [7]. Каждая подстановка, задающая элемент группы автоморфизма, дает описание такой ситуации ( рис. 7).

Рис 7. Пример группы автоморфизмов магистрального графа

Группа автоморфизмов порядка 8 как мера «симметрии» магистрального графа в террайне относительно ситуации типа «ирония судьбы» (повторение локального относительного описания в несвязных районах по этому описанию)

Пусть задано некоторое остовное дерево магистрального графа. Как известно, добавление к остовному дереву любого из оставшихся ребер образует фундаментальный цикл. Множество фундаментальных циклов, разумеется, зависит от выбора остовного дерева (которых может быть несколько). Однако число фундаментальных циклов постоянно, и любой цикл, не входящий в множество фундаментальных циклов для выбранного остовного дерева, может быть выражен через фундаментальные циклы с помощью операции симметричной разности a-bb-a . В реальных условиях выбор остовного дерева может быть предопределен практическими соображениями. Таким образом может быть получено базовое множество циклов данного магистрального графа и выражение произвольного цикла в рамках данного базового множества.

Цикл, как известно, - это потенциальная возможность зациклиться для алгоритма выбора пути (алгоритм без памяти, скорее всего, так и сделает) рис.8

Рис 8. Пример множества фундаментальных циклов для магистрального графа (пути в графе описываются ребрами).

Если остовное дерево есть , то множество фундаментальных циклов состоит из элементов:

Третий цикл выражается так:

Если остовное дерево есть , то множество фундаментальных циклов состоит из элементов:

Третий цикл выражается так:

Наконец, для конкретной задачи можно применить известную математическую технику [22], чтобы построить множество возможных путей. Для этого необходимо определить некоторый эталонный алгоритм выбора пути (рис.9).

Рис 9. Определение множества путей из точки в точку на основе символьных уравнений.

Задача . Индекс у наименования точки показывает значение соответствующей координаты точки: или .

Эталонный алгоритм: выбирает подцель справа (R) или слева (L) от направления на целевую точку G или же движение прямо в целевую точку (F).

Система уравнений, описывающее множество возможных путей ( - пустая цепочка символов).

Решение (множество возможных путей):

Имея оценки диаметра и навигационного числа для террайна, можно построить оценку для размерности магистрального множества[15]

6. НЕСРАВНИМОСТЬ И АДАПТАЦИЯ АЛГОРИТМОВ ВЫБОРА ПУТИ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ

Рассмотрим задачу достижения целевой точки g из начальной точки b на плоскости с конечным числом препятствий.

Классификация алгоритмов выбора пути в этом случае может быть проведена следующим образом. Прежде всего, мы можем различать алгоритмы с точки зрения параметров информационной системы МР. Выделим два крайних класса: V-алгоритмы и C-алгоритмы. В случае V-алгоритмов для МР доступна информация о любой точке в видимой окрестности текущего положения МР, и он может двигаться до любой точки видимой окрестности (т.е. предполагается, что МР располагает идеальными информационной и двигательной системами). В случае C-алгоритмов радиус действия информационной системы МР равен "нулю" и МР может осуществлять только две операции: двигаться в направлении к целевой точке (если это возможно) и обходить препятствие по его границе.

Предположим, что следующая подцель для V-алгоритма после сканирования МР местности и принятия решения о движении может быть только вершиной препятствия; а точка "схода" для C-алгоритма (т.е. точка, где МР меняет способ движения с обхода препятствия на движение к точке цели) также является вершиной препятствия.

Возможные точки "схода" и "захода" на препятствие для конкретного C-алгоритма мы можем рассматривать как возможные подцели движения, так же как и вершины препятствий для V-алгоритмов. Таким образом, путь, продуцируемый V- или С-алгоритмом, представляет собой ломаную. Большинство из известных и неизвестных V- и C-алгоритмов (в соответствии с приведенными выше предположениями) может быть представлено в виде следующей схемы из четырех пунктов:

1. Сканирование среды и выбор возможных подцелей для V-алгоритма (для C-алгоритма - переход от одного способа передвижения к другому в точках "схода" и "захода"). Всем новым подцелям присвоить признак «открыта».

2. Выбор вершины на пройденном пути, которая отмечена признаком "открыта" для следующей попытки движения в неизвестный район местности через некоторую (фиксированную ранее) подцель;

3. Если эта вершина не текущая, то осуществить в нее возврат.

4.Осуществление движения в неизвестный район местности; если эта попытка окончилась неудачно, то пометить эту вершину пути (или подцель) признаком "закрыта" и переход к шагу 2, иначе переход к шагу 1. Остановка, если целевая точка достигнута.

Каждый алгоритм можно характеризовать некоторой структурной формулой, которая определяет класс алгоритма. В простейшем случае имеется две формулы: V и C. V-алгоритм может быть охарактеризован также оценочной функцией для подцелей f. Функция f может быть составлена на основе оценки расстояний с помощью функций, аналогичных g и h функциям для поиска пути минимальной длины на графе [23]. Предположим, что - расстояние от подцели до целевой точки, - расстояние от текущей (не начальной - в отличие от поиска по априорно известному графу!) позиции МР до подцели. Тогда можно рассматривать такие функции f как f=, f=+, f= (+) и т.п. В структурной формуле V- алгоритма оценочная функция является вторым элементом. Тогда "естественный" V-алгоритм может быть представлен формулой V(+). В случае C-алгоритма мы можем фиксировать направление движения по границе препятствия при его обходе после первой точки "захода". Положив =+ (против часовой стрелки) и = (по часовой стрелке), получим формулы C+,C-,C (в последнем случае фиксировано, но его знак не имеет значения).

Еще одно предположение относительно C-алгоритмов заключается в следующем. После того, как МР осуществил контакт с первым встречным препятствием на точке "захода" и начал его обход по контуру, он покидает его с первой возможной точки схода, которая обязательно является вершиной препятствия.

Пусть существует базовое множество известных алгоритмов выбора пути А и множество возможных задач М. Каждая задача из М характеризуется картой препятствий, а также стартовой и целевой точками. Множество М теперь мы можем характеризовать целочисленной величиной N, которая равна максимальной длине стороны минимальной рамки, в которую может быть помещен каждый элемент из М. Число N мы будем называть "уровнем разнообразия террайна". Мы предполагаем, что каждый алгоритм из А является допустимым, т.е., для каждой задачи для любого фиксированного N он продуцирует путь от начальной до целевой точки (в предположении, что такой путь существует).

В этих предположениях продемонстрируем эффект несравнимости алгоритмов в условиях неопределенности. Эффект возникает, когда базовое множество алгоритмов А и местность достаточно разнообразны. Тогда можно показать, что не существует оптимального алгоритма для любого множества (А,М), т.е., невозможно найти алгоритм a, который продуцирует более короткий (или равный) путь, чем любой алгоритм из А на любой задаче из М. Этот факт приводит нас к необходимости хранить и использовать все несравнимые (на множестве М) алгоритмы из А (или вообще считать, что А состоит из несравнимых на М алгоритмов). Сформулируем соответствующую теорему[8].

Теорема 6.1. Если в состав базового множества алгоритмов А входят два алгоритма со структурными формулами V(+) и C, и М состоит из всех возможных элементов с уровнем разнообразия местности большим, чем 5, то не существует оптимального алгоритма для пары (А,М).