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