Kartmatchning med en andra ordningens dold Markovmodell

I INGs forskningsseminarieserie höll Efraim Laksman den 22 maj 2012 ett seminarium om sin forskning om Kartmatchning. Forskningen är en spin-off från forskning som med stöd av NetPort och Kapsch utfördes inom Arena 2, och som berörde elektroniska vägavgifter.

Kartmatchning är ett problem som går ut på att bestämma en korrekt position baserat på tillgång till karta och mätningar störda av brus. Att kunna utföra kartmatchning, d. v. s. att bestämma var fordon befinner sig och vilken väg det är mest sannolikt att ett fordon kört är av stort intresse, inte bara för privatpersoner som vill veta var på en karta de befinner sig, utan även för att t. ex. stödja utvecklingen av praktiska lösningar för elektroniska vägavgifter. Vi utgår från en satellitbaserad positioneringsteknik med GPS-mottagare som då och då mäter positionen och i Figur 1 finns ett exempel på ett vägnät med tillhörande mätpunkter. Beräkningen av den mest sannolika positionen efter en mätning – givet att mest sannolika position vid föregående mätning redan beräknats – måste beräknas inom en tidsram som är oberoende av antal tidigare mätningar, annars klarar inte algoritmen av att uppdatera förarens position när rutten blir för lång.

Det finns åtskilliga algoritmer för att lösa problemet med kartmatchning, och vår algoritm hamnar inom den kategori som kallas sannolikhetsbaserade. Den skiljer sig dock från tidigare sannolikhetsbaserade algoritmer på området, främst genom att använda en andra ordningens dold Markovmodell (HMM), istället för en första ordningens HMM som tidigare algoritmer inom området gjort. Det innebär att algoritmen kan ta hänsyn till korrelation av brus vid konsekutiva mätningar. Med en första ordningens HMM baseras algoritmen på att bruset är vitt, trots att det är välkänt att så inte är fallet.

 Figur: Exempel av vägnät och mätpunkter. Varje mätpunkt har även en tidsstämpel
som inte visas i bilden.