«Наш результат признан не только в рамках защиты проекта, но и на международном уровне»
В этом году на Европейскую конференцию по ИИ (ECAI 2025) была принята статья Multi-Agent Path Finding For Large Agents Is Intractable второкурсника бакалавриата «Прикладная математика и информатика» (ПМИ) факультета компьютерных наук ВШЭ Артема Агафонова. Работа написана в соавторстве с Константином Яковлевым, заведующим базовой кафедрой «Интеллектуальные технологии системного анализа и управления» ФИЦ ИУ РАН, доцентом ФКН. Как возникла идея написать статью и как удалось попасть на конференцию уровня А, Артем Агафонов рассказал в интервью.
С чего все начиналось
В начале второго курса мне надо было выбрать курсовой проект для работы в течение года. Меня заинтересовала тема «Многоагентное планирование траектории», предложенная Константином Яковлевым. По описанию проекта мне показалось, что в нем я смогу применить свои знания в области алгоритмов и получить новый опыт работы над научным исследованием. Также важным критерием в выборе темы было то, что в рамках этого проекта можно добиться значимых результатов.
Работа над проектом началась с погружения в уже имеющиеся результаты из сферы MAPF (multi-agent pathfinding), для чего я прочел множество научных статей. Через месяц Константин предложил мне несколько актуальных задач. Одна из них звучала так: «Придумать полиномиальный алгоритм решения задачи MAPF с большими агентами». Константин предупредил, что он предлагал эту задачу другим студентам, аспирантам и ученым, но никто не смог довести ее до конца. Этот комментарий пугал, но я все-таки решил попробовать.
В чем состояла задача
Простыми словами задачу можно объяснить следующим образом. В задаче MAPF дан граф — множество вершин, соединенных ребрами, — и множество агентов, которые расположены в вершинах графа. У каждого агента есть целевая вершина, в которую он хочет попасть, перемещаясь по ребрам. Нельзя допускать конфликты, то есть ситуации, при которых два агента попадают в одну вершину. Требуется определить план переходов, двигаясь по которому агенты смогут попасть в свои целевые вершины, или сказать, что построить такой план невозможно.
MAPF с большими агентами (LA-MAPF — MAPF with large agents) является усложнением предыдущей задачи. Здесь дополнительно граф располагается на плоскости или в пространстве, а каждый агент наделяется геометрической формой — в простом случае окружностями. Теперь конфликты происходят не только когда два агента попадают в одну вершину, но и когда при движении геометрические формы агентов пересекаются в пространстве.
Полиномиальный алгоритм решения задачи MAPF существует и называется Push-and-Rotate, а для LA-MAPF такого алгоритма нет, поэтому вопрос о его разработке был актуален. Особенностью полиномиальных алгоритмов является то, что при увеличении размера входных данных их время работы растет медленнее, чем у неполиномиальных. Поэтому данные алгоритмы интересны не только в теории, но и на практике.
И вот как все было
Сначала я пытался придумать требуемый алгоритм. Для этого были написаны программы для генерации теста задачи, для его решения полным перебором и для визуализации движения агентов в нем. Я выдвигал разные гипотезы и проверял их с помощью этих программ. Но каждый раз я сталкивался с тем, что на каком-то тесте программа не работала. Те проблемы, с которыми сталкивалось мое решение, навели меня на мысль, что решить задачу за полиномиальное время невозможно. Мне показалось, что эта гипотеза объясняла, почему другие тоже не могли решить данную задачу. Поэтому я решил попробовать доказать это.
Здесь мне пригодились знания о теории сложности алгоритмов и о способах доказательства NP-трудности задач, которые я получил в рамках курса «Алгоритмы и структуры данных». Первый успешный результат пришел относительно быстро, а затем потребовалось несколько месяцев упорной работы, созвонов и обсуждений, чтобы упростить доказательство и убедиться в его корректности. В итоге мы пришли к выводу, что задача LA-MAPF NP-трудна, а значит, детерминированного полиномиального алгоритма ее решения не существует при условии, что классы сложности P и NP не равны (данное предположение является одной из задач тысячелетия).
Результат достоен статьи
Константин сказал, что полученный результат является значимым, поэтому мы решили не только показать его на защите курсового проекта (он был оценен на десять баллов), но и поделиться с остальным научным сообществом, опубликовав статью. Конференцию ECAI выбрали, так как она считается одной из престижных — например, наукометрический центр ВШЭ внес ее в список ACONF — и даты подачи заявки в начале мая нам подходили. Мы вложили много сил, чтобы статья оказалась понятна и полезна для читателей, поэтому были рады, когда в начале июля получили одобрение на публикацию.
Структура статьи довольно стандартна: введение, анализ литературы, формулировка задачи, доказательство, обсуждение важности результата и направлений дальнейшей работы. Некоторые разделы взяты из отчета по курсовой работе и переведены на английский язык, но большая часть текста написана специально.
Основная сложность состояла не в написании статьи, а в непосредственной работе над результатом. Было немного страшно, когда времени до защиты курсового проекта становилось все меньше и меньше, а значительных результатов не появлялось. Поэтому когда я сформулировал первую версию доказательства о невозможности решить задачу, был рад, что меня посетила такая идея, а проблема с отсутствием результатов по курсовой упала с моих плеч.
Я доволен проделанной работой. Изначально я не мог ожидать, что смогу придумать что-то, что будет являться значительным достижением в этой области. Приятно осознавать, что наш результат признан не только в рамках защиты проекта, но и на серьезном международном уровне. Здорово, что в работе мне пригодились знания, полученные во время обучения в университете. Я рад, что поступил на ПМИ, ведь учеба здесь интересна и полезна.