ABONAMENTE VIDEO REDACȚIA
RO
EN
NOU
Numărul 150
Numărul 149 Numărul 148 Numărul 147 Numărul 146 Numărul 145 Numărul 144 Numărul 143 Numărul 142 Numărul 141 Numărul 140 Numărul 139 Numărul 138 Numărul 137 Numărul 136 Numărul 135 Numărul 134 Numărul 133 Numărul 132 Numărul 131 Numărul 130 Numărul 129 Numărul 128 Numărul 127 Numărul 126 Numărul 125 Numărul 124 Numărul 123 Numărul 122 Numărul 121 Numărul 120 Numărul 119 Numărul 118 Numărul 117 Numărul 116 Numărul 115 Numărul 114 Numărul 113 Numărul 112 Numărul 111 Numărul 110 Numărul 109 Numărul 108 Numărul 107 Numărul 106 Numărul 105 Numărul 104 Numărul 103 Numărul 102 Numărul 101 Numărul 100 Numărul 99 Numărul 98 Numărul 97 Numărul 96 Numărul 95 Numărul 94 Numărul 93 Numărul 92 Numărul 91 Numărul 90 Numărul 89 Numărul 88 Numărul 87 Numărul 86 Numărul 85 Numărul 84 Numărul 83 Numărul 82 Numărul 81 Numărul 80 Numărul 79 Numărul 78 Numărul 77 Numărul 76 Numărul 75 Numărul 74 Numărul 73 Numărul 72 Numărul 71 Numărul 70 Numărul 69 Numărul 68 Numărul 67 Numărul 66 Numărul 65 Numărul 64 Numărul 63 Numărul 62 Numărul 61 Numărul 60 Numărul 59 Numărul 58 Numărul 57 Numărul 56 Numărul 55 Numărul 54 Numărul 53 Numărul 52 Numărul 51 Numărul 50 Numărul 49 Numărul 48 Numărul 47 Numărul 46 Numărul 45 Numărul 44 Numărul 43 Numărul 42 Numărul 41 Numărul 40 Numărul 39 Numărul 38 Numărul 37 Numărul 36 Numărul 35 Numărul 34 Numărul 33 Numărul 32 Numărul 31 Numărul 30 Numărul 29 Numărul 28 Numărul 27 Numărul 26 Numărul 25 Numărul 24 Numărul 23 Numărul 22 Numărul 21 Numărul 20 Numărul 19 Numărul 18 Numărul 17 Numărul 16 Numărul 15 Numărul 14 Numărul 13 Numărul 12 Numărul 11 Numărul 10 Numărul 9 Numărul 8 Numărul 7 Numărul 6 Numărul 5 Numărul 4 Numărul 3 Numărul 2 Numărul 1
×
▼ LISTĂ EDIȚII ▼
Numărul 138
Abonament PDF

Localizarea drumurilor în GrabMaps

Roxana Crișan
Head of Engineering, Geo Mapping @ Grab



PROGRAMARE

GrabMaps stă la baza aplicației Grab oferind oportunitatea de a îmbunătăți serviciile noastre și de a îmbogăți harta cu date hiperlocale. Indiferent de scenariul analizat, localizarea drumurilor joacă un rol important în procesul de creare a hărții Grab. Cu toate acestea, localizarea drumurilor implică gestionarea unui volum semnificativ de date, fiind un efort costisitor și consumator de timp. În acest articol, explorăm strategiile implementate pentru a reduce costurile și pentru a diminua timpul de procesare asociat localizării drumurilor.

În 2022, Grab a devenit autosuficient în ceea ce privește serviciile sale Geo. Ca parte a acestei tranziții, un pas crucial a fost decizia de a utiliza o hartă dezvoltată intern, adaptată specificului pieței în care operează Grab.

Având control total asupra hărții, aceasta poate fi extinsă cu mai multe date sau îmbunătățită, în funcție de nevoile serviciilor care o folosesc. Un aspect cheie pe care această tranziție l-a adus a fost posibilitatea de a crea date hiperlocale la nivel de hartă.

