Einigkeit statt kleinster Quadrate: Zuverlässige Navigation durch maximalen Konsens

Projekt: Robuste Lokalisierung von Fahrzeugen mit Hilfe der Maximum Consensus Methode

Forschende: M.Sc. Jeldrik Axmann, apl. Prof. Dr.-Ing. Claus Brenner

Projektidee: Moderne Fahrzeuge erzeugen sehr viele Messdaten, die dazu verwendet werden können, ihre eigene Position genau zu bestimmen. Unter den Daten befinden sich jedoch sehr viele fehlerhafte Messungen, die identifiziert und ausgeschlossen werden müssen. In diesem Projekt wird ein besonders robuster Ansatz hierfür untersucht, die sogenannte Maximum Consensus Methode.

Positionsbestimmung als wichtiger Baustein automatisierter Fahrzeuge

Maximum Consensus – das klingt nach einem römischen Legionär in einem Asterix-Comic oder nach einer ganz besonderen Spielart höherer Diplomatie. Für automatisierte Fahrzeuge bedeutet Maximum Consensus aber Sicherheit: Diese Methode sorgt dafür, dass sich die Fahrzeuge ihrer Position im Straßenverkehr sicherer sein können. Denn für automatisierte und autonome Fahrzeuge ist die exakte Kenntnis der eigenen Position von großer Bedeutung.

Dafür haben diese Fahrzeuge verschiedenste Sensoren im Einsatz: Das sind üblicherweise Kameras, Radar, Ultraschall und LiDAR (Light Detection And Ranging) Sensoren. Heutzutage am bekanntesten ist aber wohl die Ortung über globale Navigationssatellitensysteme (GNSS). Allerdings kann diese Methode die hohen Anforderungen autonomer Systeme nicht durchgängig erfüllen. Insbesondere in Städten, in denen die Signale der Satelliten an manchen Stellen nicht durch die Häuserschluchten durchdringen (siehe GeoWerkstatt Februar 2020) bietet es sich an, die aktuellen Sensordaten zusätzlich mit einer digitalen Karte zu vergleichen. Dadurch kann die Position sehr genau und unabhängig von GNSS Empfangsverhältnissen ermittelt werden.

Der erste Akt: Erstellung einer Karte

Digitale Kartenwerke lassen sich heute auf jedem Smartphone aufrufen, beispielsweise die Karten der Vermessungsverwaltungen, kommerzielle Karten für (Fahrzeug-) Navigationssysteme und kollaborativ erstellte Karten wie OpenStreetMap. Allerdings sind diese Karten für die hochgenaue Lokalisierung nur bedingt geeignet, da sie in der Regel zu ungenau sind und die wahren Gegebenheiten abstrahieren (sogenannte Generalisierung). Deshalb ist für die Lokalisierung eigenes Kartenmaterial nötig: Häufig kommen dafür spezielle Mobile Mapping Fahrzeuge zum Einsatz, die über Kameras, LiDAR und eine hochgenaue Ortung mittels GNSS verfügen (Abb. 1, links).

LiDAR Sensoren, umgangssprachlich auch als Laserscanner bezeichnet, senden Lichtimpulse aus, die von Objekten wie etwa Häusern, Bäumen oder Autos in der Umgebung reflektiert werden. Misst man die Zeit vom Aussenden des Lichtimpulses bis zum Empfang des reflektierten Lichtimpulses, kann man die Entfernung des Sensors zu den Objekten bestimmen— und zwar, je nach LiDAR System, bis auf wenige Millimeter genau. LiDAR Systeme besitzen den Vorteil, dass sie selbst in großen Entfernungen noch genau messen können und relativ unempfindlich gegenüber Beleuchtungs- und Witterungsbedingungen sind. Die mit LiDAR und anderen Sensoren entstehenden Datensammlungen der Mobile Mapping Systeme sind nicht unbedingt „Karten“ im herkömmlichen Sinne. Oft sind es nur Punktwolken, Ansammlungen der bei der Kartierung gewonnenen Messpunkte (Abb. 2, links). Sie repräsentieren die Umgebung sehr genau und sehr dicht. Daher ist es nicht nötig, die Messdaten manuell (und mit hohen Kosten verbunden) in eine „herkömmliche“ Karte zu überführen.

