📊 statistics

A Graph-based Framework for Coverage Analysis in Autonomous Driving

Dieses Paper schlägt ein graphbasierter Framework für die Abdeckungsanalyse des autonomen Fahrens vor, das Verkehrsszenen als hierarchische Graphen darstellt und sowohl Subgraph-Isomorphie mit Archetypen-Matching als auch GINE-basierte Einbettungen einsetzt, um komplexe Interaktionen zwischen Akteuren effektiv zu erfassen und die Systemsicherheit über diverse reale sowie synthetische Szenarien hinweg zu validieren.

Ursprüngliche Autoren: Thomas Muehlenstädt, Marius Bause

Veröffentlicht 2026-02-03

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Thomas Muehlenstädt, Marius Bause

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, einem Roboter das Autofahren beizubringen. Bevor Sie ihn auf die echten Straßen loslassen, müssen Sie sicherstellen, dass er genug für jede mögliche Situation geübt hat, der er begegnen könnte. Dies wird als Coverage-Analyse bezeichnet: die Überprüfung, ob der Roboter genug verschiedene Arten von Verkehr gesehen hat, um sicher zu sein.

Das Problem mit aktuellen Methoden besteht darin, dass sie Verkehrssituationen meist einzeln betrachten, als würde man Artikel auf einer Einkaufsliste abhaken. Sie prüfen vielleicht separat: „Ist ein Auto vor mir?“ und dann „Ist ein Auto links von mir?“. Aber echter Verkehr ist chaotisch und vernetzt; Autos existieren nicht einfach isoliert, sie interagieren auf komplexe Weise miteinander.

Dieses Paper schlägt einen neuen Weg vor, Verkehr zu betrachten: als eine lebendige, atmende Karte von Verbindungen.

Die Kernidee: Das „Soziale Netzwerk“ des Verkehrs

Anstatt nur Autos aufzulisten, verwandelt die Autorenschaft eine Verkehrsszene in einen Graphen. Stellen Sie sich einen Graphen wie ein soziales Netzwerkdiagramm vor:

Die Knoten (Punkte): Dies sind die Akteure – die Autos, Fußgänger und Radfahrer.
Die Kanten (Linien): Dies sind die Beziehungen zwischen ihnen. Folgt Auto A dem Auto B? Fährt Auto C in der entgegengesetzten Spur? Fährt Auto D neben Auto E beim Spurwechsel?

Die Autoren bauen diesen Graphen in zwei Schichten auf:

Die Kartenschicht: Dies ist die statische Straße selbst. Sie weiß, welche Spuren miteinander verbunden sind, wo sich Kreuzungen befinden und welche Straßen in entgegengesetzte Richtungen führen.
Die Akteursschicht: Dies ist der dynamische Verkehr. Sie verbindet die beweglichen Fahrzeuge mit der Karte und untereinander, basierend darauf, wer in der Nähe von wem ist.

Sie verwenden einen intelligenten „Zwei-Phasen“-Konstruktionsalgorithmus, um diesen Graphen aufzubauen. Stellen Sie sich einen Türsteher im Club vor:

Phase 1 (Der Scan): Der Türsteher betrachtet alle und notiert jeden, der potenziell relevant ist (z. B. „Dieses Auto ist 100 Meter entfernt, vielleicht ist es wichtig“).
Phase 2 (Der Filter): Der Türsteher bereinigt dann die Liste. Wenn Auto A mit Auto B verbunden ist und Auto B mit Auto C, erkennt der Türsteher, dass keine direkte Linie zwischen A und C gezeichnet werden muss. Die Verbindung wird bereits durch B impliziert. Dies entfernt „redundante“ Linien und hält das Diagramm sauber und effizend.

Methode 1: Der „Musterabgleich“ (Subgraph Isomorphism)

Sob. sie diese komplexen Verkehrsgraphen erstellt haben, ist die erste Methode, die sie anwenden, wie ein Mustererkennungsspiel.

Stellen Sie sich vor, Sie haben ein Deck mit „Archetypen-Karten“. Jede Karte zeigt eine klassische Verkehrssituation, wie zum Beispiel „Zwei Autos fahren nebeneinander“ oder „Ein Auto schneidet vor ein anderes“.

