В задачах навигации скорость принятия решений — критический фактор, который ограничивает эффективность роботов. Исследование российских ученых предлагает ускорить этот процесс, переосмыслив одну из самых «узких» вычислительных операций.
В разработке приняли участие специалисты Московского физико-технического института, Уфимского университета науки и технологий и лаборатории когнитивных систем искусственного интеллекта. Статья об исследовании опубликована в Intelligent Service Robotics — академическом журнале, посвященном сервисной робототехнике.
Как объяснили ученые, в основе разработки — классические «графы видимости». Это способ, который представляет пространство в виде вершин препятствий и ребер — прямых линий между ними. Прокладывание маршрута по этим линиям позволяет получить оптимальный путь.
Раньше построение таких схем «съедало» массу вычислительных ресурсов, поскольку алгоритм попарно проверял пересечения тысяч потенциальных ребер с вершинами. В новой работе авторы нашли возможность полностью векторизовать процесс, то есть перейти к обработке массивов данных одной операцией.
«Один из самых вычислительно затратных этапов построения графа видимости — процесс проверки пересечений. Он включает определение того, пересекаются ли ребра, соединяющие узлы, с ребрами препятствий. Сложность заключается в том, чтобы избежать попарных сравнений между большим количеством потенциальных ребер видимости и ребер препятствий, которые приводят к вложенным циклам и значительным вычислительным накладным расходам. Чтобы решить проблему, предложены методы векторизации», — пояснил один из разработчиков, доцент кафедры вычислительной техники и защиты информации УУНиТ Константин Миронов.
Дополнительно ученые предложили «умный» алгоритм, который уменьшает число углов в многоугольниках, которыми обозначены препятствия. Благодаря ему количество вычислений также сокращается при сохранении оптимального варианта пути.
На маленьких картах векторизованное построение графа видимости работает иногда в 100 раз быстрее, чем, к примеру, Theta* — популярный алгоритм поиска пути. А на более крупных картах, насыщенных препятствиями, новый метод даст примерно пятикратное преимущество, отметили исследователи.
Также к достоинствам метода относится быстрота нового планирования в случае изменения обстановки. Пересчет траектории с добавлением новых стартовых и конечных точек происходит менее чем за 0,04 секунды. Это позволяет роботизированным устройствам реагировать на новые факторы почти без задержки.
«Разработка — шаг к созданию полностью автономных систем, способных самостоятельно ориентироваться в сложной среде. Мы стремимся объединить эффективные алгоритмы и современные инструменты искусственного интеллекта», — прокомментировал соавтор исследования, директор Центра когнитивного моделирования МФТИ и руководитель лаборатории когнитивных систем искусственного интеллекта Александр Панов.
Как отметили ученые, технология уже встроена в системы управления роботами и протестирована на реальных картах размером 512 × 2048 пикселей, которые включают до 280 препятствий.
Предложенный подход может применяться в складской логистике, где роботам-погрузчикам нужно ежесекундно прокладывать новые пути между стеллажами. Также он востребован в поисково-спасательных операциях, где обстановка постоянно меняется из-за завалов.
Еще одно возможное применение — управление роями дронов в закрытых помещениях, где каждый аппарат сможет мгновенно перестраивать маршрут, не дожидаясь центрального компьютера. В перспективе разработку могут взять на вооружение создатели роботизированных комплексов, предназначенных для изучения и освоения других планет и строительства внеземных баз.