Как устроен робот-доставщик Яндекса: от восприятия до планирования движения

Уже пять лет по улицам Москвы колесят роботы?курьеры Яндекса, доставляя нам еду из любимых ресторанов и магазинов быстрее, чем мы успеваем проголодаться. На пути им встречается много препятствий: от безобидной клумбы, которую можно просто объехать, до восторженных детей (и иногда взрослых), от которых порой не так просто уехать.

Вполне обычная ситуация

Нам пришлось приложить немало усилий, чтобы каждый выезд робота заканчивался успешно. Нужно было научить его видеть мир вокруг себя, а окружающих правильно реагировать на доставщика.

Привет, меня зовут Тая, и я ML?разработчик в команде восприятия робота?доставщика Яндекса. Сегодня я впервые детально расскажу о технологиях, благодаря которым наш робот успешно доставляет заказы. Разберу ключевые компоненты системы, от сенсоров до алгоритмов принятия решений, и объясню, как они взаимодействуют. Из статьи вы узнаете, что происходит «под капотом» нашего робота во время его путешествий по городу.

Готовы погрузиться в мир автономной доставки? Поехали!

Архитектура технологии

Чтобы разобраться, как работает робот?доставщик, давайте рассмотрим архитектуру технологии в целом. Для начала выделим пять основных составляющих, которые делают робота умным и способным доставлять заказы быстро и безопасно:

1. Сенсоры. Помогают роботу видеть мир вокруг и понимать собственное движение.

2. Восприятие. Превращает данные с сенсоров в понятную для робота картину мира, выделяя важные объекты вокруг.

3. Карты. Содержат подробную информацию о местности, по которой передвигается робот.

4. Локализация. Помогает роботу точно определить, где он находится на карте в каждый момент времени.

5. Поведение. «Мозг» робота, который решает, как действовать в разных ситуациях, и выбирает лучший путь.

Теперь рассмотрим детальнее каждый из основных элементов системы.

Сенсоры

Сенсоры, установленные на роботе?доставщике, можно разделить на две группы: для восприятия окружающего мира и для нахождения положения робота в нём. К первой группе относятся сенсоры, помогающие сканировать окружающую среду и распознавать объекты, например лидары, камеры, радары и парктроники. Ко второй группе относятся датчики, отслеживающие положение, скорость и ориентацию робота: IMU, GNSS и датчики вращения колёс.

Сенсоры восприятия

LiDAR (Light Detection and Ranging) — метод дистанционного зондирования, основанный на использовании лазерного излучения для определения расстояния до объектов.

Оснащённый 64 лазерными лучами, лидар формирует детализированное трёхмерное облако точек с диапазоном видимости до 30 метров. Благодаря высокой плотности данных мы не только точно измеряем расстояние до объектов, но и легко классифицируем их по форме.

Принцип работы лидара

Подробнее о технологии лидаров можно узнать из доклада Гоши Никандрова, руководителя команды разработки лидаров, или из обзора компании Hesai, ведущего мирового производителя лидаров.

Робот оснащён четырьмя fisheye?камерами, расположенными таким образом, чтобы получить полный, 360-градусный обзор без слепых зон. При подготовке данных мы преобразуем fisheye?изображения в сферическую проекцию. Это позволяет корректно объединить все кадры в общую панораму без искажений. Подробнее о проецировании fisheye?изображений можно узнать здесь.

Радар дополняет возможности лидара, используя радиоволны и эффект Доплера, чтобы измерять скорость объектов на расстоянии до 150 метров. Это особенно полезно, когда робот проезжает пешеходный переход, так как радары позволяют заранее обнаружить приближающиеся машины и оценить их скорость.

Парктроники используют ультразвуковые датчики для обнаружения объектов на близком расстоянии, что обеспечивает дополнительную безопасность в ближней зоне робота.

Сенсоры позиционирования и движения

GNSS (Global Navigation Satellite System) — глобальная система спутниковой навигации, которая используется для определения местоположения на земной поверхности. Она объединяет несколько спутниковых систем, включая американскую GPS, российскую ГЛОНАСС, европейскую Galileo и китайскую BeiDou.

