Navigační server Zobrazit historii

Verze z 2. 3. 2017, 10:30, kterou vytvořil Bures (diskuse | příspěvky) (Sloh)

Při používání aplikace Waze probíhá neustálá komunikace se servery Waze, které používají sofistikované algoritmy pro určení optimální trasy pro každý okamžik, kdy si to aplikace vyžádá. Podrobnosti algoritmů nejsou veřejné a následující text je založen na pozorování, spekulacích a informacích od zaměstnanců Waze. Akce systému Waze jsou skryté a jsou hlavním "obchodním tajemstvím" Waze. Algoritmy se mohou časem měnit a text tak nemusí přesně odpovídat současnému stavu.

Počítání trasy aplikací

Spočítat optimální trasu je obtížný úkol. Výpočetní algoritmus je sice součástí klientské aplikace, ale běžně se nepoužívá. Aplikace k němu sáhne, jen když má problém s připojením k serveru Waze.

Požadavek na určení trasy

Když v navigaci zadáte požadavek na novou trasu, je odeslán na server Waze. Podle vstupních kritérií server Waze určí optimální trasu a odešle ji zpět do vašeho zařízení.

Podle nastavení aplikace se mění parametry výpočtu trasy. V nastavení aplikace jsou např. volby:

  • Nejrychlejší nebo nejkratší trasa.
  • Povolení jízdy po placených silnicích.
  • Využití nezpevněných komunikací (polní cesty).
  • Vyhnout se dálnicím.

Nejkratší cestou se rozumí fyzická vzdálenost v metrech. Obvyklým a nejvíce využívaným nastavením je nejrychlejší trasa - 100 km po dálnici je lepší než 90 km po okreskách.

Chybějící cesty a špatné napojení do křižovatek

Waze hledá optimální trasu mezi výchozím a cílovým bodem a bere v úvahu nastavení aplikace. Pochopitelně dokáže počítat pouze s cestami, které zná, takže pokud je lepší trasa, která není zanesena v editoru, případně není zanesena správně, tak nebudete na danou trasu navigováni. Stejně tak můžou způsobit potíže různé místní úpravy v editoru, které se obecně nedoporučují (příliš krátké segmenty atp.).

Aktuální rychlosti na silnicích

Výpočetní server používá aktuální rychlosti na silnicích ze spuštěných navigací Waze a kombinuje je s historickými údaji pro každý segment, které si navíc dělí do úseků trvajících 10-15 minut. Čas potřebný k projetí krajních bodů segmentu je sledován v kontextu trasy, po které uživatel právě jede.

Na segmentu A-B jsou uložena různá data pro jízdu ve Směru 1 a Směru 2

Například pokud segment končí dvěma odbočkami - vlevo a vpravo (a žádné pokračování rovně), potom si Waze server pro daný segment pamatuje dvě rychlosti - jednu pro případ, kdy trasa na konci segmentu odbočuje vlevo a druhou pro případ, kdy trasa odbočuje vpravo. K těmto informacím nemá uživatel přístup, jsou součástí obchodního tajemství Waze.

Waze upřednostňuje aktuální rychlosti před historicky sledovanými hodnotami.  Stejně tak Waze využívá hlášení o příliš husté dopravě a navrhuje alternativní trasy s cílem vyhnout se ucpanému místu na silnici. Předpokládá se, že pro výpočet vaší trasy se v první řadě použije rychlost Wazera, který projel daný úsek chvilku před vámi (pokud takový Wazer existuje).

Aktuální rychlosti nabývají na důležitosti při rostoucím počtu uživatelů Waze. To je v souladu se základní myšlenkou Waze - navrhovat optimální trasy pro každodenní používání. Zároveň s tím, jak je Waze používáno jako všeobecná navigace i pro dálkové a méně využívané trasy, roste důležitost uchovávání historických dat a rychlostí.

