Навигация мобильного робота в динамической среде

Материал из BrSTU Robotics Wiki
Перейти к: навигация, поиск
Навигация мобильного робота в динамической среде
Тема Алгоритмы навигации
Исполнитель Никонович Валентин, ИИ-3
Руководитель Головко В.А.
Консультант Кабыш А.С.
Язык программирования Python
Операционная система Linux
Год выполнения 2011
Использованные роботы Моделирование ROS/Stage

Цель дипломной работы

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

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

  • Исходные данные робота для мониторинга помещений: планировка здания, планировка каждой из комнат.
  • Комплектация робота: устройство позиционирования; компас; комплект дальномеров, покрывающих фронтальный сектор.

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

Концепция навигационной системы

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

Навигация высокого уровня

Граф планировки этажа

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

Навигация среднего уровня

Пример дискретизации пространства
Когнитивная карта и аппроксимация контуров

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

Построение когнитивной карты и аппроксимация контуров препятствий

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

Навигация низкого уровня

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

Алгоритм навигации

Визуальная иллюстрация работы алгоритма навигации