Мне всегда интересно, как работает какая-то вещь, будь то умные часы, смартфон или Atari 2600. Очень давно, месяца три назад, мне в такси стало интересно: как работает навигатор? Каким образом он прокладывает маршрут? И решил узнать, как эта система работает изнутри на примере одного производителя оборудования и ПО.
Далеко не всегда имеет смысл изобретать велосипед. Так рассудили и в Shturmann и, вместо того чтобы с нуля создавать движок для навигационной программы и рисовать карты, использовали разработки BeNomad и картографию от HERE. В самой же компании разработали информационный контент, интерфейсную библиотеку и построенный на её базе интерфейс пользователя, систему автоматических обновлений для WinCE и прочее. В итоге пользователь получает конечный продукт.
Основной партнер и поставщик контента – Яндекс.Пробки – и именно с получаемыми от него данными приходится проводить множество манипуляций.
Если бы пользователям от навигатора была нужна лишь карта – они бы могли пользоваться и толстым атласом российских дорог. Главное в навигационной программе – это именно прокладка оптимального маршрута. Маршрутизация постоянно и непрерывно оптимизируется и настраивается с целью выдавать каждый раз наиболее близкий к идеальному результат.
Маршрут в онлайн-версии прокладывается с помощью картографии и данных о пробках, которые берутся у Яндекс.Пробок. С первой всё понятно – есть регулярно обновляемая картография HERE. А вот с пробками возникают сложности: они поступают в виде точек с 4-мя основными характеристиками: ID, скорость, направление и цвет. Это множество точек необходимо правильно наложить на карты.
Кроме того, важно как-то запаковать данные, которые поступают от Яндекса, чтобы те распаковывались быстро и без проблем даже на медленных устройствах — метод разработали в Shturmann. Кроме того, они реализовали докачку при обрыве связи.
Кроссплатформенность
На данный момент существуют три коммерческих релиза: для навигаторов на WinCE и две мобильные версии – под Android OS и под iOS. В перспективе – завершение разработки версии под WinPhone. Также существуют десктоп-версии для Windows и Linux, которые используют разработчики. Более того, версия Shturmann под Linux легла в основу совместных проектов с Marussia и Luxoft.
Навигационная программа писалась изначально с таким расчётом, чтобы её легко можно было портировать на любую платформу с нормальным С++ компилятором. На сегодняшний день таковыми являются Android OS, iOS, Mac OS, Linux, WinCE, Windows (desktop).
Таким образом, версии программы под разные платформы развиваются параллельно. Однако в разработке мобильных приложений есть особенности, которые необходимо учитывать при написании версий: например, менеджер карт в навигации Shturmann написан на Java специально под Android.
Пример прокладки маршрута
Тверская, час пик. Можно объехать по переулкам, о которых точно известно, что 5 из них стоят, а о 6-ом данных нет. Но это не значит, что переулок свободен, это может означать недостаток данных: закрытое движение, припаркованные в два ряда машины на узкой улице – любую другую невозможность проезда.
Программа строит маршрут, оказывая предпочтение тем дорогам, о которых информации больше.
Как программа определяет маршрут?
В картографии дороги разделяются на разные категории. Данные о каждой дороге содержат различные показатели, включая среднюю скорость на ней, длину дороги и много другой информации. Если не учитывать пробки, то маршрут прокладывается с учётом средней скорости и с использованием коэффициентов, определяющих тяготение к разным категориям дорог. Эти коэффициенты зависят в том числе от времени года.
Программа работает с цифрами, поэтому, чтобы она строила маршрут, учитывая пробки, ей недостаточно получить данные о пробках, оценённые в баллах (как у Яндекса).
Пробки, поступая в навигацию с сервера, имеют вид дуг – участков дороги. На каждой такой дуге можно определить среднюю скорость движения. Для построения маршрутов (с учетом этих данных) ставятся коэффициенты удлинения дуги. Чем больше загружена дорога, тем сильнее удлиняется дуга. И тем ниже шансы на то, что программа поведет пользователя по пробке.
Допустим, средняя скорость на пресловутой Тверской без пробок составляет 50 км/ч. И вдруг приходит пробка со скоростью 10 км/ч. Означает ли это, что необходимо пропорционально увеличить коэффициент тяготения – в 5 раз? Ответ: нет. Дело в том, что, помимо коэффициентов тяготения существуют коэффициенты, которые применяются в зависимости от трассы, сезонности и многих других факторов.
Безусловно, программа испытывает тяготение к «зелёным» дорогам. Если маршрут проложен из пункта А в пункт Б по двум равноценным дорогам со средней скоростью 50 км/ч, но на одной есть пробка 40 км/ч, а о другой нет информации, то программа поведёт по «пробке», потому что расценит второй вариант как недостаточно достоверный. Хотя в алгоритмах иногда используются и другие коэффициенты.
Разноцветные пробки
Даже при одинаковой скорости на участке цвет может быть различным. Иными словами, 15 км/ч на МКАДе и 15 км/ч в каком-нибудь центральном московском переулке – это две большие разницы. В одном случае пробка будет красная, в другом жёлтая – а всё потому, что используются разные диапазоны скоростей.
Ещё один наглядный пример: строящиеся развязки. Перекрытие дорог учитывают с помощью данных от Яндекса. Бордовый (или коричневый) цвет у Яндекса означает, что дорога «стоит». Программа учитывает цвета дуг и не ведёт пользователя по бордовым, например, маршрутам.
Работать, работать и еще раз работать над маршрутами
Работа над маршрутизацией является регулярной. Во-первых, с каждым обновлением картографии может меняться скорость дорог. Во-вторых, данные от Яндекса также меняют свой диапазон – это необходимо учитывать. И кроме прочего, немалую роль играет сезонность: летом ездить свободнее, тяготение к большим дорогам выше, зимой же навигатор отправляет на объездные пути, о которых водитель может и не догадываться, а затем может начать ими регулярно пользоваться. Если ему понравится.
При прокладке маршрута учитывается множество данных:
— количество левых поворотов;
— количество возможных разворотов (если водитель случайно или намеренно свернул с пути, то программа не станет моментально отправлять его обратно, а перепроложит маршрут, делая езду более спокойной. Особенно это актуально для мегаполисов: развернуться сложнее, чем проехать 500 м до ближайшего светофора);
— количество светофоров и ДТП.
По сути, информация о пробках – это и есть сводные данные, поэтому было решено не перегружать карты и не отвлекать водителей лишней информацией. На карте есть светофоры и сложные развороты, остальное пользователь получает в итоговом формате пробок.
Коэффициенты
Очень интересно, что программа получила возможность машинного обучения на основе предпочтений пользователя: для нахождения оптимальных коэффициентов перехода из скорости пробки в удлинение дуги реализуется клиент-серверное решение, которое анализирует историю маршрутов, получаемую от групп пользователей, и предлагает оптимальный набор коэффициентов для маршрутизации в определённый период времени (день, вечер и т.д.).
Это интересно:
Умный город на Mobile World Congress 2014
Тарифы мобильного интернета без абонентской платы
Автор: ivansychev