Navigační systém Waze počítá s tím, že vzdálené segmenty na trase projedete "až za delší dobu". Pro vzdálenější segmenty nemá smysl počítat s aktuálním stavem. Dopravní situace se může změnit, než na místo přijedete. Navržená trasa delší než 15-30 minut je kombinací aktuálních dat a historických dat pro segmenty, ke kterým dorazíte poté. Zároveň v takových případech Waze sleduje aktuální dopravní data a pokud z nich vyplyne vhodnější trasa, nabídne ji.

Nejrychlejší cesta

Waze zná průměrnou rychlost každého potvrzeného segmentu mezi vámi a cílem cesty. Server Waze počítá, jaké segmenty je třeba projet, aby byla cesta co nejrychlejší.

Každý požadavek na trasu je propočítáván v daný okamžik, nicméně z pozorování vyplývá, že Waze má určité hlavní body, mezi kterými má "předpočítané" nejrychlejší trasy a tyto údaje pak využívá ke zrychlení výpočtů. Pokud například systém už zná nejrychlejší trasu z bodu B do bodu C a vy si vyžádáte výpočet trasy z bodu A do bodu C, pak Waze server spočítá pouze trasu z bodu A do bodu B, jakmile zjistí, že není lepší cesta, která by znamenala úplné vyhnutí se bodu B. To mj. znamená, že při aktualizaci mapových podkladů mohou být některé vypočítané trasy během 24 hodin "méně optimální", než si systém dokáže znovu propočítat všechny alternativy mezi svými hlavními body.

Podle dostupných informací používá Waze pro určení trasy vyhledávací algoritmus A*, ke kterému přidává množství vlastních "upřesnění".

Příklad hledání trasy. Zdroj: Wikipedia

Změny v trase v různých výchozích bodech

Představme si výpočet trasy z bodu A do bodu Z. Navržená trasa je A > B > C > D > Z. Poté nechme spočítat trasu z bodu B do bodu Z. Možná vám bude navrhnuta trasa B > C > E > Z. Zdá se, že jedna trasa není optimální. 

Můžeme jen hádat, co se děje:

  • "Předpočítání" tras.
  • Délka trasy překročila 15-30 minut. Místo aktuálních dat Waze pro vzdálenější úsek použije historická data. Rozdílný čas příjezdu do bodu C mohl ovlivnit výpočet trasy do bodu Z.
  • Dodatečná optimalizaci trasy, která možná měla příliš mnoho odbočení a vynecháním trasy z A do B navigační systém nepřekročil nějaký svůj vnitřní limit.

Tohoto efektu si můžete při jízdě všimnout. Vyžádáte-li si za jízdy přepočítání trasy, systém někdy nabídne trasu jinou.

Waze občas nabídne novou trasu, která objede dopravní komplikace. Nevíme, kdy a jak Waze zvažuje změnu trasy.

Změny v trasách díky různým délkám tras

Waze má problémy s výpočtem optimální trasy u dálkových jízd, kdy nedokáže propočítat všechny možnosti. Využívá zjednodušení a předpočítaných tras. To může vést k poměrně významné změně tras už při mírné změně trasy.

Podle vyjádření Waze (2011) navigační systém silně upřednostňuje vyšší třídy silnic (vyšší než ulice/street), pokud je vzdálenost do cíle větší než 10 km.  Zdá se, že navigační server ignoruje segmenty typu street/ulice, které jsou od cíle vzdálenější než 10 km, aby urychlil celkový proces výpočtu.

Problémy s průměrnou rychlostí silnice

Pokud průměrné rychlosti nejsou v pořádku, pak není možné spočítat optimální trasu. Nicméně nikdy se nedoporučuje mazat segmenty za účelem resetu průměrné rychlosti pro daný segment. Waze stále používá data uživatelů projíždějících přes daný segment a průměrnou rychlost zpřesňuje. Máte-li podezření, že systém Waze nevyužívá určité úseky, i když by měl, pak se s největší pravděpodobností jedná o jeden z mnoha dalších důvodů, proč vás navigace danou cestou nesměruje. Rozhodně není dobré začít tím, že smažeme a znovu vytvoříme segmenty, které dle nás působí problém.

