31.07.2019

Новый алгоритм проложит траектории движения для роботов

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

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

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

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

Учёные разработали метод планирования — CCBS (Continuous-time conflict-based search). Он лишён обоих указанных недостатков, а также не привязан к геометрической форме агентов. Алгоритм CCBS основан на обнаружении потенциальных столкновений и вычислении небезопасных интервалов. Небезопасный интервал — это максимальное время, в течение которого роботу не стоит выполнять определённое действие, так как иначе он гарантированно столкнётся с другим роботом. При обнаружении потенциального конфликта между действиями агентов (например, им нужно пересечь одну границу в одно и то же время) для каждого из них вычисляются небезопасные интервалы. Затем они преобразуются в ограничения, состоящие в том, что роботам не разрешается выполнять свои действия в эти интервалы времени. Далее маршруты отдельных агентов перестраиваются с учётом наложенных ограничений с помощью индивидуального планировщика, который гарантирует отыскание кратчайшей траектории. Таким образом создается итоговое решение — множество неконфликтных траекторий. Экспериментальное исследование проводилось в режиме симуляции на картах размером 10х10 и 256х256 ячеек. Число агентов варьировалось от 4 до 20.

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

Источники:

1. polit.ru