Некоторые аспекты интерпретирующей навигации мобильного робота

( Some Problems of the Qualitative Navigation of the Mobile Robot
Preprint, Inst. Appl. Math., the Russian Academy of Science)

Введение

Традиционная навигация состоит в представлении положения ро­бота в некоторой абсолютной системе координат. Альтерна­тивой ей служит интерпретирующая навигация (ИН) - представление поло­жения робота в некоторой глобальной модели специального типа на основе анализа полученных при помощи соответствующей информаци­онной системы описаний видимой части среды. Первый под­ход требует наличия системы счисления пути, вто­рой - ее "аналога" - системы информационного слежения, позволяю­щей адекватно интерпретировать как наблюдаемую ситуацию, так и положение робота в глобальной модели. [3]

При построении корректных алгоритмов интерпретирующей нави­гации встают три проблемы:     

§        несвязность областей среда, где используемое локальное относительное (т.е. вычислимое информационной системой) описание принимает фиксированное значение, так как любая локальная ситуа­ция может повториться на любом уровне относительного описания;

§        "самоналожимость" локальных относительных описаний, т.е. разные объекты имеют одинаковые относительные признаки;

§        один и тот же ориентир (выделенный объект среды) может восприниматься по разному (иметь различные относительные призна­ки) в зависимости от "точки зрения" - местонахождения робота;

БЛАГОДАРНОСТИ

          Автор выражает признательность А.К.Платонову, С.М.Соколову и А.А.Кирильченко за поддержку исследований и плодотворные творческие дискуссии.  

1. Некоторые аспекты теории интерпретирующей навигации

1.1 Используемые модели.

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

- множество доступных роботу точек,

- множество граничных точек препятствий,

- множество вершин препятствий.

Последнее множество будем полагать всегда состоящим из ко­нечного числа элементов. Будем также полагать: (то есть робот - точка, лишенная размеров, которая может находиться на препятствии).

Мы будем полагать ограниченным некоторой прямоугольной рамкой. Далее везде под понятием "местность" подразумевается конечносвязное ограниченное множество . Под роботом будем понимать в общем случае ориентированную точку, способную перемещаться по местности. Скорость движения робота по местности будем полагать огра­ниченной значением . Предполагается, что робот снабжен информационной системой.

Введем на множестве отношение видимости: ,  если

(при этом может быть ). Отношение види­мости есть отношение толерантности,  заданное на бесконеч­ном (по числу элементов) множестве V.

Пусть  - множество точек. Через  будем обозначать под­множество точек , видимых из точки , а через  - множест­во точек местности, видимых хотя бы из одной точки .

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

1.2. Абсолютные и относительные локальные описания.

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

В состав каждого набора признаков могут, в час­тности, входить:

1) угол наблюдения ориентира ;

2) координаты ориентира в собственной системе координат измерителя ;

эти признаки не являются устойчивыми (меняются при смене положения робота);

3) Классификационный признак видимой верши­ны ; при этом значения признака являются локально устойчивыми - в окрестности  существуют области ненулевой площади, где значение локального признака не изменяется.

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

Будем полагать, что абсолютный признак у всех используемых ориентиров различен.

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

Абсолютный признак и абсолютное описание следует понимать как "ключи" к возможности использования имеющейся у робота гло­бальной модели местности того или иного типа, гарантирующие пра­вильную интерпретацию его положения по отношению к среде в гло­бальном смысле.

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

Если структурные признаки хотя бы у двух элементов кольца совпадают, то кольцо называется самоналожимым. Очевидно, что абсолютное кольцо самоналожимым быть не может. В случае относительного кольца структурный приз­нак может способствовать разделению ориентиров, имеющих одинаковые начальные наборы признаков. Например, после проведения измерения было выявлено 5 каких-либо относительных признаков. Пусть мы имеем два признака одного типа (обозначим А), два признака другого типа (обозначим В) и один признак третьего типа (обозначим С). Предположим, что мы имеем кольцо, составленное из этих признаков: ABABC. Возникает вопрос: как отличать друг от друга признаки В или А. Ответом служат структурные признаки. У первого признака В структурный признак: АВСА. У второго признака В – САВА.

Кольцо АВАВ является самоналожимым.

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

2. ОСОБЕННОСТИ МОДЕЛИРОВАНИЯ АЛГОРИТМА ИНТЕРПРЕТИРУЮЩЕЙ НАВИГАЦИИ В ИСКУССТВЕННЫХ СРЕДАХ

