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

Визуализация графика RRT после 45 и 390 итераций.

Анимация RRT, начиная с итерации от 0 до 10000.

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

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

RRT можно использовать для расчета приблизительных политик управления для управления многомерными нелинейными системами с ограничениями состояния и действия.

Описание

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

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

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

Алгоритм

Для общего конфигурационного пространства C алгоритм в псевдокоде выглядит следующим образом:

Algorithm BuildRRT
    Input: Initial configuration q_init, number of vertices in RRT K, incremental distance Δq
    Output: RRT graph G

    G.init(q_init)
    for k = 1 to K do
        q_rand ← RAND_CONF()
        q_near ← NEAREST_VERTEX(q_rand, G)
        q_new ← NEW_CONF(q_near, q_rand, Δq)
        G.add_vertex(q_new)
        G.add_edge(q_near, q_new)
    return G

« ←» означает присвоение . Например, « самый большой ← элемент » означает, что значение самого большого изменяется на значение элемента .
« return » завершает алгоритм и выводит следующее значение.

В приведенном выше алгоритме « RAND_CONF получает случайную конфигурацию q _rand в C. » Это можно заменить функцией « RAND_FREE_CONF », которая использует образцы из C _free и отклоняет те из C _obs, используя некоторый алгоритм обнаружения коллизий.

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

« NEW_CONF » выбирает новую конфигурацию q _new , перемещая приращенное расстояние Δq от q _close в направлении q _rand . (В соответствии с ^[4] в голономных задачах это следует опустить и использовать q _rand вместо q _new .)

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

РРТ-Веревка, ^[5] метод быстрого планирования почти оптимального пути с использованием детерминированного подхода к сокращению, очень эффективный в открытых и больших средах.

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

Замкнутый цикл быстрого исследования случайных чисел (CL-RRT), ^[8] расширение RRT, которое осуществляет выборку входных данных для стабильной системы с обратной связью, состоящей из транспортного средства и контроллера.

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

Быстрое изучение случайного графа (RRG) и RRT*, ^[9]^[10]^[11] вариант ЗПТ, который сходится к оптимальному решению

LQR-RRT , ^[12] кинодинамический вариант для сложной или недоработанной динамики

РРТ ⁺, ^[13] семейство планировщиков на основе RRT, целью которых является генерирование решений для многомерных систем в реальном времени путем постепенного поиска в подпространствах более низкой размерности.

РРТ*-Смарт, ^[14] метод ускорения скорости сходимости RRT* за счет использования оптимизации пути (аналогично Theta* ) и интеллектуальной выборки (путем смещения выборки в сторону вершин пути, которые после оптимизации пути, скорее всего, окажутся рядом с препятствиями)

А*-ЗРТ и А*-ЗРТ*, ^[15] метод двухфазного планирования движения , который использует алгоритм поиска по графу для поиска начального возможного пути в маломерном пространстве (не учитывая полное пространство состояний) на первом этапе, избегая опасных зон и отдавая предпочтение маршрутам с низким уровнем риска, которые затем используется для фокусировки поиска RRT* в непрерывном многомерном пространстве на втором этапе

ЗРТ*ФН, ^[16]^[17]^[18] RRT* с фиксированным количеством узлов, который случайным образом удаляет листовой узел в дереве на каждой итерации.

РРТ*-ВКЛ, ^[19] планирование альтернативных маршрутов на основе выборки

Информировано ГБР*, ^[20]^[21] улучшает скорость сходимости RRT* за счет введения эвристики, аналогично тому, как A* улучшает алгоритм Дейкстры

ЗДТ в реальном времени* (RT-RRT*), ^[22] вариант RRT* и информированного RRT*, который использует стратегию онлайн-перемонтирования дерева, которая позволяет корню дерева перемещаться вместе с агентом, не отбрасывая ранее выбранные пути, чтобы получить планирование пути в реальном времени в динамической среде, такой как компьютер игра

