Введение

Открываешь навигатор — а ты уже в деревне Пупкино. Знакомо? Спуфинг и глушение GNSS стали новой реальностью, ломая работу служб логистики, такси и даже общественного транспорта. Наша компания столкнулась с этим лицом к лицу в проекте по интеграции V2X в московские трамваи. Вагоны с нефункционирующим GPS начали «дрейфовать» в цифровом пространстве, а инерциальные системы (IMU) требовали калибровки через N поворотов на 90° — в рельсовом транспорте такое просто невозможно.

Так родился «Курвиметр» — наша реализация Dead Reckoning. Идея проста: если GPS молчит, а CAN‑шина даёт скорость, почему бы не использовать её для расчёта пройденного пути, а пройденный путь соотносить с треком? Спойлер: всё оказалось сложнее. Или спасибо машинному обучению. Вот как мы заставили трамвай «знать», где он находится, даже в зоне глушения. Кажется, это интересный кейс, поэтому не ограничивали себя в количестве представленных расчетов и графиков.

Описание проблемы

Для тех, кто не в контексте.

Dead Reckoning — алгоритм оценки текущего положения движущегося объекта на основе его предыдущего положения, скорости, направления и прошедшего времени.

Как мы могли бы использовать Dead Reckoning для решения нашей задачи?

Рассмотрим простой пример.

Что необходимо, чтобы понять, где оказался трамвай через минуту после начала движения? А через 10 минут? А через час?

Всё это можно разбить на несколько простых шагов:

1. Узнать точку старта движения трамвая.

2. Узнать, как изменялась скорость, с которой он ехал в течение заданного промежутка времени. Ведь скорость трамвая не постоянна.

3. По скорости и времени рассчитать пройденную дистанцию.

4. Наложить пройденную дистанцию на заранее записанный маршрут трамвая.

5. Выдать новое местоположение трамвая.

Расчёт пройденного расстояния

Для каждого измерения используем среднюю скорость между двумя соседними отсчётами:

где:

• — скорость из CAN‑шины на предыдущем измерении, м/с;

• — скорость из CAN‑шины на текущем измерении, м/с;

• — время между измерениями, примерно 0,1 с.

План готов, осталось проверить его в действии.

Обкатка проводилась в зоне без глушения GNSS, поскольку, чтобы сказать, что Dead Reckoning работает как задумано, мы сравнивали его с GNSS.

В идеальном мире расчётная координата должна полностью совпадать с координатами, которые выдал GNSS‑модуль.

Но мы не в идеальном мире, поэтому договорились, что 5 метров — максимальное расстояние, на которое может ошибиться Dead Reckoning по сравнению с данными GNSS.

Если ошибка превышена — алгоритмом пользоваться нельзя.

Качество определяется разницей между пройденным расстоянием, рассчитанным по CAN, и расстоянием, рассчитанным по GNSS:

где:

• — путь, рассчитанный на основе скорости из CAN‑шины;

• — путь, рассчитанный на основе скорости, которую предоставляет GNSS‑модуль.

Если:

считаем, что накопленная ошибка превысила допустимый предел работы Dead Reckoning.

Стоит отметить, что GNSS‑модуль работает в режиме RTK, который обеспечивает точность позиционирования до 5 см.

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

Первый результат

Результаты MVP, мягко говоря, расстроили: путь, который удалось пройти трамваю с заданным критерием, составил всего 196 метров — даже до ближайшей остановки не доехал.

График 1. Пройденный путь по данным из CAN‑шины и GNSS‑модуля.

Выдвинули гипотезу: скорость CAN‑шины содержит ошибку, которая накапливается в ходе расчёта расстояния.

Для проверки надо собрать данные.

---

Анализ данных и обучение

Набор данных для анализа состоит из 25 000 измерений. Руководствуемся простой логикой: больше измерений — лучше результат.

Одно измерение содержит:

• скорость, рассчитанную GNSS‑модулем ();

• скорость, полученную из CAN‑шины ();

• время между измерениями.

График 2. Отображение собранных Vcan и Vgnss, м/с.

Приближаем один из участков графика.

График 3. Участок графика 2.

Приближение дало небольшой намёк на наличие лага графика .

Обратимся к математике, а если точнее — к методу кросс‑корреляции.

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

Кросс‑корреляция подтвердила, что график требуется сдвинуть влево относительно , прежде чем анализировать данные.

Так и сделаем.

Смещение еле заметно, но картинка выглядит поприятнее:

График 4. Приближение Vcan и Vgnss, без учета лага.

График 5. Приближение Vcan и Vgnss, с учетом лага.

Корреляция скорости

GNSS‑модуль, который мы используем в рамках текущей работы, «под капотом» использует фильтр Калмана для обработки сырых данных со спутника.

