Навигация сервисного робота на поле для гольфа. Построение пути и обход препятствий

Какой метод навигации и обхода препятствий оптимален для сервисного робота?

Роботы — это программно-механические комплексы, взаимодейсвующие с реальным миром. Для сервисного робота крайне важно понимать свое текущее положение в пространстве, положение цели и умение построить маршрут до цели с обходом возможных препятствий. Мы разрабатываем робота для сбора мячей для гольфа на driving range ^[1]. Мы рассматривали разные варианты построения маршрута, чтобы найти оптимальный для себя, возможно кому-то эта информация окажется интересной.

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

Но данный алгоритм не получится применить, если перед роботом внезапно возникло препятствие. Двигаясь по прямой, ровер не сможет обогнуть его или пройти сквозь. В связи с чем он просто останавливается перед препятствием и не двигается дальше.
Как обойти препятствие? Легче всего решить возникшую проблему поможет вариант поведение, именуемый «избегание препятствий». Практически он представлен различными алгоритмами.

Алгоритм Walk To

Если цель не достигнута:

• Двигаться к цели.
• Иначе: остановиться.

Такой способ подойдет, если в мире находится исключительно робот и цель, которую он должен достигнуть. Прямая позволит дойти до конечной конфигурации максимально быстро. Но какой алгоритм применить, если на пути к цели перед роботом возникло препятствие?
Препятствие не дает роботу добраться до пункта назначения по прямой, ровер в такой ситуации просто останавливается перед ним. В таком случае также можно использовать алгоритм «Walk To», но его требуется дополнить.

Алгоритм Bug

В обычной жизни человек, когда идет из одного пункта в другой к цели и натыкается на препятствие, просто обходит его. Такой вариант поведения именуется «избегание препятствий». Его получится применить для достижения цели роботом. Проще всего применить алгоритм жука.
Алгоритм Bug назван специалистами именно так ввиду того, что за основу здесь взято поведение жука — если он видит препятствие, то обходит его.
Шаги, которые проходит робот во время движения к цели (в том числе при обходе препятствия), называются траекторией.

Алгоритм жука послужил основой для концепций, которые используются при построении маршрутов более сложного типа. К ним относятся:
Концепция траектории. Это простая последовательность передвижений робота, которые он совершает, чтобы достигнуть конечной цели. Алгоритм жука также является «Планировщиком траектории». Получив координаты точек, на которых расположены робот и его цель, алгоритм разрабатывает соответствующую траекторию перемещения.
Концепция политики. Если при помощи алгоритма жука роботу передаются определенные инструкции по перемещению, то такой способ построения маршрута именуется «Политикой Управления».
Концепция эвристики. Так именуется правило, применяемое, чтобы сообщать роботу о дальнейшем этапе алгоритма. В данной ситуации эвристикой является линия, по которой передвигается объект. При создании пути необходимо грамотно определить эвристику. Если сделать это неправильно, то построенный маршрут будет неработоспособен.
Однако, такой алгоритм ограничивает разработчика, потому что с его помощью удастся построить маршрут, который ограничен по размерам. При использовании такого алгоритма построения пути необходимо, чтобы все препятствия принимали форму выпуклого многоугольника.
Также у алгоритма Bug есть ограничения:

• Препятствия должны находиться на определенном расстоянии друг от друга, нельзя, чтобы у них были точки соприкосновения;
• Границы препятствий — замкнутые кривые, при этом они должны быть такими, чтобы прямая, по которой движется робот, пересекала каждую из них ограниченное количество раз;
• Робот — несоизмеримо малая точка, поэтому он может двигаться между препятствиями независимо от прохода между ними.

Некоторые из этих ограничений получится преодолеть, если воспользоваться усовершенствованным алгоритмом DH-Bug. Его особенность заключается в том, что с его помощью робот сможет справиться с движущимися препятствиями. При этом такой алгоритм состоит из двух слоев. Первый — совещательный. Он позволяет предварительно оценить маршрут без использования дополнительных сведений. Второй слой — адаптивный. Благодаря ему робот своевременно реагирует на возникшие препятствия, которые не были заложены в программе изначально.

Алгоритм CBUG

Алгоритм CBUG — версия построения маршрута таким способом, в которой учтены все детали. При его разработке специалисты приняли во внимание размер робота, а также решили вопросы, связанные с оптимизацией создаваемого пути. Отличительной чертой такого усовершенствованного алгоритма является то, что для генерации маршрута нужно, чтобы начальная точка всегда оставалась в памяти объекта. Неизменно для алгоритма CBUG только то, что для его применения необходимо иметь фиксированный объем памяти.

