На горизонті: тренди в картографії, злиття даних та автомобільна навігація нового покоління

Привіт! Мене звати Олена, і я Technical Product Manager в компанії Intellias. За свої 15 років в ІТ-секторі маю досвід у різних доменних сферах: від розробки мікросхем і LTE-протоколів до інвестиційного банкінгу.

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

Для багатьох слово «карти» викликає асоціацію з Google maps і питання: «Навіщо потрібні ще якісь інші карти?». Водночас впевнена, що чимала частина аудиторії так чи інакше стикалась з картографічними даними на проєктах.

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

Отож, прямуйте 200 метрів до перехрестя пару сантиметрів униз і розпочнімо.

Тренди в картографічних даних

Хочу почати з того, як за останні кілька років змінився процес збору картографічних даних. Фокусуємось на автомобільних дорогах, містах, адресах і Point of Interest (на жаль, відповідного терміну в українській мові не знайшла. Пропоную назвати «місцинка-цікавинка», як вам?).

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

Потім ці дані доповнювались джерелами: супутниковими знімками, даними державних організацій на кшталт «Укравтодору» і географічних інститутів. Вони оброблялись (часто вручну), і створювалась реляційна база з чіткими визначеннями стовпців і взаємозв’язками.

Ця база конвертувалась/компілювалась у потрібний формат і потрапляла в наші телефони/машини/пайплайни. Процес недешевий, тож переважно дані належали великим гравцям, серед яких можна виділити три: HERE, TomTom, Google (специфічні ринки, як-от Індія, Китай, Південна Корея мають своїх гравців, які потім продають ці дані вищезгаданим гігантам).

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

Заснований у 2004 році Open Street Map набуває все більшої популярності й часто використовується в комерційних продуктах. А у 2022 році Meta, Microsoft, Amazon і TomTom анонсували Overture. Спільнота працюватиме над новим форматом, який поєднуватиме в собі дані з відкритих джерел, а також комерційних джерел членів фундації.

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

Варто також сказати про трансформацію моделі даних. Реляційні бази все менше відповідають потребам сьогодення: важка підтримка й оновлення даних, мало гнучкості, дорога інфраструктура. Натомість OSM-формат пропонує зберігання даних в XML-форматі на основі лише трьох базових примітивів:

• точка;
• лінія;
• зв’язок.

На ці примітиви навішуються теги з додатковою інформацією з відповідного елементу.

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

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

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

Автомобільна промисловість і карти

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

Існує «традиційне» питання про доцільність навігаційних систем в машині: мовляв навіщо, якщо є CarPlay/Android Auto та Google Map на телефоні. Але мапи, що інтегровані в машину, мають набагато ширший арсенал даних і приховані від користувача функції.

Розділити використання можна на такі підрозділи:

Навігація — так, тут Google maps цілком можуть замінити інтегровані карти. Однак автомобільні карти мають ряд переваг, а саме:

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

SA (Intelligent Speed Assistance) — з липня 2022 року, для всіх моделей і типів автотранспорту, що виробляються/імпортуються в ЄС, є обов’язковою система розумного помічника швидкості. Система попереджає водія про перевищення допустимої швидкості, зчитуючи дані фронтальною камерою зі знаків.

Однак ці дані не є надійними, оскільки знаки можуть бути пошкоджені/заметені снігом/камера може бути засліплена сонцем і т. д. Тож ця система потребує додаткового джерела даних про наявні швидкісні обмеження, яким і є навігаційна карта.

ADAS (Advanced Driver Assistance System) — такі помічники як екстрене гальмування, круїз контроль тощо. також покладаються на велику кількість даних в карті: кривизна дороги, нахил дорожнього полотна, тип покриття, обмеження швидкостей/рекомендована швидкість і багато іншого.

AD (Autonomous Driving) — будь-які системи автопілота, окрім камер, також покладаються на картографічну інформацію, оскільки автомобіль має «бачити» далі, ніж дозволяють камери.

Для цього випадку потрібна максимальна деталізація карти: геометрія смуг руху з точністю до кількох сантиметрів, уся повнота розмітки, всі можливі навколишні об’єкти, аби система могла з цією інформацією + інформацію з камер та лідарів точно локалізувати автомобіль, ухвалити правильне рішення і насамкінець вести автомобіль правильним маршрутом.

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

Якщо говорити про тренди автомобільної промисловості, то можна виділити три основних (усі вони пов’язані між собою так само, як і всі невід’ємно спираються на карти):