Для скорости из CAN‑шины фильтр использовать не стали, так как большого разброса данных не обнаружили.

На графике 6 представлена зависимость ошибки — разницы скоростей  — от .

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

Это означает, что мы не можем использовать для расчёта расстояния без дополнительной коррекции.

Нужно определить правило, по которому будем корректировать значение скорости, полученное из CAN‑шины.

График 6. Зависимость ошибки от скорости из GNSS модуля.

---

Построение модели коррекции

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

Нам предстояло определиться с видом функции .

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

Общее представление модели выглядит так:

Считываем , подставляем значение в полином, находим и используем его для расчёта расстояния.

Получаем прирост в точности позиционирования.

Мы в шоколаде!

Осталось ответить на два вопроса:

1. Чему равен порядок полинома ?

2. Как рассчитать коэффициенты полинома?

---

Обучение моделей

Мы взяли ранее собранный датасет, состоящий из измерений и , и с помощью метода наименьших квадратов подобрали оптимальные коэффициенты для регрессионных моделей от 1-го до 6-го порядка.

Другими словами — произвели обучение.

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

• скорректированный ;

• AIC;

• BIC.

Скорректированный  — скорректированный коэффициент детерминации. Показывает, насколько хорошо модель объясняет данные, но с поправкой на количество предикторов.

Чем ближе значение к 1, тем лучше модель объясняет наблюдаемые данные.

AIC — информационный критерий Акаике, используемый в статистике для выбора модели из нескольких возможных.

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

BIC — байесовский информационный критерий.

Он аналогичен AIC, но сильнее штрафует модель за увеличение её сложности. Особенно полезен при работе с большими выборками.

---

Ниже представлены графики для каждого критерия в отдельности.

На всех графиках:

• ось X — порядок модели;

• ось Y — значение соответствующего статистического критерия.

График 7. Скорректированный R².

График 8. BIC.

График 9. АІС.

Сравнение моделей

Таблица 1. Сравнение статистических критериев АІС, ВІС, Скор. R².

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

Однако наибольший прирост наблюдается при переходе от 1-го к 3-му порядку. Поэтому модели 4–6-го порядков были исключены из дальнейшего рассмотрения.

Полином 3-го порядка показал наилучшие результаты по статистическим критериям среди оставшихся вариантов.

---

Получившиеся модели

В результате обучения получили следующие модели.

Полином 1-го порядка

Полином 2-го порядка

Полином 3-го порядка

Коэффициенты полиномов, представленных выше, получены на основе данных с конкретного трамвая.

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

---

Проверка моделей на тестовых данных

Следующий этап — прогон модели на тестовых данных.

Мы собрали ещё один набор данных, чтобы протестировать исходные модели.

Во время теста на вход моделей поступала скорость из CAN‑шины, на выходе получались скорректированные значения скорости, на основе которых рассчитывался пройденный путь для каждого полинома.

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

Оценка моделей для предстоящего проезда производилась по двум параметрам:

1. процент пройденного пути;

2. максимальное значение накопленной ошибки во время движения.

Процент пройденного пути

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

Набор тестовых данных содержал 13 км маршрута.

Максимальная накопленная ошибка

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

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

Результаты

Таблица 2. Результат прогона моделей на тестовых данных.

По итогам тестирования моделей, полином 3-го порядка показал наилучшие результаты по рассматриваемым показателям.

Модель 3-й степени смогла уменьшить накопленную ошибку по расстоянию до 2,24 метров на всём пути следования.

---

Запуск MVP

Определив подходящую модель корректировки скорости, мы перешли к обкатке Dead Reckoning на реальном маршруте.

Эксперимент проводился на беспилотном трамвае, оборудованном нашим устройством.

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

В ходе испытания мы получали две точки:

• координату, рассчитанную алгоритмом Dead Reckoning;

• координату от GNSS‑модуля, работающего в режиме RTK.

Для наглядности треки Dead Reckoning и GNSS отображались на карте FortMonitor.

FortMonitor — комплексная программная платформа для ГЛОНАСС/GPS‑мониторинга транспорта. Предназначена для получения в режиме реального времени информации о местонахождении, передвижении и состоянии транспортных средств, а также других ключевых показателей работы автопарка.

Это продукт нашей компании.

На видео отображено, как Dead Reckoning — красный вертолёт — двигается вместе с трамваем, который получает высокоточные данные на протяжении всего маршрута.

Заключение

Главный вывод: результат нас вдохновил!

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

В нашем случае простая схема:

позволила значительно уменьшить накопление ошибки.

Вместо того чтобы пытаться заставить IMU работать в условиях, для которых требуется специальная калибровка, мы использовали уже доступный на борту трамвая источник информации о скорости — CAN‑шину — и скорректировали его показания на основе данных GNSS.

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

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

Почти так же точно, как в нашей модели.