Алгоритм Дейкстры

Алгоритм, который используется на графах, был создан Э. Дейкстрой во второй половине прошлого века. С его помощью получится определить кратчайший путь от одной из вершин графа до других. Такой алгоритм завершается в момент, когда робот посетил все вершины. Если катались те, на которых он ещё не побывал, выбирается вершина, имеющая минимальную метку.

К достоинствам алгоритма Дейстера относятся:

• Обращение внимания на длину пути и его стоимость;
• Узлы обновляются в случае, если был найден более оптимальный.

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

Алгоритм Беллмана-Форда

Но часто возникают ситуации, при которых необходимо построить маршрут, где присутствуют ребра с отрицательным весом. Решить такую проблему поможет алгоритм Беллмана-Форда. Если в результате у конечного пути сумма весов ребер принимает негативное значение, то он именуется отрицательным циклом.

Алгоритм Джонсона

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

Алгоритм A*

Чтобы найти наиболее оптимальный путь используя графы, требуется применить алгоритм A*. Он позволяет определить наилучший маршрут от робота до цели по первому совпадению на графе. В основе этого алгоритма лежит формула эвристики, которая выглядит следующим образом:

f(n)=g(n)+h(n).
f(n) - значение оценки, которое назначено узлу n.
g(n) - минимальная стоимость достижения узла n от робота.
h(n) - эвристическая оценка расстояния от начальной вершины до конечной цели.

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

Алгоритм волновой трассировки

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

1. Инициализация;
2. Построение волны;
3. Восстановление маршрута.

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

Алгоритм Discretize Space

1. Конфигурационное пространство имеет неизменный размер во всех измерениях.
2. Дискретезировать все измерения так, чтобы в них присутствовало постоянное число ячеек.
3. Все ячейки, расположенные в конфигурационном пространстве внутри препятствия, отметить как непроходимые.
4. В результате все проходимые ячейки превратились в узлы.
5. Каждый узел соединяется со всеми соседними в графе.

Рандомизированный поиск пути

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

Алгоритм Probabilistic Road Maps

• 1. Создать пустой граф G.
• 2. Добавить на граф G узлы робота и его конечной цели.
• 3. За N-ное количество интеграций:
• 1. Найти однородную случайную выборку конфигурационного пространства и дать ей имя R.
  2. Если робот в коллизии при конфигурации R, то можно продолжить.
  3. Иначе: добавить R к графу G.
• 4. Определить все узлы в графе, которые располагаются в пределах точек d и R.
• 5. Для всех узлов N, которые подходят под этот параметр:

Алгоритм Rapidly Exploring Randomized Trees

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

1. Создать незаполненное дерево T.
2. Добавить к T первоначальную конфигурацию робота.
3. До момента, пока цель не достигнута:
   1. Провести выборку для узла R.
   2. Определить в T узел, расположенный к R ближе всего. Дать ему имя K.
   3. Передвигать робот от K до R, пока не будет выполнено следующее условие:
      1. При коллизии переходить к определению случайной выборки.
      2. Иначе: добавить к T новый узел в данной конфигурации.
      3. Если достигнуто максимальное расстояние между d и K, вновь начать работать над случайной выборкой.
4. Решение получено, если узел цепи расположен в пределах расстояния d от любого узла T.

Вывод

Для оптимальным является разделение вопроса построения маршрута на глобальный и локальный. Глобальный маршрут — это список целевых точек для обхода поля или цель возврата на базу. Локальный маршрут начинает строится когда ультразвуковые датчики или бампер обнаружили препятствие.
Так как в нашей специфике все препятствия имеют выпуклую форму мы используем простейший алгоритм BUG, и даже проще. Некий «пацанский» метод навигации. Ровер при обнаружении ультразвуком препятствия поворачивает по часовой стрелке на 90 градусов, проезжает 1м, поворачивает на 90 против часовой стрелке. При обнаружения препятствия бампером перед поворотом робот на 0.5 метра возвращается назад.

Планы

За время старта проекта летом 2018г. произошло огромное количество событий. Мы готовим пост о развитии нашего проекта. Спасибо за внимание!

Ссылки

• Разработка робота для сбора мячей для гольфа ^[2]
• Попытка изготовления корпуса для робота при ограниченном бюджете. Стекломат и эпоксидная смола ^[3]
• Проектирование сервисного робота. Постановка задачи, архитектура решения ^[4]
• ArduPilot для новичков. Установка и настройка на BeagleBone Blue ^[5]
• Изготовление корпуса для робота при ограниченном бюджете. Вакуумная формовка ^[6]

Автор: webzuweb

Источник ^[7]