Projekt - Teilnahme am ACM SIGSPATIAL Cup

Projektdokumentation
Teilnahme am ACM SIGSPATIL CUP 2012 im Zuge des Projektseminars
„Datenverwaltung“
Betreut durch Frau Prof. Dr. Agnès Voisard und Sebasti an Müller
Philipp Neuser – 05.09.2012
Abstract
This work develops an incremental algorithm for map matching. The algorithm is focused on
speed and accuracy. Multiple rules and approximations were developed to achieve a high
accuracy and short runtime at different GPS sampling rates. It was submitted to the ACM
SIGSPATIAL CUP 2012.
In dieser Arbeit wurde ein inkrementeller Algorithmus zum Map-Matching entwickelt. Der
Fokus bei der Entwicklung lag in der Geschwindigkeit und Genauigkeit. Es wurden mehrere
Regeln und Näherungen entwickelt, um dies bei verschiedenen Sampling-Raten von GPSTracks zu erreichen. Das Ergebnis wurde beim ACM SIGSPATIAL CUP 2012 eingereicht.
2
Inhaltsverzeichnis
1.
Einleitung ............................................................................................................................ 4
1.1
Aufgabenstellung und Ansätze ................................................................................... 5
2.
Eigener Ansatz .................................................................................................................... 7
3.
Ausarbeitung des Algorithmus zur Lösung ....................................................................... 10
3.1
Schwellwerte zur direkten Abbildung ....................................................................... 10
3.2
Zweistufiges Verfahren zur Filterung der Kantenrichtung ........................................ 11
3.3
Einbezug der Geschwindigkeit des Fahrzeugs .......................................................... 11
3.4
Gewichtungsfunktion ................................................................................................ 12
4.
Evaluation ......................................................................................................................... 14
5.
Literaturverzeichnis .......................................................................................................... 16
3
1. Einleitung
Das Projekt beinhaltet die Teilnahme am diesjährigen ACM SIGSPATIAL CUP 2012. Die
Aufgabenstellung des CUPs dieses Jahr ist es, einen Algorithmus zum MapMatching zu
entwickeln. Es geht hier darum, Daten von GPS-Tracks auf Straßen IDs in Open Street Map
(OSM) abzubilden. MapMatching hat in den letzten Jahren immer mehr an Bedeutung
gewonnen, da immer mehr Fahrzeuge GPS zur Navigation nutzen und Verkehrsleitsysteme
diese Daten nutzen, um Staus vorherzusagen, zu erkennen und entsprechende RoutingStrategien zu entwickeln sowie das Verhalten von Fahrern zu verstehen.
Es ist daher von großem Interesse, zuverlässige Algorithmen zu haben, welche die
gemessene Position auf Straßen abbilden. Um einen solchen Algorithmus zu entwickeln und
vergleichbare Bedingungen für alle Teilnehmer zu schaffen, wurden Trainingsdaten aus OSM
und diverse Tracks zu Trainingszwecken aus dem Großraum Washington zur Verfügung
gestellt. Die Daten beinhalten den Graph des Straßennetzes inkl. aller Knoten und
gerichteten Kanten, Geometrie-Informationen – sowie Straßentyp u. Name – der einzelnen
Kanten. Der zu entwickelnde Algorithmus soll eine möglichst konstante Qualität bei
verschiedenen Sampling-Raten der GPS-Daten haben. Die verschieden Trainingstracks sind
daher mit unterschiedlichen, nicht bekannten Sampling-Raten aufgenommen worden. (1)
Neben der Güte der Ergebnisse ist ein weiteres Bewertungskriterium im Wettbewerb die
Laufzeit des Algorithmus. Es sollen also schnell gute Ergebnisse geliefert werden. Die
Punktzahl ergibt sich durch folgende Formel (2):
For each output file Output_i.txt
{
For each row in Output_i.txt
{
If <EdgeId> is correct
Grade = Grade + <Confidence>
Else
Grade = Grade - <Confidence>
}
}
Grade = Grade/ExecutionTime
4
1.1
Aufgabenstellung und Ansätze
Es geht in erster Linie darum, eine GPS-Position – welche zu einem Zeitpunkt t gemessen
wurde – in Verbindung mit einer Straße oder einem Weg zu bringen. Die Distanz der
gemessen Position zu den umliegenden Straßen ist hier logischerweise der erste
Anhaltspunkt. Man vergleicht die verschiedenen Distanzen und wählt die nächstliegende
aus.
Betrachtet man immer nur eine einzelne Position, so bringt dies schon relativ gut Resultate.
Der tatsächliche Standort wird zumindest eine der nächstgelegenen Straßen/Wege sein,
welche man dem User z.B. als Auswahl präsentieren kann, damit er z.B. die nächstgelegene
Bushaltestelle finden kann. Bei der Analyse von GPS-Tracks, welche automatisiert analysiert
werden sollen, ist dieses Vorgehen allerdings nicht hinreichend genau. Es handelt sich bei
GPS-Tracks um Mitschnitte von den zurückgelegten Wegen (z.B. mit dem Auto). Der GPSEmpfänger hat hier in festen Abständen Samples (Positionen) gemessen und diese
Trajektorie gespeichert. Aus diesen Samples soll nun beim MapMatching die genaue Route
rekonstruiert werden, das heißt, welche Straßen genommen wurden und zu welchem
Zeitpunkt auf welche Straße abgebogen wurde.
Wird nun ein solcher Track nur über die Distanz auf die einzelnen Straßen abgebildet, so
stellt man einige Probleme im Bereich von Kreuzungen, parallel verlaufenden Wegen und allen voran - bei einem gerichteten Graphen beim Erkennen der richtigen Kante mit der
entsprechenden Richtung fest. Es wird hier schnell klar, dass eine Zuordnung allein über die
Distanz nicht ausreichend ist. Von Bernstein und Kornhauser wurde eine Artikel
veröffentlich, der einen guten Einstieg erlaubt. (3) Eine weiterführende Untersuchung der
auftretenden Probleme und einiger Algorithmen zur Behandlung dieser haben Christopher E
White, David Bernstein und Alain L Kornhauser veröffentlicht. (4)
Eine sehr akkurate Methode, die genommene Route auf der Karte abzubilden und die oben
genannten Probleme zu lösen, ist die Frechet Distanz. Mit der Frechet Distanz lässt sich die
Ähnlichkeit zweier Trajektorien bestimmen. Sie gibt die durchschnittliche Distanz einer
Trajektorie zur anderen an. Je kleiner sie ist, desto ähnlicher sind sich die beiden
Trajektorien. Map Matching – Algorithmen, die auf der Frechet Distanz basieren, gehen wie
folgt vor: Der GPS Track wird als Trajektorie betrachtet – entweder als Ganzes oder in
5
Teilstücke unterteilt. Aus dem Routing-Graphen und den dazugehörigen
Geometrieinformationen werden nun alle möglichen Trajektorien erzeugt und mit dem GPS
Track über die Frechet Distanz vergleichen. Diese Algorithmen sind allgemein gültig,
beruhen auf keinerlei Annahmen und sind sehr akkurat. Allerdings ist die Berechnung sehr
teuer (5), weswegen zur Erfüllung des zweiten Kriteriums (der Laufzeit) des Wettbewerbs
hier ein inkrementeller Ansatz verfolgt wird.
Bei geringen Sampling-Raten tritt das Problem auf, dass ggf. mehrere Routen zwischen den
Punkten möglich sind und mehrere Zuordnungen. Ein Ansatz zur Verbesserung ist hier,
mögliche Routen mit Routing-Algorithmen vorab zu berechnen und davon auszugehen, dass
der Fahrer eine der Routen nehmen wird. Es wird dann noch verglichen, welche Route am
wahrscheinlichsten in Frage käme bei den gemessenen Punkten. (6) (7)
6
2. Eigener Ansatz
Es ergeben sich im Wesentlichen folgende Problemsituationen, auf welche nun kurz
eingegangen werden soll.
An Abbiegungen ist es nicht klar, ab welchem Zeitpunkt die Punkte der neuen Straße
zugeordnet werden sollen. Man muss hier klare Regeln formulieren, wann die neue Straße
zur Zuordnung genommen wird.
Aus dem Problem bei den Abbiegungen ergibt sich ein viel eklatanteres, wenn man
Kreuzungen passiert. Wie man in Abbildung 1 sieht, werden, wenn sich das Fahrzeug der
Kreuzung nähert, die Messpunkte ab einem gewissen Zeitpunkt auf die kreuzende Straße
abgebildet. Obwohl das Fahrzeug die Kreuzung geradewegs passiert, entsteht hier eine
Reihe von Fehlern.
Abbildung 1: Die Messpunkte werden erst korrekterweise der roten Linie
zugeordnet, im Bereich der Kreuzung allerdings der blauen. Hier reicht eine
einfache Abbildung über die Distanz nicht mehr aus.
Laufen zwei Wege parallel zueinander oder ähnlich und nahe beieinander, zum Beispiel bei
Abzweigungen, wird es auch hier schwierig zu erkennen, auf welchem Weg das Fahrzeug
sich nun befindet. Man kann dies in Abbildung 2 leicht erkennen.
Abbildung 2: Falsche Zuordnung durch die Distanz, da die parallel verlaufende Straße
näher am Messpunkt ist.
7
Hinzu kommen die Messfehler des GPS. Diese können um +/- 10 Meter sein. Man muss
erkennen, ob es sich um einzelne Messfehler handelt oder gar eine systematisch falsche
Abbildung vorliegt. In Abbildung 3 ist ein Beispiel zu sehen, wo ohne weiteres Wissen über
den späteren Verlauf des Weges keine zuverlässige Zuordnung machbar ist. Kennt man nur
die aktuellen Messwerte, sind beide Zuordnungen logisch korrekt. Es müssen also der
weitere Verlauf und die Historie des Tracks in die Entscheidungsfindung einbezogen werden.
Ein spezieller Fall von zwei sich nahe liegenden Kanten existiert, wenn ein gerichteter Graph
des Straßennetzes vorliegt. So liegen zwei von ihrer Position, Länge und Verlauf identische
Kanten vor. Die korrekte Kante muss hier anhand der Bewegungsrichtung erkannt werden.
Sie lässt sich leicht über Betrachtung die Historie des Tracks erkennen.
Abbildung 3: Eine korrekte Zuordnung ist in diesem Fall nur mit Wissen über den späteren Verlauf möglich.
In Abbildung 4 (s. folgende Seite) ist die gemessenen GPS Position an einer Ampel zu sehen,
während das Fahrzeug steht. Der Messfehler von GPS ist klar zu erkennen, die ermittelte
Position wandert um +/-15 Meter nach vorne und nach hinten. Solch ein Verhalten muss
erkannt und herausgefiltert werden. Da sich hier durch das Wandern der gemessenen
Position und auch die Geschwindigkeit die vermeintliche Fahrtrichtung ständig ändert, muss
diese Verhalten herausgefiltert oder zumindest erkannt und entsprechend behandelt
8
werden. Ansonsten wird die Zuverlässigkeit sämtlicher Entscheidungen, die sich auf
Geschwindigkeit, Fahrtrichtung und Historie bzw. den weiteren Fortlauf des Tracks
beziehen, stark beeinträchtigt.
Abbildung 4: Die Messpunkte wandern bei stehendem Fahrzeug um die aktuelle Position durch Messfehler.
Bei langen Sampling-Intervallen von zum Beispiel 30 Sekunden oder länger wird es
zunehmend schwieriger, den originalen Pfad zu rekonstruieren und/oder richtige
Entscheidungen aufgrund der Historie zu treffen. Der Fahrer kann hier zwischen zwei
Messpunkten leicht schon mehrere Abschnitte hinter sich gelassen haben.
9
3. Ausarbeitung des Algorithmus zur Lösung
Der Algorithmus ist aus Gründen der Performance ein inkrementeller Algorithmus. Er schaut
sich also alle Messpunkte des GPS-Tracks nacheinander an. Um den zu bearbeitenden
Datenaufwand zu reduzieren, wird beim Einlesen des Tracks ein Rechteck um diesen gelegt wobei in alle Richtungen 1 Kilometer aufaddiert wird. Der nicht relevante Teil des Graphen
außerhalb wird abgeschnitten.
3.1
Schwellwerte zur direkten Abbildung
Der erste Ansatz betrachtete lediglich, ob ein Punkt auf einer Straße liegt, und wenn nicht,
welche Straße ihm am nächsten ist (siehe Abbildung 5). Zur Überprüfung, ob ein Punkt auf
der Straße liegt, wird um jede Kante ein Rechteck gelegt, dessen Breite abhängig vom
Straßentyp ist. Dieses Rechteck definiert somit Schwellwerte in den beiden Dimensionen,
die darüber entscheiden, ob der Punkt auf der Straße liegt. Die Werte, welche die besten
Ergebnisse lieferten, wurden statistisch ermittelt, indem sie variiert wurden und mit den
zehn Trainingstracks getestet wurden. Es wurden so für einen “motorway“ 32 Meter in der
Breite, für eine “primary road“ 24 Meter und für den Rest 16 Meter ermittelt. Um den Test
möglichst effizient zu gestalten, werden beim Einlesen bereits die Schwellwerte für jeden
Straßenabschnitt berechnet und die nötigen Werte für eine Koordinatentransformation
bestimmt, so dass der Ursprung im Mittelpunkt des Rechtecks liegt und das Rechteck
entlang der x-Achse orientiert ist. Ob ein Punkt die Schwellwerte nicht überschreitet, lässt
sich nach der Transformation der Koordinaten des Punktes durch einen einfachen “kleinerals-Test“ prüfen. Die Positionen, die so abgebildet sind, haben eine verschwindend geringe
Fehlerrate. Allerdings ließ sich so nur ein Bruchteil (ca. 20-30%) der Punkte zuordnen.
Abbildung 5: Die Distanz wird immer zum nächsten Punkt auf der Straße gemessen.
10
3.2
Zweistufiges Verfahren zur Filterung der Kantenrichtung
Bei der alternativen Zuordnung über die Distanz entstehen die nun angesprochenen
Probleme. Um diese in den Griff zu bekommen, wurde zunächst eine Funktion zur
Bestimmung der Orientierung der Straße und der Bewegung eingeführt. Zunächst wurde die
Funktion so implementiert, dass nur Kanten, die in die entgegengesetzte Richtung laufen,
nicht zugelassen sind. Dies hat schon entschiedene Verbesserungen gebracht. Eine genauere
Betrachtung zeigte dann, dass ein zweistufiges Verfahren bessere Ergebnisse liefert. Bei
einem normalen Verlauf darf die Orientierung der Kante nur um 15 Grad von der
Bewegungsrichtung abweichen. Ändert sich die Bewegungsrichtung um mehr als 15 Grad, so
wird das Limit auf 150 Grad hochgesetzt, da hier höchstwahrscheinlich eine Abbiegung oder
sehr enge Kurve vorliegt. Die korrekt abgebildeten Punkte konnten so auf ca. 60 Prozent
erhöht werden.
3.3
Einbezug der Geschwindigkeit des Fahrzeugs
Der nun verbleibende Großteil der falsch abgebildeten Messpunkte ergab sich an
Kreuzungen, wenn das GPS-Signal durch den Messfehler um das Fahrzeug wanderte. Hier
wurde vor allem die Funktion problematisch, welche die Kanten nach Bewegungsrichtung
filtert. Da auf die Bewegungsrichtung hier kein Verlass ist, wurden häufig die korrekten
Kanten nicht zugelassen, da das Fahrzeug zum Beispiel rückwärts zu fahren schien. Um
diesem zu begegnen, wird im Algorithmus die Geschwindigkeit des Fahrzeuges analysiert.
Steht das Fahrzeug, wobei hier die Definition ist, dass die Geschwindigkeit kleiner als 2 m/s
ist, so werden die Punkte auf den vorherigen Punkt zurückgeführt. Die Messung der
Richtung wird dann zwischen zwei Punkten vorgenommen, die mindestens 35 Meter
entfernt voneinander liegen (auch dieser Wert wurde durch Variation und Testen gegen die
Trainingtracks ermittelt). Das Verfahren ist in Abbildung 6 illustriert.
Abbildung 6: Vor der Optimierung wurde die Richtung immer durch den aktuellen Knoten und seinem
Vorgänger bestimmt. Wenn nun die Geschwindigkeit unter 8 m/s fällt, wird der Knoten genutzt, der
mindestens 35m entfernt ist.
11
3.4
Gewichtungsfunktion
Um Fehler im Bereich von Auf- und Abfahrten von Highways zu korrigieren oder bei
allgemein parallel verlaufenden Straßen, wo der parallel verlaufende Weg durch die
Messungenauigkeit gegebenenfalls näher an den einzelnen Positionen liegt, wurde eine
Gewichtungsfunktion eingebaut. Ein ähnlicher Ansatz wurde von Huabei Yin und Ouri
Wolfson vorgeschlagen. (8) Der Algorithmus gewichtet die Distanz der Graphen danach, wie
viele Knoten im Graph genommen werden müssten, um ein Kante zu erreichen. Kleinere
Wege, die parallel zum Highway verlaufen, bekommen so einen sehr niedrigen
Gewichtungsfaktor, wenn das Fahrzeug vorher auf dem Highway gefahren ist. Ebenso
anders herum. Der Gewichtungsfaktor w ist also bestimmt durch w = Anzahl der Hops zur
Kante. Damit dies auch bei Highway-Abfahrten seine entsprechende Wirkung entfacht, ist
hier noch eine weitere Gewichtung vorgesehen. Highway-Abfahrten sind nur gleich
gewichtet, wenn die Geschwindigkeit auch verringert wird. Dies führte in den Tests
allerdings zu keiner deutlichen Verbesserung mehr, da sich erst kurz vor Ende des
Wettbewerbs herausstellte, dass einige der Routen auf dem vorliegenden Graphen nicht
abbildbar waren, da hier Kanten fehlten.
Eine Übersicht über die aufgestellten Regeln und Schwellwerte gibt Tabelle 1.
12
Der Punkt liegt auf der Straße und kann direkt zugeordnet werden
Straßentyp
Schwellwert
Motorway
+/- 16m
primary road
+/- 12m
Other
+/- 8m
Filterung der in Frage kommenden Kanten anhand der Bewegungsrichtung
Änderung der Bewegungsrichtung zwischen
Erlaubte Abweichung der Kante
zwei Samples
<15°
<15°
>15°
<150°
Gewichtung der Möglichen Routen
Ermittlung der Anzahl der Hops (max. 6)
Distanz wird mit Anzahl der Hops multipliziert
Filterung von motorway_links
Geschwindigkeit um weniger als 40% gesunken
motorway_link nicht erlaubt
Tabelle 1: Übersicht über die aufgestellten Regeln
13
4. Evaluation
Der Algorithmus konnte zum Schluss bei den Test-Tracks eine durchschnittliche Fehlerrate
von 23,8 % erreichen, wie in Tabelle 1 zu sehen.
Trainingstrack Fehler #
Fehler/%
1
405
2355
17,2
2
300
1069
28,06
3
334
1565
21,34
4
385
1176
32,74
5
144
883
16,31
6
201
1016
19,78
7
569
2367
24,04
8
270
1134
23,81
9
553
1542
35,86
10
249
1319
18,88
Schnitt:
23,8
Tabelle 2: Durchschnittliche Fehlerrate ermittelt mit den Trainingstracks.
Durch die verschiedenen Filterungen konnten die stärksten Verbesserungen erlangt werden.
Insbesondere das Filtern der Kanten anhand der Bewegungsrichtung hat die Performance
deutlich verbessert. Das Betrachten des Verhaltens von Fahrzeugen, die vor einer Kreuzung
stehen, und die damit einhergehenden Messfehler konnten durch das Nicht-Werten dieser
Messpunkte und Angeben einer minimalen Distanz für die Ermittlung der
Bewegungsrichtung weitestgehend korrigiert werden.
Um die falsche Zuordnung bei parallel verlaufenden Straßen zu korrigieren, wurde eine
Bewertung des möglichen weiteren Streckenverlaufes und eine damit einhergehende
Bewertung und Gewichtung der Auswahl vorgenommen. Diese hat zu kleineren
Verbesserungen geführt, allerdings nicht zu einer vollständigen Lösung des Problems. Hier
besteht weiterer Verbesserungsbedarf. Ein sehr kritischer Punkt sind hier zum Beispiel die
Autobahnabfahrten, welche weiterhin oft falsch zugeordnet wurden. Auch die Betrachtung
des weiteren Streckenverlaufs mit der Gewichtung hat hier keine Verbesserungen gebracht,
da die Strecken oft genauso logisch erschienen. Kurz vor Ende der Abgabefrist wurde hier
auch bekannt, dass die mitgelieferten korrekten Tracks in dem gelieferten Graph keine
validen Pfade bildeten, was die Betrachtung des Streckenverlaufs vermutlich beeinträchtigt
hat.
Durch parallele Verarbeitung und die Beschneidung der Menge der Kanten anhand der
geographischen Relevanz für den Track konnte das Einlesen der kompletten
Straßennetzinformationen und die Berechnung des Matchings für alle zehn Trainingstrack
zusammen auf ca. 2 Minuten (Core i5 2,6 GHz, DualCore) gebracht werden. Die Zeit, welche
zur Bearbeitung nötig ist, hätte noch durch die Implementation von RangeQuery-Strukturen
verkürzt werden können, wie von J.L. Bentley und H.A. Maurer vorgeschlagen (9), was aber
14
innerhalb der Abgabefrist nicht mehr möglich war. Hier konzentrierte man sich auf die
Optimierung der Fehlerrate konzentriert.
Im ACM SIGSPATIAL Cup wurde Platz 10 von 31 belegt. Genauere Resultate werden erst im
Laufe der Konferenz bekannt gegeben.
15
5. Literaturverzeichnis
1. Introduction | ACM SIGSPATIAL Cup 2012. ACM SIGSPATIAL Cup 2012. [Online] 2012.
[Zitat vom: 12. 05 2012.] http://depts.washington.edu/giscup/home.
2. Submission and Evaluation | ACM SIGSPATIAL Cup 2012. ACM SIGSPATIAL Cup 2012.
[Online] 2012. [Zitat vom: 12. 05 2012.] http://depts.washington.edu/giscup/submission.
3. An Introduction to Map Matching for Personal Navigation Assitants. Berstein, David und
Kornhauser, Alain L. Newark : New Jersey TIDE Center, 1996.
4. Some map matching algorithms for personal navigation assistants. White, Christopher E,
Berstein, David und Kornhauser, Alain L. 1-6, s.l. : Transportation Research Part C: Emerging
Technologies, Frebruary-December 2000, Bd. 8, S. 91-108.
5. On Map-Matching Vehicle Tracking Data. Brakatsoulas, Sotiris, et al., et al. Trondheim,
Norway : s.n., 2005. Proceedings of the 31st VLDB Conference. S. 853-864.
6. Map-Matching for Low-Sampling-Rate GPS Trajectories. Lou*, Lin, et al., et al. s.l. : In
Proceedings of ACM SIGSPATIAL Conference on Geographical Information Systems (ACM
SIGSPATIAL GIS 2009), 2009.
7. Giovannini, Luca. A Novel Map-Matching Procedure for Low-Sampling GPS Data with
Applications to Traffic Flow Analysis. Bologna : Dipartimento di Fisica, 2011.
8. A Weight-based Map Matching Method in Moving Objects Databases. Yin, Huabei und
Wolfson, Ouri. Santorini Island : Proceedings of the 16th International Conference on
Scientific and Statistical Database Management, 2004. S. 437 - 438.
9. Efficient worst-case data structures for range searching. Bentley, J. L. und Maruer, H. A.
2, s.l. : Acta Informatica, Frebruary 1980, Bd. 13, S. 155-168.
16