Навігатор 2ГІС: Екстраполяція позиції автомобіля



У додатку 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), яку ми намагаємося побудувати.

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

<img src=«tex.s2cms.ru/svg/%0A%5Cleft%5C%7B%5Cbegin%7Baligned%7D%0Aa_i%5Capprox%20%5Cfrac%7Bv_i-v_%7Bi-1%7D%7D%20%7Bt_i-t_%7Bi-1%7D%7D%20%3D%20s_i%5E%7B»%7D%20%5C%5C%0Aj_i%5Capprox%20%5Cfrac%7Ba_i-a_%7Bi-1%7D%7D%20%7Bt_i-t_%7Bi-1%7D%7D%20%3D%20s_i%5E%7B"'%7D%20%5C%5C%0A%5Cend%7Baligned%7D%0A%5Cright.%0A" alt="\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^{&#39;} (t_i )=r_{i-1}^{&#39;} (t_i )
Це рівняння є умовою гладкості сукупності скоригованих функцій. Підставивши в обидві частини рівняння визначення скоригованих функцій, отримаємо

s_i^{&#39;} (t_i)+e_i^{&#39;} (t_i )=s_{i-1}^{&#39;} (t_i )+e_{i-1}^{&#39;} (t_i )
Раніше ми згадували про те, що після закінчення часу корекції Tфункція корекції приймає нульові значення. Додамо ще одна вимога до функції корекції — нехай її похідна після закінчення часу корекції також приймає нульові значення:

e_i^{&#39;} (t)=0,t\in[t_i+T,\infty)
Тоді, в припущенні, що час корекції завжди менше інтервалу між відліками, можна вважати, що похідна i-ї функції корекції до моменту приходу наступного відліку t_{i+1}вже звернеться в нуль. Тоді, повертаючись до умови гладкості, отримаємо:

s_i^{&#39;} (t_i )+e_i^{&#39;} (t_i )=s_{i-1}^{&#39;} (t_i )+0
Виразимо звідси e_i^{&#39;} (t_i ):

e_i^{&#39;} (t_i )=s_{i-1}^{&#39;} (t_i )-s_i^{&#39;} (t_i )

Зауважимо, що s_i^{&#39;} (t_i )представляє собою оцінку швидкості, зроблену за допомогою кінцевих різниць, підставимо її:

e_i^{&#39;} (t_i )=s_{i-1}^{&#39;} (t_i )-v_i
Права частина являє собою помилку екстраполяції швидкості — різниця між швидкістю, отриманої за попереднім экстраполяционному полиному, і «реальним» відліком швидкості. Тепер ми можемо зібрати воєдино граничні умови для корекції функцій:

\left\{
\begin{array}{lcl}
e_i(t_i) = e_i\\
e_i^{&#39;}(t_i) = s_{i-1}^{&#39;}(t_i)-v_i\\
e_i(t_i) = 0, t\in[t_i+T,+\infty] \\
e_i^{&#39;}(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^{&#39;}(t_i) = s_{i-1}^{&#39;}(t_i)-v_i\\
e_i(t_i+T) = 0\\
e_i^{&#39;}(t_i+T) = 0\\
\end{array} 
\right.
Позначимо помилку екстраполяції швидкості через ε_i=s_{i-1}^{&#39;}(t_i)-v_i:

\left\{
\begin{array}{lcl}
e_i(t_i) = e_i\\
e_i^{&#39;}(t_i) = \varepsilon_i\\
e_i(t_i+T) = 0\\
e_i^{&#39;}(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_1C_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&amp;lt;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 завдяки гарному сигналу надходять якісні дані.

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

Що стосується подальших шляхів розвитку, варто звернути увагу на згадану на початку статті вимірювальну похибка в «сирих» позиційних даних від датчика. Якщо помилки нашого прогнозування ми вже зараз намагаємося коригувати, то боротьба з помилками вимірювань — це окремий пласт роботи на майбутнє, важкий, але від цього нітрохи не менш цікавий. Користь від потенційних успіхів на цьому терені для точності відображуваної інформації важко переоцінити.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.