Kommentar von Dr. Dominik Jain und Dr. Julian Schauseil SLAM – Straßenkarten per KI und Fahrzeugflottendaten kontinuierlich aktualisieren

Anbieter zum Thema

Fujitsu Technology Solutions GmbH

Unsere Welt unterliegt einem stetigen Wandel. Das gilt im Besonderen für unser Straßennetz, welches aufgrund von Neubau, Umbau oder temporären Umstellungen sowohl topologischen als auch geometrischen Änderungen unterliegt.

Kartenanbieter vermessen das Straßennetz über spezielle Messfahrzeuge, die mit hochgenauer Sensorik spurgenaue Straßenverläufe und relevante Umgebungselemente wie Straßenschilder unmittelbar kartieren können. Ein flächendeckender, permanenter Einsatz solcher Fahrzeuge ist jedoch nicht praktikabel, weshalb Straßenkarten bereits am Tag ihrer Veröffentlichung veraltet sind. Gibt es eine Alternative?

Über Kameras und entsprechende Bildverarbeitungskomponenten nehmen aktuelle Fahrzeugmodelle z. B. Fahrbahnmarkierungen und -begrenzungen, Straßenschilder und Pfosten wahr. Zudem verfügen sie über GPS-Sensoren und Odometrie oder Dynamikdaten für absolute bzw. relative Lokalisierung. Abbildung 1 zeigt solche Sensordaten am Beispiel einer Fahrt über einen Autobahnabschnitt. Die Qualität einzelner Messungen ist dabei natürlich eine andere als bei einem Messfahrzeug. Außerdem sieht jedes Fahrzeug seine aktuelle Umgebung meist unvollständig, da andere Autos ihm die Sicht nehmen können und der Blickwinkel begrenzt ist. Durch die Kombination vieler solcher ungenauer und unvollständiger Daten kann man jedoch, wie wir im Folgenden aufzeigen, ein konsistentes, hochgenaues und aktuelles Bild der Welt erhalten.

Simultaneous Localisation and Mapping (SLAM)

Diese Aufgabe lässt sich als eine Instanz von Simultaneous Localisation and Mapping (SLAM) verstehen. SLAM-Probleme befassen sich mit der Frage, wie eine Umgebung, in der man sich bewegt und die über Sensoren wahrgenommen wird, kartiert werden kann, ohne dass man sich jedoch in dieser exakt lokalisieren könnte, wodurch zum Kartierungsproblem ein simultanes Lokalisierungsproblem hinzukommt. Mit SLAM beschäftigt man sich in der Robotik schon seit den 1980er-Jahren; man nutzt SLAM extensiv für die Navigation autonomer Agenten. Diese Problemkategorie ist daher gut verstanden und über die Zeit haben sich verschiedene Lösungsansätze entwickelt.

Das vorliegende Straßenkartierungsproblem lässt sich insbesondere durch die spezialisierte Form Graph-SLAM lösen, bei der das SLAM-Problem auf ein Inferenzproblem in einem probabilistischen grafischen Modell, einem Markov-Netz, reduziert wird. Die Zufallsvariablen in diesem grafischen Modell sind die Positionen der zu kartierenden Objekte (Fahrbahnbegrenzungen, Positionen von Straßenschildern, etc.) sowie die Fahzeugpositionen und -orientierungen (die sogenannten Posen), von denen aus diese Objekte durch die Fahrzeuge beobachtet werden. Jede Beobachtung einer Relativposition o = (x_o,y_o)^T eines Objekts durch ein Fahrzeug stellt eine Abhängigkeit zwischen zwei Zufallsvariablen her; der Pose A = (x_A,y_A,α_A)^T, von der aus beobachtet wird, und der Position B = (x_b,y_b)^T des beobachteten Objekts. Daraus ergibt sich ein Graph, genauer ein Markov-Netz, von Zufallsvariablen und Abhängigkeiten zwischen ihnen. Die Lösung des Graph-SLAM-Problems besteht schlicht darin, diejenige Belegung aller Zufallsvariablen (A und B) zu finden, die mit allen Messungen (o) am besten übereinstimmt.

Damit das Berechnungsproblem beherrschbar bleibt, machen wir die vereinfachende Annahme, dass allen Sensormessungen ein normalverteilter Fehler zugrunde liegt. Die Abhängigkeit zwischen einer Fahrzeugpose A und einer Objektposition B besteht dann also darin, dass sie über eine normalverteilte Relativposition verknüpft sind: Nehmen wir Σ_o als die Kovarianz an, die den Fehler der Messung wiederspiegelt, dann resultiert daraus die Verteilung

