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