Назад в библиотеку

---

Алгоритм нахождения возможного пути перемещения автономного мобильного робота

Автор: М. А. Таранухин, А. О. Одиноченко
Источник:Работы Одесcкого политехнического университета

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

Исследованиям в этой области посвящено большое количество работ, что привело к значительным достижениям в разработке конструкторских и алгоритмических решений для автономных мобильных роботов. Подтверждением может служить, например, организация соревнований по передвижению автономных роботов на большие расстояния, как по пустынной местности, так и в городских условиях [1]. Тем не менее, актуальность дальнейших разработок алгоритмов передвижения автономных роботов является очевидной, вследствие ещё недостаточно широкого использования роботов в человеческой деятельности,

Для успешного передвижения таких роботов одним из важных факторов является решение навигационной задачи в ближней зоне движения, которая реализуется с помощью систем технического зрения, лазерных дальномеров и других сенсоров [2…6].

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

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

Разработанный алгоритм можно разделить на три функциональные части:

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

Задача расчета текущей позиции робота в пространстве известна как Simultaneous localization and mapping (SLAM, [8]. Решение базируется на кадрах дальности и RGB – изображении, полученных с сенсора Kinect и включает такие этапы:

• расчет величины смещения робота относительно предыдущего положения как вектор t = (x, y, z). Здесь каждая компонента вектора соответствует смещению по каждой из осей в 3х мерном пространстве.
• нахождение матрицы поворота.

На первом этапе находятся особые точки на каждом кадре, производится их сопоставление и выполняется трилатерация [9].

Для нахождения особых точек был использован хорошо зарекомендовавший себя на практике метод Speeded Up Robust Features (SURF) [10], реализованный во многих открытых библиотеках программ. Идентифицировав одни и те же особые точки на разных кадрах RGB – изображений и зная расстояния до них r_i (из соответствующих кадров дальности) мы можем рассчитать перемещение робота, относительно предыдущей позиции, и, в конечном итоге, относительные координаты x, y, z робота.

С геометрической точки зрения задача трилатерации представляет собой нахождение координат точки пересечения трех сфер, которые определяются путём решения системы уравнений

Решение данной системы уравнений даёт вектор смещения t = (x, y, z).

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

Зная вектор смещения, а так же имея по три точки с текущего и предыдущего кадра, легко найти матрицу поворота путем решения трех систем линейных уравнений вида:

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

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

Анализ окружающего пространства и выбор возможных направлений движения робота осуществляется на основе определения препятствий, встречаемых на его пути. Для определения препятствий производится анализ множества точек на RGB – кадре и кадре дальности, полученных на выходе сенсора Kinect. Цель анализа – разбиение облака точек на два множества: точки, принадлежащие поверхности движения (и, следовательно, не являющиеся препятствием для движения) и точки, не принадлежащие поверхности движения (следовательно, являющиеся препятствиями). В качестве критерия разбиения учитывалось уравнение плоскости, построенное по трем точкам А, B, C, лежащим на поверхности движения. Если при подстановке в уравнение произвольной точки из облака получаем тождественное равенство нулю, то точка считается принадлежащей плоскости, т. е. поверхности движения. В противном случае, точка относится к множеству препятствий.

На основании координат точек из множества препятствий производится анализ расстояний от электромобиля до препятствий. Следует отметить, что особый интерес представляют наиболее близко расположенные препятствия. Для этого из всего облака точек препятствий, выбирают элементы с минимальным расстоянием до робота для каждого из направлений (то есть для каждого угла азимута анализируются все видимые сенсором углы места). Полученный массив точек является «линией препятствий» и используется для определения направления движения.

На рис. 1 схематически изображено расположение линии препятствий, полученных в результате анализа. Свободной зоной для движения робота считается последовательность точек линии, длиной не менее n элементов, каждый из которых находится не ближе, чем на расстоянии Q, т. е. удовлетворяет условию:

Логика передвижения робота зависит от его функционального назначения и учёта его конструктивных ограничений. Для проверки эффективности предложенного алгоритма был использован рекламный робот на базе электромобиля. Габаритные размеры робота 1,2м × 0,6м × 0,6м. Исполнительные механизмы – два двигателя постоянного тока, вращающие задние колёса, и третий двигатель, поворачивающий передние колёса. Робот оборудован сенсором Kinect и типовым ноутбуком, который производил все вычисления. В задачу робота входило прямолинейное движение до появления препятствия на пути. При наличии препятствия осуществляется поворот налево до исчезновения препятствия на новом прямолинейном пути. При невозможности движения налево производится поворот направо Если и это невозможно, то робот отъезжает назад, пока не появится возможность повернуть налево или направо и двигаться вперёд. Если движение невозможно, то робот останавливается до появления возможности движения. Испытания робота производились в большом зале, где случайным образом была расставлена мебель, стояли и передвигались люди, что классифицируется как сложная и динамично меняющаяся окружающая обстановка. В ходе испытаний робот демонстрировал квазислучайное передвижение по залу, избегая при этом наезда на людей и препятствия. Все участки зала посещались роботом с примерно одинаковой частотой.