Планирование траектории под любым углом - Any-angle path planning

Путь, найденный A * на октильной сетке, в сравнении с кратчайшим путем между начальным и целевым узлами.

Планирование траектории под любым углом алгоритмы являются подмножеством Найти путь алгоритмы, которые ищут путь между двумя точками в пространстве и позволяют поворотам на пути иметь любой угол. В результате получается путь, который ведет прямо к цели и имеет относительно мало поворотов.[1] Другие алгоритмы поиска пути, такие как А * ограничивайте пути сеткой, которая создает неровные непрямые пути.

Фон

На картах реального мира и на многих игровых картах есть открытые области, по которым наиболее эффективно проходить прямой путь. Традиционные алгоритмы плохо приспособлены для решения этих проблем:

  • A * с 8-подключенным дискретным сетка графика работает очень быстро, но просматривает пути только с шагом 45 градусов. Быстрый шаг пост-сглаживания можно использовать для выравнивания (таким образом, сокращения) неровностей на выходе, но не гарантируется, что результат будет оптимальным, так как он не учитывает все возможные пути. (В частности, они не могут изменить, какая сторона заблокированной ячейки пройдена.) Преимущество состоит в том, что все оптимизации сетки A * похожи на поиск точки перехода будет применяться.
  • А график видимости со всеми точками сетки можно найти оптимальное решение с помощью A *. Однако производительность проблематична, поскольку количество ребер в графе с вершины .

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

Определения

Тугой путь
Путь, в котором каждое изменение курса «огибает» какое-то препятствие. Для равномерной сетки оптимальными могут быть только тугие пути.
Единственный источник
Задача поиска пути, которая пытается найти кратчайший путь ко всем частям графа, начиная с одной вершины.

Алгоритмы

На основе A *

Пока что пять основных алгоритмов планирования пути под любым углом, основанных на алгоритме эвристического поиска. А *[2] были разработаны, все из которых распространяют информацию по краям сетки:

  • Поле D *[3][4] (FD *[5]) и 3D Поле D *[6][7] - Алгоритмы динамического поиска пути на основе D *, которые используют интерполяцию во время каждого расширения вершины и находят почти оптимальные пути через обычный, сетки неоднородных затрат. Поле D * поэтому пытается решить проблема взвешенной области[8] и 3D Field D * соответствующая трехмерная задача.
    • Поле с несколькими разрешениями D *[9] - Расширение поля D * для сеток с разным разрешением.
  • Тета *[5][10] - Использует тот же основной цикл, что и A *, но для каждого расширения вершины , есть прямая видимость между и преемник , . Если есть прямая видимость, путь от к используется, поскольку он всегда будет по крайней мере такой же короткой, как путь от к и к . Этот алгоритм работает только на сетках с равномерной стоимостью.[5] AP Theta *[5][10] является оптимизацией Theta *, которая использует угловое распространение для снижения затрат на выполнение вычислений прямой видимости до О (1), и Ленивая Тета *[11] - это еще одна оптимизация Theta *, которая использует ленивое вычисление для уменьшения количества вычислений прямой видимости за счет задержки вычислений прямой видимости для каждого узла с момента его исследования до момента его расширения. Инкрементальный фи *[12] является добавочный, более эффективный вариант Theta *, разработанный для неизвестных 2D сред.[13]
    • Строгая тета * и рекурсивная строгая тета * [14] улучшает Theta *, ограничивая область поиска Тугими путями, введенными ANYA. Как и Theta *, это алгоритм, который возвращает почти оптимальные пути.
  • Блок А * [15] - Создает локальную базу данных расстояний, содержащую все возможные пути на небольшом участке сетки. Он ссылается на эту базу данных, чтобы быстро находить кусочные пути под любым углом.
  • АНЯ[16] - Находит оптимальные пути под любым углом, ограничивая пространство поиска узкими путями (путь, при котором каждое изменение курса на пути плотно «оборачивается» вокруг некоторого препятствия); рассматривать интервал точек как узел, а не как отдельную точку. Самая быстрая из известных оптимальных онлайн-технологий.
  • CWave[17][18] - Использует геометрические примитивы (дискретные дуги окружности и линии) для представления фронта распространяющейся волны на сетке. Для планирования пути из одного источника на практических картах продемонстрировано, что он быстрее, чем методы, основанные на поиске по графам. Есть оптимальные и целочисленные арифметические реализации.