wobei die Funktion R eine Rotationsmatrix für den angegebenen Winkel liefert und die Funktion eo die Abweichung von der Messung (dem Mittelwert der Verteilung) für die Belegung der Variablen A und B liefert, d.h.

Die Verteilung ist als Beschränkung bezüglich möglicher Werte für A und B zu verstehen. Ihr Wert reflektiert den Grad, zu dem die Werte von A und B mit der Messung o übereinstimmen, und sie hat ihr Maximum für Belegungen, in denen die Relativposition genau o ist. Der Grad, zu dem Abweichungen davon als wahrscheinlich angesehen werden, hängt von der Kovarianzmatrix Σ_o ab, welche wir entsprechend den Sensoreigenschaften wählen.

Die optimale Belegung der Zufallsvariablen und damit die Lösung des Graph-SLAM-Problems können wir folgendermaßen bestimmen. Sei nun X die Menge aller Zufallsvariablen in unserem Markov-Netz und sei X die Menge aller möglichen Werte von X. Die Verteilung über X ist, für eine Menge von Beschränkungen {ϕ₁,…,ϕ_N}, die alle normalverteilte Dichtefunktionen wie oben sind und sich jeweils auf eine Teilmenge X_{k}⊂ X (typischerweise |X_{k}|≤ 2) beziehen, gegeben durch

Das Optimierungsproblem besteht darin, die wahrscheinlichste Belegung

zu finden, wobei n_k die Dimensionalität der k-ten Messung ist und e_k die Abweichung vom Messwert für die k-te Messung liefert (analog zu e_o oben). F_(x) ist eine Summe von quadrierten Mahalanobis-Distanzen und lässt sich effizient über nichtlineare Least-Squares-Methoden (z. B. Gauß-Newton) minimieren. Implementierungen hierfür sind in Bibliotheken wie g2o frei verfügbar. Die Lösung eines SLAM-Problems ist also technisch kein Problem, wenngleich die Probleme nicht beliebig groß werden dürfen.

Für unser Kartierungsproblem formulieren wir einfach alle Beschränkungen gemäß unserer Sensormessungen: Für die Beobachtung von Landmarken, wie z. B. Schildern oder Punkten auf Fahrbahnbegrenzungen, führen wir je eine Beschränkung zwischen einer Posen- und einer Positionsvariablen ein; für GPS-Messungen wird nur die zugehörige Posenvariable beschränkt; Relativbewegungsdaten beschränken zeitlich aufeinanderfolgende Posenvariablen. Das Optimierungsresultat x^* liefert uns die wahrscheinlichsten Positionen aller Landmarken – und damit die gesuchte Karte – sowie die wahrscheinlichsten Trajektorien der beobachtenden Fahrzeuge. Die Beobachtungen vieler Fahrzeuge komplementieren einander, und durch Mehrfachbeobachtungen derselben Objekte erhalten wir ein (hoffentlich) zuverlässigeres Bild der Realität.

Formulierung des Optimierungsproblems

Graph-SLAM-Probleme sind also lösbar. Das Problem in der Praxis besteht jedoch häufig darin, das richtige SLAM-Problem zu formulieren. Denn a priori kennen wir die Menge der Objekte, die wir kartieren müssen, nicht: Wir wissen nicht, wie viele Fahrspuren es wo auf der betrachteten Strecke gibt, wo Spuren sich aufspalten oder zusammengeführt werden, oder wie viele Schilder und Pfosten es gibt. Auch wissen wir nicht, welche Beobachtungen sich auf welche Kartenelemente beziehen, und sind dementsprechend mit einem harten Datenassoziationsproblem konfrontiert. Der Kern des Kartierungsproblems besteht daher darin, das richtige SLAM-Problem zu formulieren.

Beziehen sich zwei Schildbeobachtungen auf dasselbe oder zwei verschiedene Schilder? Zur Beantwortung solcher Fragen können wir iterativ vorgehen und das grafische Modell schrittweise um weitere Beschränkungen ϕ_k erweitern. Wir nutzen die Erkenntnisse aus dem jeweils vorangegangenen Optimierungsproblem, um neue Assoziationen zwischen Beobachtungen und Objekten zu knüpfen und neue Beschränkungen ϕ_k einzufügen.

