Ученые оптимизировали расчет поиска пути для роботов

Ученые МФТИ и Санкт-Петербургского государственного университета разработали алгоритм Bulk Search, который ускоряет планирование маршрутов для групп роботов. Он позволяет одновременно распределять роботов по целевым точкам и прокладывать их маршруты так, чтобы агенты не сталкивались.

Задача многоагентного поиска пути возникает, когда нескольким роботам необходимо добраться до заданных точек, не столкнувшись друг с другом. Она актуальна, например, для складов и транспортных терминалов. При планировании маршрутизации среду описывают графом: вершины отвечают позициям, ребра — переходам, а время разбито на шаги. За один шаг робот может либо перейти в соседнюю позицию, либо остаться на месте.

Для поиска маршрутов обычно создают временную сеть — несколько копий исходной карты, расположенных друг над другом по времени. При больших картах такая конструкция быстро разрастается. Например, для 100 роботов на карте размером 400 × 400 клеток вспомогательная сеть может содержать более 51 млрд узлов, а поиск приходится выполнять для каждого маршрута.

Авторы исследования решили не уменьшать сеть, а изменить способ ее обхода. Узлы одной и той же вершины карты на соседних временных слоях выстроены в цепочки, и если поиск добрался до какого-то узла цепочки, то все следующие ему тоже доступны.

Bulk Search (в переводе — поиск оптом) хранит и раскрывает такие цепочки целиком, как одно составное состояние — «пакет», заданный всего тремя числами: вершиной карты и двумя границами интервала высот. Вместо генерации каждого узла алгоритм кладет в очередь один компактный пакет и раскрывает его за один шаг. Ученые доказали, что алгоритм всегда находит путь, если тот существует. Теоретическая оценка показывает, что сжатие в пакеты сокращает перебор тем сильнее, чем крупнее карта относительно числа агентов и чем длительнее этот маршрут.

Вторая часть исследования посвящена варианту, в котором робот, добравшись до цели, исчезает с карты. Так бывает, например, когда поезд уходит в тупик, а складской робот заезжает на станцию зарядки за пределами проездов и больше не мешает остальным. Для такого варианта оптимального решателя до сих пор не существовало.

«Вариант, в котором робот, добравшись до цели, покидает рабочую зону, ближе к тому, как устроены реальные склады и транспортные терминалы. Для него мы построили сведение к задаче о поиске максимального потока минимальной стоимости и предложили эффективный решатель. Таким образом, мы впервые, насколько нам известно, решили исходную задачу многоагентного планирования в такой постановке оптимальным образом (по критерию суммарного времени). Следующий шаг — перенести подход на другие критерии качества и на системы, куда задания поступают потоком; отдельная задача — учесть, что уход с поля в реальности тоже занимает время», — рассказал один из авторов исследования, старший научный сотрудник лаборатории когнитивных динамических систем МФТИ Константин Яковлев.

Прежние подходы упирались в размер вспомогательной сети. В новой схеме трудоемкость поиска одного пути определяется главным образом размером исходной карты, а не гигантской сетью над ней. На открытом наборе задач Moving AI новый решатель справился со всеми тестами менее чем за 30 секунд. Стандартный подход решил около 75 % заданий, после чего дальнейший прогресс практически остановился.

Источник: Официальный ресурс Министерства образования и науки Российской Федерации