Есть также алгоритм на основе A *, отличный от указанного выше семейства:

  • Производительность подхода графа видимости может быть значительно улучшена за счет разреженного подхода, который учитывает только ребра, способные образовывать тугие пути. Многоуровневая версия ENLSVG, как известно, быстрее ANYA, но ее можно использовать только с предварительной обработкой.[19]
  • Подобно решению RRT, обсуждаемому ниже, часто необходимо также учитывать ограничения рулевого управления при пилотировании реального транспортного средства. Гибрид A * - это расширение A *, которое учитывает два дополнительных измерения, представляющих состояние транспортного средства, так что пути фактически возможны. Он был создан Stanford Racing как часть навигационной системы для Junior, их вход в DARPA Urban Challenge.[20] Более подробное обсуждение написано Peterit, et al.[21]

На основе RRT

Основная статья: Быстро исследуемое случайное дерево § Варианты

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

  • Быстро исследуемый случайный граф (RRG) и RRT *[23][24]
  • Информированный RRT *[25] улучшает скорость сходимости RRT *, вводя эвристику, аналогично тому, как А * улучшается на Алгоритм Дейкстры.

Приложения

Планирование траектории под любым углом полезно для робот-навигация и стратегия в реальном времени игры, где желательны более оптимальные пути. Гибрид A *, например, использовался в качестве входа для испытания DARPA.[20] Свойства управления рулем в некоторых примерах также применимы к автономным автомобилям.

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