Навигационная система мобильного робота должна решать две задачи:

1)     задача «Где» - определение текущего положения МР;

2)     задача «Куда» - определение текущих подцелей движения МР.

Для решения первой задачи служат алгоритмы ИН. Разработан формат универсальной команды ИН, который показан в 2.1.

Для решения второй обычно применяется теория графов, в частности метод магистралей – 2.2.

2.1. Формат универсальной команды

интерпретирующей навигации

В результате исследований был выделен универсальной формат команды ИН. Затем, для сокращения объёмов передаваемой информации, из этой команды была создана минимальная команда ИН.

На рис. 2 представлен формат универсальной команды ИН. Минимальная команда получается из неё, отбрасыванием последних 3-х блоков .

Первый блок определяет тип признака.

Второй блок определяет тип движения: вдоль ориентира означает движение вдоль указанного ориентира, к ориентиру означает движение по направлению к ориентиру, при движении обходить ориентир по кругу МР движется по окружности, центром которой является ориентир, значения двух оставшихся пунктов (вперёд и назад) не связанны с ориентиром.

Третий блок определяет, на каком расстоянии от ориентира необходимо двигаться МР.

Четвёртый блок указывает интервал времени, в течении которого роботу разрешено двигаться. По истечении этого интервала выполнение данной команды завершается.

Пятый блок определяет длину пути, который необходимо пройти.

Шестой блок указывает расстояние, на которое необходимо приблизиться к ориентиру (используется только тогда, когда выбран тип движения к ориентиру).

Седьмой блок задаёт пару колец признаков (относительных и абсолютных) в начальный момент движения.

В восьмом блоке указываются событие, до наступления которого роботу необходимо двигаться (основное событие), и события, в группе с которыми должно появиться основное событие (сопутствующие события).

В девятом блоке роботу задаётся пара колец признаков (относительных и абсолютных), при появлении которых следует завершить выполнение программы.

Выигрыш в информации при передачи минимальной команды ИН в зависимости от  показан на рис.3.

2.2. Метод магистралей

Метод магистралей предполагает, что транспортный граф (граф, состоящий из вершин, которые являются областями, в которых может находится МР и дуг их соединяющих)  покрыт специальными путями – магистралями - , причем если , , то трасса между  и  входит в ; если , , то трасса содержится в , т.е. может быть получена поэтапным соединением участков магистралей между собой. Хорошим примером подобной магистральной организации служит метро или магистральная сеть города. Вообще говоря, необязательно, чтобы сеть магистралей покрывала весь транспортный граф. Если, например,, то можно воспользоваться любым пошаговым алгоритмом, чтобы построить трас­су от  до ближайшей магистральной вершины. Аналогичным образом можно поступить, если целевая вершина  не находится на магистрали. Затем оставшуюся часть трассы можно получить магист­ральной трассировкой (прокладкой пути на магистральном покрытии).

Для описания структуры метода магистралей вводятся некоторые обозначения. Через  обозначается оптимальный путь из  в, через  - длина оптимального пути из  в у. Вершина  называется магистральной проекцией вершины , если . Если  и  - два пути, то запись  означает, что путь  содержится в , а запись  означает, что путь  cодержится в объединении путей , т.е. все вершины и ребра пути в левой части выражения входят в множества вершин и ребер в правой части. Запись , где  - вершина, а  - путь (или объединение путей), означает, что вершина   входит  в  путь .

Пусть на графе  выделены магистрали . Они обра­зуют магистральное покрытие графа, если выполнены следующие усло­вия:

1.  Если , то .

2. Если одна из вершин задачи, например, не входит в ма­гистральное покрытие (), то для вершины , являющей­ся магистральной проекцией вершины , справедливо следующее соот­ношение

,

где через • обозначена операция конкатенации путей.

Задача прокладки маршрута с помощью метода магистралей ре­шается следующим образом.

1° Определяются магистральные проекции начальной и целевой вершин задачи  и  (магистральная проекция может совпадать с самой вершиной). Этот этап называется этапом проектирования за­дачи на магистраль.

2° Строится трасса . Этот этап называется магист­ральной трассировкой. Магистральная трассировка определяет последователь­ность магистральных вершин  таких, что  и

а) для любых соседних членов последовательности

;

б)  принадлежит по крайней мере двум ма­гистралям (т.е. является вершиной магистрального перехода). Такие вершины называются "станциями пересадки" по аналогии с сетью ли­ний метро. При этом если , то .

