oformiti zayavku na zaym

Разработан новый алгоритм планирования безопасных траекторий для роботов

close

Разработан новый алгоритм планирования безопасных траекторий для роботов

Разработан новый алгоритм планирования безопасных траекторий для роботов

Depositphotos

Проблема безопасной навигации множества мобильных агентов (например, роботов) в замкнутом пространстве является весьма актуальной в настоящее время. Один из подходов к ее решению основан на планировании кратчайших безопасных траекторий, следуя по которым, агенты избегают столкновений и при этом минимизируют время выполнения миссии. Российские ученые совместно с коллегами из Израиля разработали и исследовали новый алгоритм, который гарантирует отыскание оптимальных решений и, в отличие от имеющихся аналогов, не опирается на ряд упрощающих допущений. Статья, описывающая предложенный метод, принята на крупнейшую в мире конференцию по искусственному интеллекту – International Joint Conference on Artificial Intelligence (IJCAI 2019). Исследования поддержаны грантом Российского научного фонда.

Многие крупные коммерческие компании переходят на автоматизированное обслуживание складов. В этом случае товары перемещаются не людьми, а роботами. Соответственно, возникает необходимость в создании алгоритмов, обеспечивающих безопасное и своевременное перемещение устройств. За последние годы исследователи достигли значительного успеха в разработке подобных методов автоматического планирования. Однако большинство созданных алгоритмов опираются на ряд упрощений. Например, обычно считается, что время не непрерывно, а дискретно и подразделяется на временные шаги. Одно действие совершается за один временной шаг. Соответственно, если агент выполняет действие быстрее, то он стоит и ждет, пока наступит следующий временной шаг, что замедляет процесс движения к цели. Также во многих алгоритмах роботы перемещаются только в четырех перпендикулярных направлениях, то есть рабочее пространство разбивается на квадратные ячейки и разрешается переход из одной ячейки только в четыре соседние. Это создает неудобства при необходимости движения по диагонали. Ученые разработали метод планирования – CCBS (Continuous-time conflict-based search). Он лишен обоих указанных недостатков, а также не привязан к геометрической форме агентов.

Алгоритм CCBS основан на обнаружении потенциальных столкновений и вычислении небезопасных интервалов. Небезопасный интервал – это максимальное время, в течение которого роботу не стоит выполнять определенное действие, так как иначе он гарантированно столкнется с другим роботом. При обнаружении потенциального конфликта между действиями агентов (например, им нужно пересечь одну границу в одно и то же время) для каждого из них вычисляются небезопасные интервалы. Затем они преобразуются в ограничения, состоящие в том, что роботам не разрешается выполнять свои действия в эти интервалы времени. Далее маршруты отдельных агентов перестраиваются с учетом наложенных ограничений с помощью индивидуального планировщика, который гарантирует отыскание кратчайшей траектории. Таким образом создается итоговое решение – множество неконфликтных траекторий.

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

«Результаты экспериментов демонстрируют преимущество предложенного алгоритма по сравнению с предшественниками – суммарное время выполнения миссии снижено на 20%. Таким образом, мы создали полный, оптимальный алгоритм планирования безопасных траекторий для групп агентов, превосходящий большинство мировых аналогов», – рассказывает Константин Яковлев, сотрудник Федерального исследовательского центра «Информатика и управление» РАН, кандидат физико-математических наук.