Der zweite Akt: Hochgenaue Lokalisierung

Die spezielle Mobile Mapping-Karte kann nun dem automatisierten Fahrzeug helfen, seine Position exakt zu bestimmen. Dafür sind die LiDAR Sensoren (Abb. 1, rechts) des Fahrzeug nötig. Sie sind erheblich preisgünstiger als die Mobile-Mapping-Sensoren und besitzen eine geringere Auflösung und Genauigkeit (Abb. 2, rechts). Das Grundprinzip ist ganz einfach: Die LiDAR Daten, die das Fahrzeug während der Fahrt aufnimmt, werden so verdreht und verschoben, dass sie mit der Karte des Mobile Mapping-Systems bestmöglich zur Deckung gebracht werden. So ist dann die genaue Position und Orientierung des Fahrzeugs möglich.

Robuste Lokalisierung: Die Maximum Consensus Methode

Doch was bedeutet „bestmöglich zur Deckung bringen“? Da sowohl bei der Kartierung mit dem Mobile Mapping-System, als auch bei der Lokalisierung mit den Fahrzeug-Sensoren Messfehler auftreten, kann eine exakte Deckung niemals erreicht werden. Klassische Lokalisierungsverfahren führen daher eine Fehlerminimierung durch, in der Regel eine „kleinste Quadrate“ Minimierung, die das Mittel aller quadratischen Abweichungen minimiert. Dadurch können sehr genaue Ergebnisse erzielt werden. Doch bei belebten Straßen reicht das nicht aus - außer Messfehlern treten hier auch massenhaft sogenannte Ausreißer auf: Autos in der Karte, die inzwischen umgeparkt wurden, Büsche und Bäume, die kräftig gewachsen sind oder gestutzt wurden, Baustellen, Gerüste, renovierte Fassaden, Außengastronomie — die Liste möglicher Veränderungen ist lang. Damit die Lokalisierung nicht nur genau, sondern auch robust funktioniert, müssen die Ausreißer identifiziert und entfernt werden.

Hier betritt nun die Maximum Consensus Methode die Bühne! Sie bevorzugt die Lösung, die durch die meisten Messungen „erklärt“ wird: Sie zählt lediglich die Messungen, die „passen“ und wählt die Lösung mit der größten Anzahl — also die Lösung mit dem maximalen Konsens.

Wie man sich die Zählung vorstellen muss, ist in Abb. 3 illustriert. Die ersten beiden Reihen zeigen LiDAR Messungen des Fahrzeugs zur Lokalisierung in jeweils zwei Ansichten (die zugehörigen Karten sind nicht gezeigt). In der dritten Reihe der Abbildung ist das „Zählergebnis“ für verschiedene mögliche Positionen des Fahrzeugs dargestellt, der sogenannte Akkumulator. In der linken Spalte sieht man eine Straßenkreuzung. Diese Situation führt im Akkumulator zu einer entsprechenden Struktur zwei sich kreuzender Linien. Dort, wo sich die Linien schneiden, befindet sich die Fahrzeugposition, welche zu den meisten Messungen „passt“. Schaut man sich die rechte Spalte an, sieht man, dass eine einfache Straßenschlucht zu einem linienförmigen Signal im Akkumulator führt. Das deutet darauf hin, dass die Position des Fahrzeugs quer zur Fahrbahn sehr viel besser bestimmt ist als längs der Fahrbahn.

Der Vorteil der Maximum Consensus Methode ist die enorme Robustheit: selbst mit mehr als 50% Ausreißern kommt sie in der Regel zurecht. Ein Nachteil ist der erhöhte Optimierungsaufwand. Beides untersuchen wir in diesem Projekt.