Основы теоретической робототехники. Теория толерантных пространств (обзор) — страница 9

  • Просмотров 250
  • Скачиваний 3
  • Размер файла 326
    Кб

(ядро видимости, как несложно заметить, имеет меру нуль, поскольку располагается на некотором касательном отрезке), то понятие класса видимости имеет более богатый спектр приложений. Покрытие террайна конечным числом классов или предклассов видимости используется для представления среды в виде графа районов [14], которые и могут выявляться на основе такого покрытия. Эти же покрытия применяются для навигационных вычислений.

Наличие несвязных классов видимости свидетельствует о существовании специфической конфигурации для групп роботов, получившей в работах [14] название "райского сада". Любую задачу выбора пути можно решить с точностью до класса видимости. Следует особо отметить, что в районе расположения ядер группа МР может совершать маневры типа "движение в ядре", когда в каждый момент времени роботы находятся в одном из ядер (при

этом они могут продвигаться вперед к подцели движения), а поля зрения у МР будут совпадать. Рис. 6. Атлас классов: (a,b) - связные классы, (c,d,e) - несвязные. Доказательство теорем приведено в [14]. Рис. 6,7 иллюстрируют вышесказанное. На рис.7 приведены примеры характеристик несвязного класса. Рис. 7. (f, g, h) - иллюстрация характеристик несвязного класса: l - число связных компонент, n - число "образующих" классов,  - число "одиночных"

компонент, mi - число компонент в i-ом "пучке" Теорема. Базис классов видимости имеет мощность континуум для любого террайна. Доказательство теоремы приведено в [14]. Таким образом, поскольку базис классов видимости для эффективного графа районов не подходит, попытаемся организовать стандартное конечное покрытие террайна классами видимости. Для построения конечного покрытия террайна, препятствия на котором - выпуклые, с

углами 90 и 270, классами видимости авторами был разработан следующий алгоритм: Выбирается отрезок - произвольная сторона любого препятствия на террайне и максимально распространяется в обе стороны до пересечения с другими препятствиями. Полученный отрезок назовем фронтом видимости. Фронт видимости распространяем в перпендикулярном к выбранной стороне препятствия направлении до прерывания его каким-либо препятствием.

Полученная прямоугольная область очевидно будет классом видимости. Повторяем шаги 1,2 для каждой стороны каждого препятствия. Получим совокупность пересекающихся классов видимости. Поскольку работа первых трех шагов алгоритма не гарантирует покрытия всего террайна (например, на террайне типа «мельница», представленном на рис. 8), то проводим следующую процедуру Выявляем непокрытую прямоугольную область террайна. Для каждой