Привет! Меня зовут Константин Яковлев, я научный работник и вот уже более 15 лет я занимаюсь методами планирования траектории. Часто эта задача сводится к поиску пути на графе, для чего обычно используется алгоритм эвристического поиска A*. Этот алгоритм был предложен в 60-х годах XX века и с тех пор используется повсеместно. Скорее всего, юнит вашей любимой RTS бежит по карте с помощью той или иной вариации A*. Точно так же, под капотом беспилотного авто вы, наверняка, найдёте A*, хотя там, конечно, не только он.

A* — это хороший алгоритм, но его вычислительная эффективность сильно зависит от эвристической функции, которую должен задать разработчик. Основная проблема стандартных эвристик заключается в том, что они не учитывают расположение препятствий на карте и ведут поиск буквально напролом, тратя на это ресурсы (итерации поиска). Почему бы нам не воспользоваться современными нейросетями для решения этой проблемы, а именно попросить нейросеть посмотреть на карту и подсказать поиску как лучше обходить препятствия, чтобы быстрее (за меньшее число итераций) найти нужный путь?

Этот текст посвящен как самому алгоритму A*, так и попыткам повысить его эффективность с помощью методов искусственного интеллекта. Заодно я расскажу о том, какие новшества в этом направлении придумали мы с коллегами: научная статья на эту тему опубликована в сборнике конференции AAAI 2023.

Disclaimer. Поскольку это полноценный и самодостаточный обзор, он начинается с наглядного объяснения основ поисковых алгоритмов (по крайней мере тех идей, что важны для данного поста) и изложения некоторых интересных, но не имеющих отношение к делу фактов (из серии «как так получилось, что A* это же просто модифицированный Дейкстра, а авторы A* в своей статье на Дейкстру не сослались»). Знатоки A* могут смело эту часть пролистывать, если есть такое желание.

Итак, поехали!

Гриды, Дейкстра и A*

Гриды (англ. grid) или же, по‑научному, графы регулярной декомпозиции — это самые распространенные графовые модели для представления среды мобильного агента, когда речь заходит о планировании траектории. Идея состоит в том, что мы разбиваем мир, в котором живет и перемещается агент, на клетки двух типов: проходимые и заблокированные, и разрешаем агенту прыгать по горизонтали, вертикали и диагонали от одной проходимой клетки к другой. Стоимость каждого перехода в стандартном случае считается как 1 для ортогонального (т. е. горизонтального или вертикального) перехода и √2 для диагонального. Иногда при реализации используют 10 и 14, чтобы не возиться с float'ами. В некоторых постановках при расчете стоимости учитывают также дополнительные характеристики клеток, например, как близко они расположены к препятствиям, какой тип подстилающей поверхности имеет та или иная клетка и т. д. Но здесь и далее мы будем рассматривать простой бинарный грид с переходами, весящими 1 и √2.

Для поиска на таком клетчатом графе, естественно, можно применять стандартные алгоритмы неинформированного поиска (т. е. такие алгоритмы, которые не требуют никакой доп. информации, кроме самого графа), среди которых самым популярным является алгоритм Дейкстры. Этот алгоритм был предложен Эдгаром Дейкстрой в 1959 году. Вы можете ознакомиться с оригинальной научной статьей, вернее — заметкой, по этому алгоритму — она есть в Интернете — и обратить внимание на то, что это прямо очень компактный текст на 3 странички, содержащий всего 4 ссылки на другие работы, и не содержащий ни одной картинки и псевдокода. Сейчас, конечно, статьи (даже короткие) по computer science пишут совсем по‑другому.

Алгоритм A* можно считать эвристической модификацией алгоритма Дейкстры, которая помимо самого графа использует дополнительную информацию для поиска решения. Эта информация задается в виде функции, которая как-то оценивает длину пути от произвольной вершины графа до целевой. Эта функция называется эвристической, или короче — эвристикой. 

