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

Abstract

It has become a consensus that autonomous vehicles (AVs) will first be widely deployed on highways. However, the complexity of highway interchanges becomes the bottleneck for deploying AVs. An AV should be sufficiently tested under different highway interchanges, which is still challenging due to the lack of available datasets containing diverse highway interchanges. In this paper, we propose a model-driven method, FLYOVER, to generate a dataset consisting of diverse interchanges with measurable diversity coverage. First, FLYOVER proposes a labeled digraph to model the topology of an interchange. Second, FLYOVER takes real-world interchanges as input to guarantee topology practicality and extracts different topology equivalence classes by classifying the corresponding topology models. Third, for each topology class, FLYOVER identifies the corresponding geometrical features for the ramps and generates concrete interchanges using k-way combinatorial coverage and differential evolution. To illustrate the diversity and applicability of the generated interchange dataset, we test the built-in traffic flow control algorithm in SUMO and the fuel-optimization trajectory tracking algorithm deployed to Alibaba's autonomous trucks on the dataset. The results show that except for the geometrical difference, the interchanges are diverse in throughput and fuel consumption under the traffic flow control and trajectory tracking algorithms, respectively.
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