De exemplu, prin identificarea țării căreia aparține o stradă, putem deduce automat limba oficială a acelei țări și să afișăm numele străzii în acea limbă. Un alt exemplu, cunoscând țara pentru o anumită stradă, putem deduce automat partea pe care se conduce în acea țară (stânga sau dreapta) aceasta generând o experiență de navigare mai plăcută.

În plus, această capacitate permite, de asemenea, gestionarea mai eficientă a diverse scenarii. De exemplu, știind că o stradă face parte dintr-o comunitate închisă, o zonă cu acces restricționat pentru șoferii noștri, putem împiedica tranzitul prin acea zonă.

Acestea sunt doar câteva exemple ale oportunităților create având control complet asupra hărții. Având o hartă internă putem alinia conținutul hărților noastre cu specificul piețelor în care operează Grab oferind astfel o experiență mai plăcută pentru partenerii noștri, șoferi și clienți.

Background

Pentru ca toate acestea să fie posibile, primul pas a fost localizarea drumurilor din hartă. Scopul final a fost includerea datelor hiperlocale în hartă, date specifice unei anumite zone, cum ar fi o țară, un oraș sau chiar o parte mai mică a orașului, cum ar fi o comunitate închisă. În același timp, harta trebuie livrată cu o frecvență ridicată, așadar, a fost nevoie să găsim modalitatea potrivită de a procesa această cantitate mare de date în timp ce continuam să creăm hărți într-o manieră rentabilă din punct de vedere al costurilor.

Soluția

În secțiunile următoare ale acestui articol, vom folosi un extras din harta Asiei de Sud-Est pentru a reprezenta vizual conceptele discutate.

În Figura 1, Imaginea 1 conține o vizualizare a rețelei de drumuri, drumurile care aparțin acestei zone. Liniile colorate din Imaginea 2 reprezintă granițele care identifică țările din aceeași zonă. Suprapunând informațiile din Imaginea 1 și Imaginea 2, putem extrapola și spune că întreaga suprafață inclusă într-o anumită graniță ar putea avea aceeași serie de proprietăți comune, așa cum este arătat în Imaginea 3. În Imaginea 4, continuăm prin identificarea drumurilor localizate pentru fiecare zonă.

Figura 1 - Harta Asiei de Sud-Est

Pentru ca acest lucru să fie posibil, trebuie să găsim o modalitate de a localiza fiecare drum și de a identifica țara asociată acestuia. Odată ce acest proces de localizare este complet, putem replica toate aceste informații specifice unei anumite granițe pe fiecare drum în parte. Aceste informații includ detalii precum numele țării, partea de drum pe care se conduce și limba oficială. Putem merge chiar mai departe și să extragem și mai multe informații și să adăugăm date hiperlocale. De exemplu, în Vietnam, putem împiedica automat accesul motocicletelor pe autostrăzi.

Atribuirea fiecărui drum de pe hartă unei anumite zone, cum ar fi o țară, zonă de serviciu sau subdiviziune, reprezintă o sarcină complexă. Așadar, cum se poate realiza eficient acest lucru?

Implementare

Cea mai directă abordare ar fi testarea includerii fiecărui drum în interiorul fiecărei granițe. Cu aproape 30 de milioane de segmente de drum în harta Asiei de Sud-Est și peste zece mii de granițe, costul computațional al determinării includerii sau intersecției între o linie și un poligon este mare.

Soluția găsită la această provocare implică înlocuirea operației costisitoare și precise cu o aproximare decentă. Pentru aceasta folosim o entitate intermediară, geohashul, atât pentru a aproxima zonele, cât și pentru a localiza drumurile.

Operația de includere geometrică se înlocuiește cu o serie de operații mai simple și mai puțin costisitoare. Mai întâi, efectuăm o precalculare ieftină în care se identifică toate geohashurile care aparțin unei anumite zone sau care se află într-o graniță predefinită. Apoi identificăm geohashurile prin care trec drumurile. La final folosim aceste valori precalculate pentru a crea legătura dintre setul de drumuri și cel de granițe. Acest proces este mai ieftin din punct de vedere computațional.

