Efficient Conflict Detection for Conflict Resolution
Résumé
Accurate tools to detect and solve conflicts are becoming necessary to assist air traffic controllers in their task. Air traffic controllers will eventually rely on tools to test and choose alternative trajectories. Enabling such tools demands a near real-time conflict detection algorithm. A previous publication ([1]) proposed optimization methods to perform conflict resolution in real time on moderate size problems. However, this previous publication only considered the time to solve the associated combinatorial optimization problem. It did not take into account the time to compute the conflicts between the alternative trajectories. This time can be high in the scenarios envisioned in [1]. For each aircraft, 161 alternative trajectories were considered. Detecting all the conflicts required to compare 2,721,705 pairs of trajectories for a 15 aircraft scenario and 128,308,950 pairs for a 100 aircraft scenario. The conflict detection procedure uses predicted trajectories which are inherently entangled with uncertainties. A seamlessly way to handle these uncertainties is to bound the future positions in a sequence of volume. This is how the uncertainties are modeled in the scenarios. However, this uncertainty model makes the conflict computation more time consuming. In this paper we propose a Graphics Processing Unit (GPU) implementation of a conflict detection algorithm. Compared with a CPU implementation, the proposed algorithm reduces the computation time by two orders of magnitude. The 15 aircraft scenarios, as described in [1], are computed in 30 ms and the 100 aircraft scenarios are computed in 1 s.
Domaines
Informatique [cs]
Origine : Fichiers produits par l'(les) auteur(s)