Прогнозируем движение беспилотного автомобиля (или как я вышел в тройку лидеров на Yandex Cup 2024) / forpes.ru

Главная
Прогнозируем движение беспилотного автомобиля (или как я вышел в тройку лидеров на Yandex Cup 2024)

Прогнозируем движение беспилотного автомобиля (или как я вышел в тройку лидеров на Yandex Cup 2024) +8

31.01.2025 11:42

nnazarov 0 567 Источник

*фотографии чемпионата взяты из телеграм-канала чемпионата

Хабр, привет! Меня зовут Николай Назаров, я работаю аналитиком данных в X5 Tech. Недавно завершился чемпионат по программированию Yandex Cup ML Challenge 2024, в котором я занял второе место в задаче “Self-driving cars: предсказание движения беспилотного автомобиля”. В статье расскажу про задачу и подходы, которые использовал для решения.

Задача

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

Для обучения было дано описание 42000 сцен продолжительностью около 60 секунд. Описание каждой сцены состоит из трёх файлов:

metadata.json: содержит общую информацию про сцену:

ride_date — дата проезда;
vehicle_id — уникальный идентификатор автомобиля;
vehicle_model — идентификатор модели автомобиля;
vehicle_model_modification — идентификатор модификации модели автомобиля;
tires — идентификатор типа шин;
location_reference_point_id — идентификатор референсной точки, используемой в качестве начала отсчёта координат в файле localization.csv.

localization.csv: описывает траекторию движения автомобиля. Представляет собой csv файл, каждая строчка которого имеет формат:

stamp_ns — время в наносекундах от начала сцены;
x, y, z — координаты центра задней оси автомобиля;
roll, pitch, yaw — углы Эйлера в радианах, описывающие ориентацию автомобиля в пространстве. Угол yaw считается относительно оси x в направлении оси y.

control.csv: описывает последовательность команд управления, отправленных автомобилю:

stamp_ns — время в наносекундах от начала сцены;
acceleration_level — желаемая интенсивность ускорения. Положительные значения соответствуют силе нажатия на педаль газа, отрицательные — силе нажатия на педаль тормоза;
steering — желаемый угол поворота руля в градусах относительно центрального положения.

Пример данных:

На тестирование выделено 8000 сцен продолжительностью 20 секунд. Сцены в тесте также описываются тремя файлами. Данные в control.csv содержат информацию за все 20 секунд, а в localization.csv только за первые 5 секунд. Нужно спрогнозировать значения x, y и yaw оставшихся 15 секунд.

Для оценки качества решения сравнивается близость предсказанных положений автомобиля $p_t=\{x_t, y_y, yaw_t\}$ и записанных в сцене $\hat{p}_t=\{\hat{x}_t, \hat{y}_y, \hat{yaw}_t\}$ . Близость позиций вычисляется как расстояние между предсказанной и записанной позициями на плоскости для двух опорных точек на корпусе автомобиля: $c_1 = \{x; y\}$ и $c_2 = \{x + S \times cos(yaw); y + S \times sin(yaw)\}$ , где длина отрезка между опорными точками, равная 1 метру:

$dist(p, \hat{p}) = \sqrt{\dfrac{||c_1 - \hat{c}_1 ||^2_2 + ||c_2 - \hat{c}_2 ||^2_2}{2}}$

На картинке ниже схематично изображено возможное расположение опорных точек для предсказанного и записанного в сцене положений автомобиля в некоторый момент времени:

Итоговая метрика равна среднему значению похожести траекторий, где похожесть траекторий $D = \{p_t\}_{t=1}^{T_n}$ и $\hat{D} = \{\hat{p}_t\}_{t=1}^{T_n}$ вычисляется по формуле:

$trackdist(D, \hat{D}) = \dfrac{\sum_{t=1}^{T_n} dist( p_t, \hat{p}_t )}{T_n}$

Визуализация данных

