Российские ученые совместно с коллегами из Израиля разработали новый алгоритм, который позволяет планировать оптимальные траектории перемещения роботов. Благодаря разработке удалось снизить общее время на выполнение ими задания на 20%, что превосходит большинство мировых аналогов, сообщила во вторник пресс-служба Российского научного фонда, при поддержке которого выполнено исследование.

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

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

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

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

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