Один из подходов к безопасной навигации мобильных агентов (например, роботов) основан на планировании кратчайших безопасных траекторий, следуя по которым, они избегают столкновений и при этом минимизируют время выполнения миссии. Учёные из Института проблем искусственного интеллекта Федерального исследовательского центра «Информатика и управление» РАН, Высшей школы экономики и Российского университета дружбы народов совместно с коллегами из Университета имени Бен-Гуриона разработали и исследовали новый алгоритм, который гарантирует отыскание оптимальных решений и, в отличие от имеющихся аналогов, не опирается на ряд упрощающих допущений. Статья, описывающая предложенный метод, принята на крупнейшую в мире конференцию по искусственному интеллекту — International Joint Conference on Artificial Intelligence (IJCAI 2019). Исследования поддержаны грантом Российского научного фонда, кратко о полученных результатах рассказывается в пресс-релизе фонда.
Многие крупные коммерческие компании переходят на автоматизированное обслуживание складов, когда товары перемещаются роботами. Соответственно, возникает необходимость в создании алгоритмов, обеспечивающих безопасное и своевременное перемещение устройств. Однако большинство созданных алгоритмов опираются на ряд упрощений. Например, обычно считается, что время не непрерывно, а дискретно и подразделяется на временные шаги. Одно действие совершается за один временной шаг. Соответственно, если агент выполняет действие быстрее, то он стоит и ждёт, пока наступит следующий временной шаг, что замедляет процесс движения к цели. Также во многих алгоритмах роботы перемещаются только в четырёх перпендикулярных направлениях, то есть рабочее пространство разбивается на квадратные ячейки и разрешается переход из одной ячейки только в четыре соседние. Это создаёт неудобства при необходимости движения по диагонали.
Учёные разработали метод планирования — CCBS (Continuous-time conflict-based search). Он лишён обоих указанных недостатков, а также не привязан к геометрической форме агентов. Алгоритм CCBS основан на обнаружении потенциальных столкновений и вычислении небезопасных интервалов. Небезопасный интервал — это максимальное время, в течение которого роботу не стоит выполнять определённое действие, так как иначе он гарантированно столкнётся с другим роботом. При обнаружении потенциального конфликта между действиями агентов (например, им нужно пересечь одну границу в одно и то же время) для каждого из них вычисляются небезопасные интервалы. Затем они преобразуются в ограничения, состоящие в том, что роботам не разрешается выполнять свои действия в эти интервалы времени. Далее маршруты отдельных агентов перестраиваются с учётом наложенных ограничений с помощью индивидуального планировщика, который гарантирует отыскание кратчайшей траектории. Таким образом создается итоговое решение — множество неконфликтных траекторий. Экспериментальное исследование проводилось в режиме симуляции на картах размером 10х10 и 256х256 ячеек. Число агентов варьировалось от 4 до 20.
«Результаты экспериментов демонстрируют преимущество предложенного алгоритма по сравнению с предшественниками — суммарное время выполнения миссии снижено на 20 %. Таким образом, мы создали полный оптимальный алгоритм планирования безопасных траекторий для групп агентов, превосходящий большинство мировых аналогов», — рассказывает кандидат физико-математических наук Константин Яковлев, сотрудник Федерального исследовательского центра «Информатика и управление» РАН.