НОВОСТИ    БИБЛИОТЕКА    КАРТА САЙТА    ССЫЛКИ    О ПРОЕКТЕ  

31.07.2019

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

На планировании кратчайших безопасных траекторий, следуя по которым, мобильные агенты избегают столкновений и при этом минимизируют время выполнения миссии основан один из подходов к безопасной навигации. Новый алгоритм, который гарантирует отыскание оптимальных решений и, в отличие от имеющихся аналогов, не опирается на ряд упрощающих допущений разработали и исследовали учёные из Института проблем искусственного интеллекта Федерального исследовательского центра «Информатика и управление» РАН, Высшей школы экономики и Российского университета дружбы народов совместно с коллегами из Университета имени Бен-Гуриона. Статья, описывающая предложенный метод, принята на крупнейшую в мире конференцию по искусственному интеллекту — International Joint Conference on Artificial Intelligence (IJCAI 2019). Исследования поддержаны грантом Российского научного фонда, кратко о полученных результатах рассказывается в пресс-релизе фонда.

Схема поиска неконфликтных траекторий для 3 роботов. Источник: Константин Яковлев
Схема поиска неконфликтных траекторий для 3 роботов. Источник: Константин Яковлев

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

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

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


Источники:

  1. polit.ru











© Злыгостев Алексей Сергеевич, статьи, подборка материалов, оформление, разработка ПО 2001-2019
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://roboticslib.ru/ 'Робототехника'
Рейтинг@Mail.ru