Инерциальный измерительный модуль (IMU) — это компактное электронное устройство, объединяющее акселерометр и гироскоп. Он позволяет определять линейное ускорение и угловую скорость робота в пространстве.

Датчики вращения колёс — это высокоточные датчики, установленные на колёсах робота. Регистрируют мельчайшие повороты колёс, позволяя точно измерять пройденное расстояние и скорость движения.

И раз уж мы разобрались, какую полезную информацию собирают сенсоры, давайте рассмотрим, что с этими данными делают наши алгоритмы.

Восприятие aka Perception

Главная цель системы восприятия — распознать объекты вокруг робота, которые могут повлиять на его движение. Эти объекты делятся на динамические (например, люди, машины, самокаты) и статичные (например, здания, столбы, деревья).

В случае с динамическими объектами требуется точное предсказание направления и скорости, чтобы своевременно реагировать, например, на едущие в сторону робота машину или самокат.

В случае со статичными объектами важнее определить их размер, так как распознанные статичные объекты принимают непосредственное участие в формировании траектории движения робота. Например, корректное распознавание статики важно в ситуации, когда робот едет по узкому тротуару, где ему приходится сильно прижиматься к стенам домов.

Робот?доставщик воспринимает окружающий мир с помощью 3D?детекции объектов и карты занятости (occupancy grid). 3D?детекция позволяет роботу определять тип каждого динамического объекта (например, человек или автомобиль), его точное местоположение, габариты, направление движения и скорость. Карта занятости разбивает пространство на небольшие ячейки размером 5?5 см, каждая из которых хранит тип занятости и высоту препятствий.

Чтобы лучше понять, как это работает, я приведу пример:

На картинке выше робот подъехал к пешеходному переходу и анализирует обстановку. Слева на картинке — наша визуализация того, что видит робот, а справа — данные с его камер (спереди, слева, справа и сзади). Фиолетовые столбики отображают карту занятости для статичных препятствий — на ней видны контуры здания позади робота, а ещё светофор и дорожный знак по бокам.

Робот также обнаружил движущиеся объекты, отметив их разноцветными 3D?коробками, над каждой из которых указан её класс, скорость и ускорение. Так мы можем понять, что сбоку по дороге едут машины, а сзади приближается пешеход.

Теперь разберёмся, как мы получаем разноцветные коробочки и фиолетовые столбики. Для этого мы обрабатываем данные с камер и лидара:

1. Растеризуем лидарные точки в 2D?плоскость камер, после чего объединяем их в общей плоскости с признаками, полученными с изображений.

2. Разбиваем пространство на ячейки размером 4?4 пикселя, для каждой из которых с помощью нейросети предсказываем информативные признаки (эмбеддинги).