Im ersten Schritt ist das Ziel, eine erste Hypothese für die Fahrzeugposen, von denen aus Landmarken beobachtet wurden, zu erhalten. GPS-Daten allein sind nicht hochfrequent genug verfügbar und außerdem zu ungenau. Deshalb formulieren wir das erste Optimierungsproblem, indem wir die absoluten GPS-Positionsdaten mit hochfrequenten Relativbewegungsdaten der Fahrzeuge (z. B. Odometriedaten) verknüpfen, um diese erste Hypothese für alle Fahrzeugtrajektorien zu erhalten. Die Trajektorien der einzelnen Fahrzeuge sind dabei noch unabhängig voneinander, da es keine Beobachtungen gibt, die eine Verknüpfung zwischen den Trajektorien herstellen würden.

Im zweiten Schritt ist genau jene Verknüpfung das Ziel: Wir wollen die Trajektorien über Beobachtungen derselben Objekte aneinander ausrichten (dies ist dringend notwendig, da die absoluten GPS-Positionsinformationen von Trajektorie zu Trajektorie einem systematischen Fehler unterliegen können, der mitunter den atmosphärischen Bedingungen zu den jeweiligen Fahrtzeitpunkten geschuldet ist.) Wir betrachten hierzu Kategorien von Landmarken, bei denen ein wiederholtes Auftreten in einem kleinen Umkreis extrem unwahrscheinlich ist: So ist es beispielsweise unwahrscheinlich, dass sich ein konkretes Straßenschild (wie z. B. eine Geschwindigkeitsbegrenzung auf 100 km/h) in Längsrichtung innerhalb weniger Meter wiederholt. Sehen also zwei Fahrzeuge ein solches Schild des gleichen Typs an Positionen, die, gegeben die voroptimierten Trajektorien aus dem ersten Schritt, nur wenige Meter auseinander sind, so handelt es sich mit hoher Wahrscheinlichkeit um dasselbe Schild, und das grafische Modell sollte im nächsten Schritt eine Positionsvariable enthalten, die mit den beobachtenden Posen der beiden Fahrzeuge über je eine Beschränkung modelliert wird. Die gemeinsam beobachteten Landmarken können wir über Clusteringverfahren finden; konkret verwenden wir hierfür agglomerative Clusteringverfahren. Fügen wir alle Positionsvariablen für neue Landmarken sowie die betreffenden Beschränkungen (zusätzlich zu denen aus Schritt 1) in das grafische Modell ein und führen anschließend eine Optimierung durch, so erhalten wir aneinander angeglichene Trajektorien; systematische Positionsfehler sind weitgehend nivelliert.

Im dritten Schritt haben wir also eine verlässlichere Ausgangsbasis für die weitere Kartierung aller Landmarken, die nicht „lokal einzigartig“ sind, also insbesondere alle Fahrbahnmarkierungen, Fahrbahnbegrenzungen, etc. Wir interessieren uns im Folgenden primär für die genauen Verläufe aller Fahrspuren und haben als Grundlage punktuelle Beobachtungen von Fahrbahnmarkierungslinien (Relativposition und Typ der Markierung, wobei erstere ungenau ist und zweitere falsch sein kann). Entlang einer Strecke kann sich naturgemäß an jedem Punkt die Fahrspurkonfiguration ändern, und wir wissen zunächst auch nicht, auf welchen Fahrspuren sich die Fahrzeuge tatsächlich bewegt haben. Wir verfolgen den Ansatz, Hypothesen für die Fahrspurkonfiguration (ohne Geometrie) mit den Beobachtungen zu vergleichen und eine Hypothese entsprechend dem Übereinstimmungsgrad mit den Daten zu bewerten. Wir diskretisieren den Straßenverlauf dazu in Fahrtrichtung und bauen die Hypothesen ebenso schrittweise in Fahrtrichtung auf: In jedem Schritt muss prinzipiell jede zulässige Änderung jeder Vorgängerfahrspurkonfiguration betrachtet werden. Der Hypothesenraum ist trotz Diskretisierung daher nicht handhabbar (er wächst exponentiell), weshalb wir eine Art inkrementelle Strahlsuche verwenden, welche nur hoch bewertete Vorgängerhypothesen weiterverfolgt. Unsere Hypothesenbewertung berücksichtigt drei Kernaspekte:

