Специалисты из МФТИ и Уфимского университета разработали метод построения маршрутов, который позволяет роботам находить кратчайший путь в сто раз быстрее существующих аналогов. В случае изменения обстановки система способна перестроить траекторию всего за десятки миллисекунд, говорится на сайте Десятилетия науки и технологий в России.
Поиск безопасного пути — одна из самых ресурсоемких задач для искусственного интеллекта. Обычно алгоритмы вынуждены поочередно проверять сотни отрезков на пересечение с препятствиями, что требует больших вычислительных мощностей. Российские ученые применили принципиально иной подход. Вместо последовательной обработки они использовали полную векторизацию операций на основе графов видимости.
«Граф видимости — это структура, в которой вершинами служат углы препятствий, а ребрами — прямые линии, соединяющие те вершины, между которыми нет преград. Главная проблема в том, чтобы быстро определить, какие именно отрезки не пересекаются с границами препятствий. Обычно алгоритмы обрабатывают каждый отрезок-кандидат отдельно. С помощью матричных операций наш алгоритм обрабатывает все возможные варианты одновременно», — комментирует Константин Миронов, доцент института информатики, математики и робототехники Уфимского университета.
Для еще большего ускорения исследователи применили алгоритм Дугласа-Пекера, который упрощает контуры объектов, не учитывая лишние углы на ровных стенах. Это позволило сократить время построения графа более чем в 200 раз. В ходе тестов на картах разного масштаба новый метод продемонстрировал высокую эффективность. На небольших полигонах с 10-12 препятствиями маршрут строился всего за 30 миллисекунд, что в 100 раз быстрее аналогов. При работе с крупными картами, содержащими сотни препятствий, время поиска составило около 4 секунд — в 5 раз быстрее конкурентов.
Важным преимуществом стала возможность мгновенного перепланирования. Если точка старта или цель меняется, системе требуется всего 34-37 миллисекунд, чтобы проложить новый маршрут, используя готовую структуру данных.
Метод уже интегрирован в среду ROS (Robot Operating System) как готовый навигационный узел. Технология идеально подходит для управления беспилотными доставщиками, складской логистикой и автономным транспортом, где обстановка постоянно меняется. Следующим шагом разработчиков станет адаптация системы к полностью динамическим средам с движущимися препятствиями.
Тем временем в Китае показали уникального робота-кентавра. Подробности — в другом материале Hi-Tech Mail.