Я строил различные графики, чтобы разобраться в данных. Покажу некоторые из них. Для исследования отдельных треков отображал изменение основных параметров в зависимости от времени и непосредственно траекторию движения в координатах (x, y). Для удобства разбивал трек на пятисекундные отрезки и рисовал их разными цветами. На первых шести графиках по оси абсцисс отложено значение времени. На последнем графике с траекторией движения точками отмечены положения с шагом в 1 секунду.

Что можно узнать о треке из этих графиков:

0-5 секунды — жмём на газ, ускоряемся, руль держим прямо, едем прямо;
5-10 секунды — уменьшаем нажатие на газ, переходим на тормоз;
10-20 секунды — жмём на тормоз, скорость падает, делаем небольшие повороты руля влево-вправо, возможно, перестраиваемся на соседнюю полосу;
20-25 секунды — сильно жмём на тормоз, скорость маленькая, фиолетовых точек на траектории движения практически не видно;
25-35 секунды — сильно крутим руль влево, добавляем газу, совершаем разворот;
35-40 секунды — выравниваем руль, продолжаем движение прямо;
40-50 секунды — сбрасываем скорость и затем разгоняемся.

Как думаете, зачем автомобиль тормозил на 40-45 секундах и что произошло на 45-50 секундах? Свою версию и небольшое расследование спрячу под спойлер.

Что же произошло?

На графике высоты z видно, что на 45-47 секундах было два скачка. Также на графике pitch есть резкие перепады. Следуя стереотипам о российских дорогах, я подумал, что водитель притормозил, чтобы аккуратно проехать какой-нибудь дефект дороги: яму или кочку. Нашёл это место на панорамах в Яндекс Картах и был приятно удивлён, увидев “лежачего полицейского”.

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

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

Карты траекторий треков

Всего было три локации. Шкалы по осям измеряются в метрах. Ориентация сторон света стандартная, север сверху.

Локация 1

Локация 2

Локация 3

Решение

Чтобы предсказывать траекторию движения, я обучал модели прогнозировать расположение автомобиля через 1 секунду от текущего момента. Для получения новой точки (x, y, yaw) достаточно знать три значения:

на сколько сдвинется центр задней оси автомобиля (speed);
в каком направлении будет смещение задней оси (phi);
новое значение yaw.

Модели предсказывали:

на сколько сдвинется центр задней оси автомобиля (speed);
на сколько изменится направление смещения задней оси phi относительно предыдущего смещения phi_0 (delta_phi);
на сколько изменится yaw относительно предыдущего yaw_0 (delta_yaw).

Зная текущее положение (x_0, y_0, yaw_0), предыдущее направление движения phi_0 и прогнозы моделей (speed, delta_phi, delta_yaw), следующее положение автомобиля вычисляется по формулам:

$\begin{align} &\text{x = x_0 + speed * cos(phi_0 + delta_phi)} \\ &\text{y = y_0 + speed * sin(phi_0 + delta_phi)} \\ &\text{yaw = yaw_0 + delta_yaw} \end{align}$

На картинке ниже изображено, как вычисляются таргеты моделей в момент времени t:

Почему speed и delta_phi, а не dx и dy?

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

Сложение и вычитание углов

В исходных данных значения yaw приведены в радианах в диапазоне $[-\pi, \pi]$ . Нужно аккуратно выполнять арифметические операции с углами, иначе в данных могут появиться аномалии. Например, автомобиль поворачивается по часовой стрелке, yaw меняется с $-0.94\pi$ на $0.92\pi$ . Хотим вычислить среднее значение yaw. Если вычислить среднее в лоб, то получим совершенно противоположное направление $-0.01\pi$ вместо $0.99\pi$ .

Чтобы этого избежать, при усреднении углов в окрестности угла $\pi$ , я добавлял $2\pi$ к отрицательным значениям углов. В нашем примере получается $(0.92\pi + (2\pi-0.94\pi))/2 = 0.99\pi$ .

