Как навигатор рассчитывает маршруты пользователей
В вопросах навигации человечество проделало большой путь — от ориентирования по памяти, звездам и даже птичьему пению через
Бумажная карта на рулонах соединялась тросиком с механизмом одометра — счетчика пройденного пути. По мере движения такая карта сматывалась с одного рулона на другой:
автомобильные карты до геолокационных сервисов, строящих кратчайший маршрут. Можно сказать, качественная навигация стала одним из важнейших факторов развития мировой экономики, привнеся в ее объем 1,4 триллиона долларов, и 90 процентов из них — с 2010 года.
Мы спросили у команды Яндекс Карт, как строятся маршруты, рисуются пробки и рассчитывается время в пути. Вместе с экспертами разбираемся, почему в высоконагруженных сервисах с большим количеством пользователей классическое машинное обучение зачастую оказывается предпочтительнее нейросетей.
В начале были карты
Очень точные карты. С отмеченными на них домами, реками, мостами, дорогами, перекрестками и тротуарами. Это гигантский, многослойный массив данных, в котором карта дорог — только один из слоев. Формально карта дорог — это граф. Перекрестки в нем — это вершины с точно известными координатами. А дороги, соединяющие перекрестки, — ребра.
Дорожный граф Яндекса содержит около двухсот миллионов ребер. И это не просто огромный набор перекрестков и дорог, а сложная система с множеством атрибутов: массивами координат, длинами магистралей, разрешенными маневрами, скоростями и направлениями движения. Такой объем данных затрудняет работу с графом как с единым целым, требуя значительных ресурсов.
При этом такой граф нельзя один раз построить и забыть. Транспортные системы меняются постоянно: то новую развязку откроют, то на отдельной улице введут одностороннее движение или вовсе «кирпич» повесят.
Для обновления графа используют сразу несколько источников. Во-первых, сами пользователи — а их уже более девяноста миллионов в месяц — сообщают о неточностях в Картах, Навигаторе или веб-сервисе. Обращения сверяют с открытыми источниками: сводками ГИБДД, публикациями на сайтах администраций. Если информация подтверждается, соответствующие изменения вносят в граф.
Кроме того, пользователи делятся с приложением анонимными данными о геопозиции. Эти данные в обобщенном виде обрабатываются алгоритмом — он не фиксирует передвижения каждого пользователя по отдельности, но если видит, что сразу сотни треков отклоняются от ребер графа, то сигнализирует об этом картографам. Картографы проверяют новые сведения, уточняют, изменилась ли схема движения, и вносят обновления в дорожный граф.
Раскраска для автолюбителя
Дорожный граф служит своего рода базой, «эталоном» для построения маршрутов по запросам пользователей. Теперь оценим дорожную ситуацию. Проще говоря, нанесем пробки на разные участки дорог. Здесь есть несколько особенностей.
Обобщенные данные часто содержат погрешности, поэтому напрямую их не используют. Но, сопоставляя их с дорожным графом, система корректирует ошибки. Например, если по координатам машина проехала по крыше дома или через парк, то, скорее всего, дорога проходит рядом и пользователь едет по ней. Аналогично обрабатываются нетипичные замедления: если один водитель притормозил перед поворотом, но большинство других передают данные о свободном проезде, система не учитывает аномалию, чтобы не искажать картину трафика.
Такие анонимные данные собирают в единую картину, которую сравнивают с тем, как разрешено по правилам дорожного движения. Различия в данных о реальном движении и данных графа позволяют делать выводы о пробках. Для пользователей приложений Яндекс Карты и Навигатор такие отклонения отображаются цветами — от зеленого «свободно» до темно-красного «все стоит». И для лучшего понимания дорожной обстановки, помимо цветовой дифференциации, введена и десятибалльная: если «ноль» — дороги свободны, если «десять» — движения почти нет.
Балльная оценка пробок учитывает особенности разных городов: десять баллов в Москве и десять баллов в небольшом регионе — не одно и то же. Чтобы передавать дорожную ситуацию еще понятнее, ввели цветовую градацию: от свободных участков до полностью загруженных. Такой подход отражает локальные особенности трафика и корректно передает ситуацию на дорогах.
Через 300 метров поверните направо
Построение маршрутов в Яндекс Картах проходит в несколько этапов. Пользователь указывает начальную точку и конечную, а далее в дело вступает маршрутизатор. Этот сервис использует усовершенствованную версию алгоритма Эдсгера Дейкстры — классического метода поиска кратчайших путей в графах, разработанного нидерландским ученым еще в 1959 году.
Но в случае с навигацией недостаточно просто рассчитать кратчайший путь по дорогам. Нужно учесть множество других факторов — пользовательские настройки (избегать ли грунтовых дорог, ехать ли по платным) и всю актуальную информацию, использованную прежде для подготовки «эталонного» графа.
В результате в ответ на запрос маршрутизатор строит несколько вариантов маршрутов, и для каждого из них выбирает наиболее быстрый путь.
Прогноз прибытия
Чтобы понять, какой из вариантов пути из пункта А в пункт Б оптимальный, маршрутизатор обращается к другой модели машинного обучения — CatBoost. Работает она так: каждая поездка описывается набором признаков: временем суток, днем недели, типом дороги, средней скоростью в похожих условиях. Эти признаки сопоставляются со временем, которое пользователи тратили на проезд по этому маршруту. Так модель находит закономерности и учится предсказывать, сколько займет дорога в схожей ситуации. Например, запоминает, что по пятницам вечером дороги загружены на выезд из города, а по утрам в будни — в центр на работу.
Больше о CatBoost ↓
CatBoost — алгоритм классического машинного обучения, который позволяет обрабатывать запросы за считаные миллисекунды. Это особенно важно для высоконагруженного сервиса, где скорость работы критична. При этом CatBoost хорош в обработке больших объемов разнородных данных, числовых и нечисловых, без их предварительной подготовки. Поэтому его применяют в Яндекс Картах, Навигаторе и, впрочем, во многих других сервисах компании. А с 2017 года код алгоритма открыт для всех.
Интересно, что CatBoost используется в ЦЕРН на Большом адронном коллайдере. Там этот алгоритм помогает объединять данные с разных участков коллайдера, категоризировать их и анализировать, а на выходе — получать агрегированную информацию о частице.
Когда нужно сделать прогноз, новый маршрут передается в CatBoost тоже как набор признаков. Алгоритм выдает примерное время в пути, которое пользователь видит на карте или в навигаторе.
Уже при движении по маршруту алгоритм каждые пару минут пересматривает свой прогноз. Он учитывает новые треки от других пользователей, сопоставляет их с дорожным графом и пересчитывает время в пути. Если условия маршрута значительно ухудшаются в пути — например, образуются пробки и заторы, — Яндекс Карты предложат другой, оптимальный маршрут с меньшим временем в пути.
Часть факторов нельзя просчитать заранее: аварии, внезапные перекрытия дорог или участки с редким движением, где сложно определить реальную скорость. Все это вносит отклонения в математический прогноз. Однако даже с учетом таких непредсказуемых факторов точность расчета остается высокой — отклонения от реального времени в пути составляют не более 12 процентов.
Кроме того, в некоторых местах GPS работает с перебоями. Впрочем, это не всегда мешает навигации — геолокацию можно уточнить с помощью Wi-Fi, Bluetooth и сотовых вышек. Эта функция позволяет определять координаты пользователя, хотя точность такого определения будет немного меньше.
***
Итак, пройдя несколько вычислительных этапов, запрос пользователя на расчет маршрута из одной точки в другую преобразуется в графическое отображение на экране Яндекс Карт. Человек видит путь, окрашенный в разные цвета в зависимости от затрудненности движения на отдельных его участках, расчетное время в пути и прогнозное время прибытия. Плюс несколько альтернативных вариантов маршрута.
На самом деле работа Яндекс Карт «под капотом» значительно сложнее, чем описано. Это лишь базовые этапы навигации. Фактически в построении маршрутов, составлении карт пробок и расчете времени в пути задействовано несколько вычислительных центров и центров хранения данных. Также используются алгоритмы, которые разбивают одну большую задачу навигации на несколько маленьких и затем распределяют их между центрами в зависимости от загрузки. При этом одни и те же задачи одновременно обрабатываются несколькими центрами — во имя надежности и постоянной доступности сервисов для пользователей.
Реклама: ООО «ЯНДЕКС», ИНН 7736207543. Erid: 2W5zFGsAweY
Технологии IT Партнерский материал
Источник: nplus1.ru