Având în vedere suprafața mare pe care o procesăm, folosim tehnici de Big Data pentru a distribui execuția pe mai multe noduri accelerând astfel operația. Se dorește livrarea zilnică a hărții și aceasta este una dintre multele operații care fac parte din procesul de creare a hărții.

Ce este un geohash?

Pentru a înțelege mai bine implementarea noastră, trebuie să înțelegem conceptul de geohash. Un geohash este un identificator unic al unei regiuni specifice de pe Pământ. Ideea de bază este că Pământul este împărțit în regiuni de dimensiuni definite de utilizator și fiecărei regiuni îi este asignat un ID unic, cunoscut sub numele de geohash. Pentru o anumită locație de pe Pământ, algoritmul geohash convertește longitudinea și latitudinea într-un șir de caractere.

Geohashurile folosesc un sistem de codificare alfabetică în baza 32, compus din caractere cuprinse între 0 și 9 și literele de la A la Z, cu excepția "A", "I", "L" și "O". Considerăm suprafața Pământului împărțită într-o grilă cu 32 de celule. Primul caracter dintr-un geohash identifică locația inițială a uneia dintre aceste 32 de celule. Fiecare dintre aceste celule este apoi subdivizată în alte 32 de celule mai mici. Acest proces de subdivizare continuă și se rafinează până se ajunge la locația dorită. Adăugarea de caractere la geohash împarte o celulă, focalizând efectiv către o zonă mai detaliată.

Factorul de precizie al geohashului determină dimensiunea celulei. De exemplu, un factor de precizie de unu creează o celulă cu dimensiunile de 5.000 km x 5.000 km. Un factor de precizie de șase creează o celulă având dimensiunile de 0,61 km x 1,22 km. În plus, un factor de precizie de nouă creează o celulă de 4,77 m x 4,77 m. Este important de menționat că celulele nu sunt întotdeauna pătrate și pot avea dimensiuni variate.

În Figura 2, am exemplificat o grilă geohash de 6, având codul wdts33.

Figura 2 - Exemplu de geohash de lungime 6 (wdts33)

Folosind operații mai puțin costisitoare

Calcularea incluziunii drumurilor într-o anumită graniță este o operație costisitoare. Cu toate acestea, este dificil de cuantificat exact costul deoarece acesta depinde de mai mulți factori. Un factor este complexitatea graniței. Granițele sunt în general poligoane neregulate și foarte detaliate, deoarece trebuie să reflecte corect granița reală. Complexitatea geometriei drumurilor este un alt factor care joacă un rol important, din cauză că drumurile nu sunt întotdeauna linii drepte.

Figura 3 - Drumuri de localizat

Întrucât această operațiune este costisitoare atât în ceea ce privește costurile de cloud, cât și timpul necesar pentru executare, este nevoie de o metoda mai ieftină și mai rapidă care să ofere rezultate similare. Știind că complexitatea granițelor este principala cauza a problemei, am încercat să folosim o variantă diferită, și anume un dreptunghi. Calcularea incluziunii unei polilinii într-un dreptunghi este o operație mai ieftină.

Figura 4 - Drumuri în interiorul unui dreptunghi

Astfel, transformăm această operație mare, realizată într-un singur pas, într-o serie de operațiuni mai mici, în care efectuăm următorii pași:

  1. Identificăm toate geohashurile care fac parte dintr-o anumită zonă sau aparțin unei anumite granițe. În acest proces, includem și zone suplimentare pentru a ne asigura că acoperim întreaga suprafață din interiorul graniței.

  2. Pentru fiecare segment de drum, identificăm lista de geohashuri cărora îi aparține. Un drum, în funcție de lungimea sau forma sa, ar putea trece prin mai multe geohashuri.

