Данный проект представляет собой реализацию метода TransPath, предложенного в работе

Kirilenko et al., "TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers", AAAI 2023 arXiv:2212.11730

Целью проекта является ускорение классических алгоритмов поиска пути (например, A*) за счёт использования обучаемых эвристик, предсказываемых нейросетевой моделью на основе архитектуры Transformer + CNN.

В отличие от традиционных эвристик (например, октантного расстояния), которые не учитывают препятствия, TransPath обучается на наборе задач планирования и предсказывает:

Корректирующий коэффициент (correction factor) — отношение оценки стандартной эвристики к оптимальной стоимости до цели. Карту вероятностей пути (Path Probability Map, PPM) — вероятность того, что клетка лежит на кратчайшем пути. Эти эвристики используются в модифицированных версиях алгоритмов:

WA* + CF — Weighted A* с индивидуальным весом для каждой клетки. Focal Search + PPM — Focal Search с вторичной эвристикой на основе PPM. Результаты показывают, что предложенный подход:

Ускоряет поиск до 4× по сравнению с A*, Сохраняет почти оптимальное решение (среднее превышение стоимости — менее 0.3%), Обобщается на новые карты, не виденные при обучении.

Авторы:

Глухих Антон Евдокимов Максим Сираев Роберт