FLYOVER: A Model-Driven Method to Generate Diverse Highway Interchanges for Autonomous Vehicle Testing

Yuan Zhou, Gengjie Lin, Yun Tang, Kairui Yang, Wei Jing, Ping Zhang, Junbo Chen, Liang Gong, Yang Liu

Abstract

Autonomous vehicle (AV) testing requires diverse and realistic environments, yet highway interchanges remain a significant bottleneck due to their topological and geometric complexity. This paper introduces FLYOVER, a model-driven framework that generates a massive, diverse dataset of highway interchanges. By integrating graph-based topology modeling with combinatorial sampling and evolutionary algorithms for geometry, FLYOVER produces thousands of unique scenarios. Evaluation using traffic and fuel consumption simulations demonstrates the framework's ability to reveal critical performance variations across different interchange designs.

Introduction

While autonomous vehicles (AVs) are expected to master highways first, highway interchanges remain a significant bottleneck. These areas are complex due to varying connection topologies (how ramps link roads) and geometries (the curves and slopes of those ramps). Currently, researchers face a "data drought" characterized by risky physical testing, simulation reliance on limited HD maps, and generative methods that lack diversity guarantees.

The FLYOVER Framework

The authors propose a three-stage pipeline called FLYOVER to bridge this gap. The framework automates the transition from real-world map data to high-fidelity, diverse 3D interchange models.

The FLYOVER pipeline: from interchange segmentation to sampling.

1. Topology Modeling & Classification

The system uses labeled digraphs to represent the "skeleton" of an interchange. Roads and ramps are nodes; connections are edges. Labels (like In-R or Out-L) describe exactly how a ramp merges or diverges. To ensure realism, topologies are extracted from real-world maps (e.g., 39 interchanges from Hangzhou, China) and grouped into 21 distinct "equivalence classes" using the VF2 isomorphism algorithm.

Interchange diagram and its corresponding topology graph representation.

2. Geometrical Feature Sampling

For each topology class, three key features are defined: the number of lanes, minimum ramp radius, and maximum longitudinal slope. To avoid the "curse of dimensionality," the framework employs k-way combinatorial coverage (specifically 2-way) to select a representative subset of parameters. This reduced a potential search space of 207 million combinations down to just over 1,400.

3. Concrete Interchange Generation

To turn these parameters into 3D roads, FLYOVER uses Bezier curves and splines. Differential Evolution (DE) optimization finds the best positions for curve control points, ensuring ramps are smooth and strictly follow radius and slope constraints.

Experimental Evaluation

The FLYOVER dataset consists of 1,443 unique highway interchange samples across 21 topology classes, exported in the industry-standard OpenDRIVE format.

Throughput Diversity

Testing in SUMO (Simulation of Urban MObility) revealed that "Cloverleaf" designs showed the highest throughput, while T-shaped interchanges were the most restrictive. Interestingly, differences in throughput only became statistically significant at high traffic densities, suggesting that "stress testing" requires high-volume simulation.

Fuel Consumption Sensitivity

Using Alibaba’s autonomous truck stack and TruckSim, researchers found that ramp radius and slope significantly impact fuel consumption. For instance, fuel consumption increases as up-ramp slopes become steeper and as minimum radii increase (due to longer travel distances). T-tests confirmed that even within the same topology class, geometric changes led to statistically significant differences in performance.

Conclusion

FLYOVER demonstrates that diversity must be measured at both structural (graph) and physical (geometric) levels. By efficiently generating test cases that catch performance edge cases, the framework provides a robust benchmark for AV testing. Future work will extend this model to complex urban intersections involving traffic lights and pedestrians.

Summary updated

BibTeX
@inproceedings{zhou2023flyover,
  author = {Yuan Zhou and Gengjie Lin and Yun Tang and Kairui Yang and Wei Jing and Ping Zhang and Junbo Chen and Liang Gong and Yang Liu},
  title = {{FLYOVER: A Model-Driven Method to Generate Diverse Highway Interchanges for Autonomous Vehicle Testing}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2023},
  doi = {10.1109/icra48891.2023.10160868},
}
Figure