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