Self-driving vehicles — 10-20 років тому прогнозували, що до 2030-го автопілоти захоплять ринок (або нас). Та автомобільна промисловість зіштовхнулась з багатьма складнощами — перш за все юридичними, бо в кожній країні чи навіть кожному окремому штаті США свої закони, і легалізація виявилась дуже дорогим процесом. Невдачі під час тестування і неготовність кінцевого користувача довіритись автопілотам також пригальмували цей процес.

Проте робота в цьому напрямку ведеться: у низці міст уже їздять таксі без водія. Mercedes став першим, хто запустив офіційно L3-автопілот (правда тільки в Каліфорнії, Неваді та Німеччині. І то функціонал його обмежений нешвидким рухом в смузі), вагомою відмінністю якого від інших автопілотів на ринку є юридична відповідальність компанії за наслідки аварій.

Electric vehicles — тут найбільш агресивним гравцем став Китай. Потроху підтягується інфраструктура зарядок у багатьох країнах світу. Цей тренд поки найуспішніший і найдинамічніший у розвитку.

Software-defined vehicles — отут вже цікавіше. Виробники авто (а також виробники запчастин) масово говорять про Software-defined vehicle, і набирають на роботу програмістів. Нічого нового, просто все більшою частиною запчастин в авто — від шасі до трансмісії — керують маленькі комп’ютери (ECU, Electronic Control Units) за допомогою програмного забезпечення, а не механічних механізмів (вибачте за тавтологію). Так, поколінню автомобілістів, що любить «покрутити» машину в гаражі на вихідних, це явно не до смаку, але треба йти в ногу з часом.

Окрім Embedded Software (вбудованого ПЗ), велику частину індустрії займають застосунки для користувачів — від тієї самої навігації до тетрісу, що доступні в автомобілі.

І тут серед автовиробників наразі можна спостерігати дві протилежні тенденції: одні намагаються максимально закрити цей процес і все розробляти in-house (більш європейський тренд), інші ж ідуть шляхом відкриття API, використання Android як домашньої операційної системи й відповідно заохочення до розробки застосунків для авто (більш американський тренд, хоча деякі європейські бренди його також підтримують).

До прикладу, Tesla відкрила свої АPI, General Motors також.

Разом з тим зростає список автомобілів з Android Auto OS, яка дозволяє качати в машину застосунки з Play Market так само, як і на телефон. Список марок можна знайти тут.

Гайдлайни для розробки, а також категорії розробки застосунків, які можуть бути сумісні з AAOS, можна знайти тут (от вам ідея для стартапу).

Навігація в хмарі

Одна з головних проблем карт в машинах — швидке оновлення і використання дискового простору. Більшість автовиробників використовують стандартизований формат, який регулюється асоціацією NDS (Navigation Data Standard). Туди входять найбільші гравці ринку й усі разом дружньо цей стандарт визначають і розвивають.

Класичний стандарт NDS.Classic, який ви можете побачити вже зараз у більшості авто на дорогах, використовує бінарну форму представлення даних (blob), запаковану в SQLite, яка в сервісному центрі з SD-карточки заливається в машину.

Також існує механізм ОТА (over the air) оновлення через LTE. Однак весь цей процес потребує довгого циклу оновлення даних: зібрати, скомпілювати, залити на сервер/картку пам’яті/оновити, повторити і т. д.

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

Основна ідея: карта перебуває в хмарі, кожна машина перетворюється на вузол в мережі, що через спеціальний сервіс (Smart Layer Service) отримує потрібні дані в live-режимі. Для комунікації використовується загальновідомий REST API.

Цей підхід також дає багато гнучкості з огляду контенту, адже сервіс може віддавати тільки обмеження зі швидкості для ISA, дані для звичайної навігації або ж повний пакет HD-даних для автопілотів та ADAS-систем. Це дає гнучкість як провайдерам карт і автовиробникам, так і водіям у виборі тарифних планів. Детальніше можна дізнатись тут.

Після безплатної реєстрації можна також отримати доступ до документації й прикладів карт.

Акселератор та злиття даних

У всьому різноманітті даних, архітектур і підходів завжди можна виділити типові задачі, які вирішуються кожного разу під час розробки компіляторів, зокрема:

• накладання даних з різних джерел (map matching, data fusion);
• побудова адміністративної ієрархії;
• приєднання атрибутів до об’єктів і т. д.

Тож ми вирішили виділити типові задачі та створити map accelerator — набір модулів та бібліотек для розв’язання типових задач.

На вхід наразі використовуються три джерела (OSM, Overture, Open Charge), однак механізми дозволяють легко додавати й інші формати.

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

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

