Российские ученые придумали «оптовый» поиск маршрутов для групп роботов
Новости Наука и техника
Исследователи из МФТИ и Санкт-Петербургского государственного университета создали алгоритм Bulk Search, который заметно ускоряет планирование путей для групп роботов, сообщает Минобрнауки России. Алгоритм одновременно назначает каждого робота на нужную целевую точку и прокладывает маршруты так, чтобы агенты не столкнулись по дороге.
Где это нужно
Задача многоагентного поиска пути возникает, когда группе роботов требуется разъехаться по заданным позициям без столкновений. Типичные сценарии — работа складов и транспортных терминалов.
В чем была проблема
Среду описывают графом: вершины — позиции, ребра — переходы, а время поделено на шаги. За один шаг робот либо сдвигается в соседнюю клетку, либо стоит на месте. Чтобы искать маршруты, обычно строят временную сеть — несколько копий карты, уложенных друг на друга по времени. На больших картах такая конструкция разрастается чудовищно: например, для 100 роботов на карте 400 × 400 вспомогательная сеть может содержать более 51 миллиарда узлов, и поиск нужно выполнять для каждого маршрута отдельно.
Как работает Bulk Search
Авторы решили не уменьшать сеть, а изменить способ ее обхода. Узлы одной вершины карты на соседних временных слоях выстроены в цепочки: если поиск добрался до какого-то узла цепочки, все последующие тоже доступны. Bulk Search (от англ. «поиск оптом») хранит и раскрывает такие цепочки целиком, как одно составное состояние — «пакет», заданное всего тремя числами: вершиной карты и двумя границами интервала по времени. Вместо генерации каждого узла по отдельности алгоритм кладет в очередь один компактный пакет и раскрывает его за один шаг.
Ученые доказали, что алгоритм всегда находит путь, если он существует. Теоретическая оценка показывает: сжатие в пакеты тем эффективнее, чем крупнее карта по сравнению с числом агентов и чем длиннее маршрут.
Вторая часть работы посвящена варианту, в котором робот, достигнув цели, исчезает с карты. Так бывает, например, когда поезд уходит в тупик, а складской робот заезжает на зарядную станцию вне проездов и больше не мешает остальным. Оптимального решателя для такой постановки до сих пор не существовало.
«Вариант, в котором робот, добравшись до цели, покидает рабочую зону, ближе к тому, как устроены реальные склады и транспортные терминалы. Для него мы построили сведение к задаче о поиске максимального потока минимальной стоимости и предложили эффективный решатель. Таким образом, мы впервые, насколько нам известно, решили исходную задачу многоагентного планирования в такой постановке оптимальным образом (по критерию суммарного времени). Следующий шаг — перенести подход на другие критерии качества и на системы, куда задания поступают потоком; отдельная задача — учесть, что уход с поля в реальности тоже занимает время», — рассказал один из авторов исследования, старший научный сотрудник лаборатории когнитивных динамических систем МФТИ Константин Яковлев.
|
|
|