3° Строится трасса   . В случае совпадения магистральной проекции вершины с самой верши­ной первый и последний члены правой части отсутствуют. Этап 3° называется составлением результирующей трассы.

Этапа 1° - проектирование за­дачи на магистраль (в случае, если хотя бы одна из вершин задачи не является магистральной) осуществляется с использованием известных пошаговых алгоритмов (алгоритм поиска в «глубину» и в «ширину», алгоритмы равных цен, алгоритмы упорядоченного поиска).

На этапе магистральной трассировки (этап 2°) используется структура данных, представленная на рис. 4. В массиве ссылок  для каж­дой вершины хранится величина, принимающая следующие значения:

- 0, если вершина находится не на магистрали;

- номер магистрали , если через вершину проходит одна магистраль;

- ссылку в массив  , являющийся графом пересадок, если через вершину проходит более одной магистрали.

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

"Подстыковка" к графу пересадок магистральных проекций зада­чи осуществляется с использованием массивов  и .  Входом в массив  является номер магистрали , а выходом - адрес в мас­сиве описания магистралей . Каждое описание магистрали включает в себя заголовок, куда входят число вершин, признак, определяю­щий, разрешено ли движение по магистрали в обоих направлениях, и признак, является ли магистраль закольцованной. При этом каждой станции может соответствовать ориентирное описание, а переходу от станции к станции – команда движения на языке ИН.

На этап 3° с помощью тех же массивов реализуется этап составления результирующей трассы: части магистралей, находящиеся между стан­циями пересадок, переписываются в выходной массив.

Преимущество метода магистралей заключается в том, что за­траты на вычисление оптимального маршрута значительно снижаются на этапе 2°, т.к. продвижение по магистралям ведется "большими" шагами между станциями пересадок. [4]

2.3. Модель представления здания

В данной работе использовался вариант представления местности в виде клетчатого информационного поля. В соответствии с этим вся местность покрывается регулярной сеткой. Препятствия в такой модели аппроксимируются фигурами, составленными из клеток сетки. В данной работе, необходима информация ещё и о высоте препятствия (дальномер робота расположен на какой-то высоте от земли), поэтому используется 2,5D – мерная система. Это означает, что любой трёхмерный объект задаётся значениями , и , причём значения  не может изменяться в пределах объекта, и, кроме того, движение происходит по базовой плоскости.

Полная модель среды, представленная на рис. 5, состоит из:

1)     ППЗ – полное представление здания в виде информационного поля и графа смежности районов. Вершинами этого графа являются комнаты, лестничные клетки, станции пересадок с магистрали на магистраль. Дуги графа – это переходы между вершинами;

2)     МаГ – магистральный граф. Вершинами этого графа являются станции пересадок между магистралями, а рёбрами – магистрали;

3)     ССО – система статических объектов. Объекты, положение которых не меняется в течение всего времени моделирования (стол, шкаф и т.д.);

4)     СДО – система динамических объектов. Объекты, положение которых может меняется в течение времени моделирования (стул и т.д.);

5)     Процедура абсолютной инвентаризации – процедура присвоения каждому ориентиру порядкового номера. Эту процедуру проводит оператор. 

3. ПОЛУЧЕНИЕ ОЦЕНОК ОБЪЁМА ПЕРЕДАВАЕМОЙ ИНФОРМАЦИИ ПРИ ИНТЕРПРЕТИРУЮЩЕЙ НАВИГАЦИИ

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

Введём ещё два понятия. Первое – матрица расстояний – матрица, элементами которой являются расстояния между признаками, т.е. на пересечении столбца стоит расстояние между  и  признаком. Второе – погрешность измерения дальномера . Понятно, что точнее этого значения передавать расстояние не имеет смысла. Теперь, для передачи двух колец и матрицы расстояний требуется:  бит. Подставляя в  выражение для , получаем функцию от  (рис. 7).

Итак, мы получили некоторые оценки для количества информации, передаваемого от робота оператору, но это оценки сверху, так как мы предполагали, что препятсвия расположены вплотную друг у другу (см. выражение для ).

Получим теперь средние значения величин  и . Для этого представим как , где  - характерное расстояние между препятствиями, а - характерный размер препятствия  и   распределены по нормальному закону: , т.е. среднее значение равняется 2,5 м. Построим графики функций  и  для  (рис. 8 и рис. 9).

