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