Быстрое изучение случайного дерева

• Основы RRT

  • RRT — это алгоритм для поиска невыпуклых пространств в большой размерности. 
  • Алгоритм основан на случайном построении дерева, которое растет в направлении больших неисследованных областей. 

• Разработка и применение

  • RRT были разработаны Стивеном М. Лаваллем и Джеймсом Дж. Каффнером-младшим. 
  • Алгоритм используется в автономном планировании движения роботов и для генерации траекторий в нелинейных системах. 
  • RRT может быть использован для управления нелинейными системами с ограничениями по состоянию и для смещенного поиска в конфигурационном пространстве. 

• Описание алгоритма

  • RRT строит дерево, начиная с начальной конфигурации и используя случайные выборки из пространства поиска. 
  • Вероятность расширения состояния пропорциональна размеру области Вороного. 
  • Ограничение роста дерева позволяет ему смещаться в сторону больших неисследованных областей. 
  • Вероятность выборки состояний из определенной области может быть использована для направления поиска в сторону решения задач планирования. 

• Варианты и усовершенствования

  • RRT-Rope — метод быстрого планирования маршрута, ориентированный на оптимизацию. 
  • PDRRTs — метод, сочетающий RRT с методом частичной игры для более точного поиска. 
  • CL-RRT — расширение RRT, генерирующее входные данные для стабильной замкнутой системы. 
  • RRT*-Smart — метод ускорения сходимости RRT* с помощью оптимизации траектории и интеллектуальной выборки. 
  • A*-RRT и A*-RRT* — двухэтапный метод планирования движения, использующий алгоритм поиска по графу. 
  • RRT*FN — RRT* с фиксированным числом узлов, удаляющий конечный узел на каждой итерации. 
  • RRT*-AR — планирование альтернативных маршрутов на основе выборки. 
  • RT-RRT* — вариант RRT* для планирования пути в реальном времени в динамической среде. 
  • RRTX и RRT# — оптимизация RRT* для динамических сред. 
  • Theta*-RRT — двухэтапный метод планирования движения, аналогичный A*-RRT*. 
  • RRT FND — расширение RRT* для динамических сред. 
  • RRT-графический процессор — трехмерная реализация RRT с аппаратным ускорением. 
  • APF-RRT — комбинация RRT с методом искусственных потенциальных полей. 
  • CERRT — планировщик RRT, моделирующий неопределенность. 
  • MVRRT* — алгоритм, минимизирующий уровень небезопасности. 
  • RRT-Blossom — планировщик для сильно ограниченных сред. 
  • RBV — расширение дерева вокруг препятствий. 
  • RBT — использование простых вычислений расстояния для расширения дерева. 
  • TB-RRT — алгоритм для планирования встречи двух динамических систем. 
  • RRTdT* — планировщик на основе RRT*, использующий несколько локальных деревьев. 
  • Tri-RRT-Connect — метод перемонтажа на основе треугольных неравенств. 
  • AIT* и EIT* — деревья с адаптивной информацией и информацией об усилиях. 

• Рекомендации и материалы

  • Ссылки на Викисклад, Java-визуализатор, реализацию на C++ и открытую библиотеку планирования движения RRT*.