Tiling the World - Efficient 4D Conflict Detection for Large Scale Scenarios

Dies ist die aktuellste Version dieses Eintrags.

Kurzfassung

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.

Verfügbare Versionen dieses Eintrags

• Tiling the World - Efficient 4D Conflict Detection for Large Scale Scenarios. (deposited 13 Okt 2009 15:16) [Gegenwärtig angezeigt]