Пользователь
1,3
рейтинг
2 марта 2014 в 11:48

Разработка → Навигация изнутри

Мне всегда интересно, как работает какая-то вещь, будь то умные часы, смартфон или Atari 2600. А вы в курсе, как ваш навигатор прокладывает маршрут? Я решил узнать, как эта система работает изнутри на примере одного производителя оборудования и ПО.

image

Далеко не всегда имеет смысл изобретать велосипед. Так рассудили и в Shturmann и, вместо того чтобы с нуля создавать движок для навигационной программы и рисовать карты, использовали разработки BeNomad и картографию от HERE. В самой же компании разработали информационный контент, интерфейсную библиотеку и построенный на её базе интерфейс пользователя, систему автоматических обновлений для WinCE и прочее. В итоге пользователь получает конечный продукт.

Основной партнер и поставщик контента – Яндекс.Пробки – и именно с получаемыми от него данными приходится проводить множество манипуляций.

Если бы пользователям от навигатора была нужна лишь карта – они бы могли пользоваться и толстым атласом российских дорог. Главное в навигационной программе – это именно прокладка оптимального маршрута. Маршрутизация постоянно и непрерывно оптимизируется и настраивается с целью выдавать каждый раз наиболее близкий к идеальному результат.

Маршрут в онлайн-версии прокладывается с помощью картографии и данных о пробках, которые берутся у Яндекс.Пробок. С первой всё понятно – есть регулярно обновляемая картография HERE. А вот с пробками возникают сложности: они поступают в виде точек с 4-мя основными характеристиками: ID, скорость, направление и цвет. Это множество точек необходимо правильно наложить на карты.

image

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

Кроссплатформенность


На данный момент существуют три коммерческих релиза: для навигаторов на WinCE и две мобильные версии – под Android OS и под iOS. В перспективе – завершение разработки версии под WinPhone. Также существуют десктоп-версии для Windows и Linux, которые используют разработчики. Более того, версия Shturmann под Linux легла в основу совместных проектов с Marussia и Luxoft.

Навигационная программа писалась изначально с таким расчётом, чтобы её легко можно было портировать на любую платформу с нормальным С++ компилятором. На сегодняшний день таковыми являются Android OS, iOS, Mac OS, Linux, WinCE, Windows (desktop).

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

image

Пример прокладки маршрута


Тверская, час пик. Можно объехать по переулкам, о которых точно известно, что 5 из них стоят, а о 6-ом данных нет. Но это не значит, что переулок свободен, это может означать недостаток данных: закрытое движение, припаркованные в два ряда машины на узкой улице – любую другую невозможность проезда.

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

Как программа определяет маршрут?


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

Программа работает с цифрами, поэтому, чтобы она строила маршрут, учитывая пробки, ей недостаточно получить данные о пробках, оценённые в баллах (как у Яндекса).

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

Допустим, средняя скорость на пресловутой Тверской без пробок составляет 50 км/ч. И вдруг приходит пробка со скоростью 10 км/ч. Означает ли это, что необходимо пропорционально увеличить коэффициент тяготения – в 5 раз? Ответ: нет. Дело в том, что, помимо коэффициентов тяготения существуют коэффициенты, которые применяются в зависимости от трассы, сезонности и многих других факторов.

Безусловно, программа испытывает тяготение к «зелёным» дорогам. Если маршрут проложен из пункта А в пункт Б по двум равноценным дорогам со средней скоростью 50 км/ч, но на одной есть пробка 40 км/ч, а о другой нет информации, то программа поведёт по «пробке», потому что расценит второй вариант как недостаточно достоверный. Хотя в алгоритмах иногда используются и другие коэффициенты.

image

image

Разноцветные пробки


Даже при одинаковой скорости на участке цвет может быть различным. Иными словами, 15 км/ч на МКАДе и 15 км/ч в каком-нибудь центральном московском переулке – это две большие разницы. В одном случае пробка будет красная, в другом жёлтая – а всё потому, что используются разные диапазоны скоростей.

Ещё один наглядный пример: строящиеся развязки. Перекрытие дорог учитывают с помощью данных от Яндекса. Бордовый (или коричневый) цвет у Яндекса означает, что дорога «стоит». Программа учитывает цвета дуг и не ведёт пользователя по бордовым, например, маршрутам.

