В современном мире все более востребованы мобильные автономные роботизированные комплексы. Поэтому проблемы организации их движения в неизвестных и изобилующих препятствиями средах выходят на первый план.
Чтобы решить эту задачу, ученые-программисты из Московского физико-технического института, Института AIRI и Уфимского университета науки и технологий предложили поэтапный алгоритм, реализация которого в несколько раз ускоряет ориентацию беспилотных машин в пространстве и нахождение ими наиболее оптимального маршрута. Новый метод позволяет умным роботам быстро и точно, избегая преград, перемещаться на плоской поверхности, самостоятельно определяя лучший путь к заданной конечной точке.
Исследование опубликовано в академическом издании Lecture Notes in Artificial Intelligence, которое посвящено вопросам искусственного интеллекта.
Как объяснили разработчики, предложенный алгоритм имеет модульную структуру. На первом этапе программа использует нейросеть PolyWorld. Она обрабатывает данные, полученные от камер и датчиков, и преобразует объекты физического мира в полигональные (состоящие из множества многоугольников) модели. Эти алгоритмы, в частности, успешно применяют для обработки спутниковых снимков.
На следующей стадии выполняется построение графа видимости между полигонами (препятствиями) и поиск оптимального пути на этом графе. В этой системе углы полигонов соответствуют вершинам графов, а прямые линии между ними — ребра, которые соединяют вершины, если между ними нет препятствий. По ним и проходит кратчайшая траектория между заданными точками.
Вместе с тем ускорение вычислений осуществляется за счет векторизации операции проверки пересечений ребер. Для этого координаты препятствий и ребер видимости представляются в виде векторов, что позволяет эффективно использовать одновременное выполнение однотипных операций на большом объеме данных и быстро находить оптимальный путь. Данная операция исключает возможность пересечения ребер видимости с препятствиями.
«Отличительная особенность метода заключается в его модульной структуре и применении векторизации, что позволяет значительно ускорить работу алгоритма. Она включает этапы обнаружения контуров, идентификации вершин и аппроксимации полигонов. Кроме того, внедрение векторизации процесса проверки пересечений позволило оптимизировать вычисления и ускорить алгоритм», — рассказал один из авторов исследования Кирилл Касмынин, магистрант физтех-школы прикладной математики и информатики МФТИ.
Он отметил, что эффективность разработки проверена экспериментально и значительно превосходит другие алгоритмы поиска пути, основанные на построении ребер видимости. В дальнейшем предложенный алгоритм будет внедрен в систему управления реального робота. Планируется проверить эффективность робота при движении в сложной обстановке с большим количеством препятствий по сравнению с роботами, оснащенными другими алгоритмами поиска пути.
Как считают ученые, предложенный метод позволит качественно улучшить навигацию мобильных роботов, которые перемещаются на двухмерном покрытии. В том числе беспилотных устройств — на земле или на полу в помещениях, катеров — на водной глади, глубоководных аппаратов — на морском дне, и роверов-исследователей — на поверхности планет и небесных тел.