În Figura 5, se observă că drumul din vizualizare traversează două geohashuri și vedem, de asemenea, că cele două geohashuri fac parte din granița pe care o folosim.

Figura 5 - Geohashuri ca proxy

Acum, tot ce trebuie să facem este să unim cele două seturi de date. Acest tip de operație este un candidat excelent pentru o abordare de tip Big Data, deoarece ne permite să o executăm în paralel și să accelerăm timpul de procesare.

Impact

Am menționat mai devreme că înlocuim precizia cu o aproximare decentă. Să evaluăm mai în detaliu compromisul real introdus prin adoptarea acestei abordări.

Primul aspect relevant al acestei abordări este faptul că am înlocuit precizia cu costul. Costurile de procesare se reduc datorită faptului că această abordare folosește mai puține resurse hardware și timp de calcul. Totuși, această reducere a preciziei afectează în special drumurile situate în apropierea granițelor, întrucât acestea ar putea fi clasificate greșit.

Revenind la exemplul inițial, să luăm cazul drumului extern, situat pe partea stângă a zonei considerate. După cum se vede în Figura 6, este clar că drumul nu aparține graniței noastre. Dar atunci când aplicăm abordarea geohash, acesta este inclus în geohashul din mijloc.

Figura 6 - Localizare greșită a drumului

Având în vedere că doar o mică parte a geohashului cade în interiorul graniței, întregul geohash va fi clasificat ca aparținând acelei zone și, ca urmare, drumul care aparține acelui geohash va fi localizat greșit la rândul său. Acesta este o consecință directă a compromisului de precizie. Deci, cum putem rezolva aceasta?

Precizia geohashului

O opțiune ar fi să creștem precizia geohashului. Prin utilizarea geohashurilor din ce în ce mai mici, se poate reflecta mai corect zona reală. Mergând mai adânc și împărțind geohashul și mai mult, putem urmări precis granița. Cu toate acestea, o precizie mare a geohashului echivalează și cu o operațiune intensivă din punct de vedere computațional, aducându-ne înapoi la situația inițială. Prin urmare, este crucial să găsim echilibrul între dimensiunea geohashului și complexitatea operațiunilor.

Figura 7 - Precizia geohashului

Rata de acoperire a Geohashului

Pentru a găsi un echilibru între precizie și pierderea de date, am introdus un alt concept, calcularea ratei de acoperire a geohashului. De exemplu, în Figura 8, geohashul albastru este complet în interiorul graniței. Aici putem spune că acest geohash are o acoperire de 100% în interiorul graniței.

Figura 8 - Geohash în interiorul graniței

Cu toate acestea, să luăm de exemplu geohashul din Figura 9. Acesta atinge granița și are doar aproximativ 80% din suprafața sa în interiorul ariei considerate. Având în vedere că cea mai mare parte a suprafeței sale este în interiorul graniței, putem totuși spune că aparține zonei.

Figura 9 - Geohash parțial în interiorul graniței

Să considerăm un alt exemplu. În Figura 10, doar o mică parte a geohashului se află în interiorul graniței. Putem spune că procentajul de acoperire al acestui geohash este de aproximativ 5%. În astfel de cazuri devine dificil să determinăm dacă geohashul aparține zonei. Care ar fi un compromis bun în acest caz?

Figura 10 - Geohash puțin în interiorul graniței

Forma graniței

Pentru a merge un pas mai departe, putem lua în considerare o soluție mixtă, în care să folosim forma graniței, însă doar pentru acele geohashuri care ating granița. Aceasta ar fi încă o operație computațională intensivă, dar numărul de drumuri situate în aceste geohashuri va fi mult mai mic, deci totuși un câștig.

Pentru geohashurile cu acoperire completă în interiorul zonei, vom folosi geohashul pentru localizare, operația mai simplă. Pentru geohashurile aflate în apropierea graniței, vom folosi o abordare diferită. Pentru a crește precizia în jurul granițelor, putem tăia geohashul urmând forma graniței. În loc să avem un dreptunghi, vom folosi o formă mai complexă, care totuși este mai simplă decât forma inițială a graniței.

