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