A Multi-Dimensional Coverage Metric with Evolutionary Search for Safety-Critical Scenario Generation in Autonomous Driving Testing
Keywords:
autonomous driving testing, scenario generation, coverage metric, evolutionary searchAbstract
Ensuring autonomous driving safety requires rigorous testing across diverse and safety-critical scenarios. Manual scenario design is labor-intensive and insufficient in capturing edge cases, while random generation produces redundant test cases. This paper proposes a coverage-guided evolutionary search algorithm (CGES) for automated generation of safety-critical test scenarios with quantitative coverage assessment. A parameterized scenario representation is established based on six functional dimensions, and three complementary coverage metrics---scenario parameter space coverage (SPSC), behavioral diversity coverage (BDC), and risk-weighted fault mode coverage (RFMC)---are defined to quantify test adequacy. An adaptive evolutionary search strategy that incorporates risk-prioritized fitness evaluation and diversity-aware selection is designed to efficiently explore high-risk regions of the scenario space. Experiments on CARLA using five operational design domains demonstrate that CGES achieves 17.3% higher composite coverage and discovers 28.6% more unique safety violations than the baselines, while reducing redundant test cases by 41.2%. The proposed metrics provide a quantitative foundation for evaluating the completeness of autonomous driving test suites, contributing to standardized safety validation aligned with NHTSA regulatory requirements.References
1. S. Riedmaier, T. Ponn, D. Ludwig, B. Schick, and F. Diermeyer, "Survey on scenario-based safety assessment of automated vehicles," IEEE Access, vol. 8, pp. 87456–87477, 2020.
2. E. Thorn, S. Kimmel, and M. Chaka, "A framework for testable cases and scenarios for automated driving systems," National Highway Traffic Safety Administration, Report No. DOT HS 812 623, 2018.
3. S. Feng, Y. Feng, C. Yu, Y. Zhang, and H. X. Liu, "Testing scenario library generation for connected and automated vehicles, Part I: Methodology," IEEE Transactions on Intelligent Transportation Systems, vol. 22, no. 3, pp. 1573–1582, 2021.
4. U.S. Department of Transportation, Automated vehicles comprehensive plan, Office of the Secretary, 2021.
5. G. Li, Y. Li, S. Jha, T. Tsai, M. Sullivan, S. K. S. Hari, Z. Kalbarczyk, and R. Iyer, "AV-FUZZER: Finding safety violations in autonomous driving systems," in *Proceedings of the 31st IEEE International Symposium on Software Reliability Engineering (ISSRE)*, pp. 25–36, 2020.
6. Z. Zhong, G. Kaiser, and B. Ray, "Neural network guided evolutionary fuzzing for finding traffic violations of autonomous vehicles," IEEE Transactions on Software Engineering, vol. 49, no. 4, pp. 1992–2007, 2023.
7. H. Tian, G. Wu, J. Yan, Y. Jiang, J. Wei, W. Chen, S. Li, and D. Ye, "Generating critical test scenarios for autonomous driving systems via influential behavior patterns," in *Proceedings of the 37th IEEE/ACM International Conference on Automated Software Engineering (ASE)*, 2022.
8. S. Feng, H. Sun, X. Yan, H. Zhu, Z. Zou, S. Shen, and H. X. Liu, "Dense reinforcement learning for safety validation of autonomous vehicles," Nature, vol. 615, pp. 620–627, 2023.
9. C. Hildebrandt, M. von Stein, and S. Elbaum, "PhysCov: Physical test coverage for autonomous vehicles," in *Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA)*, pp. 449–461, 2023.
10. M. Cheng, Y. Zhou, and X. Xie, "BehAVExplor: Behavior diversity guided testing for autonomous driving systems," in *Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA)*, pp. 488–500, 2023.
11. D. J. Fremont, T. Dreossi, S. Ghosh, X. Yue, A. L. Sangiovanni-Vincentelli, and S. A. Seshia, "Scenic: A language for scenario specification and data generation," in *Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)*, 2019.
12. Y. Huai, S. Almanee, Y. Chen, X. Wu, Q. A. Chen, and J. Garcia, "scenoRITA: Generating diverse, fully mutable, test scenarios for autonomous vehicle planning," IEEE Transactions on Software Engineering, vol. 49, no. 10, pp. 4656–4676, 2023.
13. W. Ding, C. Xu, M. Arief, H. Lin, B. Li, and D. Zhao, "A survey on safety-critical driving scenario generation—A methodological perspective," IEEE Transactions on Intelligent Transportation Systems, vol. 24, pp. 6971–6988, 2023.
14. S. Kim, M. Liu, J. Rhee, Y. Jeon, Y. Kwon, and C. H. Kim, "DriveFuzz: Discovering autonomous driving bugs through driving quality-guided fuzzing," in Proceedings of the ACM Conference on Computer and Communications Security (CCS), 2022.
15. T. Zohdinasab, V. Riccio, A. Gambi, and P. Tonella, "DeepHyperion: Exploring the feature space of deep learning-based systems through illumination search," in *Proceedings of the 30th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA)*, 2021.
16. C. Xu, W. Ding, W. Lyu, Z. Liu, S. Wang, Y. He, H. Hu, D. Zhao, and B. Li, "SafeBench: A benchmarking platform for safety evaluation of autonomous vehicles," in *Advances in Neural Information Processing Systems (NeurIPS), Datasets and Benchmarks Track*, 2022.
17. D. Rempe, J. Philion, L. J. Guibas, S. Fidler, and O. Litany, "Generating useful accident-prone driving scenarios via a learned traffic prior," in *Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)*, pp. 17305–17315, 2022.
18. N. Hanselmann, K. Renz, K. Chitta, A. Bhattacharyya, and A. Geiger, "KING: Generating safety-critical driving scenarios for robust imitation via kinematics gradients," in Proceedings of the European Conference on Computer Vision (ECCV), LNCS Vol. 13698, Springer, 2022.
19. A. Guo, H. Sun, Y. Yao, S. Chen, Z. Zhang, Y. Liu, and X. Xie, "SoVAR: Building generalizable scenarios from accident reports for autonomous driving testing," in *Proceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering (ASE)*, 2024.
20. S. Feng, X. Yan, H. Sun, Y. Feng, and H. X. Liu, "Intelligent driving intelligence test for autonomous vehicles with naturalistic and adversarial environment," Nature Communications, vol. 12, Article 748, 2021.
