Eindeutiger, Echtzeit- und präziser Kartenabgleich für mehrere Erfassungsquellen

In diesem Artikel wird ein schneller und eindeutiger Map-Matching-Algorithmus zur Rekonstruktion von Routen aus spärlichen GPS-Spuren vorgestellt. Im Gegensatz zu probabilistischen Methoden identifiziert er nur die Straßenabschnitte, die mit Sicherheit benutzt wurden, und vermeidet so jegliche Mehrdeutigkeit bei der Routenschätzung. Der Algorithmus verarbeitet effizient Spuren mit geringer Abtastrate und wurde mit realen und simulierten GPS-Daten aus London, Paris und Luxemburg getestet. Dabei erreichte er eine Genauigkeit von über 85 % bei einer Abtastzeit von bis zu 50 Sekunden. Es ist für Echtzeitanwendungen geeignet und bietet trotz GPS-Messfehlern eine robuste Leistung. Zukünftige Arbeiten werden sich auf die Verfeinerung des Algorithmus konzentrieren, indem die Abtastrate auf der Grundlage der lokalen Topographie dynamisch angepasst wird, um den Energieverbrauch in Crowd-Sensing-Anwendungen zu optimieren.

Intelligente Städte benötigen Echtzeitinformationen, um die Effizienz ihrer Verkehrssysteme zu verbessern. Insbesondere kann Crowd Sensing dabei helfen, die aktuelle Geschwindigkeit in jeder Straße, die überlasteten Bereiche usw. zu ermitteln. In diesem Zusammenhang sind Kartenabgleichsverfahren erforderlich, um eine Abfolge von GPS-Wegpunkten einem Satz von Straßen auf einer gemeinsamen Karte zuzuordnen. Leider sind die meisten Kartenabgleichsverfahren probabilistisch. Wir schlagen stattdessen einen eindeutigen Algorithmus vor, der in der Lage ist, alle möglichen Pfade zu identifizieren, die einer gegebenen Abfolge von Wegpunkten entsprechen. Wir benötigen eine eindeutige Identifizierung für jeden Wegpunktsatz. Zum Beispiel sollte die tatsächliche Geschwindigkeit fehlerfrei dem richtigen Straßensatz zugeordnet werden. Um alle möglichen Straßen zu identifizieren, bauen wir die Menge der Kandidaten iterativ auf. Wir identifizieren alle Kantenkandidaten um jeden Wegpunkt herum und rekonstruieren alle möglichen Unterrouten, die sie verbinden. Anschließend überprüfen wir eine Reihe von Beschränkungen, um unmögliche Routen auszuschließen. Die Straßenabschnitte, die allen berechneten Routen gemeinsam sind, bilden eine eindeutige Übereinstimmung. Wir bewerten die Trefferquote unserer Technik anhand von realen Stadtplänen (London, Paris und Luxemburg). Außerdem validieren wir unseren Ansatz mit einer echten GPS-Aufzeichnung in Seattle.