• Konsistenz: der Grad, zu dem die Typen der beobachteten Fahrbahnmarkierungslinien mit den Typen in der Hypothese übereinstimmen

• Abdeckung: der Grad, zu dem in der Hypothese vorkommende Markierungslinien tatsächlich beobachtet werden

• Räumliche A-priori-Übereinstimmung: der Grad, zu dem die beobachteten Lateralpositionen der Markierungslinien mit den Positionen übereinstimmen, an denen wir sie a priori erwarten würden, wobei die Erwartung für eine Hypothese mit k Begrenzungslinien über die Zentroide eines Clusterings der Lateralpositionen in k Cluster bestimmt wird

Für die Details verweisen wir auf unseren Beitrag auf dem IEEE Intelligent Vehicles Symposium 2019, welcher in einem Projekt mit BMW entstanden ist und in welchem wir den 3D-Kartierungsfall behandeln.

Abbildung 2 zeigt Ergebnisse für einen kleinen Straßenabschnitt auf der Autobahn A9 nach jedem der drei obengenannten Schritte vor dem Hintergrund des entsprechenden Satellitenbilds. Nach dem letzten Schritt erhalten wir ein Kartierungsergebnis der Fahrbahnbegrenzungen, bei dem die relativen Verhältnisse ziemlich gut mit dem Satellitenbild übereinstimmen. Es gibt eine leichte laterale sowie longitudinale Verschiebung, welche sehr wahrscheinlich auf Ungenauigkeiten in den GPS-Signalen zurückzuführen ist. Diese spielt jedoch für die allermeisten Anwendungsfälle von Straßenkarten keine große Rolle.

Chancen für die Zukunft

Mit diesem kurzen Einblick in Graph-SLAM und die konkrete Anwendung für die Kartierung von Straßen haben wir aufgezeigt, welche Herausforderungen es in der Praxis zu bewältigen gilt und wie ein Mix aus probabilistischer Inferenz, optimierender Suche und unüberwachtem maschinellem Lernen das Straßenkartierungsproblem mit Flottendaten lösbar machen kann.

Die zeitnahe Neukartierung von Straßen hat naturgemäß viele Anwendungen. Eine der relevantesten ist das autonome Fahren ab Stufe 3, das hochautomatisierte Fahren. Die Fahrzeuge fahren ab dieser Stufe selbstständig, wobei sie sich nicht nur auf ihre Sensorik, sondern auch auf hochgenaue Karten verlassen. Aktuelle Karten sind daher die Voraussetzung für die Freigabe von Strecken für das hochautomatisierte und autonome Fahren. Diejenigen Fahrzeughersteller, die ihre Fahrzeuge mit aktuelleren Karten versorgen können, sind daher auch in der Lage, in einem größeren Gebiet hochautomatisierte Fahrfunktionen anzubieten zu können, was einen direkten Wettbewerbsvorteil darstellen kann.

Im Kontext des autonomen Fahrens zeigen sich aber auch noch Herausforderungen. Während SLAM-Probleme auf Autobahnen und Landstraßen gut formulier- und lösbar sind, hat man es im innerstädtischen Bereich mit einer deutlich komplexeren Situation zu tun, wobei gleichzeitig die Qualität der Sensordaten schlechter ist. So sind die Straßentopologie und -geometrie komplexer, und es gibt deutlich mehr Landmarken, die auf engem Raum zusammenstehen, wodurch sie schwerer unterscheidbar sind. Zudem ist das GPS-Signal oft schwach oder verfälscht und Fahrbahnmarkierungen sind nicht vollständig oder durch stehenden Verkehr oder Vegetation verdeckt. Mit zunehmend besser werdender Sensorik – oder einer ausgebauten algorithmischen Trickkiste – werden jedoch auch diese Herausforderungen in Zukunft lösbar sein. Zum aktuellen Zeitpunkt ist verbesserte Sensorik für Serienfahrzeuge vielfach noch eine Frage der Kosten, weshalb Investitionen in Entwicklungsbudgets für künstliche Intelligenz eine wertvolle Option für die Automobilindustrie darstellen, funktionale Ziele schneller erreichen zu können.

Die Autoren

Dr. Dominik Jain und Dr. Julian Schauseil sind AI Research Scientists bei der Jambit GmbH in München. Sie arbeiten an Forschungs- und Vorentwicklungsprojekten aus den Bereichen Künstliche Intelligenz, maschinelles Lernen und Data Science.

(ID:46610330)