 | Kuenz A. High performance conflict detection and resolution for multi-dimensional objects: Diss. … Dr. rer. nat. / Deutsches Zentrum für Luft- und Raumfahrt, Institut für Flugführung, Braunschweig. - Köln: DLR, 2015. - 236 p.: ill., tab. - (Forschungsbericht; 2015-31). - Res. also Germ. - Bibliogr.: p.219-230. - Ind.: p.231-233. - ISSN 1434-8454
Шифр: (Pr 1120/2015-31) 02
|
Acronyms ........................................................ 7
Symbols ........................................................ 11
1 Introduction .............................................. 23
2 Related Work .............................................. 27
2.1 Mathematics and Algorithms ................................ 27
2.1.1 Bisection .......................................... 28
2.1.2 Binary Tree ........................................ 28
2.1.3 Binary Space Partitioning Tree ..................... 28
2.1.4 k-dimensional Tree ................................. 30
2.1.5 R-Tree ............................................. 30
2.2 Conflict Detection Mechanisms ............................. 32
2.2.1 Multiple Phases for Complex Scenarios .............. 33
2.2.2 Discrete and Continuous Motion ..................... 33
2.2.3 Convex Polygon Intersection ........................ 34
2.2.4 Simple Polygon Intersection ........................ 35
2.2.1 Plane Sweep Algorithms ............................. 36
2.2.6 Intersection and Range Searching ................... 37
2.2.7 Bounding Volume Hierarchy .......................... 38
2.2.8 Kinetic Data Structures ............................ 41
2.2.9 Sweep and Prune .................................... 43
2.2.10 Broad Phase Based on Delaunay Triangulation ........ 44
2.2.11 Spatial Subdivision ................................ 44
2.2.12 Spatial Hashing .................................... 44
2.3 Geodetic Earth Systems .................................... 73
2.3.1 The Advanced Flight Management System .............. 48
2.4.1 Conflict Situations in Aviation .................... 59
2.4.1.1 Sector Load and Flow Control Conflicts ......... 60
2.4.1.2 Trajectory Based Conflicts ..................... 60
2.4.1.3 Medium-Term Conflict Detection ................. 61
2.4.1.4 Short-Term Conflict Alert ...................... 61
2.4.1.5 Airborne Collision Avoidance System ............ 61
2.4.2 Trajectory-Based Conflict Detection ................ 62
2.4.3 Subdivision of Airspace ............................ 63
2.4.4 Conflict Detection Considering Uncertainty ......... 65
Conflict Resolution in Aviation ........................... 67
2.5.1 Conflict Resolution using Trial-and-Error .......... 69
2.5.2 Conflict Resolution using Genetic Algorithm ........ 70
2.5.3 Conflict Resolution based on Potential Fields ...... 71
2.5.4 Conflict Resolution based on Light Propagation ..... 72
2.5.5 Conflict Avoidance in Crowd Simulation ............. 72
2.5.6 Extended Flight Rules .............................. 73
2.6 Geodetic Earth Systems .................................... 73
2.6.1 Distances on Earth ................................. 76
2.6.2 Map Projection ..................................... 77
2.6.2.1 Sinusoidal Projection .......................... 77
2.6.2.2 Mercator Projection ............................ 77
2.6.2.3 Transverse Mercator Projection ................. 78
3 Conflict Detection ........................................ 81
3.1 Definitions ............................................... 83
3.2 N-Dimensional Conflict .................................... 87
3.2.1 Conflicts without Time Reference ................... 88
3.2.2 Conflicts with Time Reference ...................... 88
3.3 N-Dimensional Tiling Algorithm ............................ 89
3.3.1 Affected Tiles ..................................... 92
3.3.2 Check for Penetration .............................. 93
3.3.3 Check for Vicinity ................................. 95
3.3.4 Symmetric Simplification ........................... 97
3.3.5 Full Containment ................................... 98
3.3.6 Bounding Boxes ..................................... 99
3.3.7 Building the Tree ................................. 101
3.3.8 Monotonie Dimensions .............................. 102
3.3.9 Balancing the Tree ................................ 102
3.3.10 Broad Phase vs. Narrow Phase ...................... 104
3.3.11 Memory Limitation ................................. 105
3.3.12 Tile Knowledge .................................... 105
3.4 Supported Objects ........................................ 106
3.4.1 N-Dimensional Trajectories ........................ 106
3.4.2 N-Dimensional Volumes ............................. 107
3.4.3 N-Dimensional Moving Volumes ...................... 109
3.5 N-Dimensional Conflict Detection ......................... 113
3.5.1 Conflict between Trajectories ..................... 116
3.5.1.1 Trajectory Conflict including Time Reference .. 116
3.5.1.2 Trajectory Conflict without Time Reference .... 117
3.5.2 Conflict between Trajectory and Volume ............ 118
3.5.2.1 Trajectory/Volume Conflict including Time
Reference ..................................... 118
3.5.2.2 Trajectory/Volume Conflict without Time
Reference ..................................... 118
3.5.3 Conflict Merging .................................. 118
3.5.4 Output Format ..................................... 119
3.6 Objects in Focus ......................................... 121
3.7 Software Implementation .................................. 121
4 CD in 4D-Airspace ........................................ 125
4.1 Topological Isomorphism of Earth ......................... 126
4.1.1 The Earth-Mode .................................... 126
4.1.2 Great Circle Connections .......................... 129
4.1.3 Singularity and Discontinuity of Longitudes ....... 131
4.1.4 Alternative Earth Mapping ......................... 134
4.1.4.1 Spherical Coordinate System ................... 134
4.1.4.2 Geodesic Dome ................................. 136
4.2 Traffic Samples and Conditions ........................... 137
4.2.1 German Traffic Sample ............................. 137
4.2.2 European Traffic Sample ........................... 139
4.3 Results from Conflict Detection .......................... 141
4.4 Performance Indicators ................................... 145
4.4.1 Number of Trajectories ............................ 145
4.4.2 Density of Trajectories ........................... 147
4.4.3 Number of Trajectory Sampling Points .............. 147
4.4.4 Length of Trajectories ............................ 148
4.4.5 Number of Potential and Real Conflicts ............ 148
4.4.6 Summary of Performance Indicators ................. 148
4.5 Performance Optimization for CD .......................... 148
4.5.1 Lateral Tile Size Optimization .................... 149
4.5.2 Vertical Tile Size Optimization ................... 149
4.5.3 Time-based Tile Size Optimization ................. 151
4.5.4 Balancing the Tree ................................ 152
4.5.5 Focus on Aircraft ................................. 156
4.5.6 Shrinking the Root Tile ........................... 157
4.6 Comparison with Octrees .................................. 159
4.7 Application in Projects .................................. 161
4.7.1 Future Air Ground Integration ..................... 161
4.7.2 Luftraummanagement 2020 ........................... 163
4.7.3 Volcanic Ash Impact on the Air Transport System ... 164
4.7.4 Supercooled Large Droplets Icing .................. 167
4.7.5 4 Dimensional-Contracts - Guidance and Control .... 168
5 4D Conflict Resolution ................................... 171
5.1 Global Trial-and-Error CR ................................ 172
5.2 Lateral Resolution ....................................... 175
5.3 Vertical Resolution ...................................... 177
5.4 Time-Based Resolution .................................... 178
5.4.1 Moving Whole Flights in Time ...................... 179
5.4.1.1 Global Algorithm .............................. 180
5.4.1.2 Recursive Algorithm ........................... 181
5.4.2 Flight Duration Adaptation ....................... 183
5.5 Deconflicting Optimized Traffic .......................... 183
5.5.1 Airport-Focused Conflict Resolution ............... 187
5.5.2 Global Conflict Resolution ........................ 188
5.5.3 Resolution of En-Route Conflicts .................. 190
6 Verification and Validation .............................. 193
6.1 Nominal Case ............................................. 194
6.2 Pseudo-Parallel Case ..................................... 194
6.3 Conflict Jitter Case ..................................... 198
6.4 Singularity Case ......................................... 201
6.5 Discontinuity Case ....................................... 202
6.6 Polygon Volume Case ...................................... 205
7 Conclusions and Outlook .................................. 209
8 Update after Disputation ................................. 215
8.1 Conflict Metric .......................................... 215
8.2 Performance .............................................. 216
|
|