Das System nimmt eine echte Verkehrsszene (einen großen, chaotischen Graphen) und fragt: „Enthält diese Szene eines meiner Archetypen-Karten?“
Es nutzt einen mathematischen Trick namens Subgraph Isomorphism, um zu finden, ob das kleine Muster innerhalb des großen Chaos existiert.
Das Ergebnis: Sie können sagen: „In unseren Testdaten haben wir 90 % unserer ‚Vordrängler‘-Karten gesehen, aber nur 10 % unserer ‚Komplexen Kreuzung‘-Karten.“ Dies zeigt ihnen genau, wo in ihren Trainingsdaten Lücken klaffen.

Methode 2: Der „Magische Übersetzer“ (Graph Embeddings)

Die zweite Methode ist technologisch anspruchsvoller. Sie verwendet eine Art von KI, ein Graph Neural Network (speziell eines namens GINE).

Betrachten Sie diese KI als einen universellen Übersetzer, der komplexe Verkehrsszenen in einfache Koordinaten auf einer Landkarte (einen Vektorraum) umwandelt.

Wenn zwei Verkehrsszenen sich sehr ähnlich sehen (z. B. beide beinhalten ein Auto beim Spurwechsel auf einer regnerischen Autobahn), übersetzt die KI sie in Punkte, die auf dieser Karte sehr nah beieinander liegen.
Wenn zwei Szenen völlig unterschiedlich sind, liegen die Punkte weit auseinander.
Der Vorteil: Dies ermöglicht es den Forschern, die „Form“ ihrer Daten zu betrachten. Sie können Cluster ähnlicher Szenarien erkennen und „leere Zonen“ identifizieren, in denen keine Daten existieren. Es ist, als würde man auf eine Sternenkarte schauen und feststellen: „Hey, da ist ein riesiger dunkler Fleck am Himmel, an dem keine Sterne auftauchen.“

Das Experiment: Reale Welt vs. Simulation

Um dies zu testen, verglichen die Autoren zwei Datensätze:

Argoverse 2.0: Reale Daten, die von echten selbstfahrenden Autos in sechs US-Städten aufgenommen wurden.
CARLA: Ein Computersimulator, der künstliche Verkehrsszenen generiert.

Sie ließen ihr Graph-Framework auf beiden laufen und fanden einige interessante „Coverage-Lücken“:

Die fehlenden Kreuzungen: Der Simulator (CARLA) war gut im einfachen Autobahnfahren (Autos folgen einander), aber er war schlecht bei komplexen Stadtkreuzungen. Ihm fehlten viele der „Multi-Auto-Tanz“-Szenarien, die im echten Leben vorkommen.
Die Geschwindigkeitslücke: Selbst wenn der Simulator doch ein Szenario hatte, das einem realen ähnelte, waren die Geschwindigkeiten oft falsch. Der Simulator erfasste nicht die spezifischen Geschwindigkeiten von Autos in bestimmten Situationen.
Die Kombinationslücke: Im echten Verkehr passieren oft mehrere Dinge gleichzeitig (z. B. ein Auto folgt einem anderen, während gleichzeitig eine Kreuzung passiert). Der Simulator generierte diese komplexen Kombinationen selten.

Warum das wichtig ist

Die Autoren kommen zu dem Schluss, dass ihr graphbasierter Rahmen ein mächtiges Werkzeug ist, weil:

Er skaliert: Es spielt keine Rolle, ob 2 oder 20 Autos in der Szene sind; der Graph verarbeitet dies auf natürliche Weise.
Er effizient ist: Er benötigt keine maßgeschneiderte Regel für jede einzelne Art von Unfall oder Szenario. Er betrachtet einfach die Verbindungen.
Er das Unsichtbare findet: Er kann nicht nur fehlende Szenarien aufspüren, sondern auch fehlende Kombinationen von Szenarien und subtile Unterschiede im Verhalten (wie die Geschwindigkeit).

Kurz gesagt: Sie haben einen neuen Weg entwickelt, den Verkehr zu „sehen“, indem sie ihn als ein vernetztes Geflecht von Beziehungen statt als eine Liste isolierter Objekte behandeln, was Ingenieuren hilft, genau zu finden, wo das Training ihres selbstfahrenden Autos noch Defizite aufweist.

Technische Zusammenfassung: Ein graphbasierter Rahmen zur Abdeckungsanalyse im autonomen Fahren