Представьте, что вас спрашивают, как долго вы будете добираться до Владивостока, например, из Калининграда. Понятное дело, что точно вы сказать не можете, но, опираясь на здравый смысл, можете дать примерную оценку из серии «прямых рейсов нет, надо сначала долететь до Москвы, это 4 часа, потом пересадка, минимум 1 час, потом ещё 9 часов полета, т. е. примерно 14 часов». Вот эти самые 14 часов — это и есть эвристика.

В остальном алгоритм A* пугающе похож на Дейкстру. Вот, например, так часто представляют псевдокод A* люди, которые занимаются им профессионально (рисунок взят из статьи Максима Лихачева, профессора Carnegie Melon University и автора одной из наиболее распространенных в робототехнике модификации A* — D*Lite):

Не столь важно, что именно здесь обозначают имена переменных и функций, важно другое. Если вы хотите из этого псевдокода A* получить псевдокод Дейкстры, то вам достаточно лишь чуть‑чуть модифицировать строку 7, а именно убрать (т. е. буквально просто стереть) h(s'). т. е. выкинуть из расчета эвристику. И всё.

Кажется логичным, что при таком раскладе авторы A*, которые предложили свой алгоритм в 1968 году (вот эта статья), должны бы были сослаться на статью Дейкстры (которая была, напомню, опубликована на 9 лет раньше). Но это не так! Ссылки на Дейкстру в статье по A* нет.

В 2018 году я был на Symposium on Combinatorial Search, профильном научном симпозиуме по поисковым алгоритмам, на котором отмечали 50-летие A*, и этот вопрос был озвучен. «Дедушки» поиска (см. фото), т. е. те люди, которые были близки к авторам A* и знали ситуацию изнутри, ответили на это примерно следующее: «Авторы A*, когда делали свой алгоритм, не мыслили категориями графов, а скорее решали обобщенную задачу планирования как построения и поиска по дереву решений. И они были сосредоточены на том, как отсекать ветви этого дерева с помощью эвристики.».

Как говорится — за что купил, за то и продаю. Тем не менее, overall, близкое сходство Дейкстры и A*, когда речь идет о поиске пути на сетчатом графе (т. е. наш случай) отрицать сложно.

Принцип работы

Итак, по какому‑же принципу работает поиск пути с помощью Дейкстры/A*? Это итерационный алгоритм, на каждом шаге мы выбираем вершину‑кандидат и смотрим, до каких вершин‑соседей из неё можно дойти, считаем веса путей до них и добавляем эти вершины в список вершин‑кандидатов на дальнейшее рассмотрение (а текущую вершину вычеркиваем). И так продолжаем до тех пор пока не выберем для рассмотрения целевую вершину.

Ключевой момент — как мы выбираем вершину‑кандидат на каждой итерации. Дейкстра выбирает вершину, вес пути до которой минимален (среди других вершин кандидатов). Для обозначения этого веса используется обозначение g(n), т. е. g(n) — это вес пути от старта до n, который мы знаем к текущей итерации алгоритма. A* выбирает вершину c минимальным f‑значением, которое рассчитывается по формуле f(n) = g(n) + h(n). Первое слагаемое — то же, что и в Дейкстре, вес пути от старта до n. Второе слагаемое — эвристическая оценка веса пути (просто число) от n до финиша. т. е. в отличие от Дейкстры, который «идёт во все стороны» (т.к. при поиске ему вообще всё равно на то, где финиш), A* «сфокусирован на цели» (с помощью эвристики). Можно на это смотреть и так: Дейкстра выбирает ту (не рассмотренную) вершину, до которой ближе всего идти от старта, а A* выбирает ту вершину, которая «обещает» с помощью эвристики самый короткий путь (через неё) до финиша. Очень часто эту концептуальную разницу между двумя алгоритмами иллюстрируют картинкой примерно следующего содержания:

Давайте теперь поговорим про то, с помощью чего A* фокусирует поиск и стремится сократить число итераций алгоритма — про эвристику. Напомним, что эвристическая функция h(n) — это некоторая оценка веса (длины) пути от n до финиша goal. Как же нам оценивать эту длину на гриде? Очень просто. Представим, что между n и финишем нет никаких препятствий. Тогда, агенту нужно сделать min(dx, dy) шагов по диагонали, где dx, dy — это модуль разницы по OX, OY, и затем max(dx, dy) − min(dx,dy) шагов по горизонтали/вертикали. Соответственно, в виде общей формулы мы это можем записать как:

Эта эвристика по‑русски обычно именуется диагональной. Есть и другие, но для 8-связного грида обычно используют именно диагональную эвристику, т.к. у неё есть пара важных свойств. Во‑первых, она является допустимой, т. е. не переоценивает вес пути до финиша от любой клетки грида (неважно какие на нём препятствия, и есть ли они). Это позволяет A* гарантировать нахождение оптимального решения. Во‑вторых, если бы на графе не было заблокированных клеток (т. е. препятствий), то эта функция всегда бы давала точный ответ. Другими словами, значение эвристической функцией для любой вершины n всегда бы совпадало с весом кратчайшего пути от n до финиша. И это хорошо, поскольку в этом случае поиск бы рассматривал только вершины, лежащие вдоль одного из кратчайших путей, и, как иногда говорят в научной среде, работал «за линию от глубины решения».

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

Да, мы видим, что A* все ещё заметно лучше, чем Дейкстра, но при этом нас не оставляет чувство, что очень много промежуточных вершин рассмотрено зря. Мы тратим итерации алгоритма (а это время работы, а также память для хранения промежуточных вычислений) на рассмотрение каких‑то вершин, которые вообще не имеют никакого отношения к результирующему пути! Проблема в том, что эвристика ничего не знает про препятствия (и никак не учитывает их по своей природе — см. формулу выше) и буквально ведет поиск напролом, а не в обход препятствий.

Стандартный способ улучшить ситуацию — это домножать эвристику на некоторый коэффициент w > 1. Такой подход называется взвешиванием эвристики, а алгоритм — взвешенным A* (Weighted A*) или, короче, WA*. Концептуально на взвешивание в контексте нашей задачи можно смотреть следующим образом. Мы понимаем, что на карте у нас скорее всего есть препятствия и поэтому наивно считать, что от вершины n до финиша мы можем пройти по прямой. Скорее всего нам нужно будет делать какой‑то обход, и вот на этот обход мы и закладываем дополнительный коэффициент (вес эвристики). Это помогает (см. картинку), но до определенного предела.

Что же ещё мы можем сделать? Конечно, мы можем как‑то изменить сам принцип поиска, например добавив иерархичности и рандомизированности как в алгоритме R*, или же заняться онлайн‑отсечением симметрий на гриде как в Jump Point Search. Про последний алгоритм хочется сказать отдельно. Он был опубликован в 2011 году, и улучшал показатели стандартного A* при поиске на гриде на порядок (т. е. в >=10 раз), при этом сохраняя все теоретические гарантии. На мой взгляд, это хорошее подтверждение того, что на самом деле потенциал A* ещё не раскрыт до конца и место для (существенных) улучшений есть даже тогда, когда кажется, что алгоритм уже изучен вдоль и поперёк. Тем не менее, эти и многие другие модификации A* всё равно зависят от эвристики, которая, как мы видели выше «ведёт нас куда‑то не туда». Поэтому возникает естественное для исследователя желание, что‑то сделать с самой эвристикой.

И здесь мы переходим к основной идее нашей (и не только) работы.

Добавляем нейросеть

Итак, основная проблема стандартной (например, диагональной) эвристики при поиске пути на 8-связном гриде состоит в том, что она никак не учитывает препятствия. Как же нам добиться от эвристической функции более адекватного восприятия карты? Ответ в наше время напрашивается сам собой — давайте добавим магии в виде нейросетевого дип ленинга, а именно попросим нейросеть «посмотреть» на карту и сказать, где какое значение эвристики должно быть с учетом всех особенностей карты.

Действительно, грид совершенно естественно представляется бинарной картинкой: 0 — свободно, 1 — препятствие. Значит есть все основания думать, что какая‑нибудь сверточная нейросеть хорошо уловит особенности этой картинки и свяжет их со значением эвристической функции. т. е. на вход сети будет давать картинку‑задание (тензор 2 x m x n, где m, n — размерности карты, в первом канале сама картинка, во втором one‑shot представление целевой точки), а на выходе у нас будет тензор 1 x m х n, где каждый элемент — это значение правильной эвристики (учитывающей препятствия) с точки зрения нейросети. Обучать такую нейросеть логично в режиме обучения с учителем. В качестве обучающих примеров нам нужны картики 1 x m х n со значениями идеальной эвристики. Получить их можно, запустив для каждого входного примера поиск в ширину из целевой точки с критерием остановки — пока не обойдем весь граф. В качестве функции потерь можно взять простой MSE, т. е. рассчитать среднеквадратичную ошибку между тем, что нам предсказала сеть и тем, что должно быть на самом деле.

Мы только что повторили ход мысли авторов статьи Learning Heuristic Functions for Mobile Robot Path Planning Using Deep Neural Networks, опубликованной на ICAPS 2019, ведущей мировой конференции по вопросам планирования. В ней авторы ещё экспериментируют дополнительно с различными функциями потерь и режимами обучения (вплоть до GAN'ов) и с более сложными постановками самой задачи планирования (планирование с учетом пространственной ориентации агента и отдельными действиями‑поворотами). Но в целом основная мысль именно такая, как мы описали выше — давайте научим сверточную нейросеть хорошо предсказывать идеальную эвристику.

К существенным минусам этой статьи можно отнести довольно невнятное описание экспериментов и их результатов в тексте и, главное, отсутствие опубликованного кода и датасета. По сути воспроизвести результаты авторов не получится. И это, конечно, плохо.

Гораздо более интересная, приятная для чтения и свежая работа по использованию нейросетей в связке с A* была представлена на ICML 2021 и называется она Path Planning using Neural A* Search, или просто — NeuralA*. В ней авторы предложили учить не эвристику, а так называемую дополнительную стоимость.

Интуиция здесь следующая. Сеть смотрит на карту, старт, финиш и говорит какие области на карте должны стоить больше (т. е. без особой нужды лезть туда поиску не нужно). Сама эвристика при этом остается неизменной. Этот подход хорош тем, что он может работать не только (и не столько) на бинарных гридах, но и на картинках, где стоимость переходов неизвестна. Представьте себе, что вы смотрите на некоторый спутниковый снимок местности, или же вы запустили коптер и он вам сфотографировал подстилающую поверхность, и теперь у вас есть картинка. Вот прямо по этому снимку и можно искать траекторию с помощью NeuralA*.

NeuralA* ещё интересен тем, что он обучается end‑to‑end. То есть коллеги, во‑первых, представили алгоритм A* как последовательность сверточных операций (перемножение матриц), а во‑вторых, при обучении прогоняли градиент функции потерь через эти операции. Получается, что поисковые операции учитывались при обучении. Схематично это выглядит так:

Здесь в начале идет стандартная сверточная часть (назовем её бэкбоном), которая предсказывает карту дополнительных стоимостей, затем идут «поисковые свертки», которые на основе предсказанной карты осуществляет поиск. Само обучение идет в режиме «с учителем». В качестве эталонных примеров выступают гриды/картинки с отмеченным путём. Функция потерь устроена таким образом, что смотрит разницу между тем, какие клетки/пиксели перебирал NeuralA* при поиске пути и собственно путем. То есть мы стремимся научить бэкбон правильно предсказывать доп.стоимости (так, чтобы при поиске именно с этими доп.стоимостями поиск шел куда надо и не исследовал лишние части карты).

В NeuralA* очень хорошая экспериментальная часть. Открытый код и датасет. Авторы показывают, что обходят всех конкурентов, которые включают в себя в том числе и другие вариации обучаемого A* (которые здесь мы уже не сможем рассмотреть, т.к. иначе текст совсем перестанет помещаться в разумные рамки).

К основным минусам же NeuralA* можно отнести следующее. Во‑первых, в режиме планирования по бинарному гриде авторы используют 8-связную модель движения, но при этом перемещение по диагонали весит столько же, сколько и по горизонтали‑вертикали. Из‑за этого даже оптимальные (в такой модели стоимости) пути могут странно «вилять зигзагами» (посмотрите, например, на картинку выше, и обратите внимание на странный ground truth путь). Мелочь, а неприятно. Во‑вторых, для планирования на бинарном гриде вся эта история с прогоном градиентов через слои матричного A* кажется излишней и только замедляющей обучение. В‑третьих, сама идея предсказания доп.стоимости кажется хорошей для планирования по картинкам, когда мы не знаем стоимости перехода вообще, но не для грида, где стоимость фиксирована и логично всё‑таки предсказывать что‑то другое.

И тут мы переходим (наконец‑то), собственно, к нашей работе.

Наша работа

В своей работе мы решили сфокусироваться на планировании на 8-связном бинарном гриде и стремились избавиться от недостатков работ‑конкурентов, которые мы описали выше. Во‑первых, мы хотели работать с нормальной моделью стоимостей переходов, когда переход по диагонали весит в √2 раз больше, чем переход по горизонтали/вертикали. Во‑вторых, мы хотели добиться ещё большей эффективности в плане снижения числа итераций работы A* с нашими предсказаниями. В‑третьих, мы хотели предсказывать именно эвристику, а не доп.стоимость, как в Neural A*. В‑четвертых, мы хотели иметь простой, понятный пайплайн обучения, открытый код и датасет. В пятых, мы хотели использовать более современную архитектуру нейросетевой модели (не просто свертки, но и блоки внимания). В целом, у нас всё получилось, и давайте поговорим про это поподробней.

Мы решили учить две эвристики. Первая, это так называемый фактор или коэффициент коррекции (correction factor, cf). Он численно равен отношению между диагональной эвристикой и идеальной эвристикой:

В целом это тоже самое, что пытаться учить идеальную эвристику, но есть нюансы. Во-первых, cf по определению зажат между нулем и единицей, поскольку значение заданной эвристики всегда будет меньше либо равно значению идеальной, а это значит не нужно каких-то дополнительных нормировок при обучении. Во-вторых, коэффициент коррекции содержит в себе бо́льшее количество информации, чем в случае с обучением одной лишь функции h(s): на него влияет как заданная, так и идеальная эвристика.

Пример работы алгоритма поиска с предсказанным коэффициентом коррекции показан на следующем рисунке.

Другая эвристика, которую мы предсказывали, — это карта вероятности пути (path probability map, PPM). Концептуальная идея этой эвристики состоит в том, что нейросеть смотрит на карту (и старт‑финиш) и для каждой клетки предсказывает, какова вероятность её вхождения в итоговый путь. При непосредственно поиске эта эвристика может использоваться двумя способами. Первый — мы жадно перебираем вершины графа, обращая внимание только на предсказанную вероятность. То есть на каждом шаге поиска мы идем в вершину с наибольшим значением path probability (если у нескольких вершин pp‑значение одинаковое, то идем в ту, у которой f‑значение меньше по аналогии с A*). Если у нас очень хорошая карта вероятностей, в которой 1 стоит только вдоль нужного пути, то мы только по нему и пройдём.

Второй вариант использования PPM при поиске более консервативный. Перед началом работы алгоритма мы задаем некоторый параметр w > 1 (как во взвешенном A*), который регулирует субоптимальность решения. Например, если w = 1.1, то это значит, что мы хотим гарантированно на выходе получить решение, стоимость которого не превышает стоимость оптимального решения более чем в 1.1 раза (на 10%). Далее на каждой итерации в списке вершин‑кандидатов мы смотрим на все вершины у которых f‑значение больше либо равно минимальному f‑значению, умноженному на w. И уже из них выбираем ту, у которой pp‑значение минимально. Такой подход в литературе по эвристическому поиску носит имя Focal Search. В отличие от жадного поиска он обладает теоретическими гарантиями на стоимость итогового решения.

На практике после обучения PPM поиск с ним выглядит как на следующей картинке.

Чем и как учили

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

Более детально архитектура модели показана на следующем рисунке. На нём вы видим сверточный кодировщик, декодировщик и трансформерный блок между ними.

Мы, конечно, не знаем точно, на что именно обращает внимание модель, но гипотеза у нас следующая. Сверточные слои улавливают особенности карты, влияющие на планирование: углы препятствий, узкие проходы и прочее. А трансформенные блоки улавливают взаимосвязи между ними, из серии «нам нужно сначала обогнуть этот угол препятствия, потом пройти в этом проход, и дальше по прямой до финиша». То есть свертки смотрят локально, а блоки внимания — глобально. Это гипотеза в принципе подтверждается экспериментами, где мы отключали трансформерную часть и оставляли только сверточный кодировщик‑декодировщик — см. рисунок.

Что касается режима обучения, то мы пробовали учить и в режиме NeuralA* (т. е. end‑to‑end с прогоном градиента функции потерь через блоки поиска) и в простом режиме обучения с учителем. Последний способ, во‑первых, оказался более быстрым (что было ожидаемо), во‑вторых, не уступал по основным метрикам качества (стоимость итогового решения, количество итераций поиска). Поэтому мы в итоге остановились на нём.

Эталонные примеры для cf‑значений мы составляли стандартным образом — запускали классический поиск по всему графу из целевой клетки, чтобы получить значения идеальной эвристики, и делили каждое такое значение на значение диагональной эвристики в этой клетке. Для PPM эталонные примеры составлялись более хитро. Мы искали кратчайший путь от старта до финиша (причем делали это с помощью any‑angle алгоритма Theta*, чтобы избежать проблемы множества симметричных кратчайших путей) и далее «размывали» его окрестности. Более того, эмпирически мы обнаружили, что лучше обрезать все значения вероятности, которые меньше 0.95. То есть в итоге мы получаем эдакие путевые «колбасы», как показано на рисунке справа. Сеть учится их повторять.

Эксперименты

Для экспериментов мы расширили датасет, на котором проводили эксперименты авторы NeuralA* до 64 000 различных карт (часть была получена за счет аугментаций). Сам датасет и код нашего метода, естественно, открыт. Основное что нас интересовало это то, насколько сокращается число итераций поиска при использовании наших предсказанных эвристик, и какой стоимости получается итоговый путь. Не буду приводить детальные таблицы с результатами (они есть в нашей статье), просто скажу, что мы оказались лучше как традиционных техник в виде взвешенного A*, так и обучаемых конкурентов, в т.ч. NeuralA*. Схематично результаты выглядят как на картинке ниже.

Если же всё‑таки говорить про цифры, то в среднем на тестовой части датасета (т. е. на картах и заданиях, которые сеть вообще не видела при обучении) мы сокращаем число итераций поиска в среднем в 3–4 раза по сравнению с A* (и это лучше, чем у конкурентов), при этом длина результирующего пути повышается незначительно, на 0.5–1% по сравнению с оптимальной длиной (это, опять же, лучше, чем у конкурентов).

Мы также провели дополнительные эксперименты на картах, которые существенно отличались от тех, что были использованы на этапе обучения. Это называется out‑of‑the‑distribution экспериментами и это серьезный тест на прочность для любых нейросетевых подходов, т.к. известно, что они не всегда хорошо справляются с заданиями, которые «не похожи» на те, что были при обучении.

Результаты этих тестов показали, что, с одной стороны, эффективность предложенного подхода снижается, но мы всё равно сокращаем число итераций поиска в два раза по сравнению с A* (а не 3–4 как раньше). С другой стороны мы всё равно лучше конкурентов. Из рисунка выше видно, что основные проблемы в этой серии тестов нам доставили карты лабиринтного типа, где вообще очень сложно понять как должен выглядеть путь (пока мы не исследуем весь лабиринт).

В целом, у нас, как я сказал выше, всё получилось весьма хорошо. Мы лучше конкурентов сокращаем пространство поиска. Пути, которые строит наш метод, незначительно уступают оптимальным (буквально на несколько процентов). Наша нейросеть неплохо генерализуется на «непредвиденные» задачи. Кажется, что на этом можно было бы поставить точку, но по научной традиции хотелось бы завершить пост дискуссией.

Дискуссия

В конце предыдущего абзаца можно было бы поставить точку и радостно пойти пить кофе, но научная честность не позволяет так поступить. По‑хорошему, нам еще надо ответить на основной дискуссионный вопрос — на хрена зачем всё это нужно?

Если встать на позицию сурового критика, то можно рассуждать так:

«Для того чтобы найти путь на сетчатом графе в целом не требуется много ресурсов и пара сотен (тысяч, да даже десятков/сотен тысяч) «лишних» итераций, которые делает A* в целом не выглядит проблемой. Это просто микросекунды на любом современном вычислителе. При этом A* гарантированно дает оптимальное решение и работает с любыми входными данными (алгоритмически A* все равно на размер карты и на то какие на ней препятствия). Вы же приплетаете сюда нейросети, которые, наверняка, требуют кучу ресурсов, просто чтобы посчитать те эвристики, что вы предлагаете. Не разбиваете ли вы простой орех кувалдой? И если вы уж так хотите получить для каждого задания идеальную эвристику, то просто запустите поиск в ширину из финиша. Наверняка по ресурсам это будет примерно то же самое, что прогнать вашу чудесную нейросеть, но зато а) не нужно никакого этапа обучения б) метод универсальный и работает на любых картах в) результат будет гарантирован, т. е. A* вообще не сделает никаких лишних итераций и найдет 100% кратчайший путь!»

