Поиск точки прыжка
В информатике поиск точек перехода (JPS) — это оптимизация алгоритма поиска A* для сеток с равномерной стоимостью. Это уменьшает симметрию в процедуре поиска посредством обрезки графа, [1] исключение определенных узлов в сетке на основе предположений, которые можно сделать о соседях текущего узла, при условии, что выполняются определенные условия, относящиеся к сетке. В результате алгоритм может учитывать длинные «прыжки» по прямым (горизонтальным, вертикальным и диагональным) линиям сетки, а не небольшие шаги от одной позиции сетки к другой, которые учитывает обычный A*. [2]
Поиск точки перехода сохраняет оптимальность A*, потенциально сокращая время его работы на порядок. [1]
История
[ редактировать ]В оригинальной публикации Харабора и Грастьена представлены алгоритмы сокращения соседей и идентификации преемников. [1] Первоначальный алгоритм отсечения соседей допускал срезание углов, а это означало, что алгоритм можно было использовать только для перемещения агентов с нулевой шириной, ограничивая его применение либо реальными агентами (например, робототехникой), либо симуляциями (например, многими играми). .
Авторы представили измененные правила обрезки для тех случаев, когда обрезка углов не допускается в следующем году. [3] В этой статье также представлен алгоритм предварительной обработки сетки, чтобы минимизировать время онлайн-поиска .
В 2014 году авторы опубликовали ряд дальнейших оптимизаций. [4] Эти оптимизации включают в себя исследование столбцов или строк узлов вместо отдельных узлов, предварительное вычисление «прыжков» в сетке и более строгие правила сокращения.
Будущая работа
[ редактировать ]Хотя поиск точек перехода ограничен однородными сетками затрат и агентами однородного размера, авторы планируют будущие исследования по применению JPS с существующими методами ускорения на основе сеток, такими как иерархические сетки. [4] [5]
Ссылки
[ редактировать ]- ^ Jump up to: а б с Д. Харабор; А. Грастиен (2011). Онлайн-обрезка графов для поиска пути на сеточных картах (PDF) . 25-я Национальная конференция по искусственному интеллекту. АААИ.
- ^ Уитмер, Натан (5 мая 2013 г.). «Пояснение к поиску точки перехода» . Позитивный просмотр вперед нулевой ширины . Архивировано из оригинала 10 марта 2014 г. Проверено 10 марта 2014 г.
- ^ Д. Харабор; А. Грастиен (2012). Система поиска пути JPS . 26-я Национальная конференция по искусственному интеллекту. АААИ. Архивировано из оригинала 09.11.2020 . Проверено 11 июля 2015 г.
- ^ Jump up to: а б Харабор, Дэниел; Грастиен, Альбан. «Улучшение поиска точек перехода» (PDF) . Колледж инженерии и информатики Австралийского национального университета . Ассоциация по развитию искусственного интеллекта (www.aaai.org) . Проверено 11 июля 2015 г.
- ^ Ади Ботеа; Мартин Мюллер (2004). «Почти оптимальный иерархический поиск пути» (PDF) . Университет Альберты . Университет Альберты.