Problemstellung
Die Validierung der Sicherheit autonomer Fahrsysteme erfordert eine rigorose Abdeckungsanalyse, um sicherzustellen, dass das System über seinen gesamten Operational Design Domain (ODD) hinweg getestet wurde. Bestehende Ansätze bewerten Abdeckungsfaktoren typischerweise einzeln oder in begrenzten Kombinationen (z. B. 2–3 Faktoren) und haben Schwierigkeiten, die komplexen, hochdimensionalen Interaktionen zu erfassen, die in realen Verkehrsszenen inhärent sind. Darüber hinaus verlassen sich traditionelle Methoden oft auf Zufallsstichproben oder erfordern szenenspezifische Handhabungsregeln, die sich nicht effizient auf vielfältige Verkehrsbedingungen skalieren lassen. Es besteht ein Bedarf an einem Framework, das Verkehrsszenen systematisch repräsentiert, komplexe Akteur-Interaktionen erfasst und skalierbare Abdeckungsmetriken bereitstellt, ohne dass eine manuelle, fallweise Definition jedes einzelnen Szenarios erforderlich ist.

Methodik
Das Paper schlägt ein graphbasiertes Framework vor, das Verkehrsszenen als hierarchische Graphen darstellt und die statische Karten-Topologie mit dynamischen Akteur-Beziehungen integriert. Die Methodik besteht aus drei Kernkomponenten:

Hierarchische Graphkonstruktion:
- Karten-Graph: Ein gerichteter Multigraph ( $G_{map}$ ) kodiert das Straßennetz, wobei Knoten Längssegmenten und Kanten räumliche Beziehungen (Folgen, Nachbar, Gegenüber) darstellen.
- Akteur-Graph: Ein zweiphasiger Algorithmus konstruiert den dynamischen Graphen ( $G_{actor}$ $G_{a c t or}$ ) für spezifische Zeitschritte.
  - Phase 1 (Beziehungsentdeckung): Identifiziert potenzielle Beziehungen zwischen Akteur-Paaren basierend auf Distanzschwellenwerten und der Konnektivität der Karte. Zu den Beziehungen gehören Konfigurationen wie Fahren vor/hinter (Leading/Following), Nachbar (Neighbor) und Gegenüber (Opposite).
  - Phase 2 (Hierarchische Konstruktion): Erstellt den endgültigen Graphen durch Hinzufügen von Kanten in einer Prioritätsreihenfolge (Leading/Following > Neighbor > Opposite), während Redundanzen vermieden werden. Wenn bereits ein Pfad zwischen zwei Akteuren innerhalb einer definierten Knotendistanz existiert, wird keine direkte Kante hinzugefügt. Dies stellt sicher, dass der Graph rechentechnisch handhabbar bleibt, während die notwendige Konnektivität gewahrt bleibt.
- Temporäre Erweiterung: Das Framework unterstützt zeitindexierte Graphen, bei denen Kanten zeitabhängig sind, was die Darstellung sich ändernder Zustände (z. B. Spurwechsel) und den Umgang mit erscheinenden oder verschwindenden Akteuren ermöglicht.
Abdeckungsanalyse via Subgraph-Isomorphie:
- Dieser Bottom-up-Ansatz definiert eine Menge manuell kuratierter „Archetyp“-Graphen, die häufige Fahrszenarien repräsentieren (z. B. ungeschützte Linksabbiegevorgänge, Einschneidemanöver, Platoons).
- Unter Verwendung des VF2-Algorithmus prüft das System, ob ein Subgraph eines Verkehrsszenen-Graphen isomorph zu diesen Archetypen ist.
- Dies ermöglicht die Berechnung von Knoten-Abdeckungsprozenten sowie die Analyse von Ko-Okkurrenz-Mustern (welche Archetypen gemeinsam auftreten) und parametrischen Verteilungen (Geschwindigkeit, Pfadlänge) innerhalb spezifischer Szenariotypen.
Abdeckungsanalyse via Graph-Embeddings:
- Dieser Top-down-Ansatz nutzt Graph Isomorphism Networks mit Edge-Features (GINE), um Verkehrsszenen-Graphen in einen kontinuierlichen Vektorraum zu projizieren.
- Das Modell wird mittels selbstüberwachtem kontrastivem Lernen auf Mini-Batches von Graphen trainiert. Die Datenaugmentation erfolgt durch die Perturbation kontinuierlicher Attribute (Geschwindigkeit, Pfadlänge) und das zufällige Weglassen von Kanten.
- Die resultierenden Embeddings ermöglichen eine Ähnlichkeitsbasierte Abdeckungsbewertung, Clustering und Anomalieerkennung, ohne dass explizite Szenariodefinitionen erforderlich sind.

Wesentliche Beiträge