Это правильные аргументы и давайте на них ответим.

Во‑первых, в основе многих научных работ (а то что мы сделали, это прежде всего научная работа, без прицела на какой‑то конкретный сценарий использования) лежит простое любопытство — посмотреть «а как оно будет, если…». Глупо отрицать, что в основе нашей работы во многом также лежало это любопытство. Мы хотели понять: если взять известную и понятную задачу, которой сто лет в обед, и ударить по ней современным трансформерным дип ленингом, то, во‑первых, «а как бить», а во‑вторых «что получится»? Ответы на оба вопроса стали нам более понятны в конечном счете. Мы придумали, и как бить, и измерили (и сравнили с аналогами) результат. Вышло неплохо. Хочется надеяться, что это будет принято во внимание другими специалистами и проявит себя, может быть даже не напрямую, в других исследованиях.

Во‑вторых, мы, в отличие от всех (sic!) конкурентов, проводили замеры времени, которое требуется на то, чтобы посчитать эвристику, и оно вполне разумное, если вести обработку батчами, как это принято в машинном обучении. Другими словами, если в наш планировщик приходит одновременно куча запросов на планирование, то здесь прогон нейросети на GPU выгоден, т.к. она (нейросеть) за один проход сразу может считать несколько эвристик для различных поступивших на вход задач. Например, если на батче в 64 задания подобных тем, на которых мы проводили тесты в нашей статье, запустить стандартный A*, то на расчет уйдет 155 мс на CPU. Если же запустить наш метод, то сначала уйдет 10 — 40 мс (в зависимости от железа, а именно A100 или GTX 1660S) на GPU и потом порядка 30 мс на CPU (том же, на котором запускается чистый A*). Такие образом уже прослеживается экономия. Если же увеличивать батч и/или переходить ко всяким трюкам принятым в машинном обучении для ускорения нейросетей (дистиляция, переход к более «легким» типам данных и пр.), то экономия может стать вполне ощутимой.

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

В целом, на мой взгляд именно за интеграцией нейросетевых методов и классических алгоритмов будущее (а не лишь за «голыми» нейросетями и большими данными), поэтому важно искать способы и объединять эти два мира, чем мы, собственно, и занимались.

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

Благодарности

Я бы хотел поблагодарить соавторов публикации «TransPath: Learning Heuristics For Grid‑Based Pathfinding via Transformers», о которой идет речь в обзоре, а именно — Даниила Кириленко, Антона Андрейчука и Александра Панова. Также хочется упомянуть коллег, которые участвовали в ранних стадиях исследования — Василия Давыдова, Наталью Соболеву и Алексея Артёмова.