Быстро исследуемое случайное дерево - Rapidly-exploring random tree

Часть набор на
Вероятностный
структуры данных
Случайные деревья
Связанный
Визуализация графика RRT после 45 и 390 итераций
Анимация RRT, начиная с итерации от 0 до 10000

А быстрое изучение случайного дерева (RRT) - это алгоритм предназначен для эффективного поиска невыпуклый, многомерные пространства путем случайного построения дерево, заполняющее пространство. Дерево строится постепенно из выборок, выбранных случайным образом из области поиска, и по своей сути имеет тенденцию к росту в сторону больших неисследованных областей проблемы. RRT были разработаны Стивен М. ЛаВалль и Джеймс Дж. Каффнер мл.[1].[2]Они легко справляются с задачами с препятствиями и дифференциальными ограничениями (неголономный и кинодинамика) и широко использовались в автономный робот планирование движения.

RRT можно рассматривать как метод создания траекторий разомкнутого контура для нелинейных систем с ограничениями состояния. RRT также можно рассматривать как Монте-Карло метод смещения поиска по самым крупным Вороной районы графа в конфигурационном пространстве. Некоторые вариации можно даже рассмотреть стохастический фракталы.[3]

Описание

RRT выращивает дерево с корнями в начальной конфигурации, используя случайные выборки из области поиска. По мере отрисовки каждого образца предпринимается попытка установить соединение между ним и ближайшим состоянием в дереве. Если соединение возможно (полностью проходит через свободное пространство и подчиняется любым ограничениям), это приводит к добавлению нового состояния в дерево. При равномерной выборке пространства поиска вероятность расширения существующего состояния пропорциональна размеру его Вороной район.Как самый крупный Вороной районы принадлежат состояниям на границе поиска, это означает, что дерево преимущественно расширяется в сторону больших неизученных областей.

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

Рост RRT может быть искажен за счет увеличения вероятности выборки состояний из определенной области. В большинстве практических реализаций RRT это используется для направления поиска к целям задачи планирования. Это достигается за счет введения небольшой вероятности выборки от цели к цели. Государственная процедура выборки. Чем выше эта вероятность, тем жаднее дерево растет к цели.

Алгоритм

Для генерала конфигурационное пространство C, алгоритм в псевдокод составляет:

Алгоритм Вход BuildRRT: начальная конфигурация qв этом, количество вершин в RRT K, инкрементное расстояние Δq) Выход: график RRT г    г.в этом(qв этом)    для k = 1 к K делать        qранд ← RAND_CONF () qоколо ← NEAREST_VERTEX (qранд, г)        qновый ← NEW_CONF (qоколо, qранд, Δq)        г.add_vertex (qновый)        г.add_edge (qоколо, qновый)    вернуть г
  • «←» означает назначение. Например, "самый большой ← предмет"означает, что стоимость самый большой изменяет стоимость предмет.
  • "вернуть"завершает алгоритм и выводит следующее значение.

В приведенном выше алгоритме "RAND_CONF"получает случайную конфигурацию qранд в C. Его можно заменить функцией "RAND_FREE_CONF"который использует образцы в Cсвободный, отвергая тех, кто в CНаблюдения используя некоторый алгоритм обнаружения столкновений.

"NEAREST_VERTEX"- функция, которая проходит через все вершины v в графике г, вычисляет расстояние между qранд и v используя некоторую функцию измерения, тем самым возвращая ближайшую вершину.

"NEW_CONF"выбирает новую конфигурацию qновый перемещая инкрементное расстояние Δq от qоколо в направлении qранд. (Согласно с [4] в голономных задачах это следует опустить и qранд используется вместо qновый.)

Варианты и улучшения для планирования движения

  • RRTs (PDRRT), ориентированные на частичную игру,[5] метод, который сочетает в себе RRT с методом партий[6] чтобы уточнить поиск там, где это необходимо (например, вокруг препятствий), чтобы иметь возможность быстрее планировать и решать больше планирование движения проблемы чем RRT
  • Быстро исследующая случайная замкнутая петля (CL-RRT),[7] расширение RRT, которое производит выборку входных данных в стабильную замкнутую систему, состоящую из транспортного средства и контроллера

