Российские учёные ускорили поиск кратчайшего пути для роботов в 100 раз

Учёные МФТИ и Уфимского университета создали новый метод построения маршрутов, который ускоряет поиск кратчайшего пути в сто раз и позволяет перестраивать траекторию за десятки миллисекунд. Разработанный алгоритм использует полную векторизацию операций пересечений на основе графов видимости: вместо последовательной обработки каждого отрезка-кандидата система с помощью матричных операций обрабатывает все возможные варианты одновременно, вычисляя определители для всех пар отрезков и формируя булеву маску. Для ускорения процесса также применён алгоритм упрощения полигональных контуров Дугласа-Пекера, который сократил число вершин, описывающих препятствия, и уменьшил время построения графа более чем в 200 раз. Метод протестирован на картах разного масштаба и показал на полигонах с 10–12 препятствиями время построения маршрута 30 миллисекунд — до 100 раз быстрее аналогов при нулевом отклонении от идеального пути. На крупных картах с сотнями препятствий время построения составило около 4 секунд, что примерно в 5 раз быстрее аналогов. При изменении стартовой точки или цели перестроение маршрута занимает всего 34–37 миллисекунд. Метод уже интегрирован в среду ROS (Robot Operating System). Следующий шаг — адаптация к полностью динамическим средам с движущимися препятствиями.