image

Работать, работать и еще раз работать над маршрутами


Работа над маршрутизацией является регулярной. Во-первых, с каждым обновлением картографии может меняться скорость дорог. Во-вторых, данные от Яндекса также меняют свой диапазон – это необходимо учитывать. И кроме прочего, немалую роль играет сезонность: летом ездить свободнее, тяготение к большим дорогам выше, зимой же навигатор отправляет на объездные пути, о которых водитель может и не догадываться, а затем может начать ими регулярно пользоваться. Если ему понравится.

При прокладке маршрута учитывается множество данных:
— количество левых поворотов;
— количество возможных разворотов (если водитель случайно или намеренно свернул с пути, то программа не станет моментально отправлять его обратно, а перепроложит маршрут, делая езду более спокойной. Особенно это актуально для мегаполисов: развернуться сложнее, чем проехать 500 м до ближайшего светофора);
— количество светофоров и ДТП.

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

Коэффициенты


Очень интересно, что программа получила возможность машинного обучения на основе предпочтений пользователя: для нахождения оптимальных коэффициентов перехода из скорости пробки в удлинение дуги реализуется клиент-серверное решение, которое анализирует историю маршрутов, получаемую от групп пользователей, и предлагает оптимальный набор коэффициентов для маршрутизации в определённый период времени (день, вечер и т.д.).

Это интересно:
Умный город на Mobile World Congress 2014
Тарифы мобильного интернета без абонентской платы
Иван Сычев @ivansychev
карма
47,0
рейтинг 1,3
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (6)

  • +8
    Я совсем не догадался, что это рекламная статья
    • +1
      Если вы тоже что-то производите и хотите рассказать об этом — буду рад послушать.
      Вполне возможно, что и об этом можно будет тут написать.

      Можете также заглянуть в другие мои «рекламные» статьи, например:
      История накопителей в рекламе. Часть 1: 1956-1991 годы
      История игровых приставок в рекламе. Часть 1: от Magnavox Odyssey до Super Nintendo
      История игровых приставок в рекламе. Часть 2
      • 0
        Это статья не про то как устроен навигатор, а про рекламный проспект который Вы нашли внутри коробки.

        Вы говорите про " Так рассудили и в Shturmann", и это голословно, т.к. вы не приводите исходного кода, а узнать вы это могли только из первых рук?
        Каждый параграф написан так, как будто вы не исследовали навигатор, а его разработали.
        Вы говорите «В самой же компании разработали информационный контент», откуда Вам это известно, иначе как через инсайд?
        И так в каждом слове. Продолжать?

        К чему это лицемерное «Я решил узнать, как эта система работает изнутри на примере одного производителя оборудования и ПО»?
  • 0
    Да уж. Была бы статья из серии «Что у нас под капотом» (что вполне нормально, например, про трекер в авто), если бы не

    Очень давно, месяца три назад, мне в такси стало интересно: как работает навигатор?

    • 0
      Идея поста действительно возникла в прошлом декабре. И, как ни странно, в такси.
  • 0
    > Я решил узнать, как эта система работает изнутри на примере одного производителя оборудования и ПО.

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

    По статье же: либо пишите про алгоритмы подробнее, либо вообще не упоминайте. Не звучат откровения вида «В одном случае пробка будет красная, в другом жёлтая – а всё потому, что используются разные диапазоны скоростей» — фактуры не хватает. Вы пишите «диапазоны» — хочется уточнить «какие, как они определяются (руками/автоматом), глядя на что, как часто переигрывается разбиение?» И так со всем.

    Тем более что производитель не самый чтобы мейнстримный (более понятный юзкейс — не «купить и юзать, докупая карты и ожидая вылизывания», а «купить девайс и залить в него привычную программу-навигатор»; железо же китайское, обычное), и странно это все в сумме смотрится.

    P.S. Главный-то вопрос так и остался интригой: если там HERE + Яндекс.Пробки, то что мешает взять просто приложения от Яндекса? Прямо у вас там борьба, как одно с другим соместить, так может и не надо?

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