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