Российские ученые научили роботов находить кратчайший путь в сто раз быстрее 📈 — 27 июля 2026 г. в 10:29:01.663
Российские ученые научили роботов находить кратчайший путь в сто раз быстрее 📈 Ученые МФТИ и Уфимского университета создали метод построения маршрутов, который ускоряет поиск кратчайшего пути в сто раз и позволяет перестраивать траекторию за десятки миллисекунд. Это обеспечит быструю и точную навигацию на складах, в курьерской доставке и в беспилотном транспорте. Вместо последовательного перебора вариантов ученые заставили алгоритм работать сразу со всеми возможными отрезками одновременно, реализовав полную векторизацию операций пересечений на основе графов видимости. За один проход система вычисляет определители для всех пар отрезков и формирует Булеву маску, мгновенно исключая пересекающиеся с препятствиями варианты. ⚙️ Для ускорения применили алгоритм упрощения полигональных контуров Дугласа-Пекера, который сокращает число вершин, описывающих препятствия, и уменьшает время построения графа более чем в 200 раз. 📍 На полигонах с 10–12 препятствиями метод построил маршрут за 30 миллисекунд — до 100 раз быстрее аналогов при нулевом отклонении от идеального пути. На крупных картах с сотнями препятствий время составило около 4 секунд, что в 5 раз быстрее аналогов. Важное преимущество — быстрое перепланирование При изменении стартовой точки или цели система просто добавляет две новые точки в готовую структуру и прокладывает обновлённый маршрут за 34–37 миллисекунд. Это открывает возможность для навигации в реальном времени. Метод уже интегрирован в среду ROS и протестирован в виде готового навигационного узла. Следующий шаг — адаптация к полностью динамическим средам с движущимися препятствиями.