Оглавление
Быстрое изучение случайного дерева
-
Основы 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*.