Российские учёные ускорили алгоритмы навигации для роботов

Исследователи из российских научных центров разработали метод, позволяющий значительно повысить скорость расчёта маршрутов для автономных систем. По данным авторов, новая технология в ряде случаев ускоряет навигационные вычисления до ста раз. Результаты работы опубликованы в журнале Intelligent Service Robotics.

В проекте участвовали специалисты Московского физико-технического института, Уфимского университета науки и технологий и лаборатории когнитивных систем искусственного интеллекта. В основе решения лежит усовершенствованный подход к построению так называемых графов видимости — модели, в которой пространство описывается через точки препятствий и возможные прямые маршруты между ними.

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

Дополнительно предложен алгоритм оптимизации геометрии препятствий, который уменьшает количество используемых точек без потери точности маршрута. Это также снижает нагрузку на систему.

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

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