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