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