Займёмся теперь информацией, передаваемой от оператора к роботу. Как говорилось выше, существует минимальная команда ИН. Подсчитаем количество информации, передаваемое при использовании приведённого выше формата.

1-ый блок – 5 бит, 2-ой блок – 5 бит, 3-ий блок -  бит, 4-ый блок – 10 бит, 5-ый блок - бит, 6-ой блок -  бит. В итоге имеем:

Приводя подобные и подставляя в  выражение для , получаем функцию от . Построим также графики следующих функций:  при  (рис. 10 и рис. 11).  

2.     АЛГОРИТМ АВАРИЙНОГО ВОЗВРАТА МОБИЛЬНОГО РОБОТА

Современные системы навигации должны уметь возвращать МР в исходное положение без помощи диспетчера. Эта необходимо для того, чтобы в случа непредвиденного разрыва связи с диспетчером МР мог самостоятельно вернуться назад. В свете алгоритмов ИН возникает вопрос о построении алгоритма аварийного возврата МР. В нижеследующей таблице приведено правило перетрансляции признаков, а утверждение 1 определяет общее правило перетрансляции прямого пути в обратный.

Таблица 1. Преобразование локальных относительных признаков ориентира

Утверждение 1. Для перетрансляции  прямого пути в обратный необходимо каждую команду прямого пути перевести в соответствующую команду обратного пути по следующим правилам:

-         Информационно-двигательное действие остаётся такое же как и в соответствующей команде прямого пути;

-         Признак берётся из предыдущей команды прямого пути;

-         Признак «справа» меняется на признак «слева» и наоборот.

Подтвердим сформулированное утверждение несколькими примерами.

ЗАКЛЮЧЕНИЕ

В работе получены следующие результаты:

1)     разработана система команд на основе интерпретирующей навигации для движения мобильного робота в здании (с использованием метода магистралей);

2)     разработан интерфейс для задания структуры внешней среды в виде здания;

3)     исследовано поведения оценки сверху для объёма передачи данных при движения мобильного робота на основании интерпретирующей навигации;

4)     разработан алгоритм трансляции аварийного возврата по пройденному пути.

На основании полученных результатов можно сделать следующие выводы:

1)     существующий канал передачи данных заведомо обеспечивает работу системы в диапазоне заданных структурных параметров среды;

2)     проведенные эксперименты показали, что для организации передвижения в рамках 11 команд интерпретирующей навигации для типичной лабораторной обстановки достаточно передачи данных на сеансе в объеме 300 бит.

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

ЛИТЕРАТУРА

1.     Петров А.А. Активное формирование моделей среды очувствлёнными роботами. М.: ИППИ РАН, 1997.

2.     Э. Хант. Искусственный интеллект. М.: Мир, 1978 – 560 с.

3.     Кирильченко А.А. Интерпретация локальных относительных описаний среды подвижным роботом // Препринт ИПМ им. М.В. Келдыша РАН СССР, 1983, №149

4.        Барбашова Т.Ф., Кирильченко А.А., Павловский В.Е. Исследование и выбор эффективных алгоритмов маршрутизации // Препринт ИПМ им. М.В. Келдыша РАН, 1987,  №4, 32 с.

5.     Кирильченко А.А., Платонов А.К., Соколов С.М. Теоретические аспекты организации интерпретирующей навигации мобильного робота. // Препринт Ин-та прикл. матем. им.М.В.Келдыша РАН, 2002, №5 40с.

РИСУНКИ

1. Классификация видимых из точки  вершин: 1 – стена; 2 – вогнутый угол; 3 – скачок “к”; 4 - выпуклый угол; 5 – скачок “от”

2. Формат универсальной команды ИН

3. Выигрыш в информации при передачи минимальной команды ИН в зависимости от

4. Базовая структура данных магистрального алгоритма:  - массив указателей для вершин графа;  - массив станций пересадок; - массив указателей для магистралей; - массив описания магистралей;  - цена связи.

5. Общая схема используемой модели

6. Количество информации при передаче двух колец признаков при

7. Количество информации при передаче двух колец признаков и матрицы расстояний для

8. Количество информации при передаче двух колец признаков при

9. Количество информации при передаче двух колец признаков и матрицы расстояний для

10. Количество информации при передаче 1,3,5 и 10 универсальных команды ИН для

11. Количество информации при передаче 1,3,5 и 10 универсальных команды ИН для

12. Пример работы алгоритма аварийного возврата