Následující odstavce popisují důvody, proč navigační systém nemusí brát ohled na průměrnou rychlost daného segmentu.

Rozdíly podle denní doby

Představte si silnici, po které většina Wazerů jezdí v pět odpoledne a na níž je průměrná rychlost 20 km/h. Vy se na cestu vydáte v deset ráno, kdy je silnice prázdná a průměrná rychlost dosahuje 100 km/h. Je to nejvhodnější cesta, ale systém Waze vám nabídne jinou, protože nemá informaci o tom, jaká je rychlost kolem desáté hodiny dopolední a automaticky tak předpokládá, že průměr 20 km/h je platný po celý den.

V t akovém případě můžete samozřejmě rychlejší cestu projet na základě vlastního rozhodnutí a systém Waze se nakonec naučí, jaká rychlost je v daný čas pro danou silnici průměrná. Je logické, že v tomto případě nejen že nepomůže smazání a opětovné vytvoření dané silnice, ale navíc to uškodí ostatním Wazerům, kteří profitují z faktu, že systém již zná rychlost v pět odpoledne. Je také možné, že vaše vysoká rychlost bude ignorována, protože ji systém Waze bude považovat za abnormální.

Větší množství Wazerů projíždějící danou silnici v dopolední dobu by problém vyřešilo.

Zpoždění při změně směru jízdy

Rychlost pro určité segmenty může být velmi odlišná v závislosti na tom, co má řidič udělat na konci segmentu (typicky na křižovatce). Pokud pokračuje rovně, projede pravděpodobně celý segment rychle, zatímco pokud odbočuje vlevo, zdrží se na stejném segmentu velmi dlouho. Podobně také např. u dálničních sjezdů - jízdní pruh přecházející ve sjezd bude velmi rychlý, zatímco pruh pokračující rovně po dálnici bude beznadějně zacpaný. 

SegmentTraffic1.png
SegmentTraffic1.png

Systém Waze umí tyto situace odlišit a zaznamenává průměrnou rychlost pro segment v  závislosti na tom, jaká akce se dále koná na konci segmentu. Situace je zachycena na obrázku vlevo, kdy doprava přes Seg4 se rozdvojuje do Seg5 a Seg6. V dané situaci tedy systém Waze sleduje dvě průměrné rychlosti:

  • Seg4 - Jnct2 - Seg5
  • Seg4 - Jnct2 - Seg6

Prodlužující se čas pro Seg4 u vozidel odbočujících na Seg6 nemá žádný vliv na čas pro vozidla, která ze Seg4 odbočují na Seg5. Z tohoto důvodu je důležité dělat pokud možno delší segmenty vedoucí ke křižovatkám (zde konkrétně Seg4), aby systém co možná nejpřesněji zachytil dlouhé čekací doby pro všechny odjezdové směry.

Abychom tomuto lépe porozuměli, představme si, že přidáme ještě krátký segment navíc, konkrétně na druhém obrázku je to Seg8, který jme "vmáčknuli" mezi rozdvojení a Seg7. Řekněme, že provoz do Seg10 je tak hustý, že ve chvilce stojí kolona přes Seg8 až do Seg7. To díky krátkému Seg8 nastane velmi brzy. V ten okamžik nastává naše problémová situace: protože Seg7 má jediný odjezdový bod (a to do Seg8), nedokáže už v tento okamžik systém Waze sledovat více než jednu průměrnou rychlost a nemůže tedy zohlednit, jestli řidič stojící na Seg7 bude pokračovat do Seg9 nebo Seg10. Díky tomu se v naší modelové situaci systém Waze domnívá, že doprava směřující do Seg9 je zpomalena už v Seg7, zatímco v reálu tomu tak není. Přinejmenším to ovlivní předpokládaný čas dojezdu do cíle - nicméně může to také vyvolat přepočítání celé trasy a navržení méně optimální alternativy. Takže platí: pokud je na křižovatce reálné, že různé směry jízdy budou mít různě dlouhou "čekací dobu", než mohou opustit křižovatku, pak je třeba udělat vjezdové segmenty co nejdelší.

