Ю. В. ЧЕРНУХИН, А. А. ПРИЕМКО
Таганрогский государственный радиотехнический университет
*****@
ФОРМИРОВАНИЕ И ИСПОЛЬЗОВАНИЕ КАРТЫ
ВНЕШНЕЙ СРЕДЫ В ЗАДАЧЕ НАВИГАЦИИ
АДАПТИВНОГО МОБИЛЬНОГО РОБОТА
Аннотация
В докладе анализируются недостатки известных методов автоматического построения карт внешней среды интеллектуальных мобильных роботов. С целью уменьшения влияния таких недостатков предлагается специальная методика. Ее суть состоит в формировании карты одновременно с исследованием среды функционирования путем определения роботом проходимости участков смежных с тем, на котором он находится, и нанесением координат этих участков вместе с информацией об их проходимости на карту. Приводятся результаты экспериментов, подтверждающие полученные теоретические выводы. Данная методика ориентирована на применение в нейросетевых системах управления адаптивных мобильных роботов.
Навигация адаптивных мобильных роботов с использованием карт внешней среды является актуальной задачей современной робототехники. При этом процесс навигации включает в себя следующие этапы [2]: составление карты среды, локализация (определение положения робота на карте по его координатам в среде) и планирование маршрута (выбор оптимального пути, ведущего к цели). Первые два этапа являются взаимосвязанными (карта среды требуется для оценки собственного положения робота, знание которого, в свою очередь, необходимо для построения карты). Эта взаимосвязь затрудняет решение задачи формирование карты внешней среды. С целью преодоления отмеченной трудности в литературе [2] предложены два класса методов формирования карт. Методы первого класса формируют метрические карты, а методы второго – когнитивные карты. При этом основным недостатком методов первого класса является высокая погрешность при измерении координат робота, а методы второго класса применимы только при построении карт априори формализованных внешних сред.
Для преодоления недостатков описанных методов предлагается методика формирования карты рабочей зоны робота, суть которой состоит в том, что внешняя среда дискретизируется так же, как и в [2], при этом каждому участку, содержащему препятствие, ставится в соответствие информация о типе этого препятствия. Также предполагается, что для определения проходимости участков среды используется дистантная сенсорная подсистема сканирования на основе лазерного дальномера, а определение пройденного пути осуществляется с помощью одометрической подсистемы с применением метода пассивного колеса. Построение карты происходит одновременно с исследованием внешней среды.
Пусть в начальный момент времени внешняя среда не исследована, а робот находится в центре свободного участка (участок 0 на рис.1), который считается началом координат создаваемой карты.
Рис. 1. Траектория движения робота при составлении карты |
|
Участки с номерами 1-8 считаются потенциально проходимыми. Для уточнения их проходимости робот осуществляет последовательное сканирование данных участков. Сканирование начинается с участка номер 1. Если данный участок свободен, то выполняется перемещение в среде в направлении центра первого участка как показано на рис. 1. Причем величина перемещения равна максимальному из габаритных размеров участков, на которые дискретизируется среда. После этого считается, что робот переместился в центр следующего свободного участка. При этом координаты центра данного участка, рассчитываемые по формулам 1 и 2, наносятся на карту.
; (1)
. (2)
Здесь 
, 
– абсцисса и ордината центра предыдущего участка, 
– величина перемещения, 
– курсовой угол робота. В формуле (1) выбирается знак «+», если i-й участок расположен правее i-1 и знак «-», если левее. В формуле (2) знак «+» выбирается, если i-й участок расположен выше, чем i-1-й, и «-», если ниже. Также наряду с координатами центра каждому участку ставятся в соответствие индексы смещения по координатным осям X, Y относительно начального участка (участок 0 на рис. 1). Это делается для того, чтобы упорядочить хранение карты среды в памяти робота в соответствии с индексами участков. После того, как робот нанес информацию о первом участке на карту, он сканирует проходимость участков 2, 3, ..., 8 двигаясь против часовой стрелки по периметру участка 0, как показано на рис. 1. Если какой-то из данных участков оказывается занятым, то робот определяет находится ли на нем препятствие либо цель и вносит информацию о данном участке на карту. После обследования участков 1-8 робот расширяет зону исследований и переходит к сканированию участков 9-23 и т. д. Данный процесс продолжается до тех пор, пока во внешней среде не останется ни одного неисследованного участка. После этого в памяти робота формируется карта его рабочей зоны. Следует отметить, что описанная методика формирования карты позволяет увеличить точность определения координат ее участков, так как координаты каждого участка определяются не в глобальной, а в локальной системе координат. Также упрощается процесс локализации робота. Зная смещение робота (
, 
) относительно центра текущего участка можно определить индексы данного участка по следующим формулам:
; (4)
. (5)
После составления карты среды робот должен использовать ее в процессе перемещений к цели. Однако, полученная карта не может быть абсолютно точной из-за погрешностей измерений. Поэтому робот после каждого перемещения должен выполнять уточнение карты, позиции на ней, а также значение своего курсового угла, используя информацию об окружающей обстановке, получаемую при помощи подсистемы технического зрения. Пусть локализация на основании формул (4), (5) дает приблизительную оценку текущего положения. При этом предполагается, что робот находится в области, состоящей из множества свободных участков 
, размерами K´M участков, центральный элемент которой имеет индексы [
, 
]. Предположим, что в результате работы зрительной подсистемы сформирован план проходимости внешней среды 
в радиальной системе координат, представляющий собой массив элементов размерностью W
H, каждый из которых может хранить информацию о том, что данный участок свободен, содержит цель или препятствие определенного типа. Тогда робот формирует копию данного плана 
, используя созданную карту, и информацию о текущем курсовом угле и рассчитывает эвклидову меру сходства двух планов по формуле (6):
(6)
с запоминанием значений 
, 
. Далее система управления выполняет изменение курсового угла без поворота робота и формирует новую копию плана по значению этого угла с последующим сравнением с оригиналом и запоминанием новых значений 
и 
. При этом робот «осматривается», находя наилучшее соответствие между тем, что он видит и тем, что нанесено на карту. Данный процесс повторяется до тех пор, пока очередной рассчитанный угол не совпадет с начальным. После этого из множества значений , полученных для данного участка, выбирается и запоминается вместе с курсовым углом, обеспечивающим минимальное расхождение между зрительными данными и информацией, полученной из карты. Также запоминаются и индексы [, ] данного участка в карте. После этого в качестве кандидата на роль текущего участка нахождения робота выбирается следующий участок из множества 
и для него повторяется описанная выше процедура. Данный процесс повторяется до тех пор, пока для всех областей, входящих в не будут вычислены оптимальные значения и по приведенной выше методике. После этого происходит заключительное сравнение для всех участков, принадлежащих , и выбор минимального из них с запоминанием соответствующего ему значения курсового угла . После этого [, ] определяют координаты текущего участка нахождения робота на карте среды, а принимается в качестве курсового угла робота.
Далее робот может произвести акт движения по карте, причем планирование маршрута движения к цели осуществляется согласно бионическому методу управления мобильным роботом на основе нейропроцессорных сетей [1, 3]. Данный метод выбран в силу того, что экспериментальные исследования подтвердили его высокую эффективность (метод гарантирует, что если в среде существует оптимальный путь к цели, то он будет найден).
Пусть робот имеет в своем составе сенсорную подсистему (СП), подсистему, подсистему формирования модели внешней среды (ПФМВС), отображающую сеть (ОС), сеть афферентного синтеза (САС), сеть принятия решений (СПР), подсистему определения собственного положения (ПОСП) и эффекторную подсистему (ЭП). Пусть цель задана на карте и не попадает в зону восприятия СП робота. Тогда процедуру определения направления движения на каждом шаге выполняется в два этапа [1, 3]. На первом этапе карта в масштабе отображается в САС, где определяется направление глобального перемещения без его отработки в ЭП. Информация об этом направлении с выходов СПР отображается в тот процессор дальнего ряда радиальной САС, который соответствует выбранному направлению. На втором этапе в САС отображается информация с выходов СП, а выбранный на предыдущем этапе процессор используется в качестве целевого. Решение, принятое СПР на втором этапе, поступает в ЭП и отрабатывается исполнительными устройствами робота. После этого в САС вновь считывается карта среды, но с учетом произошедшего перемещения робота. Вновь определяется промежуточная цель, определяется и отрабатывается следующее направление движения и т. д. до выхода в зону цели [3].
Введем следующие обозначения [1]:
– функционал, определяющий возможные расстояния между целью 
и текущим положением робота 
на карте среды, представленной в масштабе М;
– вектор, определяющий промежуточное положение цели на плане в САС;
– единичный вектор направления к цели на карте среды;
- максимальный радиус радиального плана САС;
– функционал, определяющий допустимые расстояния между истинным положением робота 
в среде и промежуточной «воображаемой» целью на плане в САС;
– оператор коррекции текущего положения робота на карте, действующий по методике, описанной выше;
– единичный вектор направления на промежуточную цель;
– модуль скорости робота;
– модуль вектора градиента;
– длина траектории.
Тогда, в соответствии с бионическим методом управления, алгоритм движения к цели по карте может быть сформулирован следующим образом [1]:
1. 
2. если 
, то 11, иначе – следующий шаг;
3. 
4. 
5. 
6. 
7. 
8. определить , положить 
9. 
( шаг в направлении );
10. 
, перейти к 1;
11. если 
то останов, иначе – следующий шаг;
12. 
13. определить 
14. определить ;
15. 
(шаг в направлении 
), перейти к 1.
Данный алгоритм построен так, что в начале осуществляется проверка наличия цели в поле зрения робота, и если цель отсутствует, то в пунктах 3-9 выполняется процедура движения по карте, а в пункте 10 – коррекция положения робота на карте среды. В случае попадания цели в зону восприятия СП карта не используется и происходит движение к цели только на основе сенсорной информации (пункты 11-15).
Экспериментальная проверка предложенной методики проводилась на специально разработанной моделирующей программной среде, реализованной в операционной системе Windows (см. рис. 2) с использованием компилятора Borland Delphi 7.0. Эта среда включает программную модель адаптивного мобильного робота, редактор внешнего окружения с возможностью задания положений робота, препятствий и цели, а также подпрограммы формирования карты среды, синтезированной на основе описанной методики и подпрограммы навигации робота по карте на основе описанного выше алгоритма. На данной программной модели был проведен ряд экспериментов, один из которых показан на рис. 2, на котором представлена внешняя среда типа «лабиринт».
Рис. 2. Основное окно программной среды моделирования
В задачу робота входило исследование среды с целью составления ее карты и нахождение цели. Эксперимент проводился в два этапа. На первом этапе робот осуществлял построение карты внешней среды, двигаясь из начальной точки (см. рис. 2) в соответствии с предложенной методикой. В результате была сформирована карта, показанная на рис. 3, на котором белым цветом отмечены участки свободные для перемещения робота, черным – участки, занятые препятствием, а серым – целевой участок. На втором этапе робот помещался в начальную точку движения. При этом его задачей являлось нахождение оптимального (в смысле длины траектории пути движения к цели). Действуя в соответствии с описанным алгоритмом навигации по карте робот достиг цель по траектории, показанной на рис. 2, которая, очевидно, является наиболее оптимальной из всех траекторий, ведущих к цели.
Рис. 3. Окно отображения карты среды
Таким образом, применение описанного метода формирования карты среды совместно с нейросетевым методом навигации по ней позволяет роботу строить карту внешней среды и эффективно планировать траекторию движения к цели.
Список литературы
1. Чернухин сети. Таганрог: ТРТУ, 1999, 439 с.
2. David Fillat, Jean-Arcady Meyer. Map based navigation in mobile robots: A review of localization strategies. Preprint to Elsevier science. 58 c.
3. Однородные управляющие структуры адаптивных роботов // , Чернухин Ю. В. и др. М.: Наука, гл. ред. физ.-мат. лит., 19с.
