«Наш результат признан не только в рамках защиты проекта, но и на международном уровне»
В этом году на Европейскую конференцию по ИИ (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 — и даты подачи заявки в начале мая нам подходили. Мы вложили много сил, чтобы статья оказалась понятна и полезна для читателей, поэтому были рады, когда в начале июля получили одобрение на публикацию.
Структура статьи довольно стандартна: введение, анализ литературы, формулировка задачи, доказательство, обсуждение важности результата и направлений дальнейшей работы. Некоторые разделы взяты из отчета по курсовой работе и переведены на английский язык, но большая часть текста написана специально.
Основная сложность состояла не в написании статьи, а в непосредственной работе над результатом. Было немного страшно, когда времени до защиты курсового проекта становилось все меньше и меньше, а значительных результатов не появлялось. Поэтому когда я сформулировал первую версию доказательства о невозможности решить задачу, был рад, что меня посетила такая идея, а проблема с отсутствием результатов по курсовой упала с моих плеч.
Я доволен проделанной работой. Изначально я не мог ожидать, что смогу придумать что-то, что будет являться значительным достижением в этой области. Приятно осознавать, что наш результат признан не только в рамках защиты проекта, но и на серьезном международном уровне. Здорово, что в работе мне пригодились знания, полученные во время обучения в университете. Я рад, что поступил на ПМИ, ведь учеба здесь интересна и полезна.
Вам также может быть интересно:
НИУ ВШЭ и ведущие университеты Китая запустят масштабные исследовательские и образовательные проекты
В рамках официального визита президента РФ Владимира Путина в Китайскую Народную Республику делегация НИУ ВШЭ во главе с ректором Никитой Анисимовым заключила новые соглашения о сотрудничестве с крупнейшими университетами Китая. Соглашения направлены на расширение двустороннего партнерства в области образования, науки и культурного обмена.
Исследователи изучили, как в малых российских университетах заботятся о студентах
Исследователи из Института образования НИУ ВШЭ провели социологическое исследование в четырех малых неселективных университетах и на основе 135 интервью показали, что в таких вузах забота о студентах имеет двойственную природу. Она объединяет искреннюю помощь с постоянным надзором, напоминая родительскую опеку. Это первое детальное описание того, как формальные и неформальные практики заботы переплетаются в постсоветском образовательном контексте. Исследование опубликовано в British Journal of Sociology of Education.
На Международной летней школе в КНР Вышка поделилась опытом изучения городских стратегий
На фоне усиления глобальной геополитической и технологической конкуренции ведущие китайские вузы Чжэцзянский университет международных исследований и Пекинский университет организовали совместную Международную летнюю школу. Центральной ее темой стало изучение глобальных региональных и городских стратегий развития. Факультет городского и регионального развития НИУ ВШЭ принял участие в работе школы.
Ученые ВШЭ оптимизировали обучение генеративных потоковых нейросетей
Исследователи факультета компьютерных наук НИУ ВШЭ улучшили метод обучения генеративных потоковых нейросетей для работы с неструктурированными задачами. Это поможет искать новые лекарства эффективнее. Результаты работы были представлены на одной из ведущих конференций по машинному обучению — ICLR 2025. Текст работы доступен в репозитории Arxiv.org.
Ученые смоделировали работу суперконденсатора на уровне отдельных молекул и ионов
Ученые НИУ ВШЭ с помощью моделирования на суперкомпьютере изучили, что происходит с ионами и молекулами растворителя с водой внутри нанопор суперконденсатора. Результаты показали, что даже очень малое количество воды меняет распределение заряда внутри нанопор и влияет на то, сколько энергии может накопить устройство. Такой подход позволяет предсказывать поведение суперконденсаторов при разных составах электролита и условиях влажности. Исследование опубликовано в журнале Electrochimica Acta. Работа выполнена в рамках гранта РНФ.
ВШБ ВШЭ и Альфа-Банк провели летнюю школу для студентов из Китая
Международная летняя школа «Управление цифровым продуктом», образовательный проект Высшей школы бизнеса НИУ ВШЭ и Альфа-Банка, собрала свыше 30 студентов из ведущих университетов Китая.
Студенты и аспиранты НИУ ВШЭ приняли участие в Международной летней школе Пекинского университета
В июле в Пекинском университете проходила ежегодная летняя школа по квантовой молекулярной динамике, которая в этом года перешла на международный уровень. Ее первыми иностранными гостями стали студенты и аспиранты МИЭМ НИУ ВШЭ. У них была обширная образовательная программа, им также удалось посетить лабораторию оптоэлектронных материалов и энергетических приборов.
В НИУ ВШЭ стартовал СТП «Национальный центр социально-экономического и научно-технологического прогнозирования»
Стратегический технологический проект нацелен на создание и внедрение технологий системного анализа и прогнозирования в интересах государства, бизнеса и общества для обеспечения технологического лидерства, суверенитета и безопасности России.
«Человеческое существование без математики сегодня трудно, а завтра будет просто невозможно»
Математики всего мира говорят на одном языке и продолжают сотрудничество, несмотря на сложности последних лет. Центр их общения перемещается в Китай, где ученые разных стран встречаются на конференциях и других научных мероприятиях. Сотрудничество с ведущими китайскими университетами перспективно для продолжения прежних и организации новых контактов. Об этом, а также о том, что такое ИИ и почему государство должно сотрудничать с математиками, новостной службе «Вышка.Главное» рассказал заведующий Международной лабораторией зеркальной симметрии и автоморфных форм НИУ ВШЭ Валерий Гриценко.
Вузы разделились на шесть лагерей в отношении к искусственному интеллекту
Каким должно быть образование в эпоху ИИ? Чтобы разобраться, какие есть точки зрения и какие решения уже формируются, команда Института образования ВШЭ весной 2025 года провела серию интервью с проректорами российских университетов. Об итогах этого исследования рассказывает директор института Евгений Терентьев.