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

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

Фон

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

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

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

Определения

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

Алгоритмы

на основе A*

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

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

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

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

на основе ЗПТ

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

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

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

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

Приложения

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

См. также

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

Ссылки

^ Тансель Урас и Свен Кениг. Эмпирическое сравнение алгоритмов планирования пути под любым углом . Материалы Восьмого международного симпозиума по комбинаторному поиску.
^ Jump up to: ^а ^б ^с А. Нэш. Планирование пути под любым углом . Кандидатская диссертация, факультет компьютерных наук, Университет Южной Калифорнии, Лос-Анджелес (Калифорния), 2012 г.
^ П. Харт, Н. Нильссон и Б. Рафаэль, Формальная основа для эвристического определения путей с минимальной стоимостью , IEEE Trans. Сист. Наука и кибернетика , SSC-4(2), 100-107, 1968.
^ Д. Фергюсон и А. Стенц. Поле D*: Планировщик пути и перепланировщик на основе интерполяции . Материалы Международного симпозиума по исследованиям в области робототехники , 2005 г.
^ Дэвид Фергюсон и Энтони (Тони) Стенц, « Алгоритм поля D * для улучшенного планирования пути и перепланирования в средах с равномерными и неоднородными затратами », техн. отчет CMU-RI-TR-05-19, Институт робототехники, Университет Карнеги-Меллон, июнь 2005 г.
^ Jump up to: ^а ^б ^с ^д А. Нэш, К. Дэниел, С. Кениг и А. Фельнер. Тета*: планирование пути под любым углом на сетках . В материалах конференции AAAI по искусственному интеллекту , страницы 1177–1183, 2007 г.
^ Карстен, Джозеф; Фергюсон, Дэйв; Стенц, Энтони (9–15 октября 2006 г.). «3D-поле D *: улучшенное планирование и перепланирование пути в трех измерениях» (PDF) . Интеллектуальные роботы и системы, Международная конференция IEEE/RSJ 2006 г., посвященная . Материалы Международной конференции IEEE/RSJ 2006 г. по интеллектуальным роботам и системам. Пекин, Китай: IEEE . стр. 3381–3386. дои : 10.1109/IROS.2006.282516 . Проверено 7 ноября 2014 г.
^ Карстен, Дж.; Фергюсон, Д.; Стенц, А. (2006). «3D-поле D: улучшенное планирование и перепланирование пути в трех измерениях». 2006 Международная конференция IEEE/RSJ по интеллектуальным роботам и системам . п. 3381. CiteSeerX 10.1.1.188.150 . дои : 10.1109/IROS.2006.282516 . ISBN 978-1-4244-0258-8 . S2CID 1845942 .
^ Митчелл, JSB; Пападимитриу, CH (1991). «Проблема взвешенного региона: поиск кратчайших путей через взвешенное плоское подразделение». Журнал АКМ . 38 : 18–73. дои : 10.1145/102782.102784 . hdl : 1813/8768 . S2CID 12673773 .
^ Дэйв Фергюсон и Энтони Стенц. Поле мультиразрешения D* . Материалы Международной конференции по интеллекту, 2006 г.
^ Jump up to: ^а ^б Дэниел, К.; Нэш, А.; Кениг, С.; Фельнер, А. (2010). «Тета *: планирование пути под любым углом на сетках» (PDF) . Журнал исследований искусственного интеллекта . 39 : 533–579. дои : 10.1613/jair.2994 .
^ Нэш, А.; Кениг, С.; Тови, К. (2010). «Lazy Theta*: планирование пути под любым углом и анализ длины пути в 3D» (PDF) . Материалы конференции AAAI по искусственному интеллекту . 24 : 147–154. дои : 10.1609/aaai.v24i1.7566 . S2CID 3754577 .
^ Нэш, А.; Кениг, С.; Лихачев, М. (2009). «Инкрементное Phi *: поэтапное планирование пути под любым углом на сетках» (PDF) . Материалы Международной совместной конференции по искусственному интеллекту (IJCAI) : 1824–1830 гг.
^ Шуньхао О, Хон Вай Леонг, 2016. Строгая Тета *: планирование более короткого пути движения с использованием тугих путей. В материалах двадцать шестой Международной конференции по автоматизированному планированию и составлению графиков. https://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13049
^ П. Яп, Н. Берч, Р. Холте и Дж. Шеффер, Блок A *: Поиск на основе базы данных с приложениями при планировании пути под любым углом . Материалы двадцать пятой конференции AAAI по искусственному интеллекту, 2011 г.
^ Дэниел Харабор и Альбан Грастиен. Оптимальный алгоритм поиска пути под любым углом . Материалы двадцать третьей международной конференции по автоматизированному планированию и составлению графиков.
^ Синюков Дмитрий А.; Падир, Таскин (май – июнь 2017 г.). «CWave: Высокопроизводительное планирование пути под любым углом с одним источником на сетке». Материалы Международной конференции IEEE по робототехнике и автоматизации (ICRA) 2017 г. Международная конференция IEEE по робототехнике и автоматизации (ICRA), 2017 г. Сингапур: IEEE . стр. 6190–6197. дои : 10.1109/ICRA.2017.7989733 .
^ Синюков Дмитрий А.; Падир, Таскин (2020). «CWave: теория и практика быстрого алгоритма планирования пути под любым углом с одним источником». Роботика . 38 (2). Издательство Кембриджского университета: 207–234. дои : 10.1017/S0263574719000560 . S2CID 182189674 .
^ О, Шуньхао; Леонг, Хон Вай (5 июня 2017 г.). «Графы разреженной видимости на N-уровне по краям: быстрый оптимальный поиск пути под любым углом с использованием иерархических тугих путей» . Десятый ежегодный симпозиум по комбинаторному поиску . arXiv : 1702.01524 .
^ Кюи, Майкл; Харабор, Дэниел Д.; Грастиен, Альбан (2017). «Бескомпромиссный поиск пути в навигационной сетке» . Материалы двадцать шестой международной совместной конференции по искусственному интеллекту : 496–502.
^ Jump up to: ^а ^б Юниор: участие Стэнфорда в Urban Challenge
^ Петерайт, Янко; Эмтер, Томас; Фрей, Кристиан В.; Копфштедт, Томас; Бойтель, Андреас (май 2012 г.). «Применение гибрида A* к автономному мобильному роботу для планирования пути в неструктурированной внешней среде» . РОБОТИК 2012; 7-я Немецкая конференция по робототехнике : 1–6.
^ ЛаВалль, Стивен М. (октябрь 1998 г.). «Быстрое исследование случайных деревьев: новый инструмент для планирования пути» (PDF) . Технический отчет (ТР 98–11).
^ Караман, Сертак; Фраццоли, Эмилио (3 мая 2010 г.). «Алгоритмы оптимального планирования движения на основе дополнительной выборки». arXiv : 1005.0416 [ cs.RO ].
^ Караман, Сертак; Фраццоли, Эмилио (5 мая 2011 г.). «Алгоритмы оптимального планирования движения на основе выборки». arXiv : 1105.1186 [ cs.RO ].
^ Гаммелл, Джонатан Д.; Шриниваса, Сиддхартха С.; Барфут, Тимоти Д. (2014). «Информированная RRT *: оптимальное планирование пути на основе выборки, ориентированное на прямую выборку допустимой эллипсоидальной эвристики». Международная конференция IEEE/RSJ по интеллектуальным роботам и системам , 2014 г. стр. 2997–3004. arXiv : 1404.2334 . дои : 10.1109/IROS.2014.6942976 . ISBN 978-1-4799-6934-0 .

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