Figura 11 - Geohash tăiat după forma graniței

Rezultat

Am început cu o abordare simplă, pe care am continuat să o îmbunătățim pentru a crește precizia. Odată cu aceasta a crescut și complexitatea operației. În această secțiune, am încercat să evaluăm beneficiile reale ale acestei abordări.

În primul rând, am creat o referință prin extragerea unei mici mostre de date pentru care am rulat procesul de localizare pe un laptop. Mostrele cuprindeau aproximativ 2% din granițe și 0.0014% din drumuri. Am rulat procesul de localizare folosind două abordări.

Cu prima abordare, cea în care am calculat intersecția între toate drumurile și granițele, întreaga operațiune a durat aproximativ 38 de minute.

Pentru a doua abordare, cea în care am optimizat operația folosind geohashurile, timpul de rulare a fost de doar de 78 de secunde (1.3 minute). Cu toate acestea, este important de menționat că aceasta nu este o comparație directă. Operația pe care am măsurat-o a fost localizarea drumurilor, dar nu am inclus aici și operația de umplere a granițelor cu geohashuri.

Aceasta se datorează faptului că această operație nu trebuie rulată de fiecare dată. Poate fi rulată o dată și utilizată de mai multe ori.

Deși nu este adesea necesar, este totuși important să luăm în considerare operația de precalculare a zonelor și umplerea granițelor cu geohashuri. Procesul de precalculare depinde de mai mulți factori:

Cu toate că această precalculare ar putea fi costisitoare, ea este rulată relativ rar deoarece granițele nu se schimbă des și rerularea calculării lor poate fi făcută doar la nevoie. Dincolo de acest aspect, operațiunea regulată, cea în care găsim granița în interiorul căreia aparține fiecare drum, este rulată mult mai des deoarece drumurile se schimbă continuu. În sistemul nostru, de exemplu, această localizare se rulează pentru fiecare procesare de hartă.

Abordarea aceasta poate fi optimizată și mai mult aplicând abordarea opusă. Geohashurile care au acoperire completă în interiorul unei granițe pot fi reunite în geohashuri mai mari, simplificând astfel calculul în interiorul graniței. În cele din urmă, putem avea o soluție complet optimizată nevoilor proiectului, cu cel mai bun raport cost-performanță.

Figura 12 - Geohashuri optimizate

Concluzie

Deși geohashurile par a fi soluția potrivită pentru acest tip de problemă, trebuie luat în considerare și conținutul acestora. Densitatea drumurilor într-un geohash joacă un rol important. De exemplu, un geohash în centrul unui oraș are de obicei multe drumuri, în timp ce unul în zonele rurale poate avea mult mai puține. Acest aspect trebuie luat în considerare pentru a avea o operațiune de calcul echilibrată și pentru a profita pe deplin de abordarea Big Data. În cazul nostru, realizăm acest echilibru prin luarea în considerare a numărului de kilometri de drumuri dintr-un geohash.

Figura 13 - Distribuție dezechilibrată de date

Resursele alese pentru rularea procesului de localizare sunt, de asemenea, importante. Trebuie găsit un echilibru între timpul de rulare și costul resurselor. După cum se vede în Figura 14, pe baza datelor de test folosite pentru aceasta rulare, uneori cel mai bun rezultat se obține atunci când folosim mașini mai mici.

Figura 14 - Cost vs. timp de rulare

Realizările și perspectivele prezentate în acest articol sunt datorate contribuțiilor aduse de către Mihai Chintoanu. Expertiza și implicarea sa au adus o valoare semnificativă conținutului și concluziilor prezentate în această lucrare.

NUMĂRUL 149 - Development with AI

Sponsori

  • Accenture
  • BT Code Crafters
  • Accesa
  • Bosch
  • Betfair
  • MHP
  • BoatyardX
  • .msg systems
  • P3 group
  • Ing Hubs
  • Cognizant Softvision
  • Colors in projects