Исследователи Института AIRI и НИУ ВШЭ представили алгоритм EPIBT, позволяющий управлять движением сотен роботов в условиях реального склада или городской логистики так, чтобы они не мешали друг другу.
В работе рассматривался реалистичный сценарий, в котором роботы постоянно получают новые задания: как только одно задание выполнено, сразу появляется следующее. В модели движения учитывается не только положение, но и ориентация робота. Он может ехать только вперёд, а чтобы развернуться, ему нужно повернуться на месте. Алгоритм должен успевать за ограниченное время (менее секунды) выдать следующее действие для всех агентов.
Для таких задач зачастую используется алгоритм PIBT, также помогающий робот не сталкиваться. Но он работает только на один шаг вперёд, что приводит к проблемам, например, в узких коридорах. Роботы с высоким приоритетом могут «выталкивать» остальных или взаимно блокировать друг друга, особенно когда нужно учитывать время, необходимое на повороты.
EPIBT вместо одиночных шагов рассматривает короткие последовательности элементарных действий как одну «многодейственную» операцию. Это позволяет ему заглядывать на несколько шагов вперёд, не переходя к трудоёмкому и долгому полному планированию маршрутов. При этом рассматриваются не все возможные комбинации элементарных действий, а лишь небольшое подмножество, которое позволяет покрыть все возможные последовательности положений работа на выбранном горизонте планирования.
Наибольший эффект эта модификация даёт при высокой плотности агентов, то есть в ситуации, когда много роботов одновременно находится в ограниченном пространстве. Возможность оценивать несколько будущих шагов делает их действия более согласованными. В экспериментах алгоритм EPIBT показал лучший результат, то есть позволил системе обработать больше заданий за то же время. Год назад аналогичная задача решалась в рамках международного турнира The League of Robot Runners, где коллектив авторов метода занял первое место.