Lazy Theta*: более быстрое планирование траектории под любым углом
А. Нэш и С. Кениг. Планирование пути под любым углом . Журнал «Искусственный интеллект» , 34, (4), 85-107, 2013.
Поиск под любым углом , демонстрационный код с открытым исходным кодом Шуньхао О

[1] Тансель Урас и Свен Кениг. Эмпирическое сравнение алгоритмов планирования пути под любым углом . Материалы Восьмого международного симпозиума по комбинаторному поиску.

[NashThesis-2] Jump up to: ^а ^б ^с А. Нэш. Планирование пути под любым углом . Кандидатская диссертация, факультет компьютерных наук, Университет Южной Калифорнии, Лос-Анджелес (Калифорния), 2012 г.

[3] П. Харт, Н. Нильссон и Б. Рафаэль, Формальная основа для эвристического определения путей с минимальной стоимостью , IEEE Trans. Сист. Наука и кибернетика , SSC-4(2), 100-107, 1968.

[4] Д. Фергюсон и А. Стенц. Поле D*: Планировщик пути и перепланировщик на основе интерполяции . Материалы Международного симпозиума по исследованиям в области робототехники , 2005 г.

[5] Дэвид Фергюсон и Энтони (Тони) Стенц, « Алгоритм поля D * для улучшенного планирования пути и перепланирования в средах с равномерными и неоднородными затратами », техн. отчет CMU-RI-TR-05-19, Институт робототехники, Университет Карнеги-Меллон, июнь 2005 г.

[Daniel_et_al._2007-6] Jump up to: ^а ^б ^с ^д А. Нэш, К. Дэниел, С. Кениг и А. Фельнер. Тета*: планирование пути под любым углом на сетках . В материалах конференции AAAI по искусственному интеллекту , страницы 1177–1183, 2007 г.

