GPS Funktionalitet, anpassa vägvalet

[sejohas]

Hej,

Nedan stående inlägg hämtat från
http://forum.bmw-mc-klubben.se/forum/showthread.php?t=1610

Någon som har några ideer?

//
Stefan


Inför en europaresa nyligen så köpte jag mig en "riktig" GPS att montera på hojen. Jag var rätt trött på min handdator/GPS iQue 3600 där man inte kan lägga in rutter ens en gång. Så det blev en 276C. En funktion jag såg fram emot var funktionen "anpassat vägval", dvs möjlighet att styra preferens av vilka vägar man vill köra. Det fungerar så i GPS enheten att man har tre reglage, ett för stora vägar, ett för mellanstora vägar, ett för små vägar.
Vill man köra små vägar så är idén att man helt enkelt drar ner reglagen i botten för stora och medelstora vägar, medans småvägar dras upp till max prioritet. Jag har testat detta ett antal gånger men det tycks inte alls fungera. Dvs det blir ingen skillnad på hur rutten beräknas. Undvik motorvägar, kortast distans osv fungerar väl hyggligt iofs.
Någon som har erfarenheter? Något säger mig att denna funktion kanske inte finns i de europeiska City Select kartinformationen, utan bara i de amerikanska.

 

[apersson850]

Funktionen för att prioritera vissa sorters vägar lider av begränsningar i prestanda och minne hos mottagaren.
Om du sätter den till att priortera de största vägarna, är detta inget problem. Det är ju det normala, i vanliga fall.
Problemet uppstår när man vill prioritera mellanstora, eller ännu värre, mindre vägar. Dessa har en lägre "routing level", då de innehåller betydligt fler korsningar än motorvägar och riksvägar.

Eftersom ruttberäkningen sker genom att kartgrafen traverseras med en algoritm, som börjar räkna från både din position mot destinationen, och omvänt, samtidigt, går det åt betydligt mycket mer minne för att hålla ordning på de korsningar som finns, när man tar småvägar, med låg routing level, med i beräkningen.

Visserligen är beräkningen baserad på en girig algoritm, men inte fullt ut, för då skulle vissa vägval bli ännu dummare än vad de nu ändå blir ibland. Därför måste mottagaren hålla ordning på ett ganska stort antal alternativ, så att den kan utvärdera dessa, när beräkningen fortskridit en bit längre.
Som ett mellanresultat av detta får man två vågfronter, som närmar sig varandra. Dessa vågfronter består av noder i ruttdatagrafen, noder som mottagaren än så länge anser vara tänkbara att passera. När vågfronterna gått en bit in i varandra, så att man fått ett antal rutter som knutits samman, från start till mål, sker en utvärdering av vilken av dessa möjliga rutter som passar bäst mot de kriterier som användaren satt upp.

Om det nu är så, att användaren specifcerat önskemål om att följa små vägar, blir det ofta, för att inte säga nästan alltid, så att högsta antalet noder, som mottagaren kan hålla i minnet, överstigs innan vågfronterna slår ihop. I ett sådant fall överger GPS:n den ruttprioritering den har fått, och går upp till vägar med högre routing level, för att alls få ihop en rutt. Därför kan det ofta bli så, att alternativet med full prioritet på de största vägarna ger just det man önskar, medan full prioritet på de minsta vägarna ger samma resultat, dvs. rutten följer de största vägarna, eftersom minnet inte räcker till för något annat.
Även om minnet varit tillräckligt stort, kan det tänkas att processorn inte hade haft prestanda nog att utvärdera alla alternativ längs småvägarna inom rimlig tid.

Ett sätt att i högre grad få rutten att följa småvägarna är att sätta en viapunkt i rutten här och där. Beräkningen sker inom varje ruttsegment för sig, och oftast växer antalet möjliga noder med mer än kvadraten på avståndet mellan dem, så en futtig viapunkt på mitten kan göra stor skillnad för algoritmen. Räcker inte det, så sätt några till.

