Der Fahrdienst-Vermittler Lyft hat einen Algorithmus entwickelt, der die Open-Streetmap-Daten verbessert und berichtet in einem Blogpost darüber.
Laut einem Blogpost habe das Unternehmen tausende von Fehlern in Open Streetmap behoben. Das nicht ohne Eigennutz, denn Lyft verwendet, wie andere Anbieter auch, Open Streetmap (OSM) als Basis für das eigene Kartenmaterial. So misst das Unternehmen Wegdistanzen und errechnet die dafür benötigte Fahrzeit, lokalisiert Fahrer und Kunden und sucht die kürzesten Wege.
Allerdings ist das OSM-Material aus verschiedenen Gründen nicht vollständig, denn Städte verändern sich permanent. Einerseits fehlen alte und neu gebaute Straßen, wegen Bauarbeiten geschlossene Straßen sind wieder offen oder es gibt neue Gebäude. Zumindest für den Einsatzbereich, in dem sich die Lyft-Fahrer bewegen (meist urbane Innenstädte) kann Lyft das Material verbessern, weil die Lyft-Fahrer permanent Smartphone-Daten an das Unternehmen schicken.
Der von Lyft entwickelte Algorithmus (semi-interacting Multiple Model, sIMM) verbindet dabei einen Kalman-Filter (der ungebundene GPS-Daten erzeugt) mit einem Map-Matching-Algorithmus auf Basis des Hidden Markov Model (HMM). Lyft erfährt aus diesen Daten dann, ob die GPS-Positionen auf das in den Karten verzeichnete Straßennetz passen.
Zwei Fehlertypen
Dafür gibt es zwei Typen von Fehlermeldungen. Die erste erscheint, wenn ein Fahrer dort lang fährt, wo es laut OSM keine Straße gibt. Hier fehlen also Straßen in der Map und der Kalman-Filter kommt zum Einsatz. Der zweite Fehlertyp tritt dort auf, wo laut Map eine Straße existiert, aber der Fahrer eine andere Route nimmt, weil die Straße in der Realität nicht existiert oder nicht befahrbar ist (HMM). Beide Fehlermeldungen betreffen auch die Richtungen von Einbahnstraßen und die Existenz von Wendemöglichkeiten. Typ 1 zeigt also, wo Straßen auf der Karte fehlen, Typ 2 zeigt, ob Straßen in der Realität fehlen oder nicht befahrbar sind, die die Karte aber anzeigt.
Anhand der Unterschiede zwischen dem Kartenmaterial und dem von den Lyft-Fahrern gesendeten Daten erkennt Lyft so also Defizite und repariert sie in Open Streetmap. Beispiele aus Minneapolis und Details zu den Problemen beim Tracken von GPS-Daten erklärt der Blogpost. So funktioniert etwa die Typ-1-Fehlererkennung auf breiten Straßen oft nicht gut. Auch wenn die Karte in diesem Fall stimmt, aktiviert die Software häufig den Off-Road-Modus. Das liegt daran, dass OSM zwar ein Tag für die Breite von Straßen besitzt, dieses aber selten wirklich zum Einsatz kommt.
