Российские ученые совместно с коллегами из Израиля разработали и протестировали новый алгоритм, который находит оптимальные траектории для перемещения роботов. В отличие от предшественников, модель не опирается на ряд упрощающих допущений.

Исследователи представят разработку на конференции International Joint Conference on Artificial Intelligence (IJCAI 2019) в Калифорнии.

Многие коммерческие компании автоматизированно обслуживают склады — товары перемещают не люди, а роботы. Поэтому нужны алгоритмы, перемещающие устройства. Большинство уже созданных алгоритмов опираются на ряд упрощений. Время, как правило, разбивается на временные шаги, а робот перемещается только в четырех перпендикулярных направлениях. Разбиение времени приводит к тому, что одно действие совершается за один временной шаг. Если робот выполняет действие быстрее, то затем стоит и ждет, пока наступит следующий временной шаг. Разбиение рабочего пространства влечет за собой переходы из одной ячейки только в четыре соседние.Это создает неудобства при необходимости движения по диагонали.

Поддержанные грантом Российского научного фонда, исследователи из Института проблем искусственного интеллекта Федерального исследовательского центра «Информатика и управление» РАН, Национального исследовательского университетом «Высшая школа экономики» и Российского университета дружбы народов и Университета имени Бен-Гуриона разработали новый метод планирования, который назвали CCBS (Continuous-time conflict-based search). Алгоритм лишен указанных недостатков и не привязан к геометрической форме перемещающихся объектов. CCBS отыскивает потенциальные столкновения роботов и вычисляет небезопасные интервалы.

Небезопасный интервал — максимальное время, в течение которого роботу не стоит выполнять действие, чтобы избежать столкновения с другим роботом. Например, роботам нужно пересечь одну границу в одно и то же время. Тогда для каждого из них вычисляются небезопасные интервалы и преобразуются в ограничения. Индивидуальный планировщик выстраивает оптимальные траектории с учетом ограничений. Таким образом создается неконфликтные траектории.

Модель протестировали в режиме симуляции на картах размером 10х10 и 256х256 ячеек. Число агентов варьировалось от 4 до 20. Эксперимент показал, что алгоритм выполняет миссию на 20% быстрее своих предшественников.