Abstract
Ensuring pedestrian-safety is paramount to the acceptance and success of autonomous cars. The scenario-based training and testing of such self-driving vehicles in virtual driving simulation environments has increasingly gained attention in the past years. A key challenge is the automated generation of critical traffic scenarios which usually are rare in real-world traffic, while computing and testing all possible scenarios is infeasible in practice. In this paper, we present a formal method-based approach CriSGen for an automated and complete generation of critical traffic scenarios for virtual training of self-driving cars. These scenarios are determined as close variants of given but uncritical and formally abstracted scenarios via reasoning on their non-linear arithmetic constraint formulas, such that the original maneuver of the self-driving car in them will not be pedestrian-safe anymore, enforcing it to further adapt the behavior during training.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
OpenDS scenarios are described in specific XML files from which such behaviors can be extracted.
- 2.
This disallows maneuvers in which a car drives slowly by, say, 1 m/s, and decelerates by 2 m/s, thus reversing its motion direction. Reversing the sense of direction should be described by decelerating to a stop and a further deceleration for driving backwards.
- 3.
The units do not really matter as long as they are kept consistent throughout the specification.
- 4.
This can trivially be described as a quantifier elimination problem.
- 5.
\(\epsilon \) compensates minor differences between the computed reachable states and the driving simulator’s behavior.
- 6.
Evidently, for any \(0\le c\le a\le 10\) the corresponding instantiation is behavior equivalent to the original scenario. Therefore the safe (green) variants form the top-left triangle instead of a single point.
- 7.
Note that in this illustration the unsafe region and the original region do not intersect, since cutting the area with the plane at \(b=1\) produces exactly Fig. 5.
References
Althoff, M., Lutz, S.: automatic generation of safety-critical test scenarios for collision avoidance of road vehicles. In: Proceedings of the 29th IEEE Intelligent Vehicles Symposium (IV) (2018)
Aréchiga, N.: Specifying safety of autonomous vehicles in signal temporal logic. In: Proceedings of the 30th IEEE Intelligent Vehicles Symposium (IV) (2019)
Bouton, M., Nakhaei, A., Fujimura, K., Kochenderfer, M.J.: Safe reinforcement learning with scene decomposition for navigating complex urban environments. In: Proceedings of the 30th IEEE Intelligent Vehicles Symposium (IV) (2019)
Damm, W., Kemper, S., Möhlmann, E., Peikenkamp, T., Rakow, A.: Traffic sequence charts - from visualization to semantics. Technical report, AVACS (2017)
DFKI: OpenDS. https://opends.dfki.de/
Dolzmann, A., Sturm, T.: Redlog. http://www.redlog.eu
Dolzmann, A., Sturm, T., Weispfenning, V.: Real quantifier elimination in practice. In: Matzat, B.H., Greuel, G.M., Hiss, G. (eds.) Algorithmic Algebra and Number Theory. Springer, Heidelberg (1999). https://doi.org/10.1007/978-3-642-59932-3_11
Eggers, A., Stasch, M., Teige, T., Bienmüller, T., Brockmeyer, U.: Constraint systems from traffic scenarios for the validation of autonomous driving. In: Proceedings of Symbolic Computation and Satisfiability Checking (2018)
Frassinelli, D., Gambi, A., Nürnberger, S., Park, S.: DRiVERSITY - synthetic torture testing to find limits of autonomous driving algorithms. In: Proceedings of the 2nd ACM Computer Science in Cars Symposium (CSCS) (2018)
Fremont, D.J., Dreossi, T., Ghosh, S., Yue, X., Sangiovanni-Vincentelli, A.L., Seshia, S.A.: Scenic: a language for scenario specification and scene generation. In: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). ACM (2019)
Groh, K., Kuehbeck, T., Fleischmann, B., Schiementz, M., Chibelushi, C.C.: Towards a scenario-based assessment method for highly automated driving functions. In: Proceedings of the 8th Conference on Driver Assistance (2017)
Henzinger, T.A., Rusu, V.: Reachability verification for hybrid automata. In: Henzinger, T.A., Sastry, S. (eds.) HSCC 1998. LNCS, vol. 1386, pp. 190–204. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-64358-3_40
Jesenski, S., Stellet, J.E., Schiegg, F., Zöllner, J.M.: Generation of scenes in intersections for the validation of highly automated driving functions. In: Proceedings of the 30th IEEE Intelligent Vehicles Symposium (IV) (2019)
Klischat, M., Althoff, M.: Generating critical test scenarios for automated vehicles with evolutionary algorithms. In: Proceedings of the 30th IEEE Intelligent Vehicles Symposium (IV) (2019)
Lamport, L.: Hybrid systems in TLA+. In: Grossman, R.L., Nerode, A., Ravn, A.P., Rischel, H. (eds.) HS 1991-1992. LNCS, vol. 736, pp. 77–102. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-57318-6_25
Menzel, T., Bagschik, G., Isensee, L., Schomburg, A., Maurer, M.: From functional to logical scenarios: detailing a keyword-based scenario description for execution in a simulation environment. In: Proceedings of the 30th IEEE Intelligent Vehicles Symposium (IV) (2019)
Pusse, F., Klusch, M.: Hybrid online POMDP planning and deep reinforcement learning for safer self-driving cars. In: Proceedings of the 30th IEEE Intelligent Vehicles Symposium (IV). IEEE (2019)
Queiroz, R., Berger, T., Czarnecki, K.: GeoScenario: an open DSL for autonomous driving scenario representation. In: Proceedings of the 30th IEEE Intelligent Vehicles Symposium (IV) (2019)
Wachi, A.: Failure-scenario maker for rule-based agent using multi-agent adversarial reinforcement learning and its application to autonomous driving. In: Proceedings of International Joint Conference on Artificial Intelligence (IJCAI) (2019)
Yaghoubi, S., Fainekos, G.: Gray-box adversarial testing for control systems with machine learning components. In: Proceedings of the 22nd ACM International Conference on Hybrid Systems: Computation and Control (HSCC) (2019)
Acknowledgement
This research was supported by the German Federal Ministry for Education and Research (BMB+F) in the project REACT.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Nonnengart, A., Klusch, M., Müller, C. (2020). CriSGen: Constraint-Based Generation of Critical Scenarios for Autonomous Vehicles. In: Sekerinski, E., et al. Formal Methods. FM 2019 International Workshops. FM 2019. Lecture Notes in Computer Science(), vol 12232. Springer, Cham. https://doi.org/10.1007/978-3-030-54994-7_17
Download citation
DOI: https://doi.org/10.1007/978-3-030-54994-7_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-54993-0
Online ISBN: 978-3-030-54994-7
eBook Packages: Computer ScienceComputer Science (R0)