Tyto údaje nicméně ve Waze Map Editoru neuvidíte, počítá s nimi pouze navigační server.

Úpravy v Editoru map

Průměrná rychlost segmentu může být dramaticky změněna také editováním segmentu ve Waze Editoru map. Představme si 50 metrů dlouhý segment, který je průměrně projet za 36 sekund. Editor "natáhne" daný segment a udělá z něj celou silnici, která je 10 kilometrů dlouhá. Touto změnou nicméně segment neztratí informaci o průměrné době, za kterou se daný segment dá projet a z ní odvodí průměrnou rychlost - kolem 1 000 km/h. Buďte tedy opatrní v situacích, kdy zamýšlíte zásadně změnit délku segmentu. Lepším řešením může být nakreslení nové silnice a následné spojení.

Semafory

Waze nezaznamenává umístění semaforů. Některé navigační systémy toto umí a poskytují informace typu "na dalším semaforu odbočte vpravo", tyto informace jsou ale často nepřesné, nesprávné nebo prostě jen zastaralé. Proto systém Waze nemá žádnou podporu pro umisťování a používání semaforů.

Nicméně system Waze samozřejmě bere v potaz vliv semaforů na plynulost dopravy jako takové. Zvažujme například semafory, na nichž je dlouhá čekací doba - ta ovlivní průměrnou rychlost, za jakou je schopen řidič daný segment projet.  Pokud klesne rychlost pod kritickou hranici, nabídne systém Waze řidiči raději alternativní trasu, kde nehrozí nebezpečí takto nízké rychlosti. Toto bylo pozorováno v reálu a je to ukázkový příklad přizpůsobování reálné situaci. Systém Waze není určen k tomu, aby se vyhýbal semaforům - je určen k tomu, aby se vyhýbal pomalým silnicím. Pokud semafor přiliš zpomaluje provoz, bude se mu Waze vyhýbat.

Někteří řidiči pravidelně jezdí raději delšími cestami, "protahují" se bočními uličkami, jen aby nemuseli stát v na semaforech. Waze umí takové cesty také navrhovat a stejně tak se Waze umí vrátit na cestu se semafory, jakmile je nasbírán dostatek dat z bočních uliček a porovnán s průměrnými rychlostmi segmentů vedoucích k semaforům. Nicméně je dobré mít na paměti, že díky krátký segmentům před křižovatkami, které jsou popsány v kapitole výše, může být informace při odbočování nepřesná.

Zastaralé a abnormální rychlosti segmentu

Situace na silnicích se stále mění, probíhají uzavírky, stavby, mění se kvalita povrchu.... to vše má zásadní vliv na průměrnou rychlost segmentů. Jeden den můžete být zaseknutí za kamionem, další den opatrně převážíte ve dvě hodiny v noci svoje akvárium. Nebo má prostě vaše GPS slabší chvilku a pohybujete se rychlostí 1 000 km/h.

Průměrné rychlosti se zkrátka mohou významně měnit a průjezdní doby tak mohou být abnormální nebo prostě jen špatné - a mohou zůstat špatné po velmi dlouho.

Lze očekávat, že systém Waze s tímto počítá. Existují určité indicie, které nasvědčují tomu, že abnormální rychlosti a příliš staré údaje o rychlosti již nejsou používány, je-li dostatek čerstvých informací, případně jim není dána taková váha.

"Časové okno" průměrné rychlosti

Je-li pro daný segment dostatek informací o průjezdové rychlosti, rozdělí si systém Waze den na více časových okének a sleduje rychlosti pro každé okénko zvlášť. Nejmenší interval je 30 minut - to znamená, že pro klasickou obousměrnou silnici je sledováno až 96 různých rychlostí během 24 hodin. Můžeme předpokládat, že pokud se pro určité idividuální časové okénko přestane dařit sbírat dostatek informací o průjezdové rychlosti, pak se interval každého okénka prodlouží a počet časových okének se tak sníží. Stejně tak s houstnoucím počtem Wazerů si systém časová okénka zkrátí a přidá.

