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

Может быть, эта тема кому-нибудь будет интересна, поэтому добавлю немного от себя. Алгоритм RRT не является оптимальным. Существует его оптимальная (в пределе) версия RRT*.

Помимо поиска в конфигурационном пространстве, где мы учитываем только кинематику нашего робота и принимаем, что полученный путь может быть в дальнейшем исполнен нашим контроллером, можно искать путь сразу в пространстве управления. В этом случае мы можем определить динамическую модель робота (от ручных дифференциальных уравнений до какого-то физического движка) и использовать ее. Это называется в kinodynamic planning и дает преимущество для управления роботами с какой-то сложной динамикой. Сложность заключается в переходе к случайно сгенерированному узлу. Здесь надо определить функцию steer, позволяющую определить необходимое управление для перехода из одного состояния в другое (т.е. решить обратную задачу). В общем случае, это весьма нетривиально нереально. В простейшем — рандомный выбор. Думаю, понятно, сколько шагов потребуется солверу.

Поиграться с разными sample-based солверами можно в библиотеке Open Motion Planning Library, в которой реализованы RRT, RRT* и ряд других.

И встречал весьма оригинальный метод, как сделать это несколько проще, моделируя систему робот+контроллер:

• Motion Planning for Urban Driving using RRT
• Motion Planning in Complex Environments using Closed-loop Prediction

А вот у меня в процессе чтения возник вопрос.

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

У вас робот оснащен компасом/одометрией, чтобы точно поворачивать и ездить?

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

Отличный подбор алгоритмов. Спасибо автору! Вспомнилось, как писали алгоритм построения маршрута уборки для промышленной поломоечной машины внутри рандомного прямоугольника многократно превышающего размеры робота с рандомным набором препятсвий внутри. И вычисление этого маршрута за адекватное количество переборов и оптимизаций. Для нас решением стало применение огромного ряда эвристик, какой бы базовый метод мы не выбирали.

Вопрос. Робот предназначен для сбора мячей. Каким образом вы задаете целевую точку движения для робота? Т.е. как он понимает куда ему ехать(где сейчас находится мячик)? Или в итоге он все равно проезжает все поле?