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