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

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

Как рассказал один из авторов исследования, старший научный сотрудник лаборатории когнитивных динамических систем МФТИ Константин Яковлев, зачастую нескольким роботам необходимо добраться до заданных точек, не столкнувшись друг с другом. И в этом случае возникает задача поиска многоагентных маршрутов.

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

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

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

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

Мона Платонова.

Фото mos.ru