Рекомендации

  1. ^ Тансель Урас и Свен Кениг. Эмпирическое сравнение алгоритмов планирования пути под любым углом. Материалы восьмого Международного симпозиума по комбинаторному поиску.
  2. ^ П. Харт, Н. Нильссон и Б. Рафаэль, Формальная основа для эвристического определения путей минимальной стоимости, IEEE Trans. Syst. Наука и кибернетика, ССК-4 (2), 100-107, 1968.
  3. ^ Д. Фергюсон и А. Стенц. Поле D *: планировщик и перепланировщик пути на основе интерполяции. Материалы Международного симпозиума по робототехническим исследованиям, 2005.
  4. ^ Дэвид Фергюсон и Энтони (Тони) Стенц "Алгоритм поля D * для улучшенного планирования пути и перепланирования в средах с единообразной и неоднородной стоимостью, "технический отчет CMU-RI-TR-05-19, Институт робототехники, Университет Карнеги-Меллона, июнь 2005 г.
  5. ^ а б c d А. Нэш, К. Даниэль, С. Кениг и А. Фельнер. Theta *: планирование пути под любым углом на сетке. В Материалы конференции AAAI по искусственному интеллекту, страницы 1177–1183, 2007.
  6. ^ Карстен, Джозеф; Фергюсон, Дэйв; Стенц, Энтони (9–15 октября 2006 г.). «3D-поле D *: улучшенное планирование пути и перепланирование в трех измерениях» (PDF). Интеллектуальные роботы и системы, Международная конференция IEEE / RSJ 2006 г.. Материалы Международной конференции IEEE / RSJ 2006 по интеллектуальным роботам и системам. Пекин, Китай: IEEE. С. 3381–3386. Дои:10.1109 / IROS.2006.282516. Получено 2014-11-07.
  7. ^ Carsten, J .; Ferguson, D .; Стенц, А. (2006). «3D Поле D: Улучшенное планирование пути и перепланирование в трех измерениях». 2006 Международная конференция IEEE / RSJ по интеллектуальным роботам и системам. п. 3381. CiteSeerX  10.1.1.188.150. Дои:10.1109 / IROS.2006.282516. ISBN  978-1-4244-0258-8.
  8. ^ Mitchell, J.S.B .; Пападимитриу, К. Х. (1991). «Проблема взвешенной области: поиск кратчайших путей через взвешенное плоское подразделение». Журнал ACM. 38: 18–73. Дои:10.1145/102782.102784. HDL:1813/8768.
  9. ^ Дэйв Фергюсон и Энтони Стенц. Поле с несколькими разрешениями D *. Материалы Международной конференции по интеллекту, 2006.
  10. ^ а б Daniel, K .; Nash, A .; Koenig, S .; Фельнер, А. (2010). «Тета *: планирование пути под любым углом на сетке» (PDF). Журнал исследований искусственного интеллекта. 39: 533–579. Дои:10.1613 / jair.2994.
  11. ^ Nash, A .; Koenig, S .; Тови, К. (2010). "Ленивая тета *: планирование пути под любым углом и анализ длины пути в 3D" (PDF). Материалы конференции AAAI по искусственному интеллекту (AAAI).
  12. ^ Nash, A .; Koenig, S .; Лихачев, М. (2009). «Инкрементальный фи *: добавочное планирование пути под любым углом на сетке» (PDF). Труды Международной совместной конференции по искусственному интеллекту (IJCAI): 1824–1830.
  13. ^ А. Нэш. Планирование пути под любым углом. Кандидатская диссертация, факультет компьютерных наук, Университет Южной Калифорнии, Лос-Анджелес (Калифорния), 2012 г.
  14. ^ Шунхао О, Хон Вай Леонг, 2016. Строгая тета *: планирование более короткого пути движения с использованием тугих путей. В материалах Двадцать шестой Международной конференции по автоматизированному планированию и календарному планированию. https://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13049
  15. ^ П. Яп, Н. Берч, Р. Хольте и Дж. Шеффер, Блок A *: поиск на основе базы данных с приложениями при планировании пути под любым углом. Труды Двадцать пятой конференции AAAI по искусственному интеллекту, 2011 г.
  16. ^ Даниэль Харабор и Альбан Грастьен. Оптимальный алгоритм поиска пути под любым углом. Труды двадцать третьей международной конференции по автоматизированному планированию и календарному планированию.
  17. ^ Синюков, Дмитрий А .; Падир, Таскин (май – июнь 2017 г.). «CWave: высокопроизводительное планирование пути под любым углом с одним источником в сети». Материалы Международной конференции IEEE по робототехнике и автоматизации 2017 г. (ICRA). Международная конференция IEEE по робототехнике и автоматизации, 2017 г. (ICRA). Сингапур: IEEE. С. 6190–6197. Дои:10.1109 / ICRA.2017.7989733.
  18. ^ Синюков Дмитрий А .; Падир, Таскин (2020). «CWave: теория и практика быстрого алгоритма планирования пути под любым углом с одним источником». Роботика. Издательство Кембриджского университета. 38 (2): 207–234. Дои:10.1017 / S0263574719000560.
  19. ^ О, Шунхао; Леонг, Хон Вай (5 июня 2017 г.). "Границы разреженной видимости на уровне N: быстрый поиск оптимального пути под любым углом с использованием иерархических тугих путей". Десятый ежегодный симпозиум по комбинаторному поиску.
  20. ^ а б Младший: Стэнфордский конкурс на участие в программе Urban Challenge
  21. ^ Петерейт, Янко; Эмтер, Томас; Frey, Christian W .; Копфстедт, Томас; Бейтель, Андреас (май 2012 г.). «Применение Hybrid A * к автономному мобильному роботу для планирования пути в неструктурированной внешней среде». ROBOTIK 2012; 7-я Немецкая конференция по робототехнике: 1–6.
  22. ^ ЛаВалль, Стивен М. (Октябрь 1998 г.). «Быстро исследуемые случайные деревья: новый инструмент для планирования пути» (PDF). Технический отчет (TR 98–11).
  23. ^ Караман, Сертак; Фраццоли, Эмилио (3 мая 2010 г.). «Алгоритмы на основе инкрементной выборки для планирования оптимального движения». arXiv:1005.0416 [cs.RO ].
  24. ^ Караман, Сертак; Фраццоли, Эмилио (5 мая 2011 г.). «Алгоритмы на основе выборки для планирования оптимального движения». arXiv:1105.1186 [cs.RO ].
  25. ^ Гаммелл, Джонатан Д .; Srinivasa, Siddhartha S .; Барфут, Тимоти Д. (2014). «Информированный RRT *: оптимальное планирование пути на основе выборки, ориентированное на прямую выборку допустимой эллипсоидальной эвристики». 2014 IEEE / RSJ Международная конференция по интеллектуальным роботам и системам. С. 2997–3004. arXiv:1404.2334. Дои:10.1109 / IROS.2014.6942976. ISBN  978-1-4799-6934-0.

внешняя ссылка