Российские исследователи ускорили ИИ-навигацию для роботов в 100 раз

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

Как работает новая технология?

В основе метода лежат так называемые «графы видимости» — способ представления пространства, где вершинами служат углы препятствий, а ребрами — прямые линии между ними. Оптимальный маршрут прокладывается по этим линиям. Однако раньше построение такого графа требовало огромных вычислительных ресурсов: алгоритм попарно проверял пересечения тысяч потенциальных ребер с вершинами.

Авторам работы удалось полностью векторизовать этот процесс, то есть перейти к обработке массивов данных одной операцией. «Один из самых вычислительно затратных этапов построения графа видимости — процесс проверки пересечений. Он включает определение того, пересекаются ли ребра, соединяющие узлы, с ребрами препятствий. Сложность заключается в том, чтобы избежать попарных сравнений между большим количеством потенциальных ребер видимости и ребер препятствий, которые приводят к вложенным циклам и значительным вычислительным накладным расходам. Чтобы решить проблему, предложены методы векторизации», — пояснил доцент кафедры вычислительной техники и защиты информации УУНиТ Константин Миронов.

Дополнительно ученые разработали «умный» алгоритм, который уменьшает число углов в многоугольниках, обозначающих препятствия. Это также сокращает объем вычислений, сохраняя при этом оптимальность маршрута.

Преимущества в цифрах и перспективы

На небольших картах новый метод работает до 100 раз быстрее популярного алгоритма Theta*. На крупных картах, насыщенных препятствиями, преимущество составляет примерно пятикратное ускорение. Еще одно важное достоинство — скорость пересчета траектории при изменении обстановки. Если добавить новые стартовые или конечные точки, маршрут пересчитывается менее чем за 0,04 секунды, что позволяет роботу реагировать почти мгновенно.

Технологию уже интегрировали в системы управления роботами и испытали на реальных картах размером 512 × 2048 пикселей, содержащих до 280 препятствий. Исследование опубликовано в журнале Intelligent Service Robotics.

По словам соавтора работы, директора Центра когнитивного моделирования МФТИ Александра Панова, разработка — шаг к созданию полностью автономных систем, способных ориентироваться в сложной среде. Метод может найти применение в складской логистике, где роботы-погрузчики должны ежесекундно прокладывать пути между стеллажами, в поисково-спасательных операциях при постоянно меняющихся завалах, а также в управлении роями дронов внутри помещений. В перспективе технологию могут использовать для роботизированных комплексов, предназначенных для изучения и освоения других планет и строительства внеземных баз.