Планирование пути под любым углом

Алгоритм поиска кратчайших евклидовых путей

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

Алгоритмы планирования пути под любым углом — это алгоритмы поиска пути , которые ищут евклидов кратчайший путь между двумя точками на карте сетки , допуская при этом повороты на пути под любым углом. Результатом является путь, который напрямую пересекает открытые области и имеет относительно мало поворотов. ^[1] Более традиционные алгоритмы поиска пути, такие как A*, либо не обладают достаточной производительностью, либо создают неровные, косвенные пути.

Фон

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

• A* с 8-связным дискретным графом сетки (2D; 26 для трехмерного тройного кубического графа) очень быстр, но рассматривает только пути с шагом в 45 градусов. Такое поведение дает в среднем 8% дополнительной длины пути в 2D и 13% в 3D. ^{[2] : 60, 69} Быстрый шаг после сглаживания может быть использован для выпрямления (и, таким образом, укорачивания) неровного вывода, но результат не гарантированно будет оптимальным, поскольку он не рассматривает все возможные пути. (Более конкретно, они не могут изменить то, какая сторона заблокированной ячейки пересекается.) Преимущество в том, что будут применяться все оптимизации сетки A*, такие как поиск точки скачка .
• Граф видимости со всеми точками сетки можно искать с помощью A* для оптимального решения в 2D пространстве. Однако производительность проблематична, поскольку количество ребер в графе с вершинами равно . Такой граф не всегда обеспечивает оптимальное решение в 3D пространстве. ^[2] ${\displaystyle V}$ ${\displaystyle O(V^{2})}$

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

Определения

Натянутый путь

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

Из одного источника

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

Алгоритмы

A*-основанный

На сегодняшний день разработано пять основных алгоритмов планирования траектории под любым углом, основанных на эвристическом алгоритме поиска A* ^{[3] , все из которых распространяют информацию вдоль краев сетки:}

• Поле D* ^{[4] [5]} (FD* ^[6] ) и 3D Поле D* ^{[7] [8]} - Динамические алгоритмы поиска пути на основе D*, которые используют интерполяцию во время каждого расширения вершины и находят почти оптимальные пути через регулярные , неравномерные сетки стоимости. Поэтому Поле D* пытается решить задачу взвешенной области ^[9] , а 3D Поле D* - соответствующую трехмерную задачу.
  • Поле D* с несколькими разрешениями ^[10] – Расширение поля D* для сеток с несколькими разрешениями.
• Theta* ^{[6] [11]} - Использует тот же основной цикл, что и A*, но для каждого расширения вершины есть проверка прямой видимости между и последующим элементом , . Если есть прямая видимость, используется путь от до , поскольку он всегда будет по крайней мере таким же коротким, как путь от до и до . Этот алгоритм работает только на сетках с равномерной стоимостью. ^[6] AP Theta* ^{[6] [11]} - это оптимизация Theta*, которая использует распространение угла для снижения стоимости выполнения вычислений прямой видимости до O (1) . ${\displaystyle s}$ ${\displaystyle parent(s)}$ ${\displaystyle s}$ ${\displaystyle s'}$ ${\displaystyle parent(s)}$ ${\displaystyle s'}$ ${\displaystyle parent(s)}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle s'}$
  • Lazy Theta* ^[12] — это еще одна оптимизация Theta*, которая использует ленивую оценку для сокращения количества вычислений прямой видимости путем задержки вычислений прямой видимости для каждого узла с момента его исследования до момента его расширения. Она достаточно способна работать в трехмерном пространстве.
  • Инкрементный Phi* ^[13] — это инкрементный , более эффективный вариант Theta*, разработанный для неизвестных двумерных сред. ^[2]
  • Strict Theta* и Recursive Strict Theta* ^[14] улучшает Theta*, ограничивая пространство поиска до Taut Paths, представленных ANYA. Как и Theta*, это алгоритм, который возвращает почти оптимальные пути.