Если после преобразований углы вышли из отрезка $[-\pi, \pi]$ , можно вернуть их на место:

def process_array_phi(phi: np.array):
    phi = phi.copy()
    phi[phi > np.pi] -= 2*np.pi
    phi[phi < -np.pi] += 2*np.pi
    return phi

Почему 1 секунда?

В исходных данных измерения производятся с частотой 25 Гц. С одной стороны, обучение моделей предсказывать с шагом в 1 секунду позволяет уменьшить количество данных, что приведёт к ускорению обучения и инференса. С другой стороны, при агрегации мы теряем часть информации, что может приводить к ухудшению качества прогнозов. Реализовав пайплайн обучения и оценки качества для шага в 1 секунду, попробовал перейти к шагу в 0.5 секунды. Качество от этого не улучшилось, поэтому решил остаться на 1 секунде.

Resample 1s

Чтобы прогнозировать с шагом в 1 секунду, нужно уметь определять положение автомобиля в определённый момент времени. Для этого я аппроксимировал функции x(t), y(t) и yaw(t) полиномами второй степени от времени в окрестности нужной временной точки. В коде это выглядит так:

# values - np.array [[ts, x, y, yaw]]
# ts - время, для которго нужна точка
loc = values[np.abs(values[:, 0] - ts) < 1]
yaws = loc[:, 3]
if yaws.max() - yaws.min() > np.pi:
    loc[yaws < 0, 3] += 2 * np.pi
deg = 2
coefs = np.polyfit(loc[:, 0], loc[:, 1:4], deg)
point = ((ts ** np.arange(deg, -1, -1)) * coefs.T).sum(axis=1)

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

в 3-ой строке выбираем точки из окрестности ;
в 4-6 строках предобрабатываем углы, чтобы не получить аномалий;
в 7-8 строках строим полиномы второй степени от времени;
в 9-ой строке вычисляем значение в нужной точке.

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

Inference

Зная положения автомобиля в нужные моменты времени, можно вычислить для них фичи и таргеты и обучить модели. Чтобы спрогнозировать траекторию на 15 секунд вперёд, я вычислял признаки для последней известной точки, делал прогнозы на следующую секунду, переходил в новую точку и повторял эти шаги 15 раз. Таким образом получалась траектория с шагом в 1 секунду:

Для формирования сабмита нужно получить значения в промежуточных точках с частотой 25 Гц. Допустим, хотим получить значения в момент времени 17.8 секунды. Я использовал следующий подход:

Берём пару ближайших известных точек. Для 17.8 секунды это 17 и 18 секунд.
Оцениваем скорость движения автомобиля в этих точках. Я просто усреднял скорости за секунду до и после нужного момента времени.
Делаем из известных точек шаг по направлению yaw на малое приращение времени в 0.001 секунды. Получаем две дополнительные точки.
По четырём точкам аппроксимируем функции x(t), y(t) и yaw(t) полиномами второй степени от времени.
Подставляем нужный момент времени 17.8 секунды в получившиеся полиномы, получаем положение автомобиля.

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

Модели и признаки

Для прогнозирования всех трёх таргетов я использовал LightGBM с одинаковыми гиперпараметрами и признаками. Код обучения:

max_bin = 2500
num_boost_round = 350
params = {
    'objective': 'regression',
    'metric': 'rmse',
    'boosting': 'gbdt',
    'verbose': 1,
    'force_col_wise': True,
    #
    'reg_alpha': 0.001,
    'reg_lambda': 0.001,
    'colsample_bytree': 0.95,
    'subsample': 0.95,
    'subsample_freq': 1,
    'min_child_samples': 20,
    'cat_smooth': 150,
    'num_leaves': 2500,
    'max_bin': max_bin,
    'learning_rate': 0.06,
    ‘min_gate_to_split’: 0.00001,
}
models = {
    target_name: lgb.train(
        params,
        lgb.Dataset(
            data=df_params[feature_names],
            label=df_params[target_name],
            categorical_feature=cat_feature_names,
            params={'max_bin': max_bin,}
        ),
        num_boost_round=num_boost_round,
    )
    for target_name in tqdm(target_names)
}

