Assessing the Similarity of Traffic Scenarios Using Graph Neural Networks

Motivation

Validating automated driving functions requires billions of kilometers of testing. Scenario-based testing is a cost-effective alternative, but working with large datasets of real-world or synthesized traffic scenarios demands a deeper understanding of their varieties and dynamics. Existing clustering and classification methods rely on hand-crafted features and expert knowledge, which limits scalability to diverse scenario types and urban settings.

Graph Representation of Traffic Scenarios

This project proposes a flexible graph representation for traffic scenarios built on the CommonRoad framework. Each scenario is encoded as a graph where:

Nodes represent traffic entities with type-specific attributes:

• Lanelet nodes — Road structure (object type, ID)
• Static obstacle nodes — Fixed obstacles (position, orientation)
• Dynamic obstacle nodes — Vehicles over time (position, velocity, steering angle, per time step)
• Ego vehicle nodes — The automated vehicle’s trajectory over time

Edges encode pairwise relationships using predicates:

• isAdjacent — Lanelet connectivity (successor, predecessor, lateral adjacency)
• isNextState — Temporal trajectory links between time steps of the same vehicle
• isBehind — Longitudinal following relationship on the same or merging lanelets
• unsafeDistance — Safe distance rule violations, indicating critical situations
• onLanelet — Spatial relationship between vehicles/obstacles and road segments

Deep Divergence Graph Kernels (DDGK)

The graph representations are processed using an unsupervised framework called Deep Divergence Graph Kernels, which learns similarity embeddings without requiring labeled data or known node alignments.

The framework operates in several stages:

1. Graph encoding — A Node-to-Edges encoder is trained per source graph to predict each node’s neighbors, learning the graph’s structural representation
2. Cross-graph attention — An isomorphism attention mechanism aligns nodes between graphs of different sizes, enabling comparison of structurally different scenarios
3. Attribute consistency — Regularization losses preserve node and edge attribute alignment during cross-graph comparison
4. Divergence scoring — The augmented encoder’s prediction loss on a target graph serves as a divergence score: low divergence indicates structural similarity, high divergence indicates dissimilarity

Each target graph is embedded as a vector of divergence scores against a population of source graphs, forming a kernel space suitable for downstream tasks.

Experiments & Results

Lanelet Structure Similarity

Using 80 CommonRoad scenarios (labeled Critical or Comfort) with 8 source graph encoders:

• Hierarchical clustering successfully grouped scenarios by lanelet complexity — simpler structures (fewer nodes/edges, uniform edge distribution) separated from complex “spiky” structures
• SVM classification on the learned embeddings achieved 95% accuracy distinguishing Critical vs. Comfort scenarios using 10-fold cross validation

Combined Lanelet Structure & Vehicle Behavior

Using scenarios generated from the HighD naturalistic highway dataset, incorporating vehicle trajectories, interaction predicates, and lanelet structure:

• Hierarchical clustering separated scenarios by vehicle interaction patterns — clusters with unsafeDistance edges (critical following behavior) grouped distinctly from those without
• SVM classification achieved 75% accuracy on Critical vs. Comfort labels, with room for improvement through richer node attributes (position, velocity, orientation)

Tools & Technologies

• PyTorch — DDGK implementation (graph encoders, attention networks, training pipeline)
• CommonRoad — Traffic scenario framework and dataset conversion
• NetworkX — Graph construction, manipulation, and visualization
• Matplotlib — Embedding visualization and clustering dendrograms
• scikit-learn — SVM classification and hierarchical clustering