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

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

Фон [ править ]

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

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

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

Определения [ править ]

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

Алгоритмы [ править ]

A * -based [ править ]

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

  • Поле D * [3] [4] (FD * [5] ) и 3D Поле D * [6] [7] - алгоритмы динамического поиска пути на основе D *, которые используют интерполяцию во время расширения каждой вершины и находят почти оптимальные пути через регулярные , неоднородные стоимостные сетки. Поле D * поэтому пытается решить проблему взвешенной области [8], а 3D Поле D * - соответствующую трехмерную задачу.
    • Поле D * с несколькими разрешениями [9] - Расширение поля D * для сеток с несколькими разрешениями.
  • Тета * [5] [10] - Использует тот же основной цикл как *, но для каждого расширения вершины , существует прямая видимость между проверка и преемник , . Если есть прямая видимость, используется путь от до, поскольку он всегда будет не меньше длины пути от до и до . Этот алгоритм работает только на сетках с равномерной стоимостью. [5] AP Theta * [5] [10] - это оптимизация Theta *, которая использует угловое распространение для снижения стоимости выполнения вычислений прямой видимости до O (1) и Lazy Theta * [11]- это еще одна оптимизация Theta *, которая использует ленивое вычисление для уменьшения количества вычислений прямой видимости за счет задержки вычислений прямой видимости для каждого узла с момента его исследования до момента его расширения. Инкрементальный Phi * [12] - это инкрементный , более эффективный вариант Theta *, разработанный для неизвестных 2D-сред. [13]
    • Строгая Тета * и Рекурсивная Строгая Тета * [14] улучшают Тета *, ограничивая пространство поиска тесными путями, введенными ANYA. Как и Theta *, это алгоритм, который возвращает почти оптимальные пути.
  • Блок A * [15] - Создает локальную базу данных расстояний, содержащую все возможные пути на небольшом участке сетки. Он обращается к этой базе данных, чтобы быстро находить кусочные пути под любым углом.
  • ANYA [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]
  • Informed RRT * [25] улучшает скорость сходимости RRT *, вводя эвристику, подобную тому, как A * улучшает алгоритм Дейкстры .

Приложения [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ Тансель Урас и Свен Кениг. Эмпирическое сравнение алгоритмов планирования пути под любым углом . Материалы восьмого Международного симпозиума по комбинаторному поиску.
  2. ^ П. Харт, Н. Нильссон и Б. Рафаэль, Формальная основа для эвристического определения путей с минимальной стоимостью , IEEE Trans. Syst. Наука и кибернетика , SSC-4 (2), 100-107, 1968.
  3. ^ Д. Фергюсон и А. Стенц. Поле D *: Планировщик и перепланировка пути на основе интерполяции . Материалы Международного симпозиума по исследованиям робототехники , 2005 г.
  4. ^ Дэвид Фергюсон и Энтони (Тони) Стенц, « Алгоритм Field D * для улучшенного планирования и перепланирования пути в средах с единообразными и неоднородными затратами », tech. отчет CMU-RI-TR-05-19, Институт робототехники, Университет Карнеги-Меллона, июнь 2005 г.
  5. ^ a b c d А. Нэш, К. Даниэль, С. Кениг и А. Фельнер. Theta *: планирование пути под любым углом на сетке . В материалах конференции AAAI по искусственному интеллекту , страницы 1177–1183, 2007 г.
  6. ^ Карстен, Джозеф; Фергюсон, Дэйв; Стенц, Энтони (9–15 октября 2006 г.). «3D-поле D *: улучшенное планирование пути и перепланирование в трех измерениях» (PDF) . Интеллектуальные роботы и системы, 2006 IEEE / RSJ Международная конференция по . Материалы Международной конференции IEEE / RSJ 2006 года по интеллектуальным роботам и системам. Пекин, Китай: IEEE . С. 3381–3386. DOI : 10.1109 / IROS.2006.282516 . Проверено 7 ноября 2014 .
  7. ^ Карстен, Дж .; Ferguson, D .; Стенц, А. (2006). «3D Поле D: Улучшенное планирование пути и перепланирование в трех измерениях». 2006 Международная конференция IEEE / RSJ по интеллектуальным роботам и системам . п. 3381. CiteSeerX 10.1.1.188.150 . DOI : 10.1109 / IROS.2006.282516 . ISBN  978-1-4244-0258-8.
  8. ^ Митчелл, JSB; Пападимитриу, СН (1991). «Проблема взвешенной области: поиск кратчайших путей через взвешенное плоское подразделение». Журнал ACM . 38 : 18–73. DOI : 10.1145 / 102782.102784 . ЛВП : 1813/8768 .
  9. ^ Дэйв Фергюсон и Энтони Стенц. Поле с несколькими разрешениями D * . Материалы Международной конференции по интеллекту, 2006.
  10. ^ a b Даниил, К .; Nash, A .; Koenig, S .; Фельнер, А. (2010). "Theta *: планирование пути под любым углом на сетке" (PDF) . Журнал исследований искусственного интеллекта . 39 : 533–579. DOI : 10.1613 / jair.2994 .
  11. ^ Нэш, А .; Koenig, S .; Тови, К. (2010). «Ленивая тета *: планирование пути под любым углом и анализ длины пути в 3D» (PDF) . Труды конференции AAAI по искусственному интеллекту (AAAI) .
  12. ^ Нэш, А .; 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. DOI : 10.1109 / ICRA.2017.7989733 .
  18. ^ Синюков, Дмитрий А .; Падир, Таскин (2020). "CWave: теория и практика быстрого алгоритма планирования пути под любым углом с одним источником". Роботика . Издательство Кембриджского университета. 38 (2): 207–234. DOI : 10.1017 / S0263574719000560 .
  19. ^ О, Шунхао; Леонг, Хон Вай (5 июня 2017 г.). «Графики разреженной видимости краев N-уровня: быстрый поиск оптимального пути под любым углом с использованием иерархических тугих путей» . Десятый ежегодный симпозиум по комбинаторному поиску .
  20. ^ a b Junior: Стэнфордский вход в городской вызов
  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 . DOI : 10.1109 / IROS.2014.6942976 . ISBN 978-1-4799-6934-0.

Внешние ссылки [ править ]

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