26.08.2016 07:26
mirage_angerson 91 16100 Источник


В приложении 2ГИС теперь есть навигатор. Мы научились «ехать» по треку, озвучивать манёвры, автоматически перестраивать маршрут, рассчитывать время в пути, доводить пользователя до входа в здание или организацию, учитывая заборы и шлагбаумы, — и всё это в честном офлайне. Пробки (вот разве что для них нужен интернет), разведённые мосты и перекрытые улицы учитываем давно. Пока в нашем навигаторе — необходимый минимум. Чуть позже научим его предупреждать о слишком высокой скорости, лежачих полицейских и камерах ГИБДД, настроим ночной режим, сделаем маршруты по платным и грунтовым дорогам опциональными. Чтобы воспользоваться им, нужно обновить 2ГИС в своем смартфоне или скачать в AppStore или Windows Store. Для Android обновление выходит постепенно, начиная с 22 августа (будет доступно на всю аудиторию к сентябрю).

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

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

Маркер GPS и маршрут


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

В самом простом случае можно отображать позицию устройства на местности, считывая координаты с датчика GPS и размещая маркер в соответствующее место на карте. Уже здесь мы сталкиваемся с первой проблемой — измерительной погрешностью, которая даже в условиях неплохого сигнала вполне может достигать 20–30 метров.

Для ответа на обычный вопрос «Где я нахожусь?» такого способа отображения будет вполне достаточно, особенно если вокруг маркера нарисовать ещё и круг точности с радиусом, равным оценке погрешности. Однако для навигации нужно придумать что-то получше, ведь водителя, движущегося по городской улице, вряд ли устроит маркер GPS, расположенный внутри соседнего дома или, того хуже, на каком-нибудь внутриквартальном проезде.

Решить проблему помогает маршрут, построенный программой до точки назначения и всегда присутствующий в сценарии навигации. При помощи некоторых ухищрений мы можем «притянуть» точку на карте к маршруту, нивелируя некоторую часть измерительной погрешности датчика GPS. В первом приближении притяжку можно рассматривать как проецирование точки на линию маршрута. Рассмотрение же нюансов, а также способов обнаружения схода с маршрута, к сожалению, выходит за рамки данной статьи.

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

Отображение геопозиции во времени


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

1. Самый простой способ заключается в том, чтобы при получении каждого нового отсчёта от датчика тут же выполнять притяжку к маршруту и отображать соответствующее местоположение на карте. Среди достоинств стоит отметить исключительную лёгкость реализации, высокую в некотором смысле точность (ведь здесь мы просто отображаем спутниковые данные, не внося в них каких-либо серьёзных изменений) и минимальную вычислительную трудоёмкость. Главный недостаток в том, что маркер в этом случае не движется по карте в привычном понимании, а «телепортируется» из точки в точку. В основном сценарии навигации камера (виртуальный наблюдатель — термин из области компьютерной графики) привязана к маркеру GPS, поэтому подобные его телепортации приводят к резкому «проматыванию» карты вдоль маршрута и, как следствие, к дезориентации водителя, особенно на высоких скоростях, когда за время между отсчётами геопозиции автомобиль преодолевает значительное расстояние. Наша задача — помочь пользователю, а не сбить его с толку, поэтому указанного изъяна уже достаточно, чтобы исключить данный вариант из рассмотрения.

Единственная возможность избежать дезориентации состоит в том, чтобы перемещать маркер GPS плавно, без «телепортаций», а значит, двигать его нужно существенно чаще, чем приходят отсчёты геопозиции. Чтобы обеспечить такое движение, требуется каким-либо образом вычислять промежуточные точки между реальными отсчётами с датчика и использовать их, пока не будет получен очередной отсчёт. Конкретному подходу к вычислению этих промежуточных точек стоит уделить особое внимание, так как он в конечном итоге сильно повлияет на общую эргономику программы-навигатора.

2. Второй способ отображать местоположение пользователя связан с самым очевидным подходом к генерации промежуточных точек — интерполяции между последними реальными отсчётами GPS. Смысл в том, чтобы двигать маркер от предпоследнего отсчёта к последнему в течение некоторого заданного времени, вычисляя промежуточные точки с требуемой частотой по одной из известных математических функций (простейший вариант — линейная интерполяция). Пользоваться навигатором при таком способе значительно удобнее, но недостатки у него тоже есть.

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

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

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

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

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

Ведение по маршруту с экстраполяцией позиции


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

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

s_i, i\in \mathbb{N} — реальные отсчёты смещения, получаемые притяжкой позиции GPS к линии маршрута;
t_i, i\in \mathbb{N} — время прихода соответствующих отсчётов смещения.
На этом, собственно, список входных данных и заканчивается. Придётся выжимать из них максимум полезной информации.

В конечном итоге нам необходимо построить функцию экстраполяции смещения s=s(t),t \in [t_0; +\infty), которая будет приближена к реальной динамике автомобиля и при этом обеспечит плавность движения маркера GPS по всему нашему маршруту (его длина ни на что не повлияет, так как завершение маршрута обрабатывается отдельно, поэтому условно будем считать маршрут бесконечным). Для обеспечения хорошей визуальной плавности достаточно будет условия гладкости s(t), то есть ни позиция, ни скорость маркера не должны меняться скачком. Другими словами, функция s(t) обязана быть непрерывной вместе со своей первой производной (здесь и далее — по времени) на всей области определения.

Обратим внимание, что каждый реальный отсчёт смещения несёт существенно новую информацию о движении. Например, если в течение длительного времени автомобиль ехал равномерно, а затем стал ускоряться, то «почувствовать» ускорение навигатор сможет только с приходом очередного отсчёта. Так как заглянуть в будущее на сколь угодно длительный срок мы не можем, все поступающие новые отсчёты GPS будут в общем случае изменять поведение искомой функции s(t), что не позволяет задать её одним аналитическим выражением. Вместо этого попытаемся определить функцию кусочно. Для этого решим сперва более простую задачу.