[7] Карстен, Джозеф; Фергюсон, Дэйв; Стенц, Энтони (9–15 октября 2006 г.). «3D-поле D *: улучшенное планирование и перепланирование пути в трех измерениях» (PDF) . Интеллектуальные роботы и системы, Международная конференция IEEE/RSJ 2006 г., посвященная . Материалы Международной конференции IEEE/RSJ 2006 г. по интеллектуальным роботам и системам. Пекин, Китай: IEEE . стр. 3381–3386. дои : 10.1109/IROS.2006.282516 . Проверено 7 ноября 2014 г.

[8] Карстен, Дж.; Фергюсон, Д.; Стенц, А. (2006). «3D-поле D: улучшенное планирование и перепланирование пути в трех измерениях». 2006 Международная конференция IEEE/RSJ по интеллектуальным роботам и системам . п. 3381. CiteSeerX 10.1.1.188.150 . дои : 10.1109/IROS.2006.282516 . ISBN 978-1-4244-0258-8 . S2CID 1845942 .

[9] Митчелл, JSB; Пападимитриу, CH (1991). «Проблема взвешенного региона: поиск кратчайших путей через взвешенное плоское подразделение». Журнал АКМ . 38 : 18–73. дои : 10.1145/102782.102784 . hdl : 1813/8768 . S2CID 12673773 .

[10] Дэйв Фергюсон и Энтони Стенц. Поле мультиразрешения D* . Материалы Международной конференции по интеллекту, 2006 г.

[Daniel_et_al._2010-11] Jump up to: ^а ^б Дэниел, К.; Нэш, А.; Кениг, С.; Фельнер, А. (2010). «Тета *: планирование пути под любым углом на сетках» (PDF) . Журнал исследований искусственного интеллекта . 39 : 533–579. дои : 10.1613/jair.2994 .

[12] Нэш, А.; Кениг, С.; Тови, К. (2010). «Lazy Theta*: планирование пути под любым углом и анализ длины пути в 3D» (PDF) . Материалы конференции AAAI по искусственному интеллекту . 24 : 147–154. дои : 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] П. Яп, Н. Берч, Р. Холте и Дж. Шеффер, Блок A *: Поиск на основе базы данных с приложениями при планировании пути под любым углом . Материалы двадцать пятой конференции AAAI по искусственному интеллекту, 2011 г.

[16] Дэниел Харабор и Альбан Грастиен. Оптимальный алгоритм поиска пути под любым углом . Материалы двадцать третьей международной конференции по автоматизированному планированию и составлению графиков.

[17] Синюков Дмитрий А.; Падир, Таскин (май – июнь 2017 г.). «CWave: Высокопроизводительное планирование пути под любым углом с одним источником на сетке». Материалы Международной конференции IEEE по робототехнике и автоматизации (ICRA) 2017 г. Международная конференция IEEE по робототехнике и автоматизации (ICRA), 2017 г. Сингапур: IEEE . стр. 6190–6197. дои : 10.1109/ICRA.2017.7989733 .

[18] Синюков Дмитрий А.; Падир, Таскин (2020). «CWave: теория и практика быстрого алгоритма планирования пути под любым углом с одним источником». Роботика . 38 (2). Издательство Кембриджского университета: 207–234. дои : 10.1017/S0263574719000560 . S2CID 182189674 .

[19] О, Шуньхао; Леонг, Хон Вай (5 июня 2017 г.). «Графы разреженной видимости на N-уровне по краям: быстрый оптимальный поиск пути под любым углом с использованием иерархических тугих путей» . Десятый ежегодный симпозиум по комбинаторному поиску . arXiv : 1702.01524 .

[20] Кюи, Майкл; Харабор, Дэниел Д.; Грастиен, Альбан (2017). «Бескомпромиссный поиск пути в навигационной сетке» . Материалы двадцать шестой международной совместной конференции по искусственному интеллекту : 496–502.

[has-21] Jump up to: ^а ^б Юниор: участие Стэнфорда в Urban Challenge

[22] Петерайт, Янко; Эмтер, Томас; Фрей, Кристиан В.; Копфштедт, Томас; Бойтель, Андреас (май 2012 г.). «Применение гибрида A* к автономному мобильному роботу для планирования пути в неструктурированной внешней среде» . РОБОТИК 2012; 7-я Немецкая конференция по робототехнике : 1–6.

[lavalle_tr98-23] ЛаВалль, Стивен М. (октябрь 1998 г.). «Быстрое исследование случайных деревьев: новый инструмент для планирования пути» (PDF) . Технический отчет (ТР 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 . дои : 10.1109/IROS.2014.6942976 . ISBN 978-1-4799-6934-0 .

[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]