Můžeme se domnívat, že systém Waze sleduje i další parametry, např. den v týdnu. Uživatelé pozorují, že silnice, která bývá pravidelně ucpána v pracovní dny, je o víkendech nabízena jako optimální trasa.

V určitých situacích také musí systém Waze zvažovat kalendářní měsíc, protože rozdílnost sezónního provozu může mít na průjezdnost silnic také významný vliv.

Při plánování trasy Waze zohledňuje čas, kdy pravděpodobně budete daným segmentem projíždět a podle toho zvolí rychlost platnou pro dané časové okénko.

Díky tomuto "časovému okénku" tedy navigační systém Waze navrhuje různé cesty v různou denní dobu. To samozřejmě záleží na tom, kolik dat se povede nasbírat a kdy - pokud je mnoho průjezdů, ale všechny jsou ve stejnou denní dobu, pak metoda časových okének moc nepomůže. Je-li zaznamenáno 1 000 průjezdů v pět odpoledne a 2 průjezdy v deset ráno, pak průměrná rychlost počítaná pro 10 ráno bude stále z velké části ovlivněna průjezdy zaznamenanými v 5 odpoledne.

Zpřesňování navigačního algoritmu

Penalizace na křižovatkách

Domněnka: Pro nově vytvořené silnice aplikuje Waze standardně pětivteřinovou penalizaci EN pro každou křižovatku, přes kterou cesta prochází. Jakmile jsou zaznamenána reálná data z průjezdů, je tato penalizace vypuštěna.

Špatná trasa

Nejdříve vygenerujte alternativní trasy. To může odhalit, proč Waze navrhuje nečekanou trasu.

Poté zkontrolujte Waze Map Editor, jestli jsou všechny cesty, které jste očekávali, správně napojeny a jsou povolena odbočení.

Pokud ani to nepomůže, můžete vznést dotaz do fóra. Nezapomeňte poskytnout dostatek detailů - odkud, kam, v kterou dobu. Můžete využít diskuzního fóra EN přímo k problémům výpočtu tras a nebo využijte přímo české fórum. Možná je v navigačním algoritmu problém a nahlášená chyba pomůže tisícům dalších Wazerů.

Změna trasy

Když systém Waze obdrží hlášení o dopravní situaci, použije aktuální rychlost na trase, nikoliv průměrnou rychlost.  To se týká pouze automatických hlášení o hustotě provozu. Ruční hlášení dopravní zácpy a nehod jsou pouze pro vaši informaci a na výpočet trasy vliv nemají.

Je možné, že i přes hustý provoz není možné najít vhodnější trasu a Waze vám tak neumí nabídnout lepší alternativu.

Vy jste řidič

Waze nemůže nikdy vědět, že jedete "na zelené vlně", že je zrovna státní svátek v ČR atp. Může vám jen nabídnout radu, jaká by byla nejlepší cesta při zohlednění průměrných podmínek. Ale za volantem sedíte vy - a vy musíte rozhodnout na základě toho, co vidíte, jaká bude vaše cesta pro daný den.

Kdyby všichni sledovali cesty, kterými je Waze směruje, a nevydali se po nových silnicích, nemusel by se systém Waze nikdy dozvědět, že ta druhá trasa je ve skutečnosti efektivnější. Každá vaše jízda s Waze je analyzována a pomůže všem ostatním v navrhování optimální trasy. I v situacích, kdy jedete podle sebe a ignorujete návrhy Waze. Někdy budete mít pravdu. Někdy zjistíte, že jste pravdu neměli. Pokud jste pravdu neměli, budete příště hledat efektivnější trasu. A pokud jste pravdu měli, pomohli jste tím spoustě dalších uživatelů Waze.