Tiling the World - Efficient 4D Conflict Detection for Large Scale Scenarios
Kuenz, Alexander and Peinecke, Niklas (2009) Tiling the World - Efficient 4D Conflict Detection for Large Scale Scenarios. In: 28th DASC Proceedings, 28. 28th DASC 2009, 25.-29. Okt. 2009, Orlando, Florida, USA.
This is the latest version of this item.
Full text not available from this repository.
Official URL: http://www.dasconline.org
Today, 4D-Trajectory-Based Operations and international harmonization for global Air Traffic Management (ATM) systems are the main driving concept elements for the modernization of ATM. The availability of ground-based 4D trajectories leads to new possibilities allowing early conflict detection and efficient conflict avoidance. Nevertheless, efficient conflict detection becomes a big challenge when dealing with large amounts of detailed trajectories in a global environment. This paper proposes a new representation of 4D trajectories facilitating a highly efficient conflict detection algorithm. The basic idea is to limit conflict detection runs on closely located trajectories regarding 2D distance, altitude separation and time of day. Therefore, the convex envelope containing all trajectories is divided into 4D tiles. The division is done using a tree structure. The root node of this tree represents a 4D tile containing all trajectories, e.g. the whole world with all altitudes up to 100.000 feet for an entire day. The tree is extended only if two trajectories are member of the same tile. Since every division is done in all four dimensions, a node may have up to 16 children. The subdivision process is carried out until the constraints of separation meet the tile size. Assuming the global world being the root tile, a typical depth of the tree is around 15. All detected conflicts are stored in the root tile for easy access. Conflicts detected in a local tile are automatically detected as part of a global conflict of two trajectories. Since the conflict detection is carried out by storing the trajectory in the tree, no explicit conflict detection is necessary with each surrounding trajectory. A real conflict may only occur within the lowest separation-sized leaf. Therefore, the complexity of the scenario has only minor influence on the algorithm’s runtime. First simulations with large scenarios and the above mentioned setup proved a high performance of the algorithm. Storing a new 4D trajectory in the tree and conflict detection with already stored trajectories is typically done in a few milliseconds. Deleting a stored trajectory is performed in less than a millisecond. Therefore, successive changes of trajectories in a scenario can be updated very efficiently in the proposed tree. The paper gives a detailed description of the developed algorithm and results from simulations. Furthermore, usage for other applications like detecting access violations of restricted areas and efficient conflict resolution are discussed.
|Document Type:||Conference or Workshop Item (Speech, Paper)|
|Additional Information:||Scopus referiert - geändert in Journal referiertes Absract|
|Title:||Tiling the World - Efficient 4D Conflict Detection for Large Scale Scenarios|
|Date:||27 October 2009|
|Journal or Publication Title:||28th DASC Proceedings|
|In ISI Web of Science:||Yes|
|Series Name:||DASC Conference|
|Keywords:||4D, Trajectories, Conflict Detection, Conflict Resolution, Large Scenarios, Huge Scenarios|
|Event Title:||28th DASC 2009|
|Event Location:||Orlando, Florida, USA|
|Event Type:||international Conference|
|Event Dates:||25.-29. Okt. 2009|
|HGF - Research field:||Aeronautics, Space and Transport|
|HGF - Program:||Aeronautics|
|HGF - Program Themes:||L AO - Air Traffic Management and Operation|
|DLR - Research area:||Aeronautics|
|DLR - Program:||L AO - Air Traffic Management and Operation|
|DLR - Research theme (Project):||L - Human Factors and Safety in Aeronautics|
|Institutes and Institutions:||Institute of Flight Control > Pilot Assistance|
|Deposited By:||Alexander Kuenz|
|Deposited On:||13 Oct 2009 15:16|
|Last Modified:||20 Jul 2012 10:52|
Available Versions of this Item
- Tiling the World - Efficient 4D Conflict Detection for Large Scale Scenarios. (deposited 13 Oct 2009 15:16) [Currently Displayed]
Repository Staff Only: item control page