Непосредственная кусочная экстраполяция


Построим такую функцию экстраполяции смещения s_i (t),t\in[t_i;+\infty), чтобы после i-го отсчёта её значения предсказывали реальное расположение пользователя в течение достаточного времени до прихода (i+1)-го отсчёта. Все полезные данные, которыми мы обладаем, — последовательность отсчётов до i-го включительно вместе со временем получения каждого из них.

Вспомнив про конечные разности, отметим, что у нас есть возможность оценить скорость движения автомобиля в i-й момент времени, разделив длину отрезка между последним и предпоследним смещением на соответствующий временной интервал:

v_i\approx \frac{s_i-s_{i-1}}{t_i-t_{i-1}}=s_i{^'} (t_i)

, где v_i — оценка скорости по отсчётам, а s_i{^'} (t_i) — производная экстраполяционной функции s_i (t), которую мы пытаемся построить.

Аналогично для производных более высокого порядка — ускорения, рывка и т.д.:

\left\{\begin{aligned} a_i\approx \frac{v_i-v_{i-1}} {t_i-t_{i-1}} = s_i^{''} \j_i\approx \frac{a_i-a_{i-1}} {t_i-t_{i-1}} = s_i^{'''} \\end{aligned} \right.

Как видно из этих формул, для получения оценки всё более старших производных смещения требуется учитывать всё больше отсчётов, предшествующих текущему: для определения скорости нужны два отсчёта, для ускорения — три, для рывка — четыре и т.д. С одной стороны, чем больше динамических характеристик движения мы будем учитывать в своём прогнозе, тем большую моделирующую способность получим; с другой — полезная информация, содержащаяся во всё более «старых» отсчётах, драматически теряет актуальность. Например, тот факт, что мы ехали со скоростью 30 км/ч минуту назад ничем не поможет нам в текущий момент времени: с тех пор можно было несколько раз разогнаться, затормозить или вообще остановиться. По этой причине оценки всё более старших производных смещения становятся всё дальше от реальности; кроме того, вклад погрешности вычисления некоторой производной в общую аналитическую модель смещения тоже растёт с увеличением порядка этой производной. Раз так, то, начиная с какого-то порядка, динамические характеристики, оценённые при помощи конечных разностей, вместо уточнения будут только портить нашу модель.

По результатам проверок на реальных данных выяснилось, что оценка рывка j_i, особенно в случаях «среднего» качества сигнала GPS, уже достаточно плоха, чтобы от неё было больше вреда, чем пользы. С другой стороны, к счастью, наиболее частые сценарии динамики автомобиля — это покой, равномерное и равнопеременное движение, описываемые полиномиальными уравнениями 0-й, 1-й и 2-й степени от времени соответственно.

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

s_i (t)=s_i+v_i t+\frac12 a_i t^2

Осталось сделать всего один шаг: область определения s_i (t) начинается с момента времени t_i, поэтому время в вычислениях удобнее считать с этого же момента.

В итоге функция примет вид:

s_i (t)=s_i+v_i (t-t_i )+\frac12 a_i (t-t_i )^2,t?[t_i;+\infty)

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

Теперь возьмём несколько реальных отсчётов смещения с устройства и попробуем экстраполировать их на каждом интервале (хотя s_i (t) определена до +\infty, в момент прихода отсчёта t_{i+1} будем сразу переходить к следующей функции s_{i+1} (t), ведь она располагает более свежими данными):



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

Гладкость каждого экстраполяционного полинома s_i (t) прекрасно видна на соответствующем временном интервале, но вот беда — на стыках интервалов общая серая кривая терпит разрывы, подчас весьма заметные.

Назовём величину разрыва в i-й момент времени ошибкой экстраполяции e_i. Действительно, именно это значение показывает, какую неточность имеет каждый наш прогноз к концу его временного интервала. Вычислить значение ошибки можно при помощи следующего выражения:

e_i=s_{i-1} (t_i )-s_i

Увы, свести ошибку к нулю, варьируя сами функции s_i (t), мы никак не можем, ведь это было бы эквивалентно стопроцентной точности видения будущего. Значит, для решения нашей исходной задачи построения единой функции s(t) придётся каким-то образом «склеить» между собой кусочные экстраполяционные полиномы, то есть скорректировать возникающие на стыках ошибки.

Подход к коррекции ошибок


В соответствии с выбранными выше обозначениями можно неформально сказать, что к моменту прихода нового отсчёта s_i мы находимся в точке (s_i+e_i), т.е. сдвинуты относительно реальной позиции на величину погрешности e_i, накопленной к моменту t_i предыдущим экстраполяционным полиномом s_{i-1} (t).

С одной стороны, с точки зрения соответствия выдаваемых пользователю данных реальности, наилучшим способом коррекции ошибки e_i будет разрыв функции s(t) в точку начала следующего полинома s_i, однако мы не можем так поступить, ведь в этом случае снова станем «телепортировать» маркер по карте и дезориентировать водителя.

Очевидно, что если мгновенное изменение значения s(t) недопустимо, коррекция ошибки будет занимать некоторое ненулевое время. Также понятно, что коррекцию ошибки желательно завершить до прихода следующего отсчёта, дабы не допустить накопления ошибки.

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

Если снова говорить неформальным языком, для коррекции ошибки требуется из точки (t_i;s_i+e_i) за время T плавно «вернуться» на следующий экстраполяционный полином — кривую s_i (t).

Для описания процесса коррекции ошибки удобно ввести отдельные функции коррекции e_i (t) таким образом, чтобы в момент времени t_i соответствующая функция коррекции принимала значение e_i, а начиная с момента (t_i+T) становилась равна нулю:

\left\{ \begin{array}{lcl} e_i (t_i )=e_i\e_i (t)=0,t\in[t_i+T,\infty)\\end{array} \right.

Если сложить такую функцию коррекции с соответствующим интерполяционным полиномом, то в ключевых точках t_i и (t_i+T) мы обеспечим коррекцию ошибки смещения:

\left\{ \begin{array}{lcl} s_{i-1} (t_i)+ e_i(t_i)=s_i(t_i)\s_i(t_i+T) + e_i(t_i+T)=s_i(t_i+T)\\end{array} \right.

Назовём скорректированной функцией смещения r_i (t) сумму экстраполяционного полинома и соответствующей функции коррекции:

r_i (t)=s_i (t)+e_i (t)

Заметим, что благодаря описанным выше свойствам функций коррекции мы получили очень важное свойство функций r_i (t) — они уже «сшиты по смещению», т.е. не терпят разрывов в точках t_i:

r_i (t_i )=r_{i-1} (t_i )

Совокупность скорректированных функций r_i (t) могла бы претендовать на роль искомой модели смещения s(t), определённой во все моменты времени, если бы не одно обстоятельство: несмотря на отсутствие разрывов смещения в точках t_i, производные этой совокупности функций в общем случае всё ещё рвутся.

Конкретно нас интересует разрыв первой производной — скорости, потому что исходные требования содержат условие повсеместной гладкости s(t), т.е. условие повсеместной непрерывности скорости. С учётом этого необходимо расширить требования к функциям коррекции e_i (t), чтобы «сшить» ещё и производные скорректированных функций r_i (t):

r_i^{'} (t_i )=r_{i-1}^{'} (t_i )

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

s_i^{'} (t_i)+e_i^{'} (t_i )=s_{i-1}^{'} (t_i )+e_{i-1}^{'} (t_i )

Ранее мы упоминали о том, что после истечения времени коррекции T функция коррекции принимает нулевые значения. Добавим ещё одно требование к функции коррекции — пусть её производная после истечения времени коррекции также принимает нулевые значения:

e_i^{'} (t)=0,t\in[t_i+T,\infty)

Тогда, в предположении, что время коррекции всегда меньше интервала между отсчётами, можно считать, что производная i-й функции коррекции к моменту прихода следующего отсчёта t_{i+1} уже обратится в ноль. Тогда, возвращаясь к условию гладкости, получим:

s_i^{'} (t_i )+e_i^{'} (t_i )=s_{i-1}^{'} (t_i )+0

Выразим отсюда e_i^{'} (t_i ):

e_i^{'} (t_i )=s_{i-1}^{'} (t_i )-s_i^{'} (t_i )


Заметим, что s_i^{'} (t_i ) представляет собой оценку скорости, сделанную при помощи конечных разностей, подставим её:

e_i^{'} (t_i )=s_{i-1}^{'} (t_i )-v_i

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

\left\{ \begin{array}{lcl} e_i(t_i) = e_i\e_i^{'}(t_i) = s_{i-1}^{'}(t_i)-v_i\e_i(t_i) = 0, t\in[t_i+T,+\infty] \e_i^{'}(t_i) = 0, t\in[t_i+T,+\infty] \\end{array} \right.

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


Выбор функции коррекции ошибок


Стоит отметить, что получить единое аналитическое выражение для функций коррекции e_i (t), в точности удовлетворяющее вышеуказанным четырём условиям, очень сложно. Проблема заключается в той части области определения, которая идёт после истечения времени коррекции T, — нужно добиться нулевых значений функции и её производной на всём остатке числовой оси. Для упрощения задачи сократим область определения искомого аналитического выражения функции коррекции до интервала коррекции [t_i,t_i+T), а после верхней его границы будем считать значение функции и её производной тривиально нулевым (благо, на уровне программного кода у нас есть такая возможность из-за наличия ветвлений).

Формально с учётом этого приёма функция коррекции кусочной — некоторое выражение для интервала коррекции и константа 0 далее, однако при соблюдении граничных условий в точке (t?_i+T) не будет разрыва ни самой функции коррекции, ни её первой производной. Так как разрывы более старших производных нас не интересуют (они не испортят гладкости искомой функции s(t)), в дальнейшем не будем упоминать о нулевом «хвосте» функции коррекции, а граничные условия переформулируем в более удобном виде:

\left\{ \begin{array}{lcl} e_i(t_i) = e_i\e_i^{'}(t_i) = s_{i-1}^{'}(t_i)-v_i\e_i(t_i+T) = 0\e_i^{'}(t_i+T) = 0\\end{array} \right.

Обозначим ошибку экстраполяции скорости через ?_i=s_{i-1}^{'}(t_i)-v_i:

\left\{ \begin{array}{lcl} e_i(t_i) = e_i\e_i^{'}(t_i) = \varepsilon_i\e_i(t_i+T) = 0\e_i^{'}(t_i+T) = 0\\end{array} \right.

Теперь нужно определить аналитическое выражение для e_i (t). В связи с эргономическими требованиями к программе, помимо граничных условий, нужно, чтобы функция коррекции имела как можно меньше экстремумов и перегибов на интервале коррекции — чтобы маркер GPS «не дёргался».

Самой простой функцией, подходящей под эти требования, опять является полином — полином минимально возможной степени от времени t (теоретически, сходными характеристиками среди элементарных функций обладает ещё и, например, синус, но вычислять его значение накладнее с точки зрения процессорного времени).

Так как граничные условия представляют собой систему из четырёх нетривиальных уравнений, то минимальной степенью полинома, обеспечивающей достаточную параметризацию функции коррекции, является третья. Учитывая то, что при построении аналитического выражения для e_i (t) удобнее считать время с момента i-го отсчёта (ровно так же, как и в определении s_i (t)), нужный полином примет следующий вид:

e_i (t)=C_3 ?(t-t_i)?^3+C_2 ?(t-t_i)?^2+C_1 (t-t_i )+C_0

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

\left\{ \begin{array}{lcl} C_3 = \frac {\varepsilon_iT + 2e_i} {T^3} \C_2 = - \frac {2\varepsilon_iT + 2e_i} {T^3} \C_1 = \varepsilon_i \C_0 = e_i \\end{array} \right.

В итоге, если определить функции коррекции e_i (t) описанным образом, то скорректированные функции r_i (t) сливаются в единую функцию экстраполяции s(t), гладкую во все моменты времени. Полное выражение для s(t) приводить не будем в силу его громоздкости.

Примечание: последняя неточность осталась в допущении при выборе времени коррекции T — наши рассуждения строились в свете условия, что T всегда будет меньше интервала между отсчётами:

(\forall i \in \mathbb{N})(T<t_i-t_{i-1})

Приятной особенностью построенной модели s(t) является то, что нам достаточно выбрать T таким образом, чтобы оно не превышало среднего времени между отсчётами: в случае, если отдельные интервалы (t_i-t_{i-1}) будут меньше T, то часть ошибки, которую мы не успели докорректировать на слишком коротком интервале, будет скорректирована на одном из следующих. Для этого достаточно будет вычислять ошибку экстраполяции не по обычной экстраполяционной функции s_i (t), а по скорректированной r_i (t):

e_i=r_{i-1} (t_i )-s_i

На рисунке ниже изображён пример графика итоговой функции экстраполяции s(t), построенный по реальным данным:



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

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

Адаптация математической модели к реальным условиям


Запрет движения маркера в обратном направлении


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

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

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

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

Раз так, то обеспечить неубывание экстраполированного смещения будет нетрудно: достаточно сравнить новое полученное значение с предыдущим, и если текущее окажется меньше, то подменить его предыдущим. Несмотря на кажущуюся грубость этого приёма, гладкости функции экстраполяции мы не нарушим, ведь, для того чтобы начать двигаться назад по гладкой функции, нужно сначала полностью остановиться.
В будущем режим работы, когда мы подменяем математически корректные значения s(t) более старыми, чтобы не допустить движения назад, будем называть режимом принудительной остановки.

Слишком большие ошибки экстраполяции и слишком долгие интервалы между отсчётами


Несмотря на то, что мы построили в некотором смысле качественную функцию s(t), иногда ошибки экстраполяции могут достичь недопустимых величин. В этих случаях программа должна прекратить попытки скорректировать ошибки штатными средствами. Ещё одна ситуация, когда экстраполированные данные теряют актуальность, возникает, если новый отсчёт смещения по какой-либо причине не приходит слишком долго — моделирующая способность s(t) драматически падает с момента получения последнего отсчёта. Чтобы не перейти грань между попытками прогнозирования и бессовестной ложью, полагаться на модель обычно стоит не дольше трёх секунд.

Для простоты назовём первую негативную ситуацию некорректируемой ошибкой смещения, а вторую — некорректируемой ошибкой времени.

Работать с каждым из этих видов ошибок мы можем двумя способами:
  • Входить в упомянутый выше режим принудительной остановки. Достоинство этого подхода — в сохранении плавности движения маркера геопозиции по карте местности. Однако чем дольше мы находимся в режиме принудительной остановки, тем хуже мы информируем пользователя о его реальном местоположении;
  • Мгновенно телепортировать маркер GPS на место последнего отсчёта. Здесь мы, наоборот, жертвуем эргономикой ради достоверности информации, подаваемой пользователю.

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

Затянувшийся режим принудительной остановки


Любой вход в режим принудительной остановки сопряжён с выдачей менее точных данных о местоположении в угоду запрету обратного движения маркера GPS. Чтобы не дезинформировать пользователя в особо неблагоприятных случаях, наша модель дополнительно наделена возможностью прерывать режим принудительной остановки «телепортацией» маркера на последнее реальное положение по истечении заданного промежутка времени, вне зависимости от причины входа в режим (математический результат экстраполяции или некорректируемые ошибки смещения/времени). В этот момент даже плавность движений приходится принести в жертву ради «остатков» точности.

Выводы


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

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

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

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


  1. Loki3000
    26.08.2016 10:57
    #9773174

    А появится ли навигатор на десктопной версии?


    1. Fullmoon
      26.08.2016 14:22
      #9773810
      +1

      Присоединюсь к вопросу.
      И заодно, как обстоит дело с десктопной версией под Мак? Последнее обновление, если не ошибаюсь, было в марте прошлого года.


      1. fuCtor
        26.08.2016 15:38
        #9774060

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


    1. mrmixsun
      26.08.2016 15:17
      #9773986
      +1

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

      А какой сценарий использования навигатора на десктопе возможен? Поставить ноутбук на пассажирское кресло?


      1. Loki3000
        26.08.2016 16:15
        #9774162
        +1

        А какой сценарий использования навигатора на десктопе возможен?

        CarPC на базе x86 архитектуры.


    1. barsulka
      26.08.2016 16:28
      #9774182
      +1

      Помимо того, что к ноутбуку должна прилагаться жена, которая его будет держать под удобным углом, еще нужно будет купить gps-модуль. Ибо, например, Яндекс.Маркет прямо сейчас предлагает всего 7 ноутов с предустановленным GPS, один из которых — полупланшет :)

      Безусловно, есть еще Car PC на x86, но сколько их у людей? И сколько их будет в будущем с учётом грядущих автомобильных ОС от гугла и эппла?

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


      1. Loki3000
        26.08.2016 16:35
        #9774208

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


        1. barsulka
          26.08.2016 16:38
          #9774218

          и слежение за местоположением по GPS

          Ого. Вот, что значит юзать 5 лет исключительно онлайн и мобильную, спасибо.


        1. ittakir
          26.08.2016 16:47
          #9774236

          Десктопная версия родом из начала 2000х. Тогда смартфонов не было, и одним из способов навигации по городу был как раз ноутбук с внешним GPS. Сам так ездил.


          1. nick_volynkin
            27.08.2016 09:10
            #9775090

            Я как-то раз так ездил штурманом: ноутбук и десктопный 2гис на нём, выдавал водителю голосовые инструкции. Но GPS не было, сам считал кварталы и повороты.


  1. xtelekom
    26.08.2016 11:05
    #9773196

    Несколько раз ставил себе 2гис и удалял именно из-за отсутствия нормального навигатора. Буду пробовать.


    1. SuhoffGV
      26.08.2016 14:22
      #9773816

      Смысл пробовать появится когда у них будут карты уровня OSM или Навитела. С мелкими городами и дорогами. Пока это все полумеры. И приходится держать на смарте Навител и 2Gis. Брать из 2Gis адрес и ехать к нему по навителу.


      1. mrmixsun
        26.08.2016 15:15
        #9773978

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

        По поводу глобальной карты — функционал уже в разработке. Будет покрытие карты вообще везде, где есть, например, OSM.


        1. fuCtor
          26.08.2016 15:35
          #9774050

          Скорее всего вы вот про это http://job.2gis.ru/vacancy/novosibirsk/id/1476/? Ну и другеи вакансии по этому проекту.


        1. SuhoffGV
          26.08.2016 15:59
          #9774126

          Да, предупреждения о лежачих полицейских лучше сделать отключаемыми. Я поездил с навителом и скином NewNavitel — уведомления о лежачих полицейских отключил очень быстро.
          А вот если запилите функционал аналогичный NewNavitel будет отлично. Можно будет подумать и об отказе от навитела.


  1. mihmig
    26.08.2016 11:21
    #9773258
    +5

    С каждым релизом программа всё «тяжелее» — я понимаю, что функционал растёт, как и мощность смартфонов. Но как быть тому проценту пользователей, у которых «старые» смартфоны? Может возможно сделать лайт-версию программы?


    1. Andrey_Epifantsev
      26.08.2016 14:22
      #9773812
      +2

      Я тоже за лайт версию. А то у меня на смартфоне запуск 2гис занимает 3 минуты. И переход от экрана к экрану тоже не быстрый.


      1. Akr0n
        27.08.2016 03:57
        #9775004

        А что за смартфон и город? Список охраненных маршрутов не пробовали чистить? У меня из-за него были жуткие тормоза в Москве.


    1. SyrexS
      26.08.2016 14:22
      #9773814
      +1

      Или выпускать программу модулями — по принципу больших компаний?


    1. mrmixsun
      26.08.2016 15:09
      #9773966

      Мы много работаем над производительностью приложения. Бета-тестировщики, которые пару месяцев пользуются 2ГИС v4, заметили серьёзный рост производительности в последних релизах. Если у вас Андроид, то дождитесь обновления на v4, и проверьте — время запуска должно быть в пределах 2-3 секунд для популярных девайсов или 6-7 секунд для самых «старых», на которых мы тестировали.


      1. mihmig
        26.08.2016 15:20
        #9774000

        Спасибо за надежду.
        Но мы с Andrey_Epifantsev и SyrexS спрашивали насчёт кардинального «улучшения» программы — путём выпуска облегчённой версии (с функционалом 3-х летней давности — поиск по адресам и маршруты городского транспорта). Тогда она работала на одноядерном ARMv6 (да-да, эти телефоны всё ещё есть и работают).


      1. somniator
        26.08.2016 15:26
        #9774022

        Только что запустил на Nexus 5 — зпуск 19 секунд. Nexus 9 — 14 секунд. Последняя бета с Google Play. Аппараты, конечно, не новые, но я бы не назвал их старее тех самых старых, на которых вы тестировали.


  1. Mart_Slaaf
    26.08.2016 11:36
    #9773310
    +2

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


    1. Lamaster
      26.08.2016 13:58
      #9773742

      Встаёт вопрос «Что брать за нулевую скорость» измеряя данные акселерометра. Хотя секунду подумав я решил, что за нулевую скорость можно брать данные акселерометра в момент, когда данные GPS не сдвинулись с места.
      Но если автомобиль двигается продолжительное время, то вес поправки координаты по данным акселерометра надо снижать.
      То есть через 30 минут после старта данные акселерометра не будут использоваться вообще.


      1. Mart_Slaaf
        26.08.2016 14:07
        #9773770

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


        1. mmlevin
          26.08.2016 14:22
          #9773818

          Кстати, да. Штатная навигационная система той же Toyota использует показания с GPS (это используется в 2ГИС сейчас), акселерометра (это доступно на смартфонах), и датчика скорости автомобиля. Пока, к сожалению, ни один из известных мне навигаторов для смартфона не использует данные с акселерометра. Если это не так, прошу поправить.


        1. Dolbe
          27.08.2016 20:37
          #9775560

          Именно такая мысль не покидает меня уже пару лет, как снова сел за руль. И правда, почему не считывать данные с акселерометра и гироскопа внутри телефона/планшета/навигатора? Ведь при временном ухудшении сигнала GPS можно и правда корректировать положение маркера на карте, основываясь на данных с этих датчиков. Даже была где-то статья, что кто-то нечто подобное разрабатывает (поправьте меня, если неправ, но вроде даже на Хабре она была).


    1. ittakir
      26.08.2016 15:29
      #9774030
      +1

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


      1. Skerrigan
        26.08.2016 17:03
        #9774278

        тогда прикрутить тумблер ручного включения, как опции для повышения качества?


    1. mirage_angerson
      27.08.2016 05:31
      #9775028

      Мы размышляли об идее использования акселерометров.
      Хоть как-то позиционирование с учётом данных акселерометра будет работать только в идеальных условиях (если точность показателей хорошая), а сам аппарат закреплён.

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


  1. Ti_webdev
    26.08.2016 11:48
    #9773362
    +1

    Знаки / дорожную разметку знает?


    1. mrmixsun
      26.08.2016 15:03
      #9773956
      +1

      Знаки знает, дорожную разметку учитывает при построении маршрута (например, не прокладывает маршрут по дорогам с односторонним движением против направления движения), но не показывает. В ближайших планах — добавить отображение разметки («перестройтесь в крайний левый ряд») и информации о лежачих полицейских и камерах.


    1. pashuk
      26.08.2016 18:58
      #9774498

      А навигатор вообще можно реализовать без этих знаний?


  1. VladimirAndreev
    26.08.2016 11:49
    #9773372
    +1

    надо будет попробовать.
    а нет ли в планах, если пользователь двигается в тоннеле, GPS там нет, перекидывать не на последнее известное реальное место, а на выезд из тоннеля?
    например, в Лефортовском тонне гуглокарты в какой-то момент отбрасывают в начало тоннеля, что несколько раздражает, я ведь с вероятностью 99+% выеду из тоннеля, а не сдам назад…


    1. martin_wanderer
      26.08.2016 12:23
      #9773458

      Давно волнует этот же вопрос про тоннели. В идеале в инфрастуктуру тоннеля должны входить этакие WiFi-пикеты для определения положения.


    1. DC88
      26.08.2016 12:27
      #9773468

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


      1. VladimirAndreev
        26.08.2016 14:59
        #9773942

        ну, не знаю… может, это особенность Asus Zenfone2, но с включенным WiFi, AGPS, ГЛОНАСС и всем-всем — примерно в середине длинной ветки тоннеля — перелетает в его начало…


    1. ittakir
      26.08.2016 15:35
      #9774052

      Судя по данной статье, вас будет плавно вести вдоль маршрута по тоннелю с той скорость, с которой вы въехали в тоннель (если конечно просто не спрячет маркер, когда GPS отвалится)


  1. guyfawkes
    26.08.2016 12:25
    #9773464

    А можете подробнее пояснить, как вы решали систему относительно констант? Не смог понять уже начиная с расчета C1 — ведь там везде получаем вычитание ti из него же.


    1. mirage_angerson
      27.08.2016 07:15
      #9775042
      +1

      Пожалуйста:


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


      1. guyfawkes
        27.08.2016 09:30
        #9775114

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


    1. mirage_angerson
      27.08.2016 07:16
      #9775044

      Пожалуйста:


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


  1. IronHead
    26.08.2016 14:23
    #9773820

    А поддержка областей между городами не планируется? Хотя бы на не масштабной обзорной карте. А то бывает выехал чуть за карту, включил 2gis, а оно тебе: к сожалению, мы не можем вас найти…


    1. mrmixsun
      26.08.2016 15:01
      #9773952

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


  1. Bedal
    26.08.2016 14:23
    #9773822
    -2

    А в чём преимущество перед прочими навигационными программами, которых — легион?
    И — в условиях, когда даже навител деградирует и, похоже, умрёт, в борьбе с монополистами картовых сервисов — какие шансы на выживание двагиса?


    1. VladimirAndreev
      26.08.2016 15:01
      #9773948
      +2

      навител умирает потому, что предлагает тоже самое, но за деньги… причем задорого.


      1. Ryav
        26.08.2016 16:57
        #9774266

        На самом деле далеко не то же самое, чего стоит только «показать вход» и навигация внутри крупных торговых центрах у 2ГИС.


      1. Bedal
        26.08.2016 17:04
        #9774284

        Насчёт навитела Вы вряд ли правы, но речь не о них, я просто иллюстративно упомянул.

        В общем, вопрос был не о о том.


    1. mrmixsun
      26.08.2016 15:22
      #9774008
      +1

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

      По поводу выживания. Ведение с голосовыми подсказками — вполне логичный путь развития сервиса, связанного с поиском организаций. Иначе говоря, мы не выпускали ещё один навигатор — мы сделали 2ГИС ещё удобнее.


    1. ProLimit
      26.08.2016 18:24
      #9774452

      Им требуется интернет — видимо, в этом преимущество. Но есть и ещё одно — так как поиск организаций в 2ГИС сделан неплохо и база хорошая, свою нишу они занимают и пользователи есть. А функция прокладки маршрута — полезный довесок, чтобы не переходить в другую программу для навигации и не вбивать там нужный адрес.

      Главное, чтобы удобный справочник не превратился в неповоротливого монтсра «все в одном», что нередко происходит с популярными программами.


  1. Camellan
    26.08.2016 14:23
    #9773824

    Для Blackberry OS10 будет новая версия?


  1. eBuster
    26.08.2016 15:39
    #9774068

    Вот бы OSM тоже сделал перемещение плавным, цены б ему не было! И так нет, но не было бы ещё больше.


    1. mobilz
      26.08.2016 15:45
      #9774088

      wat? И давно вам OSM делает перемещение? ))))


      1. eBuster
        26.08.2016 19:10
        #9774522

        Карта по экрану перемещается (или курсор по карте, смотря где наблюдатель) дискретно во время движения, а хочется плавно. Как в гуглокартах, например. В чём вопрос состоит, где wat?

        Если что, то имелся ввиду конечно же андроидный OSM&MAPS.


  1. ittakir
    26.08.2016 15:57
    #9774118

    Вот что меня больше всего напрягает в навигаторе (любом), так это огромная стрелка своего местоположения и неочевидность, где я сейчас относительно этой стрелки — на кончике острия, в середине или в конце.
    Особенно это досаждает, когда карта на приличном удалении так, что размер стрелки в несколько раз больше толщины дорог. Маршрут не построен. Я быстро еду по главной дороге и хочу свернуть на одну из второстепенных дорог. И тут начинается: «я уже проехал поворот или еще нет?».

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


    1. vics001
      26.08.2016 18:58
      #9774500
      +1

      С интерполяцией местоположения об этом можно забыть так как это будет всегда гадание.


      1. ittakir
        26.08.2016 19:33
        #9774548

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


        1. vics001
          27.08.2016 00:44
          #9774896

          Мы в OsmAnd делаем по центру стрелки, но с другой стороны, не все ли равно? В режиме навигации всегда стрелка притягивается к самому маршруту сначала, а потом рисуется, поэтому проблема поворота всегда есть. (Проблема поворота: гадание приложения уже повернул автомобиль на соседнюю улицу справа по маршруту после светофора или нет, так как GPS может скакать и давать погрешность до 10-20 метров, что достаточно много).


          1. ittakir
            27.08.2016 04:45
            #9775016

            Обычно все-таки на современном телефоне с GPS+Глонасс приемником позиция определяется довольно точно, +- пара метров.
            А вот стрелка на карте имеет физический размер метров 100, на типичном зуме, когда едешь на авто.


    1. mirage_angerson
      27.08.2016 06:10
      #9775036

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

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


  1. vics001
    26.08.2016 19:03
    #9774514

    Есть несколько замечаний:
    1) Почему нет такого очевидного ограничения как то, что точка не должна двигаться назад. Это же полный бред в физическом мире, если ты едишь вперед а точки прилетают назад (т.е. водитель резко сбросил скорость, а алгоритм продолжил вперед). У вас судя по графику такое вполне возможно.
    2) Непонятно зачем нужна непрерывность первой производной. Скорость меняется скачкообразно даже в реальном мире и в этом не возникает проблем.
    3) Почему нельзя взять алгоритм адаптивного приближения, наподобие функции Калмана?


    1. vics001
      26.08.2016 19:08
      #9774520

      4) Наверное я что-то пропустил, но тут хорошо описан алгоритм для одномерной функции, в то же время как задача двумерная. А может даже и 3х мерная так как нам надо экстраполировать 3 параметра, x, y, и направление движения. Каждый из них вносит свои погрешности. Может у вас есть ссылка на сам алгоритм, а то из 1-мерной экстраполяции непонятно как это все вместе будет работать?


      1. ittakir
        26.08.2016 19:27
        #9774534

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


      1. mirage_angerson
        27.08.2016 05:26
        #9775024

        Почитайте пожалуйста статью внимательно.
        Задача решается в одномерном пространстве маршрута.

        Как показала практика, этого вполне достаточно, и даже на поворотах проблем не возникает.


    1. mirage_angerson
      27.08.2016 05:43
      #9775030

      1) Ограничение движения назад у нас есть, почитайте внимательнее. Но оно работает не всё время. Если мы сильно проэкстраполировали вперёд, а в течении некоторого промежутка времени новые позиции поступают позади, то мы «телепортируемся».
      2) Без непрерывности первой производной заметны рывки в движении маркера.
      3) Такой способ не очень хорош, даёт большую задержку.


      1. vics001
        27.08.2016 16:52
        #9775466

        Прочитал, по 1-2
        >> достаточно сравнить новое полученное значение с предыдущим, и если текущее окажется меньше, то подменить его предыдущим. Несмотря на кажущуюся грубость этого приёма, гладкости функции экстраполяции мы не нарушим, ведь, для того чтобы начать двигаться назад по гладкой функции, нужно сначала полностью остановиться.
        — 1) Как раз здесь и нарушится непрерывность производной, которую вы хотели сделать непрерывной.
        2) Если человек двигался все время 40кмч и за 1 секунду сбросил скорость с 40кмч до 0кмч перед светофором. то обеспечивая непрерывность первой производной, вы перенесете человека гораздо дальше за светофор, чем нужно было.
        Желание, чтобы скорость движения маркера была непрерывной, возможно похвально и рисует хорошие графики, но надо не забывать, что в реальном мире человек вообще-то не видит скорость непрерывной. К примеру, в фильме с автомобилем достаточная плавность обеспечивается 24 кадрами в секунду и скорость абсолютно точной не является непрерывной, хотя бы потому что у нас дискретное наблюдение. В телефоне точно так же есть частота обновления экрана.
        Опять же не занудствую, но мне кажется непрерывность скорости придает искусственность картинке, хотя в данной задаче реализм может быть важнее. Хорошо было бы сравнить два алгоритма в реальной жизни, а не по графикам.


        1. mirage_angerson
          28.08.2016 06:52
          #9775854

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


  1. SpiritOfVox
    27.08.2016 13:32
    #9775308

    Вы не планируете учитывать данные от obd2 сканнеров?


  1. mirsev
    27.08.2016 15:36
    #9775420

    1. Странно, что для определения скорости используются только координаты и время соседних отсчётов. Почему не использовать о скорости с GPS. Там скорость определяется довольно точно, и в случае передачи данных по протоколу NMEA должна быть доступна приложениям.

    2. Повторю вопрос из этого комментария: почему не использовать оценку с ограничениями, как в фильтрах Калмана? Там для сглаживания флуктуаций из-за ошибок вводятся ограничения, согласно физической модели объекта, например, органичения по скорости и ускорению.


    1. mirage_angerson
      27.08.2016 15:44
      #9775426

      По поводу скорости с GPS — на самом деле она используется. Производится комплементарная фильтрация от двух источников — скорости с GPS и описанной в статье скорости по отсчётам.

      Сами по себе фильтры Калмана исследовались, но они вносили слишком большую «инертность», модель тяготела к устаревшим данным, что было более вредно, нежели ситуативные выбросы. А борьбу с этими самыми выбросами решено было вести при помощи фильтрации сырых данных с GPS, соответствующие алгоритмы находятся в разработке.


  1. RingoAl
    27.08.2016 20:37
    #9775582

    Ездил несколько дней с навигатором.
    Притягивание к маршруту не работает корректно.
    Периодически перекидывает на пересекаемую улицу при остановке на перекрестке.
    При езде по прямой тоже может перекинуть на перпендикулярную улицу при смещении фактического трека влево/вправо от маршрута.
    Причем все это вызывает цепочку «вы ушли с маршрута» -> «маршрут построен» -> «поверните/развернитесь» и т.д.
    При движении по улицам с плотной застройкой может откинуть во дворы со всеми вытекающими.


    1. mirage_angerson
      28.08.2016 07:11
      #9775858

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

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


      1. RingoAl
        28.08.2016 13:07
        #9776012

        Проблему с перекрестком вы не поняли.
        Я в Google Plus подробнее описывал.
        Маршрут нарисован красным. Движение маркера — зеленым. В момент пересечения маркером Егоршинского проезда — я для 2GIS окажусь на нем и маршрут перестроится.
        image
        Аналогично при остановках. Перекидывает на улицу перпендикулярную маршруту.


  1. Nekitos
    27.08.2016 22:10
    #9775706

    Вроде бы не было такого вопроса. А планируется ли введение фичи указывать промежуточные стопы? Что в гугл-картах, что в яндекс-картах, в приложениях не поддерживается. Сейчас посмотрел бету 2гис и там тоже оказывается нету. Хотелось бы очень.


    1. mirage_angerson
      28.08.2016 07:16
      #9775860

      Да, подобное в планах есть.


  1. Diokuz
    28.08.2016 11:27
    #9775932

    Используется ли в процессе экстраполяции гироскоп и компас? И если нет, то почему? Казалось бы, данных от них «в моменте» намного больше и они гораздо важнее точек от GPS из прошлого, необходимых для расчёта производных.


    1. IronHead
      01.09.2016 15:34
      #9783522

      У меня вот нет на моем телефоне компаса, зато 2gis работает,
      телефон менять не собираюсь, андроид 4.2 и акб на 5000 мА/ч полностью устраивает
      а вот всякие VR не работают и даже не запускаются, ругаются на отсутствие компаса, поэтому я ими не пользуюсь.
      Так что все правильно делают, ибо не существует стандартов, что в каждом телефоне должен быть компас, а терять из за этого пользователей отличной программы — было бы глупо.


      1. ArtRoman
        01.09.2016 20:24
        #9784290

        Так понятно, что не надо запрещать установку приложения на телефоны без компаса. Но список датчиков можно получить и наличии компаса вполне логично его использовать, потому что при потере GPS (в тех же туннелях) это позволит лучше «угадывать» текущее местоположение.


        1. mirage_angerson
          05.09.2016 08:28
          #9788308

          Использование гироскопов и акселерометров при потере GPS — один из возможных этапов дальнейшего развития.


  1. insomnium1
    29.08.2016 15:26
    #9777438
    -1

    Наконец то! Наконец то можно удалить навигатор от яндекса! Спасители вы наши!


    1. Seekeer
      31.08.2016 09:15
      #9780108
      +1

      А в чём преимущество 2ГИС перед ним?
      Расскажите, может я тоже пересяду:)


      1. yetanothercoder
        31.08.2016 09:32
        #9780126

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


      1. insomnium1
        01.09.2016 13:31
        #9783164

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


  1. DimonSmart
    30.08.2016 12:49
    #9778732

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


    1. Skerrigan
      31.08.2016 04:53
      #9779976

      На правах дилетанта: чтобы собрать телеметрию «дыры в полотне», в нее нужно все же въехать — мало кто осознанно будет бить свою машину,


      1. DimonSmart
        31.08.2016 07:50
        #9780020

        В ямы не только въезжают но их ещё и объезжают. А сам факт объезда небольшого препятствия — это уже явный паттерн на акселерометрах. Если успростить — то на ровной дороге резкие ускорения куда либо это редкость. На дороге из гравия машину будет изрядно трясти, при объезде препятствия будет большее (по сравнению с просто камушком под колесом) по продолжительности ускорение в одну а потом в другую сторону. И конечно же всё это нужно приправить статистикой. А судя по количеству формул в статье — с этим в 2гис всё очень неплохо.


        1. Skerrigan
          31.08.2016 08:49
          #9780082
          +1

          Блин, а знаете, ваша идея уже мне не кажется такой дикой и в этом что-то есть. Как минимум вы правы в том, что есть и другие косвенные признаки. Если задача их «выловить из общего шума показаний» выполнима, то над этим стоит крепко задуматься.
          P.S. Спасибо за интересные идеи.


        1. ArtRoman
          01.09.2016 20:28
          #9784294

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


    1. mirage_angerson
      05.09.2016 08:18
      #9788302

      Сама по себе мысль хороша, но вычленить полезную информацию из всех показаний на первый взгляд маловозможно. Да и потом, телефон же не всегда жёстко лежит на приборной панели или закреплен в держателе — придётся как-то отметать ложные «ямы» от взятия телефона в руки, например. А ещё у разных автомобилей разные системы амортизации, жёсткость подвески и т.д. — всё это тоже будет влиять на показания акселерометров.


  1. webkumo
    31.08.2016 20:41
    #9781796

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

    PS пользуюсь с «заветных времён» (года этак с 2007го кажется) и большую часть доволен… но для меня дубльгис всегда был удобным справочником с хорошей картой… очень хочется надеяться, что и дальше не придётся с него уходить — конкуренты дают менее вкусный сервис.


  1. Kidar
    01.09.2016 15:24
    #9783486

    2ГИС beta установлен как основной навигатор уже пару месяцев.
    Отмечаю оперативное ежемесячное исправление после проверки на местности выездной бригадой всех отправленных замечаний по карте — новые дома, проезды или их отсутствие и т.д.

    Из пожеланий:
    — выведите на экран текущую скорость движения «по спутнику» (показания спидометра неточны, т. к. зависят от диаметра шин и степени их накачки);
    — укажите места работы «Автодории» и среднюю скорость прохождения участка при нахождении внутри зоны контроля скорости.