Привет! Я Иван Косолапов, тимлид команды ETA/RTA. Мы часть сервиса Data Science и занимаемся анализом данных и машинным обучением для задач навигации в 2ГИС.

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

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

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

Под наведением порядка в процессе разработки я подразумеваю решение четырёх задач:

• выбор правильной метрики,

• подготовка данных,

• построение воспроизводимой системы экспериментов,

• перенос алгоритмов туда, где их проще всего развивать.

Расскажу, как решая эти задачи, мы добились более точного отображения автобусов на карте в 2ГИС, упростив существующую на тот момент сложную систему.

Отображение автобусов на карте

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

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

Как транспорт попадает на карту

На автобусах стоят GPS-трекеры, которые определяют текущие координаты и отправляют их агрегатору. Этот агрегатор отправляет эти данные нам. Кроме координат нам нужны также геометрии маршрутов, чтобы понять, где автобусы в принципе могут находиться.

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

• какой маршрут,

• в каком направлении автобус едет,

• где на линии маршрута он находится.

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

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

Проблемы с метриками

Оценить качество отображения автобуса на карте можно двумя способами.

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

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

Значения выглядели хорошо, ошибка — всего несколько десятков метров. Но в реальности это не соответствовало тому, что происходило в продукте!

Начали разбираться. Если бы мы показывали пользователям данные напрямую от GPS-трекера, они всегда бы получали устаревшую информацию, потому что есть задержка между записью на GPS-трекере и получением данных в приложении. Поэтому мы показываем пользователю прогноз. Когда приходят новые данные, это тоже прогноз, но более свежий. Мы решили сравнивать два этих прогноза и считать разницу в метрах между ними перед тем, как отправлять пользователям.

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

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

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

Максимальное значение ошибки

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

Ошибка у нас будет максимальной в двух случаях:

• Когда автобус стоит, а мы показываем, что он едет.

• Когда автобус едет, а мы предсказываем, что он стоит.

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

Для 60 км/ч это 16,67 метров. Если прогнозировать на две секунды, максимальная ошибка увеличится до 33,3 метров. С каждой секундой максимальная ошибка увеличивается.

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

Вопросы к исходным данным

Оказалось, что координаты автобусов у некоторых агрегаторов обновлялись чаще, чем за ними приходил 2ГИС.

Поэтому сократив интервал обновления данных с 30 до 10 секунд, удалось уменьшить горизонт прогноза на 20 секунд. Это позволило снизить максимальную погрешность на сотни метров, особенно в Москве и Санкт-Петербурге.

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

Этот подход оказался проблемным по нескольким причинам↓

Неточные координаты. Из-за погрешности GPS расстояние между точками измерения было неточным: мы не могли знать 50 метров между ними или 100. Это делало расчёты скорости тоже неточными.

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

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

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

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

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

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

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

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

Проблемы с воспроизводимостью экспериментов

Раньше для прогноза движения использовали сложную систему корректировки в реальном времени. Это создавало проблему: было невозможно воспроизвести работу боевого кода локально для экспериментов.

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

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

Чтобы исправить это, мы разработали инструменты на Python. Они позволяют подготовить датасет из большого количества реальных данных, применить к нему алгоритм и посчитать метрики.

Теперь у нас был фундамент для быстрого улучшения алгоритмов.

Переходим к алгоритмам

К этому моменту у нас было несколько отдельных наборов данных, метрик и скриптов для экспериментов с разными алгоритмами, например:

• определения направления автобуса,

• определения его позиции на маршруте,

• предсказания движения.

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

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

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

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

Мы отказались от корректировки в приложении и перенесли сглаживание на сервер. Для этого:

• выбрали метрику,

• создали датасет,

• провели офлайн-эксперименты.

Теперь бекенд полностью контролирует, что будет происходить на клиентах.

Итоги по задаче

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

MAE прибытия автобуса на остановку в секундах:

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

Логика работы системы стала сильно проще, теперь её можно контролировать и быстро развивать.

Заключение

Я описал общий подход к работе в нашей команде: так мы работаем на всех проектах. Если вы столкнулись со сложной задачей, то попробуйте использовать наш подход и ответить себе на несколько вопросов:

— Можете ли вы как-то измерить качество вашей работы?

— Корректны ли данные, на которые вы опираетесь?

— Можете ли вы проводить надёжные эксперименты?

— Уверены ли вы, что решаете проблему именно в том месте?

— Не усложняете ли вы решение?

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