Automated vehicles are assumed to play an important role in the future of mobility, but their operation must be provably safe. They consist of automated driving systems (ADSs) that perform various automated driving tasks without the active participation of a human driver. These automated driving tasks can be mainly categorized as perception, decision-making, and motion control. These tasks must be accomplished by the components of an ADS, which must be seamlessly integrated to ensure safety. The complexity of the ADS architecture makes the safety assessment rather challenging. This complexity is further exacerbated when automated vehicles need to interact in different traffic situations. Design, verification, and testing of ADSs as simulation models provide a safer and cost-efficient early development opportunity compared to real-world testing. To this end, a capable simulation framework that incorporates the simulation models of ADSs must be developed for designing, implementing, and testing these models in a traffic simulation.
The main contributions of this thesis are denoted as (i), (ii), and (iii). Safety assessment of ADS can be done either experimentally by (i) simulation-based testing in (ii) a simulation framework or theoretically (iii) using formal methods. Simulation-based testing requires two components: (i) efficient testing strategies for different ADS components and (ii) a simulation framework containing the models of ADS components for applying these testing strategies. Simulation-based testing alone cannot prove or guarantee safety. In order to complement the safety assessment process, whenever applicable, (iii) formal methods must be utilized to derive theoretical safety proofs for certain types of systems for a set of assumptions. Formal methods for synthesis include methods such as correct-by-construction of control protocols and reachability analysis for dynamic systems, which can be used to design provably safe decision-making and control algorithms. The correct-by-construction synthesis of discrete control protocols can be used as safety filters for decision-making algorithms, such as autonomous intersection management algorithms, to verify the safety of taken actions. The reachability analysis is useful for predicting trajectories for possible maneuvers in a finite time horizon for an automated vehicle on a highway. By over-approximating these ego vehicle trajectories, safety verification of possible maneuvers can be done by comparing them to the possible trajectories of other vehicles. A game-theoretical decision-making approach, such as minimax, can augment safety in maneuver planning by considering the worst-case situations up to a finite time horizon. Such an online maneuver planning algorithm reconsiders the maneuvers at each planning cycle in a receding horizon fashion. However, to apply formal methods, certain assumptions must be made about complex parts of ADSs, and therefore, simulation-based testing is still needed to check the validity of these assumptions in simulation models. Safety assessment with a holistic approach is presented that combines the previously mentioned contributions of this thesis (i), (ii), and (iii) into a workflow of modeling, design/synthesis, and testing. Such an approach is essential for developing safe algorithms for ADSs in a simulation framework.:Kurzfassung v
Abstract vii
Contents ix
1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Scope of the Thesis . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Research Questions . . . . . . . . . . . . . . . . . . . . . . . 2
1.4 Structure of the Thesis . . . . . . . . . . . . . . . . . . . . . 3
2 Safety Assessment of Automated Driving Systems - State of
the Art 5
2.1 State of the Art . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 Definition of ADS . . . . . . . . . . . . . . . . . . . . 5
2.1.2 Meaning of Safety for ADS . . . . . . . . . . . . . . . 8
2.1.3 Testing for Safety . . . . . . . . . . . . . . . . . . . . 12
2.1.4 Simulation Frameworks for ADSs and AVs . . . . . . 14
2.1.5 Roles of Formal Methods . . . . . . . . . . . . . . . . 16
2.2 Challenges and Contributions . . . . . . . . . . . . . . . . . 18
2.2.1 Challenges in the State-of-the-Art . . . . . . . . . . . 18
2.2.2 The Contributions . . . . . . . . . . . . . . . . . . . 21
3 Simulation-based Testing using Fault Injection 23
3.1 Related Work and Preliminaries . . . . . . . . . . . . . . . . 24
3.1.1 Fault Injection . . . . . . . . . . . . . . . . . . . . . 24
3.1.2 Fault Types and Parameters . . . . . . . . . . . . . . 27
3.1.3 Testing for ADS safety using FI . . . . . . . . . . . . 30
3.1.4 Metrics and Specifications for Safety Evaluation . . . 33
3.1.5 Simulative Error Propagation Analysis . . . . . . . . 35
3.2 Developing a Testing Strategy using Fault Injection . . . . . 36
3.2.1 Automated Testing . . . . . . . . . . . . . . . . . . . 37
3.2.2 Using Domain-specific Knowledge . . . . . . . . . . . 40
3.2.3 Smart Testing Strategy . . . . . . . . . . . . . . . . . 41
3.3 Application of Testing Strategies . . . . . . . . . . . . . . . 42
3.3.1 Testing of ACC Systems for Fault Tolerance using Fault
Injection . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.3.2 Discovering Fault Parameter Space using Smart Testing
Strategy . . . . . . . . . . . . . . . . . . . . . . . 48
3.4 General Functionalities for Efficient Tools . . . . . . . . . . . 52
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4 A Framework for Simulating Automated Driving Systems in
Traffic 55
4.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.1.1 Levels of Detail in Traffic Simulation . . . . . . . . . 56
4.1.2 Traffic Simulations and Scenario-based Testing . . . . 59
4.1.3 Generic ADS Architecture . . . . . . . . . . . . . . . 64
4.2 Preliminaries and Definitions . . . . . . . . . . . . . . . . . . 65
4.2.1 Map and Path Planning . . . . . . . . . . . . . . . . 66
4.2.2 Decision Making and Trajectories . . . . . . . . . . . 67
4.2.3 Vehicle Motion Control . . . . . . . . . . . . . . . . . 68
4.3 Mapping the ADS structure into a Simulation Model . . . . 72
4.3.1 Sensor-based Perception . . . . . . . . . . . . . . . . 72
4.3.2 V2X Communication . . . . . . . . . . . . . . . . . . 73
4.3.3 Global Path Planner . . . . . . . . . . . . . . . . . . 75
4.3.4 Behavioral Planner/Maneuver Planner . . . . . . . . 78
4.3.5 Longitudinal and Lateral Motion Control . . . . . . . 80
4.4 Interfaces and Layering between Modules . . . . . . . . . . . 81
4.4.1 Relations between Discrete Decision-Making and Continuous
Control . . . . . . . . . . . . . . . . . . . . . 82
4.4.2 Vehicles and the Infrastructure - Autonomous Intersection
Management . . . . . . . . . . . . . . . . . . . . 83
4.5 Instantiating a Model-based Traffic Simulation . . . . . . . . 86
4.5.1 Traffic Simulation Environment Architecture . . . . . 88
4.5.2 Road Network and the Map Format . . . . . . . . . . 91
4.5.3 Scenario-based Traffic Simulation as Test Cases . . . 95
4.5.4 Overview of the Simulation Framework with Fault Injection
. . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.6 Case Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.6.1 Urban Traffic Simulations . . . . . . . . . . . . . . . 101
4.6.2 Fault-Error-Failure Chain Analysis for Safety Assessment
. . . . . . . . . . . . . . . . . . . . . . . . . . . 103
4.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5 Using Formal Methods for Safe Algorithms Design 111
5.1 Control Protocol Synthesis . . . . . . . . . . . . . . . . . . . 111
5.1.1 Related Work and Preliminaries . . . . . . . . . . . . 111
5.1.1.1 Finite State Transition Systems . . . . . . . 112
5.1.1.2 Linear Temporal Logic and Büchi Automaton 113
5.1.1.3 Correct-by-Construction Control Protocol
Synthesis . . . . . . . . . . . . . . . . . . . 114
5.1.2 Application in an Autonomous Intersection Management
Algorithm . . . . . . . . . . . . . . . . . . . . . 116
5.1.2.1 Modeling the Intersection and the Behaviors
of the Vehicles . . . . . . . . . . . . . . . . 116
5.1.2.2 Specifications for Synthesis . . . . . . . . . 120
5.1.2.3 Algorithm for Safe Decision-Making for AIM 122
5.2 Game-Theoretical Decision-Making and Trajectory Verification
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
5.2.1 Related Work and Preliminaries . . . . . . . . . . . . 125
5.2.1.1 Game-Theoretical Minimax Decision-Making 126
5.2.1.2 Reachability Analysis for Trajectory Generation
. . . . . . . . . . . . . . . . . . . . . . 127
5.2.1.3 Motion in Frenet Coordinates . . . . . . . . 130
5.2.1.4 Modeling of AVs and Maneuvers . . . . . . 132
5.2.2 Application in a Safe Maneuver Planning Algorithm . 137
5.2.2.1 Fixed Abstraction and the Over-
Approximation of Trajectories . . . . . . . . 138
5.2.2.2 Safety Quantification of Maneuvers . . . . . 140
5.2.2.3 Minimax Decision-Making for Safe Maneuver
Planning . . . . . . . . . . . . . . . . . . . 143
5.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
6 Safety Assessment with a Holistic Approach 151
6.1 Overview and the Application of the Approach . . . . . . . . 152
6.2 Case Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
6.2.1 Case Study 1: Safety of an Autonomous Intersection
Management Algorithm . . . . . . . . . . . . . . . . 155
6.2.1.1 Modeling . . . . . . . . . . . . . . . . . . . 155
6.2.1.2 Design/Synthesis . . . . . . . . . . . . . . . 157
6.2.1.3 Testing and Results . . . . . . . . . . . . . 159
6.2.1.4 Conclusion . . . . . . . . . . . . . . . . . . 161
6.2.2 Case Study 2: Safety of a Maneuver Planning Algorithm
for Highway Driving . . . . . . . . . . . . . . . 162
6.2.2.1 Modeling . . . . . . . . . . . . . . . . . . . 163
6.2.2.2 Design/Synthesis . . . . . . . . . . . . . . . 163
6.2.2.3 Testing and Results . . . . . . . . . . . . . 167
6.2.2.4 Conclusion . . . . . . . . . . . . . . . . . . 175
7 Conclusions 177
7.1 Main Findings . . . . . . . . . . . . . . . . . . . . . . . . . . 178
7.2 Answers to the Research Questions . . . . . . . . . . . . . . 179
7.3 Possible Future Directions . . . . . . . . . . . . . . . . . . . 181
Appendix A Additional Details 185
A.1 Rigid Bodies of the Vehicles . . . . . . . . . . . . . . . . . . 185
A.2 Collision Detection . . . . . . . . . . . . . . . . . . . . . . . 186
A.3 Trajectory Tracking in Frenet Coordinates . . . . . . . . . . 187
References 189
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:91684 |
| Date | 03 June 2024 |
| Creators | Saraoglu, Mustafa |
| Contributors | Janschek, Klaus, Voßwinkel, Rick, Technische Universität Dresden |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, doc-type:doctoralThesis, info:eu-repo/semantics/doctoralThesis, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0034 seconds