Three-Dimensional Conflict Resolution Strategy Based on Network Cooperative Game

Wenda Yang, Xiangxi Wen, Minggong Wu, Kexin Bi, Longfei YueSymmetry 2022 · DOI

TL;DR

This paper introduces a novel approach to resolving three-dimensional flight conflicts among multiple aircraft by modeling the problem as a network cooperative game. By integrating complex network theory with cooperative game theory and employing the NSGA-II algorithm, the method effectively balances conflict resolution capability with fairness and reduced resolution costs, outperforming existing methods in complex scenarios.

What Problem Does This Paper Address?

The increasing volume of air traffic leads to a higher probability of flight conflicts, which are a major cause of aviation accidents. Existing conflict resolution methods often struggle with the complexity of three-dimensional airspace, the dynamic nature of flight paths, and the fair distribution of resolution costs among multiple aircraft. Specifically, the challenge lies in developing a strategy that can efficiently resolve conflicts for numerous aircraft in 3D space while ensuring that the burden of resolution is distributed equitably and that the overall cost is minimized.

Methods

The authors propose a multi-aircraft conflict resolution method based on a network cooperative game. The core components are:

  • Flight Conflict Network Model: Aircraft are represented as nodes, and conflicts between them are represented as weighted edges. The edge weights signify the urgency of the conflict.
  • Three-Dimensional Conflict Detection: A combination of the ellipsoid flight protection zone and the speed obstacle method is used to detect potential conflicts in 3D space, considering both position and relative velocity.
  • Comprehensive Network Index (CNI): A metric combining robustness (R), network efficiency (NE), and clustering coefficient (CC) is developed to evaluate the overall effectiveness of a resolution strategy.
  • Cooperative Game Theory & Nucleolus Solution: The "nucleolus solution" concept from cooperative game theory is applied to balance the overall alliance welfare with individual aircraft interests, aiming for a fair distribution of resolution costs. An alliance cost function (V) is defined, considering speed and heading adjustments.
  • Node Priority: Aircraft nodes are prioritized based on their "node strength" (sum of edge weights) to focus resolution efforts on critical aircraft.
  • NSGA-II Algorithm: The Non-dominated Sorting Genetic Algorithm II is employed to solve the multi-objective optimization problem, seeking a Pareto optimal set of solutions.
  • Optimization Techniques: Two key optimizations are introduced to improve timeliness:
  • Adjusting High-Priority Nodes: Focusing resolution efforts on aircraft with higher priority.
  • Customizing Initial Resolution Scheme: Injecting pre-calculated initial resolution schemes into the NSGA-II algorithm's initial population to accelerate convergence.

Datasets

Not explicitly discussed in the paper. The simulations appear to be based on randomly generated scenarios within a defined airspace and altitude range.

Key Insights and Ideas

  • Networked Conflicts: Viewing flight conflicts as a network problem allows for a more holistic approach, considering the interdependencies between aircraft rather than just pairwise conflicts.
  • Fairness as a Core Objective: The "nucleolus solution" concept is crucial for ensuring that conflict resolution doesn't unfairly burden certain aircraft, leading to a more acceptable and implementable strategy.
  • Synergy of Network and Game Theory: Combining complex network theory (for structure and evaluation) with cooperative game theory (for fair resource allocation) provides a powerful framework for multi-aircraft conflict resolution.
  • Optimization for Timeliness: The two proposed optimizations (high-priority nodes and initial schemes) significantly improve the algorithm's speed, which is critical for real-time air traffic control.
  • Compound Resolution Superiority: The compound resolution method (adjusting both speed and heading) generally offers the best balance of conflict resolution capability and cost reduction, especially in complex scenarios.

Key Results

  • The proposed method can adjust 10 aircraft in 15.17 seconds.
  • It successfully resolves 12 flight conflicts in a complex scenario with 40 aircraft.
  • The method reduces resolution costs by more than 22.1% on average compared to methods that don't consider resolution costs.
  • Compound resolution demonstrated the best release effect, resolving more conflicts with lower costs compared to heading or speed resolution alone.
  • The optimization techniques (high-priority nodes and initial schemes) significantly improved algorithm convergence speed and reduced computation time.

Limitations and Future Work

  • Computational Cost of Compound Resolution: While effective, compound resolution leads to longer chromosome lengths in the NSGA-II algorithm, potentially slowing down convergence.
  • Optimization of Computation Time: The authors suggest further optimizing computation time by discretizing decoupling strategies.
  • Optimization of Adjustment Node Selection: Future work will focus on optimizing the selection of adjustment nodes, potentially by computing the minimum dominating set of the network.
  • Real-World Data: The simulations rely on generated scenarios; validation with real-world air traffic data would strengthen the findings.

Summary updated

Abstract

Aiming at the problems of difficult handling of three-dimensional flight conflicts and unfair distribution of resolution costs, we propose a multi-aircraft conflict resolution method based on the network cooperative game. Firstly, we establish a flight conflict network model with aircraft as nodes and the conflict relationship between node pairs as edges. After that, we propose a comprehensive network index that can evaluate the effect of resolution strategy. Based on the concept of “nucleolus solution”, we establish a conflict network alliance with all nodes as participants, and balance the interests of all participants through the resolution cost function. In order to improve the timeliness of the method, we propose two optimization methods: adjusting high-priority nodes and customizing the initial resolution scheme. Finally, we combine the NSGA-II algorithm to solve the optimal conflict resolution scheme. The simulation results show that our method can adjust 10 aircraft in 15.17 s and resolve 12 flight conflicts in a complex conflict scenario containing 40 aircraft; our method reduces the resolution cost by more than 22.1% on average compared with the method without considering the resolution cost. The method ensures both the conflict resolution capability and the reduction in resolution cost.
BibTeX
@inproceedings{yang2022three,
  author = {Wenda Yang and Xiangxi Wen and Minggong Wu and Kexin Bi and Longfei Yue},
  title = {{Three-Dimensional Conflict Resolution Strategy Based on Network Cooperative Game}},
  booktitle = {Symmetry},
  year = {2022},
  doi = {10.3390/sym14081517},
}
Figure