Далі всі дані зводяться до проміжного формату — паркетів (GeoParquet), з яких можна отримати потрібний кінцевий формат: GeoJSON, раніше згаданий NDS.Live чи інший необхідний формат. Компілятор не є продуктом, а радше допоміжним засобом, щоб прискорити та здешевити розробку компіляторів для клієнтів.

Ще одне цікаве рішення, яке ми втілили в життя (наразі як доказ концепції) разом з одним з наших клієнтів, — це використання можливостей NDS.Live формату для уточнення певних картографічних атрибутів для кожного конкретного автомобіля.

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

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

Map Matching

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

Розберемо два випадки:

Маємо геометрії об’єктів (наприклад, будівлі) з двох, трьох чи більше джерел. У реальності кожна така геометрія матиме похибку — більшу чи меншу, залежно від способу отримання. Нам же треба отримати одну усереднену геометрію.

Для цього наша лібка використовує афінні перетворення:

Кожне афінне перетворення — представлення у вигляді матриці 3×3, яка описує трансформації об’єкта: масштабування, обороти навколо центральної точки, зміщення по x- і y-координатах. У більшості випадків це дозволяє повністю описати всі можливі зміни геометричного об’єкта.

Основна ідея — усереднення не власне об’єктів, а їхніх трансформацій. Наприклад, у нас три об’єкти — A, B, C. У першій ітерації маємо:

• стартовий об’єкт А;
• об’єкт Б, зміщений відносно А;
• об’єкт С, також зміщений відносно А.

Для обох «різниць» між об’єктами обчислюємо матрицю афінного перетворення, усереднюємо її та отримуємо проміжний результат. Якщо об’єкт Б обернений на 10° відносно об’єкту А, а С на 20°, то отримаємо об’єкт обернений на 15°. І так почергово для всіх комбінацій перетворень.

Математичний апарат роботи з афінними матрицями доступний в OpenCV. Приклади роботи алгоритму:

Інша задача — накладання GPX-треку на геометрію доріг. Найочевидніше застосування — локалізація машини на дорозі (щоб знати, що їдемо не зустрічною чи сусідньою вулицею; GPS-приймач теж має похибку) та прокладання маршруту і, власне, навігація чи навіть аналізу поведінки водія, що є зараз досить трендовою темою.

Але може використовуватись і в суміжних сферах, як-от зоологія (відстеження маршрутів міграції) чи туризм (нові туристичні маршрути на основі популярних траєкторій).

Для цього нам потрібен власне трек — сукупність послідовних точок з певною похибкою та дорожня сітка у вигляді відрізків (якій ми довіряємо). На рисунку нижче це представлено так:

• синя лінія — GPX-трек руху автомобіля;
• червоні лінії — сітка доріг. Тут показано спрощений варіант — всі дорогі двосторонні, ніяких обмежень по типу заборони розворотів або «цеглин» немає;
• зелена лінія — результат роботи алгоритму.

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

Тут оцінюється відсоткова ймовірність приналежності кожної точки вулицям: точка А з різним ступенем ймовірності може належати відрізкам DF, FG, FE; B ж має два кандидати: EF та FH і так далі. Алгоритм розраховує найбільш ймовірний маршрут, відкидаючи неможливі варіанти/комбінації.

Тут використовується Марковська модель з теорії ймовірності, яка не переносить уплив ймовірностей між точками. Цей принцип наразі є state-of-the-art для проблем накладання маршруту, тож ми вирішили запропонувати власну реалізацію.

Залучення молодих талантів

І наостанок кілька слів про ініціативу, про яку вже писали тут. До розробки акселератора ми долучаємо молоде покоління талантів. Перший випуск вже відбувся і враження більш ніж позитивні як у менторів, так і в студентів. Тож тепер чекаємо найкращих на наших проєктах!

Якщо підсумувати, то в цій статті я хотіла розкрити загальне бачення трендів індустрії, заглибитись у кілька практичних геометричних задачок. А також поділитись досвідом ініціатив, як-от розробка акселераторів та внутрішніх доказів концепцій, внеску в розвиток стандартів, участі в різних організаціях, зокрема NDS, співпраці з університетами. Адже вони приносять багато плюсів: мотивація співробітників, залучення талантів, маркетинг, поглиблення компетенцій та розширення бізнесу.

На цьому буду зупинятись, бо й так уже довго. Якщо зацікавила котрась тема — коментуйте, будемо заглиблюватись далі.

P.S. Дякую колезі Володимиру Гренюх, Middle Java Developer в Intellias за допомогу у підготовці матеріалу