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