Алгоритм МФТИ и Уфимского университета строит маршрут робота за 30 миллисекунд
Учёные МФТИ и Уфимского университета разработали метод планирования маршрутов, который на полигонах с 10–12 препятствиями прокладывает кратчайший путь за 30 мс - до 100 раз быстрее классических и вероятностных аналогов при нулевом отклонении от оптимальной траектории. Исследование опубликовано в журнале Intelligent Service Robotics.
Как работает метод
В основе - граф видимости: вершины препятствий соединяются рёбрами там, где между ними нет преград. Классические алгоритмы проверяют каждый отрезок-кандидат последовательно. Новый метод применяет полную векторизацию операций пересечений: за один проход вычисляются определители для всех пар отрезков и формируется булева маска «видно/не видно», что исключает перебор.
Дополнительно применён алгоритм упрощения контуров Дугласа-Пекера - он убирает незначимые углы на почти прямых стенах, сохраняя форму препятствий. Это сократило число вершин и время построения графа более чем в 200 раз.
Результаты на разных масштабах
На крупных картах с сотнями препятствий маршрут строится примерно за 4 секунды - в 5 раз быстрее аналогов. На городской карте из четырёх крупных полигонов с тысячами вершин отклонение от идеального пути составило менее 0,07% - показатель, недостижимый для быстрых вероятностных планировщиков (PRM, RRT, BIT, FMT).
Перестроение маршрута при смене стартовой точки или цели занимает 34–37 мс: система добавляет две новые точки в готовую структуру без пересчёта всей сцены.
Текущий статус
Метод интегрирован в ROS (Robot Operating System) и протестирован как готовый навигационный узел. Следующий этап - адаптация к динамическим средам с движущимися препятствиями для применения в беспилотных автомобилях и роботах-курьерах.
Источник — CNews — промтехнологии