Vereinheitlichte Graph-Repräsentation: Ein neuartiges Framework, das Karten-Topologie und Akteur-Beziehungen in eine einzige hierarchische Graphstruktur kombiniert, die explizit für die Abdeckungsanalyse entwickelt wurde.
Zwei-Phasen-Konstruktionsalgorithmus: Eine systematische Methode zur Erfassung räumlicher Beziehungen unter Vermeidung redundanter Kanten, was die Skalierbarkeit auf Szenen mit variierenden Anzahlen von Akteuren sicherstellt.
Dual-Mode-Analyse: Die Integration zweier komplementärer Methoden:
- Subgraph-Isomorphie: Bietet interpretierbare, feingranulare Abdeckungsmetriken gegenüber vordefinierten Archetypen.
- Graph-Embeddings: Bietet eine skalierbare, unüberwachte Methode zur Ähnlichkeitsbewertung und Anomalieerkennung in hochdimensionalen Räumen.
Gap-Analyse-Framework: Ein strukturierter Ansatz zur Identifizierung von „Definitionslücken“ (Abdeckungslücken) durch den Vergleich von struktureller Präsenz, parametrischen Verteilungen und Ko-Okturrenz-Mustern zwischen Datensätzen.

Ergebnisse
Das Framework wurde unter Verwendung von Realdaten aus dem Argoverse 2.0-Datensatz und synthetischen Daten aus dem CARLA-Simulator (Town01–07) validiert.

Ergebnisse der Subgraph-Isomorphie:
- Die gesamte Knotenabdeckung über beide Datensätze hinweg betrug 62 %.
- Signifikante strukturelle Lücken wurden identifiziert: CARLA unterrepräsentierte komplexe Multi-Akteur-Intersektionsszenarien (z. B. erschien ein „Cut-out“ an Kreuzungen in 8,2 % der Argoverse-Szenen, gegenüber 0,3 % in CARLA).
- Die parametrische Analyse zeigte, dass CARLA selbst dann, wenn strukturelle Archetypen vorhanden waren, oft versagte, spezifische Geschwindigkeitsbereiche abzudecken, die in realen Daten üblich sind (z. B. moderate bis hohe Geschwindigkeiten bei Spurwechseln).
- Die Ko-Okkurrenz-Analyse zeigte, dass CARLA es an realistischen Kombinationen von Archetypen mangelte, wie etwa simultanen Folgen- und Überholmanövern.
Ergebnisse der Graph-Embeddings:
- Das GINE-Modell projizierte Verkehrsszenen erfolgreich in einen latenten Raum, in dem die euklidische Distanz mit der Szenenähnlichkeit korrelierte.
- Dimensionsreduktion (PCA und t-SNE) visualisierte distinkte Cluster für CARLA- und Argoverse-Szenarien, was bestätigte, dass das Modell zwischen den Datensätzen unterscheiden und verschiedene Simulationsumgebungen abbilden kann.
- Die Embeddings demonstrierten die Fähigkeit, strukturelle und parametrische Unterschiede ohne explizites Subgraph-Matching zu erkennen, was ihren Einsatz für die skalierbare Abdeckungsbewertung unterstützt.

Bedeutung und Ansprüche
Das Paper behauptet, dass das vorgeschlagene Framework signifikante Vorteile gegenüber traditionellen Methoden der Abdeckungsanalyse bietet:

Skalierbarkeit: Es skaliert effizient auf diverse Verkehrsszenarien, ohne dass szenenspezifische Handhabungsregeln oder die manuelle Definition jedes Testfalls erforderlich sind.
Flexibilität: Es kann nativ mit variierenden Anzahlen von Akteuren in einer Szene umgehen, wodurch die Notwendigkeit entfällt, Teilnehmer auszuschließen oder sich auf willkürliche Teilmengen zu konzentrieren.
Komplementarität: Durch die Kombination der Interpretierbarkeit von Subgraph-Isomorphie mit der Skalierbarkeit von Graph-Embeddings bietet das Framework ein robustes Werkzeug zur Identifizierung von Abdeckungslücken sowohl in strukturellen als auch in parametrischen Dimensionen.
Validierungsnutzen: Der Ansatz etabliert eine Methode, um zu verifizieren, ob synthetische Simulationsdaten (wie CARLA) die Verteilung von Realdaten (wie Argoverse) adäquat abdecken, was handlungsrelevante Erkenntnisse für die Verbesserung von simulationsbasierten Test-Pipelines liefert.

Die Autoren merken an, dass die aktuelle Arbeit zwar auf manuell definierten Archetypen basiert, zukünftige Arbeiten jedoch die automatische Extraktion dieser Archetypen aus Realdaten und die Integration temporaler Informationen in die Graphstruktur untersuchen werden.