РРТ ^Х и РРТ ^#, ^[23]^[24] оптимизация RRT* для динамических сред

Тета*-ЗПТ, ^[25] метод двухфазного планирования движения, аналогичный A*-RRT*, который использует иерархическую комбинацию поиска под любым углом с планированием движения RRT для быстрого создания траектории в средах со сложными неголономными ограничениями.

РРТ* ФНД, ^[26]^[27] расширение RRT* для динамических сред
РРТ-ГПУ, ^[28] трехмерная реализация RRT, использующая аппаратное ускорение

АПФ-РРТ, ^[29] сочетание планировщика RRT с методом искусственных потенциальных полей, упрощающее задачу перепланирования

ЦЕРРТ, ^[30] планировщик RRT, моделирующий неопределенность, которая снижается за счет контактов
МВРРТ*, ^[31] Минимальное нарушение RRT*, алгоритм, который находит кратчайший маршрут, минимизирующий уровень безопасности («стоимость» нарушенных правил окружающей среды, например, правил дорожного движения).

РРТ-Цветок, ^[32] Планировщик RRT для сред с высокими ограничениями.

РРВ, ^[33] эффективно расширять дерево вокруг препятствий и узких проходов, используя доминирующие собственные векторы вокруг узлов дерева.

РБТ, ^[34] использует простые вычисления расстояний в рабочей области для расширения дерева вместо дорогостоящей проверки коллизий.

ТБ-ЗРТ, ^[35] Алгоритм RRT на основе времени для планирования встречи двух динамических систем.

РРдТ*, ^[36]^[37] планировщик на основе RRT*, который использует несколько локальных деревьев для активного балансирования исследования и эксплуатации пространства путем выполнения локальной выборки.

Три-РРТ-Коннект, ^[38]^[39] Метод перемонтажа на основе треугольного неравенства с алгоритмом RRT-Connect, приближающий его к оптимальному.

Адаптивно информированные деревья (AIT*) и деревья, информированные об усилиях (EIT*) ^[40]

См. также

Ссылки