Detta har alltså ingenting alls att göra med vilken världsdel som kartan täcker.

Anders

 

[haraldn]

Tackar för den utförliga redogörelsen. Jag kan väl säga att jag har fått vatten på min kvarn. Det är bättre att välja väg själv, åtminstone om man ska ut på småvägar. Om jag ska ut på okända småvägar så brukar jag se ut en väg på kartan. Sedan sätter jag brytpunkter i GPS:en vid de korsningar som jag tror kan vara svåra att snabbt identifiera och länkar ihop dem till en rutt. Det räcker ju att få veta var man ska byta väg. Man behöver ingen GPS för att hålla sig på vägen. Den kan väl snarare ha motsatt effekt i värsta fall.

 

[thureb]

Samma begränsingar på PC?

Anders utläggning ovan var intressant och kan vara en förklaring till mina erfarenheter med ruttberäkning på PC i Mapsource Euroguidekarta för cykel och rullskridskoturer.

Är det samma typ av problem när man beräknar rutten på en PC?

Jag har också använt knepet att lägga in delmål för att få in just den rutt jag önskar som jag sedan laddar ned i GPSen.

Thure

 

[apersson850]

Det finns naturligtvis en begränsning, även när man kör på en PC. Fast den har ju vanligtvis betydligt mer resurser att tillgå, eftersom en sådan procssor, som brukar sitta i dagens hemma-PC, skulle gluffa i sig alldeles för mycket ström, för att vara användbar i en batteridriven manick.

Nu stödjer ju inte Mapsource, än så länge, denna möjlighet till "Custom routing", så det är inte så lätt att jämföra.

Informationen har jag för övrigt fått från ett samtal med en av de programmerare, som skrivit algoritmen, när han jobbade på Garmin. Så jag har god anledning att tro att den är vederhäftig.
Nu jobbar han inte där längre, så han kan därför tala lite friare, om somliga saker.

Anders

 

[jonasolof]

Anders, det du skrev om hur ruttberäkningen sker leder till "pseudounderstanding" (intern antydning mellan oss) men det vore roligt att få veta mer. Låt den pedagogiska ådran flöda!

 

[apersson850]

Jag håller på med att skriva en artikel om detta, dvs hur ruttberäkning sker i Garmins GPS. Den kommer att publiceras på http://www.gps.no när den blir färdig. Det tar nog några veckor till.

Tills vidare vill jag helst inte gå in på området i större detalj här, för det intresserar troligen inte tillräckligt många, och det tar upp ett utrymme här, som ett vanligt meddelande inte har plats för.

Den vetgirige rekommenderas att söka på exempelvis "grafteori" och "Dijkstras algoritm" på internet.
Utöver detta finns det en del ytterligare lök på laxen, där vissa av finesserna är patenterade av Garmin.

Anders

 

[thureb]

Flagga här

Jag tror att konsekvenserna av detta kan intressera ganska många här på forumet. Flagga gärna när din artikel är utlagd Anders.

Thure

 

[apersson850]

Nu finns artikeln om ruttberäkning i Garmins GPS på http://www.gps.no

Anders

 

[Brune]

Hela länken

Hela länken är http://www.gps.no/anm/templates/?a=863&z=2 för så småningom ligger inte artikeln på förstasidan.

Per

 

[apersson850]

Tur att det finns någon som tänker lite längre än näsan räcker.

Tack.

Anders

 

[johanj]

Inställning av hastighet

Hej

Mycket intressant artikel, har undrat över detaljerna i Garmins ruttberäkning en längre tid. Däremot undrar jag fortfarande om de hastigheter jag manuellt knappar in på de olika vägtyperna i MapSource följer med över till GPS:n när jag laddar över kartor etc. eller är hastigheterna i GPS:n låsta till något standardvärde? Dvs. kan jag påverka ruttberäkningen i GPS:n genom att uppdatera hastigheterna i Mapsource?

Hänger ni med?

/Johan