Марат Хамадеев
Блочный поиск существенно ускорил анонимное многоагентное планирование пути
Сложно спорить с тезисом о том, что в недалёком будущем многие повседневные задачи будут выполнять роботы под управлением различных алгоритмов искусственного интеллекта. Но на этом пути возникает множество преград. Например, если роботов более одного, нужно, чтобы при движении они не мешали друг другу.
Над обеспечением последнего исследователи работают уже сегодня благодаря тому, что эту робототехническую проблему можно формализовать с помощью движения множества абстрактных агентов по некоторому графу. Класс задач о движении нескольких агентов получил название многоагентного планирования пути (Multi-Agent Path Finding, MAPF).
Решение MAPF-задач не требует знания о техническом устройстве агента, хотя ряд нюансов позволяют разделить такие задачи на несколько типов. Например, если в системе присутствует центральный контроллер, способная видеть всех агентов и их цели, а также выполнять координацию их движения, то такую проблему называют централизованным MAPF. С точки зрения составления алгоритмов, она проще, чем децентрализованный вариант, при котором приходится придумывать инструкции для каждого из агентов. По этой причине существующие централизованные алгоритмы вроде RHCR и PIBT показывают довольно высокую эффективность.
Ещё одним упрощением является анонимизация MAPF (AMAPF), при которой агенты неразличимы, и любой агент может быть направлен на любую цель. Такая ситуация, например, имеет место на автоматизированных складах. Общий подход к AMAPF-оптимизации основан на конструировании вспомогательного графа, на котором решается задача максимизации потока. Однако такой граф, называемый сетью (network), зачастую сильно больше исходного графа, что тормозит вычисления.
На эту проблему обратил внимание коллектив исследователей, состоящий из Константина Яковлева, ведущего научного сотрудника ФИЦ ИУ РАН и AIRI, и аспиранта МФТИ Зейна Алабедина Али. Они предположили, что отдельные состояния графа поиска можно компоновать в блоки или последовательности, и оперировать уже с последними, что даст прирост скорости алгоритма. Полученный метод получил название блочного поиска (Bulk Search, BS).
Команда показала, что с точки зрения математики блочный поиск обладает необходимой полнотой. Для практической проверки нововведения авторы провели серию экспериментов на популярном бенчмарке, предложенного Штерном с коллегами, и сравнила результаты с SOTA AMAPF солвером, описанным в статье Окумуры и Дефаго. Бенчмарк состоит из 33 карт разного размера и 25 случайных сценариев расположения агентов и целей. Солвер Окумуры и Дефаго, в свою очередь, решает проблему множественности состояний с помощью алгоритма Форда — Фулкерсона.
На первом этапе исследователи сравнивали процент достижения целей для обоих алгоритмов при условии того, что время, за которое последний агент добирается до конца, ограничено 30 секундами. Эксперимент показал, что BS-подход достигает успеха в 100 процентах случаев, в то время как его предшественник теряет эффективность по мере увеличения размера карты.
Нормализованная доля успешного достижения цели в зависимости от ограничения по времени для обоих алгоритмов
На втором этапе авторы изучили то, как количество агентов на карте влияет на производительность алгоритма. Они выяснили, что BS-подход раскрывает на порядок меньше нод, что и объясняет его скорость. В будущем учёные планируют адаптировать новый метод к оптимизации стоимости путей, чтобы улучшить другие MAPF-подходы.
Раскрытие нод на трёх картах в зависимости от количества агентов
Исследование было представлено на конференции AAAI-24, в сборнике которой вышла соответствующая статья, а код доступен в репозитории GitHub. На той же конференции команда исследователей, в которую входил Константин Яковлев, доложилась об успехах в улучшении работы децентрализованных MAPF-методов в условии ограниченной видимости. Недавно мы кратко пересказывали суть их работы.