3. Эмбеддинги проецируем на вид сверху (Bird's Eye View) с использованием координат лидарных точек, усредняя по z?координате.

4. Запускаем на спроецированных эмбеддингах ещё две подсети. Первая предсказывает объекты в 3D, вторая определяет класс для каждой лидарной точки. Из совокупности лидарных точек мы получаем ячейки карты занятости.

В итоге получаем 3D?детекции объектов и сегментацию лидарных точек. Затем система отслеживания перемещения объектов (трекер) использует венгерский алгоритм, чтобы сопоставить новые обнаруженные детекции с уже известными объектами, найденными на снимках в предыдущие моменты времени.

Трекер обновляет информацию о каждом отслеживаемом объекте (его трек), включая положение, скорость и направление движения. При обнаружении новых объектов создаются новые треки. Это обеспечивает непрерывное отслеживание всех объектов вокруг робота, даже если они временно пропадают из поля зрения сенсоров.

Предсказанные карты занятости также агрегируются во времени. Для этого используется фильтр Байеса, который трактует отдельные предсказания карты занятости в вероятностном смысле и пересчитывает апостериорные вероятности занятости отдельных ячеек карты. Это существенно повышает точность распознавания статичных препятствий.

Восприятие играет ключевую роль в безопасном передвижении робота, позволяя ему «видеть» и интерпретировать окружающую среду в реальном времени. Однако для эффективной навигации роботу недостаточно только текущего восприятия, ему также нужно представление о более широком контексте своего окружения. Именно здесь на помощь приходят HD?карты.

HD-карты

Карты High Definition (HD) — это карты высокой детализации. Они включают в себя трёхмерное представление окружающей среды в виде плотного лидарного облака для локализации, а также векторный слой, содержащий данные о дорожной инфраструктуре (например, светофоры, пешеходные переходы, границы дорог и тротуаров), которые помогает планировать траектории движения робота.

Лидарный слой

Лидарный слой HD?карты — это детальная трёхмерная модель окружающей среды, которая состоит из плотного облака точек, имеющего привязку к абсолютным координатам.

Создание этого слоя полностью автоматизировано. Для запуска робота?доставщика на новом месте достаточно один раз проехать по всем тротуарам и пешеходным дорожкам в ручном режиме, выгрузить данные и запустить процесс оптимизации, который на выходе выдаст плотное облако для локации. Если какие?то тротуары проходят близко к дороге, то для ускорения записи можно использовать беспилотный автомобиль — его лидарные облака также подойдут для создания такого слоя.

Лидарные облака, из которых строится слой карты, подвергаются предварительной фильтрации. Из них удаляются точки, принадлежащие динамическим объектам, таким как автомобили или пешеходы (с их детекцией помогает система восприятия). Благодаря этому мы получаем надёжную основу для локализации робота, которая редко меняется.

Векторный слой

Векторный слой HD?карты создаётся картографами на основе лидарных данных и изображений с камер. Слой хранит информацию о границах зон для движения робота в виде полигонов с разбивкой на типы зон. Мы выделяем следующие типы: пешеходные переходы, тротуары, велодорожки, зоны смешанного пользования (например, парковки или дворовая территория).

Также в карте хранится информация о положении светофоров, об их связи друг с другом и о том, какие манёвры они контролируют. Это позволяет определять состояние тех светофоров, которые встретятся роботу на пути, но которые не будет видно из?за людей или машин.

И наконец, сейчас в карте дополнительно хранятся полосы для робота в пределах допустимых зон для его движения, велосипедные полосы для предсказания поведения велосипедистов и агентские полосы — прогнозируемые траектории движения автомобилей. Эти данные помогают роботу эффективно планировать максимально безопасный маршрут с учётом особенностей городской среды и ожидаемого поведения других участников движения.

Все объекты в векторном слое рисуются с сантиметровой точностью. Это в том числе делает невозможным использование готовых HD?карт, точность которых ниже. И дальнейшие работы в проекте идут по пути уменьшения количества сущностей в векторном слое, упрощения формата, переноса детекции части сущностей в модуль восприятия, а также по пути автоматизации создания векторного слоя с помощью ML?алгоритмов.

Пока же векторный слой карты позволяет существенно разгрузить вычисления на борту и упростить систему восприятия. Но чтобы использовать информацию из этого слоя, робот должен уметь определять своё положение на карте. И с этим ему помогает модуль локализации.

Локализация

Главная цель локализации — определить положение, ориентацию, скорость и ускорение робота в пространстве. Для этого мы комбинируем данные с различных сенсоров.

• GNSS (Global Navigation Satellite System). Предоставляет данные о положении робота на поверхности Земли, например в виде классических широты и долготы. Однако GNSS может давать некорректные результаты в ситуациях, когда связь со спутником ослаблена, зашумлена или в принципе отсутствует: при плохих погодных условиях, в городской застройке, в тоннелях.

• IMU (Inertial Measurement Unit). Предоставляет данные об ускорении и угловой скорости робота. Эта информация критически важна для точной локализации, хотя показания могут колебаться при сильных наклонах или вибрациях корпуса робота.

• Колёсная одометрия. Используя данные с датчиков вращения колёс, мы оцениваем скорость движения робота, преодолённое им расстояние и изменения ориентации. Этот метод обеспечивает высокую точность на коротких дистанциях, но со временем ошибки могут накапливаться, особенно при проскальзывании колёс или движении по неровным поверхностям. Зимние условия представляют особую сложность для одометрии, поскольку увеличивают вероятность ошибок из?за скользких поверхностей и изменения сцепления.

А ещё нам помогает лидарная локализация, которая позволяет определять положение робота благодаря лидарному слою из HD?карты и текущему снимку с лидара. На примере любимой лошади Яндекса исходные данные могут выглядеть так:

Эта задача называется point?cloud registration, и существует множество алгоритмов её решения. В нашем случае для робота используется алгоритм NDT (Normal Distribution Transform). Вот как он работает.

Лидарный слой HD?карты предобрабатывается, всё трёхмерное пространство разбивается на ячейки. Если ячейка содержит лидарные точки, то строится некоторая модель поверхности, описывающая точки в этой ячейке. Модель приближает поверхность некоторым эллипсом, в каждой ячейке сохраняются параметры этой модели и координаты центральной точки.

Лидарное облако с робота перед применением алгоритма NDT также предварительно обрабатывается. Из него удаляются точки, принадлежащие самому роботу, а также движущимся объектам. Кроме этого, выбирается некоторое опорное подмножество точек из всего облака для оптимизации вычислений.

Важно отметить: чтобы алгоритм работал правильно, необходимо знать начальное приближение для положения робота, так как алгоритм эффективен только в ограниченном радиусе вокруг фактической позиции.

Для каждого нового лидарного облака алгоритм выполняет следующие действия:

1. Берёт текущее наилучшее предположение о положении робота.

2. Пытается «вписать» облако точек в карту, основываясь на этом предположении.

3. Для каждой точки облака, которая попала в заполненную ячейку карты, вычисляет, насколько нужно сдвинуться, чтобы точка лучше соответствовала модели поверхности в ячейке.

4. Усредняет все эти сдвиги и применяет их к текущему предположению о положении.

5. Повторяет процесс, пока изменения не станут очень маленькими или пока не пройдёт определённое количество итераций.

Этот метод позволяет точно определять положение робота, однако могут возникать трудности в пустых пространствах из?за недостатка характерных объектов (например, на пустой парковке) или в местах с однотипной застройкой (например, мы можем подумать, что находимся по другую сторону дома).

Всё вместе — EKF!

Учитывая, что у каждого метода локализации есть свои погрешности, мы используем Extended Kalman Filter (EKF) для объединения показаний всех сенсоров и получения наиболее точного результата.

Какие особенности нашей задачи делают EKF подходящим решением?

• Измерения неточные: каждый сенсор в определённых условиях может давать погрешности.

• Измерения избыточные: положение робота определяется по GNSS и ICP, скорость/ускорение — по колёсам и IMU, ориентация — по одометрии и ICP.

• Измерения несогласованные: данные от различных сенсоров поступают в разные моменты времени и представляют собой как абсолютные, так и относительные измерения.

Чтобы правильно учесть и абсолютные знания о локализации, и информацию об относительном перемещении, EKF на каждом такте работы совершает два действия. Во?первых, прогнозирует новое положение робота, а также параметры скорости, ускорения и ориентации на основе известного предыдущего состояния робота и некоторой модели движения. Во?вторых, актуализирует прогноз, используя данные от сенсоров и лидарной локализации. Полученная оценка становится отправной точкой для следующего такта работы EKF.

В теории звучит хорошо и надёжно, но на практике EKF требует правильной настройки параметров: какому методу в какой ситуации больше верить. При неверной калибровке могут возникать нестабильности, приводящие к «прыжкам» в локализации.

Тем, кому эта тема показалась интересной, советую посмотреть доклад от гуру локализации Саши Иванова — там вс? объясняется подробно и с картинками.

Теперь, когда мы разобрались, как робот воспринимает окружающий мир и определяет своё положение в нём, давайте перейдём к самой интересной части — узнаем, как робот принимает решения и планирует действия.

Планировщик движения & управление

После того как компоненты восприятия, локализации и HD?карт предоставили полную информацию о среде, следующим шагом становится планирование движения робота?доставщика и управление движением. Планировщик движения строит оптимальный маршрут на основе полученных данных, предсказывает возможные траектории других участников, а система управления отвечает за точное следование этому маршруту, корректируя движение робота в реальном времени.

Построение маршрута (Routing)

Любая поездка робота?доставщика начинается с появления двух точек, через которые надо проехать: отдельный сервис на бэкенде сообщает роботу, где забрать заказ и куда его доставить. Затем начинается планирование маршрута с учётом данных HD?карт, включая дорожную инфраструктуру (переходы, тротуары, велодорожки) и потенциальные препятствия (ремонтные работы, снежные заносы, узкие места). А ещё мы учитываем местоположение и планируемые траектории других роботов?доставщиков, чтобы они могли благополучно разъехаться в узких местах.

На основе этой информации строится взвешенный граф, где вес ребра зависит от различных факторов. Для поиска оптимального пути применяется алгоритм A*.

Предсказания

Итак, у нас есть глобальный маршрут — пора ехать. Но вспоминаем ПДД: прежде чем сделать первый шаг, нужно хорошенько осмотреться. Мы уже знаем о статичных препятствиях из HD?карт и только что получили свежую информацию от системы восприятия. К тому же мы в курсе, где находятся другие участники движения и с какой скоростью они перемещаются.

Но и этого мало! Чтобы безопасно проложить путь, нам нужно предугадать, куда могут направиться все эти движущиеся объекты, чтобы своим движением не создавать им помех. Поэтому для каждого движущегося объекта мы пытаемся предсказать возможные траектории движения. В этом нам помогает система предсказания движения.

Сейчас эта система представляет собой сложный набор правил, которые опираются на информацию из трекера (класс, направление и скорость объекта), и данные из HD?карт (например, где находятся полосы движения).

Планировщик движения (Motion planner)

Оценив все потенциальные препятствия, робот переходит к планированию локального маршрута — обычно на ближайшие 20 метров вдоль глобального пути. В этом процессе участвуют два планировщика:

1. Mesh planner — строит траекторию движения.

2. Speed planner — определяет скорость движения на различных участках траектории.

Как и при построении глобального маршрута, здесь также используется алгоритм A*, но с учётом дополнительных факторов: физических ограничений робота, пересекающих путь людей, машин и статичных объектов, ограничений скорости из соображений безопасности и других параметров.

Мы активно развиваем различные ML?подходы, но классический алгоритм A* всё ещё не подводит.

Управление (Control)

После построения траектории следовать ей непросто из?за множества факторов: неровностей дороги, изменяющегося трения, неполных данных с датчиков. Эти ошибки могут сбить робота с курса, поэтому необходима система управления для постоянной корректировки движения.

Наш подход к управлению роботом?доставщиком включает два основных компонента:

1. PID?регулятор для продольного управления (аналог педали газа). Этот метод поддерживает заданную скорость робота, эффективно корректируя отклонения и обеспечивая стабильное движение.

2. Pure Pursuit для поперечного управления (аналог руля). Этот метод вычисляет линейную и угловую скорость робота, чтобы достичь целевой точки траектории, расположенной впереди его текущего положения.

Не буду подробно описывать, как именно устроены эти алгоритмы управления: тема достойна отдельной статьи от моих коллег. Но если любопытство пересиливает, то советую классную вики?страничку — там есть и про PID, и про кинематическую велосипедную модель, и про Pure Pursuit.

Таким образом, компонента Control обеспечивает принятие решений на всех уровнях: от глобального планирования маршрута до локального маневрирования, позволяя роботу?доставщику эффективно и безопасно выполнять свои задачи.

Итак, мы рассмотрели основные составляющие системы робота?доставщика: от сенсоров до алгоритмов принятия решений. Однако это ещё не всё! У робота есть много не менее важных и интересных элементов: калибровка сенсоров, взаимодействие со светофорами и различные дополнительные детекторы (например, детектор ям), а еще блюр лиц и автомобильных знаков для защиты персональных данных. Надеюсь, в будущем мы напишем и о них.

Что касается планов, то мы продолжаем улучшать технологию робота?доставщика:

• автоматизируем и ускоряем построение HD?карт;

• прорабатываем ML?решения для планирования маршрутов;

• приближаем восприятие к уровню человеческого глаза, следуя за SOTA?открытиями в мире Computer Vision;

• делаем локализацию более надёжной и устойчивой к воздействиям внешней среды.

Теперь вы знаете, сколько всего нужно, чтобы маленький робот довёз вашу большую пиццу :)

Спасибо Вите Юрченко, Саше Иванову, Серёже Страдомскому, Лёше Голомедову, Олесе Криндач, Лёне Гречишникову и Саше Смирнову за чтение черновиков этой статьи и ценные советы.