^ ЛаВалль, Стивен М. (октябрь 1998 г.). «Быстрое исследование случайных деревьев: новый инструмент для планирования пути» (PDF) . Технический отчет (ТР 98–11). Факультет компьютерных наук Университета штата Айова.
^ ЛаВалле, Стивен М .; Каффнер-младший, Джеймс Дж. (2001). «Рандомизированное кинодинамическое планирование» (PDF) . Международный журнал исследований робототехники . 20 (5): 378–400. дои : 10.1177/02783640122067453 . S2CID 40479452 .
^ http://msl.cs.uiuc.edu/rrt/about.html. Архивировано 21 октября 2007 г. в Wayback Machine About RRT, Стив ЛаВалле.
^ Быстрое исследование случайных деревьев: прогресс и перспективы (2000), Стивен М. Лаваль, Джеймс Дж. Каффнер-младший. Алгоритмическая и вычислительная робототехника: новые направления, http://eprints.kfupm.edu.sa/60786/1 /60786.pdf ^{[ постоянная мертвая ссылка ]}
^ Пети, Луи; Дебьен, Алексис Люсье (17 октября 2021 г.). «RRT-Rope: детерминированный подход к сокращению для быстрого, почти оптимального планирования пути в крупномасштабных незагроможденных трехмерных средах» . Международная конференция IEEE по системам, человеку и кибернетике (SMC) 2021 г. Мельбурн, Австралия: IEEE. стр. 1111–1118. дои : 10.1109/SMC52423.2021.9659071 . ISBN 978-1-6654-4207-7 . S2CID 252590377 .
^ Ранганатан, Анант; Кениг, Свен . PDRRTs: « Интеграция планирования на основе графов и ячеек ». В материалах Международной конференции IEEE по интеллектуальным роботам и системам (IROS) , страницы 2799–2808, 2004 г.
^ Мур, AW; Аткесон, К.Г., « Алгоритм частичной игры для обучения с подкреплением с переменным разрешением в многомерных пространствах состояний », Machine Learning , vol. 21, нет. 3, страницы 199–233, 1995.
^ Кувата, Ёсиаки; Тео, Джастин; Фиоре, Гастон; Караман, Сертак; Фраццоли, Эмилио; Как, Джонатан П. (сентябрь 2009 г.). «Планирование движения в реальном времени с применением к автономному городскому вождению» (PDF) . Транзакции IEEE по технологии систем управления . 17 (5): 1105–1118. CiteSeerX 10.1.1.169.7922 . дои : 10.1109/tcst.2008.2012116 . hdl : 1721.1/52527 . S2CID 14526513 . Архивировано из оригинала (PDF) 12 июня 2021 года . Проверено 10 апреля 2017 г. .
^ Jump up to: ^а ^б Караман, Сертак; Фраццоли, Эмилио (3 мая 2010 г.). «Алгоритмы оптимального планирования движения на основе дополнительной выборки». arXiv : 1005.0416 [ cs.RO ].
^ Караман, Сертак; Фраццоли, Эмилио (5 мая 2011 г.). «Алгоритмы оптимального планирования движения на основе выборки». arXiv : 1105.1186 [ cs.RO ].
^ ОлжасАди (26 января 2015 г.). «RRT* Краткое объяснение» (видео) . Ютуб . Архивировано из оригинала 12 декабря 2021 г. Проверено 3 августа 2016 г.
^ Перес, Алехандро; Платт, Роберт; Конидарис, Джордж; Кельблинг, Лесли; Лозано-Перес, Томас (май 2012 г.). «LQR-RRT*: оптимальное планирование движения на основе выборки с автоматически полученной эвристикой расширения» . 2012 Международная конференция IEEE по робототехнике и автоматизации . стр. 2537–2542. дои : 10.1109/ICRA.2012.6225177 . ISBN 978-1-4673-1405-3 . S2CID 1914056 .
^ Ксантидис, Мариос; Эспозито, Джоэл М.; Реклейтис, Иоаннис; О'Кейн, Джейсон М. (01 декабря 2020 г.). «Планирование движения путем выборки в подпространствах постепенно возрастающей размерности» . Журнал интеллектуальных и робототехнических систем . 100 (3): 777–789. дои : 10.1007/s10846-020-01217-w . ISSN 1573-0409 . S2CID 3622004 .
^ Ислам, Фахад; Насир, Джаувайрия; Малик, Усман; Аяз, Ясар; Хасан, Осман; « RRT*-Smart: быстрая реализация конвергенции RRT* к оптимальному решению », в материалах Международной конференции IEEE по мехатронике и автоматизации (ICMA) , страницы 1651–1656, Чэнду, Китай, август 2012 г.
^ Бруннер, М.; Брюггеманн, Б.; Шульц, Д. « Иерархическое планирование движения по пересеченной местности с использованием оптимального метода, основанного на выборке », в Int. Конф. по робототехнике и автоматизации (ICRA) , Карлсруэ, Германия, 2013.
^ Адиятов, Олжас; Варол, Гусейн Атакан. «Быстрое исследование эффективного планирования движений на основе случайного дерева». В «Мехатронике и автоматизации» (ICMA), Международная конференция IEEE 2013 г. , стр. 354–359, 2013 г. дои : 10.1109/ICMA.2013.6617944
^ Адиятов, Олжас; Варол, Атакан (2013). «MATLAB Toolbox алгоритмов RRT, RRT* и RRT*FN» . Проверено 3 августа 2016 г.
^ ОлжасАди (26 января 2015 г.). «Краткое объяснение RRT*FN» (видео) . Ютуб . Архивировано из оригинала 12 декабря 2021 г. Проверено 3 августа 2016 г.
^ Чоудхури, Санджибан; Шерер, Себастьян; Сингх, Санджив. « RRT*-AR: Планирование альтернативных маршрутов на основе выборки с применением автономной аварийной посадки вертолета ». В книге «Робототехника и автоматизация» (ICRA), Международная конференция IEEE 2013 г. , Карлсруэ, 6–10 мая 2013 г., страницы 3947–3952. два : 10.1109/ICRA.2013.6631133
^ Гаммелл, Джонатан Д.; Шриниваса, Сиддхартха С.; Барфут, Тимоти Д. (8 апреля 2014 г.). «Информированная RRT *: оптимальное планирование пути на основе выборки, ориентированное на прямую выборку допустимой эллипсоидальной эвристики». Международная конференция IEEE/RSJ по интеллектуальным роботам и системам , 2014 г. стр. 2997–3004. arXiv : 1404.2334 . дои : 10.1109/IROS.2014.6942976 . ISBN 978-1-4799-6934-0 . S2CID 12233239 .
^ utiasASRL (4 июля 2014 г.). «Информированное РРТ*@УТИАС (ИРОС 2014)» (видео) . Ютуб . Архивировано из оригинала 12 декабря 2021 г. Проверено 3 августа 2016 г.
^ Надери, Курош; Раджамяки, Йоосе; Хямяляйнен, Пертту (2015). « RT-RRT*: алгоритм планирования пути в реальном времени на основе RRT* ». В материалах 8-й конференции ACM SIGGRAPH по движению в играх (MIG '15). ACM, Нью-Йорк, Нью-Йорк, США, 113–118. дои : 10.1145/2822013.2822036
^ "РРТ ^Х: Планирование/перепланирование движения в реальном времени для сред с непредсказуемыми препятствиями» (PDF) . Архивировано из оригинала (PDF) 19 мая 2017 г. Проверено 2 марта 2018 г. .
^ Сравнение RRTX, RRT# и RRT* при обнаружении ярлыка в статической среде.
^ Пальмьери, Луиджи; Кениг, Свен ; Аррас, Кай О. « Планирование неголономного движения на основе RRT с использованием смещения пути под любым углом ». В «Робототехнике и автоматизации» (ICRA), 2016 г., материалы Международной конференции IEEE , стр. 2775–2781, 2016 г.
^ RRT* FND - планирование движения в динамических средах
^ Адиятов, Олжас; Варол, Гусейн Атакан. «Новый алгоритм планирования движения на основе RRT в динамических средах». В «Мехатронике и автоматизации» (ICMA), Международная конференция IEEE 2017 г. , страницы 1416–1421, 2017 г. дои : 10.1109/ICMA.2017.8016024
^ Форд, Кристен (12 июня 2018 г.). RRT-GPU и Minecraft: аппаратное ускорение быстрого исследования случайных деревьев в трех измерениях (Диссертация). дои : 10.13140/rg.2.2.15658.11207 .
^ Амирян, Джавад; Джамзад, Мансур (2015). Адаптивное планирование движения с использованием искусственных потенциальных полей с использованием предшествующего пути . Робототехника и мехатроника (ИКРОМ), 2015 3-я Международная конференция RSI. стр. 731–736.
^ Зиверлинг, Арне; Эппнер, Клеменс; Вольф, Феликс; Брок, Оливер (2017). Чередование движений в контакте и в свободном пространстве для планирования в условиях неопределенности (PDF) . Международная конференция IEEE/RSJ по интеллектуальным роботам и системам (IROS), 2017 г. стр. 4011–4073.
^ Рус, Даниэла; Фраццоли, Эмилио; Караман, Сертак; Тумова, Яна; Чаудхари, Пратик; Кастро, Луис И. Рейес (6 мая 2013 г.). «Алгоритм планирования движения с минимальным нарушением на основе дополнительной выборки». arXiv : 1305.1102 [ cs.RO ].
^ "Мацей Калисяк - RRT-цветение" . www.dgp.toronto.edu . Проверено 18 января 2020 г.
^ Тахирович, Аднан; Феризбегович, Мина (май 2018 г.). «Быстрое исследование случайных лоз (RRV) для планирования движения в конфигурационных пространствах с узкими проходами» . Международная конференция IEEE по робототехнике и автоматизации (ICRA) 2018 . стр. 7055–7062. дои : 10.1109/ICRA.2018.8460186 . ISBN 978-1-5386-3081-5 . S2CID 52285080 .
^ Лачевич, Бакир; Османкович, Динко; Адемович, Аднан (май 2016 г.). «Буры свободного C-пространства: новая структура планирования пути» . Международная конференция IEEE по робототехнике и автоматизации (ICRA) , 2016 г. стр. 70–76. дои : 10.1109/ICRA.2016.7487117 . ISBN 978-1-4673-8026-3 . S2CID 15834630 .
^ Синтов, Авишай; Шапиро, Амир (2014). «Алгоритм RRT на основе времени для планирования сближения двух динамических систем» . 2014 Международная конференция IEEE по робототехнике и автоматизации (ICRA) . Международная конференция IEEE по робототехнике и автоматизации (ICRA). стр. 6745–6750. дои : 10.1109/ICRA.2014.6907855 . ISBN 978-1-4799-3685-4 .
^ Лай, Тин; Рамос, Фабио; Фрэнсис, Гилад (2019). «Балансирование глобального исследования и использования локальных связей с быстрым исследованием случайных несвязанных деревьев» . 2019 Международная конференция по робототехнике и автоматизации (ICRA) . Монреаль, Квебек, Канада: IEEE. стр. 5537–5543. arXiv : 1810.03749 . дои : 10.1109/ICRA.2019.8793618 . ISBN 978-1-5386-6027-0 . S2CID 52945105 .
^ Лай, Тин; Морер, Филипп; Рамос, Фабио; Фрэнсис, Гилад (апрель 2020 г.). «Байесовское планирование на основе локальной выборки». Письма IEEE по робототехнике и автоматизации . 5 (2): 1954–1961. arXiv : 1909.03452 . дои : 10.1109/LRA.2020.2969145 . S2CID 210838739 .
^ Кан, Джин-Гу; Лим, Дон Ву; Чой, Ён-Сик; Чан, У-Джин; Юнг, Джин Ву (6 января 2021 г.). «Улучшенный алгоритм RRT-Connect на основе треугольного неравенства для планирования пути робота» . Датчики . 21 (2): 333. дои : 10.3390/s21020333 . ISSN 1424-8220 . ПМЦ 7825297 . S2CID 231303809 .
^ Кан, Джин-Гу; Юнг, Джин Ву (12 июля 2021 г.). «Метод послетреугольной замены проводки для планирования более короткого пути робота RRT». arXiv : 2107.05344 [ cs.RO ].
^ Струб, Марлин П.; Гаммелл, Джонатан Д. (2 ноября 2021 г.). «AIT * и EIT *: асимметричное двунаправленное планирование пути на основе выборки». arXiv : 2111.01877 [ cs.RO ].

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

[lavalle_tr98-1] ЛаВалль, Стивен М. (октябрь 1998 г.). «Быстрое исследование случайных деревьев: новый инструмент для планирования пути» (PDF) . Технический отчет (ТР 98–11). Факультет компьютерных наук Университета штата Айова.

[lavalle_ijrr01-2] ЛаВалле, Стивен М .; Каффнер-младший, Джеймс Дж. (2001). «Рандомизированное кинодинамическое планирование» (PDF) . Международный журнал исследований робототехники . 20 (5): 378–400. дои : 10.1177/02783640122067453 . S2CID 40479452 .

[3] ttp://msl.cs.uiuc.edu/rrt/about.html. Архивировано 21 октября 2007 г. в Wayback Machine About RRT, Стив ЛаВалле.

[4] Быстрое исследование случайных деревьев: прогресс и перспективы (2000), Стивен М. Лаваль, Джеймс Дж. Каффнер-младший. Алгоритмическая и вычислительная робототехника: новые направления, http://eprints.kfupm.edu.sa/60786/1 /60786.pdf ^{[ постоянная мертвая ссылка ]}

[5] Пети, Луи; Дебьен, Алексис Люсье (17 октября 2021 г.). «RRT-Rope: детерминированный подход к сокращению для быстрого, почти оптимального планирования пути в крупномасштабных незагроможденных трехмерных средах» . Международная конференция IEEE по системам, человеку и кибернетике (SMC) 2021 г. Мельбурн, Австралия: IEEE. стр. 1111–1118. дои : 10.1109/SMC52423.2021.9659071 . ISBN 978-1-6654-4207-7 . S2CID 252590377 .

[6] Ранганатан, Анант; Кениг, Свен . PDRRTs: « Интеграция планирования на основе графов и ячеек ». В материалах Международной конференции IEEE по интеллектуальным роботам и системам (IROS) , страницы 2799–2808, 2004 г.

[7] Мур, AW; Аткесон, К.Г., « Алгоритм частичной игры для обучения с подкреплением с переменным разрешением в многомерных пространствах состояний », Machine Learning , vol. 21, нет. 3, страницы 199–233, 1995.

[8] Кувата, Ёсиаки; Тео, Джастин; Фиоре, Гастон; Караман, Сертак; Фраццоли, Эмилио; Как, Джонатан П. (сентябрь 2009 г.). «Планирование движения в реальном времени с применением к автономному городскому вождению» (PDF) . Транзакции IEEE по технологии систем управления . 17 (5): 1105–1118. CiteSeerX 10.1.1.169.7922 . дои : 10.1109/tcst.2008.2012116 . hdl : 1721.1/52527 . S2CID 14526513 . Архивировано из оригинала (PDF) 12 июня 2021 года . Проверено 10 апреля 2017 г. .

[incremental-9] Jump up to: ^а ^б Караман, Сертак; Фраццоли, Эмилио (3 мая 2010 г.). «Алгоритмы оптимального планирования движения на основе дополнительной выборки». arXiv : 1005.0416 [ cs.RO ].

[10] Караман, Сертак; Фраццоли, Эмилио (5 мая 2011 г.). «Алгоритмы оптимального планирования движения на основе выборки». arXiv : 1105.1186 [ cs.RO ].

[11] ОлжасАди (26 января 2015 г.). «RRT* Краткое объяснение» (видео) . Ютуб . Архивировано из оригинала 12 декабря 2021 г. Проверено 3 августа 2016 г.

[12] Перес, Алехандро; Платт, Роберт; Конидарис, Джордж; Кельблинг, Лесли; Лозано-Перес, Томас (май 2012 г.). «LQR-RRT*: оптимальное планирование движения на основе выборки с автоматически полученной эвристикой расширения» . 2012 Международная конференция IEEE по робототехнике и автоматизации . стр. 2537–2542. дои : 10.1109/ICRA.2012.6225177 . ISBN 978-1-4673-1405-3 . S2CID 1914056 .

[13] Ксантидис, Мариос; Эспозито, Джоэл М.; Реклейтис, Иоаннис; О'Кейн, Джейсон М. (01 декабря 2020 г.). «Планирование движения путем выборки в подпространствах постепенно возрастающей размерности» . Журнал интеллектуальных и робототехнических систем . 100 (3): 777–789. дои : 10.1007/s10846-020-01217-w . ISSN 1573-0409 . S2CID 3622004 .

[14] Ислам, Фахад; Насир, Джаувайрия; Малик, Усман; Аяз, Ясар; Хасан, Осман; « RRT*-Smart: быстрая реализация конвергенции RRT* к оптимальному решению », в материалах Международной конференции IEEE по мехатронике и автоматизации (ICMA) , страницы 1651–1656, Чэнду, Китай, август 2012 г.

[15] Бруннер, М.; Брюггеманн, Б.; Шульц, Д. « Иерархическое планирование движения по пересеченной местности с использованием оптимального метода, основанного на выборке », в Int. Конф. по робототехнике и автоматизации (ICRA) , Карлсруэ, Германия, 2013.

[16] Адиятов, Олжас; Варол, Гусейн Атакан. «Быстрое исследование эффективного планирования движений на основе случайного дерева». В «Мехатронике и автоматизации» (ICMA), Международная конференция IEEE 2013 г. , стр. 354–359, 2013 г. дои : 10.1109/ICMA.2013.6617944

[17] Адиятов, Олжас; Варол, Атакан (2013). «MATLAB Toolbox алгоритмов RRT, RRT* и RRT*FN» . Проверено 3 августа 2016 г.

[18] ОлжасАди (26 января 2015 г.). «Краткое объяснение RRT*FN» (видео) . Ютуб . Архивировано из оригинала 12 декабря 2021 г. Проверено 3 августа 2016 г.

[19] Чоудхури, Санджибан; Шерер, Себастьян; Сингх, Санджив. « RRT*-AR: Планирование альтернативных маршрутов на основе выборки с применением автономной аварийной посадки вертолета ». В книге «Робототехника и автоматизация» (ICRA), Международная конференция IEEE 2013 г. , Карлсруэ, 6–10 мая 2013 г., страницы 3947–3952. два : 10.1109/ICRA.2013.6631133

[20] Гаммелл, Джонатан Д.; Шриниваса, Сиддхартха С.; Барфут, Тимоти Д. (8 апреля 2014 г.). «Информированная RRT *: оптимальное планирование пути на основе выборки, ориентированное на прямую выборку допустимой эллипсоидальной эвристики». Международная конференция IEEE/RSJ по интеллектуальным роботам и системам , 2014 г. стр. 2997–3004. arXiv : 1404.2334 . дои : 10.1109/IROS.2014.6942976 . ISBN 978-1-4799-6934-0 . S2CID 12233239 .

[21] utiasASRL (4 июля 2014 г.). «Информированное РРТ*@УТИАС (ИРОС 2014)» (видео) . Ютуб . Архивировано из оригинала 12 декабря 2021 г. Проверено 3 августа 2016 г.

[22] Надери, Курош; Раджамяки, Йоосе; Хямяляйнен, Пертту (2015). « RT-RRT*: алгоритм планирования пути в реальном времени на основе RRT* ». В материалах 8-й конференции ACM SIGGRAPH по движению в играх (MIG '15). ACM, Нью-Йорк, Нью-Йорк, США, 113–118. дои : 10.1145/2822013.2822036

[23] "РРТ ^Х: Планирование/перепланирование движения в реальном времени для сред с непредсказуемыми препятствиями» (PDF) . Архивировано из оригинала (PDF) 19 мая 2017 г. Проверено 2 марта 2018 г. .

[24] Сравнение RRTX, RRT# и RRT* при обнаружении ярлыка в статической среде.

[25] Пальмьери, Луиджи; Кениг, Свен ; Аррас, Кай О. « Планирование неголономного движения на основе RRT с использованием смещения пути под любым углом ». В «Робототехнике и автоматизации» (ICRA), 2016 г., материалы Международной конференции IEEE , стр. 2775–2781, 2016 г.

[26] RRT* FND - планирование движения в динамических средах

[27] Адиятов, Олжас; Варол, Гусейн Атакан. «Новый алгоритм планирования движения на основе RRT в динамических средах». В «Мехатронике и автоматизации» (ICMA), Международная конференция IEEE 2017 г. , страницы 1416–1421, 2017 г. дои : 10.1109/ICMA.2017.8016024

[28] Форд, Кристен (12 июня 2018 г.). RRT-GPU и Minecraft: аппаратное ускорение быстрого исследования случайных деревьев в трех измерениях (Диссертация). дои : 10.13140/rg.2.2.15658.11207 .

[29] Амирян, Джавад; Джамзад, Мансур (2015). Адаптивное планирование движения с использованием искусственных потенциальных полей с использованием предшествующего пути . Робототехника и мехатроника (ИКРОМ), 2015 3-я Международная конференция RSI. стр. 731–736.

[30] Зиверлинг, Арне; Эппнер, Клеменс; Вольф, Феликс; Брок, Оливер (2017). Чередование движений в контакте и в свободном пространстве для планирования в условиях неопределенности (PDF) . Международная конференция IEEE/RSJ по интеллектуальным роботам и системам (IROS), 2017 г. стр. 4011–4073.

[31] Рус, Даниэла; Фраццоли, Эмилио; Караман, Сертак; Тумова, Яна; Чаудхари, Пратик; Кастро, Луис И. Рейес (6 мая 2013 г.). «Алгоритм планирования движения с минимальным нарушением на основе дополнительной выборки». arXiv : 1305.1102 [ cs.RO ].

[32] "Мацей Калисяк - RRT-цветение" . www.dgp.toronto.edu . Проверено 18 января 2020 г.

[33] Тахирович, Аднан; Феризбегович, Мина (май 2018 г.). «Быстрое исследование случайных лоз (RRV) для планирования движения в конфигурационных пространствах с узкими проходами» . Международная конференция IEEE по робототехнике и автоматизации (ICRA) 2018 . стр. 7055–7062. дои : 10.1109/ICRA.2018.8460186 . ISBN 978-1-5386-3081-5 . S2CID 52285080 .

[34] Лачевич, Бакир; Османкович, Динко; Адемович, Аднан (май 2016 г.). «Буры свободного C-пространства: новая структура планирования пути» . Международная конференция IEEE по робототехнике и автоматизации (ICRA) , 2016 г. стр. 70–76. дои : 10.1109/ICRA.2016.7487117 . ISBN 978-1-4673-8026-3 . S2CID 15834630 .

[35] Синтов, Авишай; Шапиро, Амир (2014). «Алгоритм RRT на основе времени для планирования сближения двух динамических систем» . 2014 Международная конференция IEEE по робототехнике и автоматизации (ICRA) . Международная конференция IEEE по робототехнике и автоматизации (ICRA). стр. 6745–6750. дои : 10.1109/ICRA.2014.6907855 . ISBN 978-1-4799-3685-4 .

[36] Лай, Тин; Рамос, Фабио; Фрэнсис, Гилад (2019). «Балансирование глобального исследования и использования локальных связей с быстрым исследованием случайных несвязанных деревьев» . 2019 Международная конференция по робототехнике и автоматизации (ICRA) . Монреаль, Квебек, Канада: IEEE. стр. 5537–5543. arXiv : 1810.03749 . дои : 10.1109/ICRA.2019.8793618 . ISBN 978-1-5386-6027-0 . S2CID 52945105 .

[37] Лай, Тин; Морер, Филипп; Рамос, Фабио; Фрэнсис, Гилад (апрель 2020 г.). «Байесовское планирование на основе локальной выборки». Письма IEEE по робототехнике и автоматизации . 5 (2): 1954–1961. arXiv : 1909.03452 . дои : 10.1109/LRA.2020.2969145 . S2CID 210838739 .

[38] Кан, Джин-Гу; Лим, Дон Ву; Чой, Ён-Сик; Чан, У-Джин; Юнг, Джин Ву (6 января 2021 г.). «Улучшенный алгоритм RRT-Connect на основе треугольного неравенства для планирования пути робота» . Датчики . 21 (2): 333. дои : 10.3390/s21020333 . ISSN 1424-8220 . ПМЦ 7825297 . S2CID 231303809 .

[39] Кан, Джин-Гу; Юнг, Джин Ву (12 июля 2021 г.). «Метод послетреугольной замены проводки для планирования более короткого пути робота RRT». arXiv : 2107.05344 [ cs.RO ].

[40] Струб, Марлин П.; Гаммелл, Джонатан Д. (2 ноября 2021 г.). «AIT * и EIT *: асимметричное двунаправленное планирование пути на основе выборки». arXiv : 2111.01877 [ cs.RO ].

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]