В финальной версии моделей использовал 80 признаков. Шесть признаков из metadata: год, месяц, неделя, идентификатор передних шин, идентификатор автомобиля, идентификатор модификации модели автомобиля. 28 признаков по данным из control.csv: по 14 для силы нажатия на педаль и угла поворота руля. Вычислял среднее в окне с шагом 0.25 секунды. На картинке ниже приведена иллюстрация вычисления признаков для момента t=34 . Синяя линия — значения в исходных данных, чёрные горизонтальные линии внутри оранжевых скобок — вычисленные значения признаков:

По данным из файла localization.csv вычислял скорость движения автомобиля, скорости изменения углов phi и yaw, разницу углов phi и yaw, произведение скорости движения и угла поворота руля, изменение высоты за секунду (координата z), а также ряд статистик, посчитанных по значениям углов pitch других треков, которые проезжали рядом с текущими координатами в том же направлении. Для полученных признаков брал шифты на 1 и 2 секунды, то есть использовал дополнительно аналогичные признаки, рассчитанные для прошлой и позапрошлой секунд.

Увеличение датасета

Далее расскажу о двух трюках, которые помогли улучшить результат. Первый — увеличение размера датасета за счёт сдвига по времени. Обучался прогнозировать из 5-ой секунды 6-ую, из 6-ой — 7-ую и так далее. Можно по тем же данным прогнозировать из момента 4.5 секунды на 5.5 секунды, из 5.5 на 6.5 и так далее. По сути, мы просто сдвинули временную шкалу на 0.5 секунды и получили другой набор данных того же размера. Аналогично добавил сдвиги на 0.25 и 0.75 секунды, увеличив исходный датасет в четыре раза. Такой способ увеличения датасета приводит к уменьшению ошибки на валидации. Продемонстрирую это на графике для одной из моделей:

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

Проекции на дороги

Второй трюк, улучшивший качество — проекция на дороги. Получив прогнозы на тестовой выборке, я сравнивал предсказанные траектории с треками из обучения. На картинке ниже приведён пример сравнения. Оранжевые точки — прогнозы, синие — известные треки:

По картинке видно, что небольшая ошибка в предсказании угла движения после поворота со временем накапливается и приводит к большим отклонениям. Я решил исходить из предположения, что автомобили ездят по дорогам и не съезжают далеко за их пределы. Появилась идея при наличии рядом похожих треков проектировать на них предсказанный трек, если он отклоняется в сторону. Для этого я брал последнюю точку посекундного прогноза и искал ближайшую похожую точку известных треков. Если расстояние между точками большое, то, возможно, эта точка уже с другой дороги, поэтому делать проекцию на неё не нужно. Если расстояние было от 0.5 до 30 метров, запоминаем найденную точку. Продолжаем перебирать точки спрогнозированного трека, пока они не станут ближе 0.5 метра к известным точкам. После этого строим линейное приближение точек трека, строим линейное приближение найденных ближайших точек, вычисляем угол между этими прямыми и поворачиваем точки спрогнозированного трека на этот угол.

На картинке ниже приведена иллюстрация описанного алгоритма. Оранжевые точки — посекундные прогнозы, чёрные точки — проекции прогнозов на известные треки, в чёрный кружок выделена точка, которая стала ближе 0.5 метров к точкам известных треков:

Результат применения такой постобработки приведён на картинке ниже. Уходящие с дороги треки исчезли. Это помогло улучшить public score с 0.87 до 0.79.

Результаты

Судя по лидерборду, в соревновании участвовали 139 человек. 61 участник смог побить baseline (private score 16.87). Решение, описанное в статье, позволило получить private score 0.81 и занять второе место. Private score победителя равен 0.70.