Исследователи из МФТИ и Санкт-Петербургского государственного университета предложили алгоритм Bulk Search, который оптимально и быстро разводит по общему пространству группы роботов. Новый решатель справился со всеми задачами открытого набора Moving AI, тогда как прежний подход на картах большого размера не решал почти ни одной.
Задача многоагентного поиска пути формулируется просто: развести роботов по целевым точкам так, чтобы они не сталкивались.
Среду описывают графом: вершины отвечают позициям, ребра — переходам, а время разбито на шаги. За один шаг агент либо ждет, либо переходит в соседнюю вершину.
Качество плана измеряют двумя способами.
Makespan — это момент, когда до цели добрался последний агент.
Сумма стоимостей — суммарное время всех агентов.
Есть важный частный случай, в котором задачу решить становится значительно проще. Если роботы взаимозаменяемы и не важно, какой робот займет цель, задача называется анонимной: так устроены зарядные станции, пункты выдачи и места разгрузки на складе.
Рисунок 1. Слева — обычная задача многоагентного поиска пути на сетке 4 × 4: робот 1 обязан попасть в цель 1, робот 2 — в цель 2. Справа — анонимный вариант: цели взаимозаменяемы, и оптимально отправить каждого робота к ближайшей из них. Источник: Journal of Artificial Intelligence Research
Из исходной карты строят «слоеный пирог» — по копии графа на каждый момент времени, где дуги между слоями кодируют перемещения и ожидания. На «слоеном пироге» решается задача о нахождении минимального потока. Это известная задача в компьютерных науках, для которой есть множество эффективных решателей. Проблема в том, что если пирог слишком большой (как в ширину, так и в высоту), то поиск путей на нем осложняется. Для 100 агентов на карте 400 × 400 клеток вспомогательная сеть разрастается более чем до 51 млрд узлов, а путь в ней нужно найти 100 раз.
Исследователи из МФТИ и СПбГУ решили не уменьшать сеть, а изменить способ ее обхода. Узлы одной и той же вершины карты на соседних временных слоях выстроены в цепочки, и если поиск добрался до какого-то узла цепочки, то все следующие ему тоже доступны.
Bulk Search, то есть «поиск оптом», хранит и раскрывает такие цепочки целиком, как одно составное состояние — «пакет», заданный всего тремя числами: вершиной карты и двумя границами интервала высот. Вместо генерации каждого узла алгоритм кладет в очередь один компактный пакет и раскрывает его за один шаг.
Рисунок 2. Фрагмент вспомогательной сети при поиске пути от источника к стоку. Обычный обход графа раскрыл бы 23 отдельных узла, отмеченных розовыми линиями; Bulk Search считает каждую такую линию одним пакетным состоянием и раскрывает всего восемь. Источник: Journal of Artificial Intelligence Research
Ученые доказали, что алгоритм всегда находит путь, если тот существует. Теоретическая оценка показывает, что сжатие в пакеты сокращает перебор тем сильнее, чем крупнее карта относительно числа агентов и чем длительнее этот маршрут.
Вторая часть исследования посвящена варианту, в котором робот, добравшись до цели, исчезает с карты. Так часто и бывает: поезд уходит в тупик, складской робот заезжает на станцию зарядки за пределами проездов и больше не мешает остальным.
Для такого варианта с критерием суммы стоимостей оптимального решателя не существовало. Авторы предложили сведение к задаче о максимальном потоке минимальной стоимости: в сеть добавляются узлы-концентраторы для каждой цели, а стоимость дуги в концентратор равна моменту прибытия. Поток минимальной стоимости в такой сети строго соответствует плану с минимальной суммой времен прибытия.
Рисунок 3. Доля решенных задач набора Moving AI в зависимости от отведенного времени. Решатель на основе Bulk Search закрывает все задачи менее чем за 30 секунд, тогда как решатель на стандартном алгоритме максимального потока выходит на плато около 75% на восьмой секунде. Источник: Journal of Artificial Intelligence Research
Прежние подходы упирались в размер вспомогательной сети. В новой схеме трудоемкость поиска одного пути определяется главным образом размером исходной карты, а не гигантской сетью над ней.
В складской логистике задания появляются непрерывно, и система раз за разом решает, какой робот едет к какой точке и каким маршрутом. Модель с исчезающими агентами здесь удобнее: роботу не нужно стоять на цели и ждать остальных. Такой решатель авторы уже применяли в системе, занявшей третье место в треке Scheduler соревнования League of Robot Runners 2024, которое спонсировала Amazon.
Константин Яковлев, старший научный сотрудник лаборатории когнитивных динамических систем МФТИ, так рассказал о работе:
Вариант, в котором робот, добравшись до цели, покидает рабочую зону, ближе к тому, как устроены реальные склады и транспортные терминалы. Для него мы построили сведение к задаче о поиске максимального потока минимальной стоимости и предложили эффективный решатель. Таким образом, мы впервые, насколько нам известно, решили исходную задачу многоагентного планирования в такой постановке оптимальным образом (по критерию суммарного времени). Следующий шаг — перенести подход на другие критерии качества и на системы, куда задания поступают потоком; отдельная задача — учесть, что уход с поля в реальности тоже занимает время.
Работа опубликована в журнале Journal of Artificial Intelligence Research.
Источник: Минобрнауки России