Было показано, что в «мягких технических условиях» стоимость наилучшего пути в RRT почти наверняка сходится к неоптимальному значению.[8] По этой причине желательно найти варианты RRT, которые сходятся к оптимуму, например RRT *. Ниже следует список методов на основе RRT * (начиная с самого RRT *). Однако не все производные методы сами сходятся к оптимуму.

  • Быстро исследуемый случайный граф (RRG) и RRT *,[8][9][10] вариант RRT, который сходится к оптимальному решению
  • РРТ * -Умный,[11] метод для ускорение скорости сходимости RRT * с помощью оптимизации пути (аналогично Тета * ) и интеллектуальная выборка (путем смещения выборки в сторону вершин пути, которые после оптимизации пути, вероятно, будут близки к препятствиям)
  • A * -RRT и A * -RRT *,[12] двухфазный планирование движения метод, который использует алгоритм поиска по графу для поиска начального возможного пути в низкоразмерном пространстве (без учета всего пространства состояний) на первом этапе, избегая опасных зон и предпочитая маршруты с низким уровнем риска, который затем используется для фокусировки поиска RRT * в непрерывном высоком -мерное пространство во второй фазе
  • RRT * FN,[13][14][15] RRT * с фиксированным числом узлов, который случайным образом удаляет листовой узел в дереве на каждой итерации.
  • RRT * -AR,[16] планирование альтернативных маршрутов на основе выборки
  • Информированный RRT *,[17][18] улучшает скорость сходимости RRT *, вводя эвристику, аналогично тому, как А * улучшает Алгоритм Дейкстры
  • RRT в реальном времени * (RT-RRT *),[19] вариант RRT * и информированный RRT *, который использует стратегию перемонтирования онлайн-дерева, которая позволяет корню дерева перемещаться вместе с агентом, не отбрасывая ранее выбранные пути, чтобы получить в реальном времени планирование пути в динамической среде, такой как компьютерная игра
  • RRTИкс и RRT#,[20][21] оптимизация RRT * для динамических сред
  • Тета * -RRT,[22] двухфазный планирование движения метод, аналогичный A * -RRT *, который использует иерархическую комбинацию поиск под любым углом с планированием движения RRT для быстрого построения траектории в средах со сложными неголономный ограничения
  • RRT * FND,[23] расширение RRT * для динамических сред
  • РРТ-ГПУ,[24] трехмерная реализация RRT, использующая аппаратное ускорение
  • АПФ-РРТ,[25] комбинация планировщика RRT с методом искусственных потенциальных полей, что упрощает задачу перепланирования
  • CERRT,[26] неопределенность моделирования планировщика RRT, которая уменьшает использование контактов
  • МВРРТ *,[27] Минимальное нарушение RRT *, алгоритм, который находит кратчайший маршрут, который сводит к минимуму уровень небезопасности («стоимость» нарушенных правил окружающей среды, например, правил дорожного движения)
  • РРТ-Блоссом,[28] Планировщик RRT для сильно ограниченных сред.
  • TB-RRT,[29] Временной алгоритм RRT для планирования сближения двух динамических систем.
  • RRdT *,[30] планировщик на основе RRT *, который использует несколько локальных деревьев для активного балансирования исследования и исследования пространства путем выполнения локальной выборки.

Смотрите также

