Введение 3
Постановка задачи 4
Обзор литературы 5
Глава 1. Система навигации мобильного робота 7
1.1. Описание движения мобильного робота. 7
1.2. Структура системы навигации. 8
1.3. Алгоритм SLAM 10
1.4. Построение карты окружающей среды в виде карты-сетки. 11
1.5. Трассировка препятствий 12
Глава 2. Планирование пути мобильного робота 13
2.1. Общая структура планирования 13
2.2. Алгоритмы обхода препятствий 13
2.2.1.Алгоритм Дейкстры 14
2.2.2.АлгоритмA* (A-star) 16
2.2.3.АлгоритмA* (A-star) для колесных роботов 17
2.2.4.Алгоритм D* (D-star) 19
2.3. Метод эффективного пути 21
Глава 3. Результаты программной реализации 23
3.1. Построение карты препятствий 23
3.2. Реализация рассмотренных алгоритмов 24
3.3. Сравнение точности и скорости рассмотренных алгоритмов 27
Выводы 28
Заключение 28
Список литературы 30
Приложение

Купить

В настоящее время тема робототехники и, в частности, движения в среде с препятствиями является актуальной и используемой во многих сферах жизни. Мы можем встретить автономных роботов, например, в квартирах, в виде робота-пылесоса, в музеях и на экскурсиях в виде робота экскурсовода, в автомобилях с системой автоматической парковки, в космосе и это далеко не все сферы применения данной технологии. Многие крупнейшие компании, такие как “Tesla” и “Google”, работающие над созданием так называемого автомобиля без водителя, занимаются реализацией подобных технологий.
Несмотря на то, что нас окружает уже довольно большое количество автономных роботов, данная тема остается актуальной, так как существует большое количество сфер для ее применения. Кроме того, использование автономных роботов необходимо для выполнения работы, которая является опасной либо непосильной для человека. Например, в труднодоступных местах, таких как космос, океаны и других.
Задача построения траектории обхода препятствий состоит из множества подзадач:
• Построение траектории в детерминированной среде со стационарными препятствиями – базовая подзадача, которая может быть применена на практике. Сферы применения: помещения, в которых отсутствуют объекты, меняющие со временем свое местоположение. Данная подзадача решается с помощью алгоритма A* и алгоритма Дейкстры;
• Построение траектории в недетерминированной среде со стационарными препятствиями – подзадача, сфера применения которой – совершение движения в неизвестной местности. Роботы, способные автономно передвигаться в недетерминированной среде, могут быть использованы как в помещениях для выполнения стандартных сервисных функций, так и для исследования новых территорий, труднодоступных для человека. Данная подзадача может быть решена с помощью алгоритма D*
• Построение траектории в недетерминированной среде с динамическими препятствиями – самая актуальная из подзадач. Сфера применения роботов, способных автономно передвигаться в дан-ной среде, практически не ограничена. Возможность решения этой подзадачи на сегодняшний день зависит от множества факторов, таких как скорость движения подвижных объектов, возможность приближенно предсказать местонахождение препятствий в следующий момент времени и многих других. Одним из вариантов решения данной подзадачи является система навигации, рассмотренная в первой главе.
В настоящее время самыми часто используемыми автономными подвижными объектами по причине удобства их использования являются мобильные роботы. В связи с этим рассматривается задача построения навигационной системы именно для данного типа роботов.
Постановка задачи
Разработать методы планирования траектории подвижного объекта, способного совершать автономное движение в различных средах.
Цели работы:
• Анализ известных методов построения навигационной системы, позволяющей мобильным роботам совершать автономное движение в различных средах;
• Создание навигационной системы, позволяющей совершать автономное движение на плоскости (2D);
• Разработка программного обеспечения (ПО), реализующего рас-смотренные алгоритмы обхода препятствий. Представить с помощью ПО следующие сведения: траектория, схематичное движение робота по карте.
• Оптимизация полученной траектории.
Обзор литературы
На сегодняшний день существует множество методов, применяемых для управления роботом в среде с препятствиями. К ним можно отнести метод структурного синтеза, использование нечеткой логики, построение навигационной системы, основанной на алгоритме SLAM.
Метод структурного синтеза, рассмотренный в [1, 2] является синергетическим методом. Главной особенностью данного метода является задание цели управления, а управление рассматривается в виде аттракторов. В работах [3, 4] рассматривается закон управления, позволяющий строить асимптотически устойчивое движение.
Мобильные роботы, основанные на использовании нечеткой логики, применяются для решения различных задач планирования движения автономных подвижных объектов. В работе [5] предложен метод, позволяющий управлять мобильным роботом в недетерминированной среде со статически-ми препятствиями. В статье[6] представлены методы, основанные на использовании нечеткой логики и позволяющие подвижным объектам перемещаться в среде с динамическими препятствиями.
В статье [7] представлен метод управления роботом в трехмерной среде с точечными препятствиями. Данный метод создан на базе позиционно траекторного закона управления. Рассматривается движение объекта вдоль траекторий, состоящих из прямых линий.
В работах [8, 9] рассматривается проблема генерации стратегии в сложных задачах в условиях отсутствия полной информации о внешней среде. Проведен ряд экспериментов, доказывающих эффективность предложенного метода, заключающегося в способности системы самостоятельно генерировать шаги в среде с неполной информацией.
Один из самых эффективных методов управления подвижными объектами в среде с препятствиями предложил Герасимов В. Н. в своей диссертации[10], в которой представил разработанную им систему, основанную на использовании алгоритма SLAMдля локализации мобильного робота и построения динамической карты окружающей среды. Кроме того данная система позволяет строить траекторию, используя различные известные алгоритмы построения траектории в среде с препятствиями. На данный момент известно множество алгоритмов, позволяющих строить траекторию обхода препятствий в различных средах, в следствии чего сфера применения предложенной системы очень велика.
Алгоритм SLAM, подробно разобранный в работе [11] на сегодняшний день является очень популярным и эффективным. Задача навигации мобильного робота в недетерминированной среде с ограниченной областью действия сенсорных датчиков была решена с использованием данного алгоритма в работе [12].
Наиболее популярными алгоритмами построения траектории обхода препятствий являются алгоритм Дейкстры, алгоритм A* и алгоритм D*.
Алгоритм Дейкстры является базовым алгоритмом, разработанным Эдсгером Дейкстрой в 1959 году. Несмотря на то, что на данный момент этот алгоритм в большинстве случаев является слишком медленным, в следствии чего редко применяется на практике, ему до сих пор можно найти применение в некоторых сферах. В работе [13] с помощью данного алгоритма была решена проблема использования модели сети дорог с параметрами для про-кладки кратчайшего пути.
Алгоритм А* является усовершенствованной модификацией алгоритма Дейкстры, разработанной Нильсом Нильсоном, Бертрамом Рафаэлем и Пите-ром Хартом. Его основным отличием являет использование эвристики, благодаря которой значительно повышается скорость работы алгоритма с сохранением оптимальности траектории по длине пути. Задача построения траектории обхода препятствий с использованием данного алгоритма и после-дующего применения к полученной траектории метода эффективного пути рассмотрена в [14, 15].
Алгоритм D*, разработанный Свеном Кёнигом и Максимом Лихачевым в 2002 году, позволяет строить траекторию обхода препятствий в недетерминированной среде. Задача построения траектории обхода препятствий с помощью данного алгоритма была рассмотрена в [16].

Купить