Алгоритмы планирования пути для роботизированных приложений должны находить оптимальный маршрут через возможные области пространства на каждом этапе. Одним из простейших алгоритмов планирования пути для поиска маршрута является быстрое исследование случайного дерева (RRT), предложенное Стивеном Лавалем [1]. RRT использует жадную эвристику для охвата всего пространства, что делает его действительно эффективным. Существует вариант RRT*, который может найти оптимальный маршрут [2].
Основные этапы построения RRT следующие:
- Случайный узел – выберите узел случайным образом и убедитесь, что в нем нет коллизий.
- Ближайший сосед — получение ближайшего узла к заданному случайному узлу.
- Интерполированный узел — добавляет новый узел на определенном расстоянии от ближайшего узла в направлении случайного узла.
Пример RRT, охватывающий двумерное пространство, показан на рисунке 1 с кодом, размещенным на Github.
Есть несколько желательных свойств RRT, которые делают его широко используемым алгоритмом планирования пути:
- Сходимость — RRT быстро сходится из-за того, что единственной операцией является измерение расстояния относительно случайного узла.
- Никаких предположений о пространстве состояний — его можно использовать в невыпуклом многомерном пространстве.
- Ограниченный — может использоваться для различных ограничений, управляющих физическими системами.
- Предвзятость к неизведанному пространству — предпочтение отдано большим районам Вороного, чтобы выбрать самые большие неисследованные регионы.
Я хочу подключить оригинальную веб-страницу RRT Стива Лаваля.
[1] ЛаВалле, С. М. (1998). Быстрое изучение случайных деревьев: новый инструмент для планирования пути.
[2] Караман, С., и Фраццоли, Э. (2011). Алгоритмы на основе выборки для оптимального планирования движения. Международный журнал исследований в области робототехники, 30(7), 846–894.