использованная литература

  1. ^ ЛаВалль, Стивен М. (Октябрь 1998 г.). «Быстро исследуемые случайные деревья: новый инструмент для планирования пути» (PDF). Технический отчет. Департамент компьютерных наук, Государственный университет Айовы (TR 98–11).
  2. ^ ЛаВалль, Стивен М.; Каффнер-младший, Джеймс Дж. (2001). «Рандомизированное кинодинамическое планирование» (PDF). Международный журнал исследований робототехники (IJRR). 20 (5): 378–400. Дои:10.1177/02783640122067453. S2CID  40479452.
  3. ^ http://msl.cs.uiuc.edu/rrt/about.html О RRT, Стив ЛаВалль
  4. ^ Быстро исследуемые случайные деревья: прогресс и перспективы (2000), Стивен М. Лавалле, Джеймс Дж. Каффнер-младший. Алгоритмическая и вычислительная робототехника: новые направления. http://eprints.kfupm.edu.sa/60786/1/60786.pdf[постоянная мертвая ссылка ]
  5. ^ Ранганатан, Анант; Кениг, Свен. PDRRTs: "Интеграция планирования на основе графиков и ячеек ". В Материалы Международной конференции IEEE по интеллектуальным роботам и системам (IROS), страницы 2799–2808, 2004.
  6. ^ Мур, А. В .; Аткесон, К. Г. "Игровой алгоритм для обучения с подкреплением с переменным разрешением в многомерных пространствах состояний," Машинное обучение, т. 21, нет. 3, страницы 199–233, 1995.
  7. ^ Кувата, Йошиаки; Тео, Джастин; Фиоре, Гастон; Караман, Сертак; Фраццоли, Эмилио; Как, Джонатан П. (сентябрь 2009 г.). «Планирование движения в реальном времени с приложениями для автономного городского вождения» (PDF). IEEE Transactions по технологии систем управления. 17 (5): 1105–1118. CiteSeerX  10.1.1.169.7922. Дои:10.1109 / tcst.2008.2012116. HDL:1721.1/52527. S2CID  14526513. Получено 10 апреля 2017.
  8. ^ а б Караман, Сертак; Фраццоли, Эмилио (3 мая 2010 г.). «Алгоритмы на основе инкрементальной выборки для планирования оптимального движения». arXiv:1005.0416 [cs.RO ].
  9. ^ Караман, Сертак; Фраццоли, Эмилио (5 мая 2011 г.). «Алгоритмы на основе выборки для планирования оптимального движения». arXiv:1105.1186 [cs.RO ].
  10. ^ ОлжасАди (26 января, 2015). «RRT * Краткое объяснение» (видео). YouTube. Получено 3 августа 2016.
  11. ^ Ислам, Фахад; Насир, Яувайрия; Малик, Усмань; Аяз, Ясар; Хасан, Осман; "RRT * -Smart: быстрая сходимость реализации RRT * к оптимальному решению ", в Труды Международной конференции IEEE по мехатронике и автоматизации (ICMA), страницы 1651–1656, Чэнду, Китай, август 2012 г.
  12. ^ Brunner, M .; Bruggemann, B .; Шульц, Д .. "Иерархическое планирование движения на пересеченной местности с использованием оптимального метода выборки," в Int. Конф. по робототехнике и автоматизации (ICRA), Карлсруэ, Германия, 2013.
  13. ^ Адиятов, Олжас; Варол, Гусейн Атакан. «Быстрое изучение случайного дерева на основе эффективного планирования движения с памятью». В Мехатроника и автоматизация (ICMA), Международная конференция IEEE 2013 г., страницы 354–359, 2013. Дои:10.1109 / ICMA.2013.6617944
  14. ^ Адиятов, Олжас; Варол, Атакан (2013). "MATLAB Toolbox алгоритмов RRT, RRT * и RRT * FN". Получено 3 августа 2016.
  15. ^ ОлжасАди (26 января, 2015). «RRT * FN Краткое объяснение» (видео). YouTube. Получено 3 августа 2016.
  16. ^ Чоудхури, Санджибан; Шерер, Себастьян; Сингх, Санджив. "RRT * -AR: планирование альтернативных маршрутов на основе выборки с приложениями для автономной аварийной посадки вертолета ". В Робототехника и автоматизация (ICRA), Международная конференция IEEE 2013 г., Карлсруэ, 6–10 мая 2013 г., страницы 3947–3952. Дои:10.1109 / ICRA.2013.6631133
  17. ^ Гаммелл, Джонатан Д .; Srinivasa, Siddhartha S .; Барфут, Тимоти Д. (8 апреля 2014 г.). Информированный RRT *: оптимальное планирование пути на основе выборки, ориентированное на прямую выборку допустимой эллипсоидальной эвристики. 2014 IEEE / RSJ Международная конференция по интеллектуальным роботам и системам. С. 2997–3004. arXiv:1404.2334. Дои:10.1109 / IROS.2014.6942976. ISBN  978-1-4799-6934-0. S2CID  12233239.
  18. ^ utiasASRL (4 июля 2014 г.). «Информированный RRT * @ UTIAS (IROS 2014)» (видео). YouTube. Получено 3 августа 2016.
  19. ^ Надери, Курош; Раджамаки, Йозе; Хямяляйнен, Пертту (2015). "RT-RRT *: алгоритм планирования пути в реальном времени на основе RRT * ". В Материалы 8-й конференции ACM SIGGRAPH по движению в играх (МИГ '15). ACM, Нью-Йорк, Нью-Йорк, США, 113–118. DOI =https://dx.doi.org/10.1145/2822013.2822036
  20. ^ RRTИкс: Планирование движения в реальном времени / перепланирование для сред с непредсказуемыми препятствиями
  21. ^ Сравнение RRTX, RRT # и RRT * при обнаружении ярлыка в статической среде
  22. ^ Пальмиери, Луиджи; Кениг, Свен; Аррас, Кай О. "Неголономное планирование движения на основе RRT с использованием смещения траектории под любым углом ". В Робототехника и автоматизация (ICRA), Материалы Международной конференции IEEE по, страницы 2775-2781, 2016.
  23. ^ RRT * FND - планирование движения в динамических средах
  24. ^ Форд, Кристен (12.06.2018). RRT-GPU и Minecraft: аппаратное ускорение, быстрое изучение случайных деревьев в трех измерениях (Тезис). Дои:10.13140 / rg.2.2.15658.11207.
  25. ^ Амирян, Джавад; Джамзад, Мансур (2015). Адаптивное планирование движения с искусственными потенциальными полями с использованием предшествующего пути. Робототехника и мехатроника (ICROM), 3-я Международная конференция RSI, 2015 г. С. 731–736.
  26. ^ Сиверлинг, Арне; Эппнер, Клеменс; Вольф, Феликс; Брок, Оливер (2017). Чередование движений в контакте и в свободном пространстве для планирования в условиях неопределенности (PDF). Международная конференция IEEE / RSJ по интеллектуальным роботам и системам (IROS), 2017 г. С. 4011–4073.
  27. ^ Русь, Даниэла; Фраццоли, Эмилио; Караман, Сертак; Тумова Яна; Чаудхари, Пратик; Кастро, Луис И. Рейес (2013-05-06). «Алгоритм на основе инкрементальной выборки для планирования движения с минимальным нарушением». arXiv:1305.1102 [cs.RO ].
  28. ^ "Мацей Калисиак - RRT-цветок". www.dgp.toronto.edu. Получено 2020-01-18.
  29. ^ Синтов, Авишай; Шапиро, Амир (2014). Временной алгоритм RRT для планирования сближения двух динамических систем. Международная конференция IEEE по робототехнике и автоматизации (ICRA). Дои:10.1109 / ICRA.2014.6907855.
  30. ^ Лай, Тин; Рамос, Фабио; Фрэнсис, Гилад (2019). «Уравновешивание глобального исследования и использования локальной связи с быстро исследуемыми случайными несвязными деревьями». Международная конференция по робототехнике и автоматизации 2019 (ICRA). Монреаль, Квебек, Канада: IEEE: 5537–5543. Дои:10.1109 / ICRA.2019.8793618. ISBN  978-1-5386-6027-0.

внешние ссылки