Карты рабочей зоны для мобильного робота

Васильев Иван Анатольевич, Санкт-Петербург, ЦНИИ РТК, нач. лаб., к.т.н.

 

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

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

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

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

Итак, картографирование осуществляется в три приема:

1.      Привязка текущих измерений дальномера к карте с учетом текущего положения робота;

2.      Упорядочивание текущих точек на текущей карте;

3.      Построение карты с учетом новых точек.

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

,

где      - угол поворота робота относительно нуля – начального положения;

            х и у – смещения робота относительно нуля – начального положения.

Тогда текущие координаты точки, измеренной дальномером, будут такими:

,

где       и  - локальные координаты точки, измеренной дальномером.

Вторая задача – упорядочивание текущих точек на известной карте – сложнее. Дело в том, что со времени создания известной карты могли произойти изменения. Требуется не только внести эти изменения в карту, но и не упустить старые, известные, препятствия, которые могут быть заново измерены.

Карта представляет собой набор отрезков, в которых известны три точки – две концевых и средняя. Средняя точка берется для устойчивости алгоритма аппроксимации. Для повышения точности следовало бы запоминать все точки, но это довольно быстро приведет к тому, что программа управления будет требовать ресурсы, превышающие возможности любой вычислительной системы, так как количество точек, с которыми одновременно будет производиться работа, может превышать любое разумное число. Например, для популярного дальномера SICK LMS-290 за 1 минуту работы количество измерений превышает 20 000. За час работы точки будут считаться уже миллионами. Поэтому и требуется некоторым способом «сжимать» полученную информацию. Рассмотрим рисунок 1.

На этом рисунке обозначены точки: 1 и 2 – конечные точки отрезка, m – средняя точка, 3 – новая, упорядочиваемая точка, Lij – расстояние между точками i и j, жирной линией обозначен сам отрезок. Если точка «слева» или «справа» от отрезка она может как уточнять сам отрезок, так и принадлежать соседнему, смежному, отрезку, если такой есть. Если она принадлежит смежному, то тогда она должна быть упорядочена уже в нем.

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

,

где      (,) и (,) – координаты двух конечных точек отрезка;

            х и у – координаты новой точки.

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

 

Рисунок 1 – иллюстрация упорядочивания точек

 

Итак, точки упорядочены. То есть, имеется набор точек, которые требуют внесения в отрезки.

Аппроксимация прямолинейными отрезками производится по методу наименьших квадратов. Сами отрезки задаются обычным уравнением прямой с угловым коэффициентом:

В этом уравнении два параметра a и b, следовательно, для их нахождения требуются два уравнения. Поэтому, для метода наименьших квадратов применяется система из двух уравнений:

,

где      - оператор производной по переменной k;

            n – количество измерений;

            a – искомый угловой коэффициент прямой;

            b – искомый коэффициент смещения прямой;

            xk, yk – k-тые абсцисса и ордината (измеренные).

 

Решение этой системы выглядит так

                                          

 

Теперь для каждого уточненного отрезка требуется найти крайние точки. Для каждой из них это делается как нахождение точки прямой, находящейся максимально близко к бывшей крайней точке:

,

где      (,) – координаты бывшей крайней точки.

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

Рассмотрим другой метод построения карты. В этом методе проблема «сжатия» информации решается просто. На карте строится сетка, размер ячеек которой не должен превосходить допустимой погрешности. Например, для случая, когда не требуется заранее решать задачи проезда в узкости, размер ячейки разумно выбрать как половину от ширины робота, возможно, расширенной на величину зоны безопасности.

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

Оба приведенных здесь метода построения карт широко используется для мобильных роботов, разработанных и разрабатываемых в ЦНИИ РТК.

 

 

 

Литература

 

1. Springer handbook of robotics. // под. ред. Bruno Siciliano, Oussama Khatib, «Springer» - 2008

2. С.Ф.Бурдаков, И.В.Мирошник, Р.Э.Стельмаков. Системы управления движением колесных роботов. СПб, «Наука»-2001

3. Lyashin A.M., Vasilyev I.A. Localization and trajectory motion control of a mobile robot with tank-like chassis setup, equipped with laser rangefinder and machine vision system. // Труды конференции «Mechatronics & Robotics ‘04» Aachen – Germany. P. 469-470

4. С. Л. Зенкевич, А.А. Минин. Построение карты мобильным роботом, оснащенным лазерным дальномером, методом рекуррентной фильтрации. // «Мехатроника, автоматизация, управление», №8, 2007, стр. 5-12

5. Г.Корн, Т.Корн. Справочник по математике для научных работников и инженеров. // М. «Наука» - 1984

6. Построение карты окружающего пространства для колёсного робота, снабжённого лазерным сканирующим дальномером. // Труды XXI Международной научно-технической конференции «Экстремальная робототехника» - 2010