• Блок A* ^[15] - Генерирует локальную базу данных расстояний, содержащую все возможные пути на небольшом участке сетки. Он ссылается на эту базу данных для быстрого поиска кусочно-любых угловых путей.
• ANYA ^[16] - Находит оптимальные пути под любым углом, ограничивая пространство поиска до натянутых путей (путь, где каждое изменение направления на пути «оборачивает» плотно вокруг некоторого препятствия); рассматривая интервал точек как узел, а не как отдельную точку. Самый быстрый из известных оптимальных методов онлайн. Этот алгоритм ограничен двумерными сетками.
• CWave ^{[17] [18]} - Использует геометрические примитивы (дискретные дуги окружности и линии) для представления распространяющегося волнового фронта на сетке. Для планирования пути с одним источником на практических картах он демонстрирует более высокую скорость, чем методы на основе поиска по графу. Существуют оптимальные и целочисленные арифметические реализации.

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

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

на основе RRT

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

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

Другие алгоритмы

• Вероятностная дорожная карта

Приложения

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

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

• Планирование движения

Ссылки

1. Тансель Урас и Свен Кёниг. Эмпирическое сравнение алгоритмов планирования пути под любым углом. Труды Восьмого международного симпозиума по комбинаторному поиску.
2. А. Нэш. Планирование траектории под любым углом. Кандидатская диссертация, кафедра компьютерных наук, Университет Южной Калифорнии, Лос-Анджелес (Калифорния), 2012.
3. П. Харт, Н. Нильссон и Б. Рафаэль, Формальная основа для эвристического определения путей с минимальной стоимостью, IEEE Trans. Syst. Science and Cybernetics , SSC-4(2), 100-107, 1968.
4. Д. Фергюсон и А. Стенц. Поле D*: Планировщик и перепланировщик путей на основе интерполяции. Труды Международного симпозиума по исследованиям в области робототехники , 2005.
5. Дэвид Фергюсон и Энтони (Тони) Стенц, «Алгоритм Field D* для улучшенного планирования и перепланирования пути в однородной и неоднородной среде», технический отчет CMU-RI-TR-05-19, Институт робототехники, Университет Карнеги-Меллона, июнь 2005 г.
6. А. Нэш, К. Дэниел, С. Кёниг и А. Фелнер. Theta*: Планирование траектории под любым углом на сетках. В трудах конференции AAAI по искусственному интеллекту , страницы 1177–1183, 2007.
7. Карстен, Джозеф; Фергюсон, Дейв; Стенц, Энтони (9–15 октября 2006 г.). «3D Field D*: Improved Path Planning and Replanning in Three Dimensions» (PDF) . Интеллектуальные роботы и системы, Международная конференция IEEE/RSJ 2006 г. по . Труды Международной конференции IEEE/RSJ 2006 г. по интеллектуальным роботам и системам. Пекин, Китай: IEEE . стр. 3381–3386. doi :10.1109/IROS.2006.282516 . Получено 07.11.2014 .
8. Карстен, Дж.; Фергюсон, Д.; Стенц, А. (2006). "3D Field D: Улучшенное планирование и перепланирование пути в трех измерениях". Международная конференция IEEE/RSJ по интеллектуальным роботам и системам 2006 г. стр. 3381. CiteSeerX 10.1.1.188.150 . doi :10.1109/IROS.2006.282516. ISBN  978-1-4244-0258-8. S2CID  1845942.
9. Митчелл, JSB; Пападимитриу, CH (1991). «Проблема взвешенной области: нахождение кратчайших путей через взвешенное плоское подразделение». Журнал ACM . 38 : 18–73. doi : 10.1145/102782.102784. hdl : 1813/8768 . S2CID  12673773.
10. Дэйв Фергюсон и Энтони Стенц. Поле D* с множественным разрешением. Труды Международной конференции по интеллектуальным технологиям, 2006.
11. Daniel, K.; Nash, A.; Koenig, S.; Felner, A. (2010). "Theta*: планирование траектории под любым углом на сетках" (PDF) . Журнал исследований искусственного интеллекта . 39 : 533–579. doi : 10.1613/jair.2994 .
12. Нэш, А.; Кёниг, С.; Тови, К. (2010). «Ленивая тета*: планирование пути под любым углом и анализ длины пути в 3D» (PDF) . Труды конференции AAAI по искусственному интеллекту . 24 : 147–154. doi :10.1609/aaai.v24i1.7566. S2CID  3754577.
13. Нэш, А.; Кёниг, С.; Лихачев, М. (2009). «Инкрементный Phi*: Инкрементное планирование траектории любого угла на сетках» (PDF) . Труды Международной объединенной конференции по искусственному интеллекту (IJCAI) : 1824–1830.
14. Шунхао О, Хон Вай Леонг, 2016. Строгая Тета*: Планирование более коротких путей движения с использованием узких путей. В трудах Двадцать шестой международной конференции по автоматизированному планированию и составлению расписаний. https://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13049
15. P. Yap, N. Burch, R. Holte и J. Schaeffer, Block A*: Поиск на основе баз данных с приложениями в планировании пути под любым углом. Труды двадцать пятой конференции AAAI по искусственному интеллекту, 2011.
16. Дэниел Харабор и Альбан Грастиен. Оптимальный алгоритм поиска пути под любым углом. Труды двадцать третьей международной конференции по автоматизированному планированию и составлению расписаний.
17. Синюков, Дмитрий А.; Падир, Таскин (май–июнь 2017 г.). «CWave: высокопроизводительное планирование траектории с одним источником и любым углом наклона на сетке». Труды Международной конференции IEEE по робототехнике и автоматизации (ICRA) 2017 г. . Международная конференция IEEE по робототехнике и автоматизации (ICRA) 2017 г. Сингапур: IEEE . стр. 6190–6197. doi :10.1109/ICRA.2017.7989733.
18. Синюков, Дмитрий А.; Падир, Таскин (2020). «CWave: Теория и практика быстрого алгоритма планирования пути с любым углом и одним источником». Robotica . 38 (2). Cambridge University Press: 207–234. doi : 10.1017/S0263574719000560. S2CID  182189674.
19. О, Шунхао; Леонг, Хон Вай (5 июня 2017 г.). «График видимости разреженных ребер N-уровня: быстрый оптимальный поиск пути под любым углом с использованием иерархических узких путей». Десятый ежегодный симпозиум по комбинаторному поиску . arXiv : 1702.01524 .
20. Куи, Майкл; Харабор, Дэниел Д.; Грастьен, Албан (2017). «Безкомпромиссный поиск пути на навигационной сетке». Труды Двадцать шестой Международной совместной конференции по искусственному интеллекту : 496–502.
21. Junior: Стэнфордский университет в городском конкурсе
22. Петерайт, Янко; Эмтер, Томас; Фрей, Кристиан В.; Копфштедт, Томас; Бойтель, Андреас (май 2012 г.). «Применение гибридного A* к автономному мобильному роботу для планирования пути в неструктурированной внешней среде». ROBOTIK 2012; 7-я немецкая конференция по робототехнике : 1–6.
23. ЛаВаль, Стивен М. (октябрь 1998 г.). «Быстрое исследование случайных деревьев: новый инструмент для планирования пути» (PDF) . Технический отчет (TR 98–11).
24. Караман, Сертак; Фраззоли, Эмилио (3 мая 2010 г.). «Алгоритмы на основе инкрементальной выборки для оптимального планирования движения». arXiv : 1005.0416 [cs.RO].
25. Караман, Сертак; Фраззоли, Эмилио (5 мая 2011 г.). «Алгоритмы на основе выборки для оптимального планирования движения». arXiv : 1105.1186 [cs.RO].
26. Гэммелл, Джонатан Д.; Шриниваса, Сиддхартха С.; Барфут, Тимоти Д. (2014). «Информированное RRT*: оптимальное планирование пути на основе выборки, сфокусированное на прямой выборке допустимой эллипсоидальной эвристики». Международная конференция IEEE/RSJ по интеллектуальным роботам и системам 2014 г. стр. 2997–3004. arXiv : 1404.2334 . doi :10.1109/IROS.2014.6942976. ISBN 978-1-4799-6934-0.

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

• Ленивая Тета*: более быстрое планирование пути под любым углом
• А. Нэш и С. Кёниг. Планирование траектории под любым углом. Журнал «Искусственный интеллект» , 34, (4), 85-107, 2013.
• Поиск пути под любым углом, открытый демонстрационный код Shunhao Oh