标题： 聚类与分散：一种使用无监督学习的通用空中冲突解决启发式方法 显示英文标题

标题： Cluster & Disperse: a general air conflict resolution heuristic using unsupervised learning

摘要： 我们为航空冲突解决问题提供了一个通用且灵活的启发式方法。 该启发式方法基于一种新的邻域结构，用于搜索轨迹和飞行高度的解空间。 通过无监督学习，我们启发式的核心思想是将冲突点聚类并分散到不同的飞行高度。 我们的第一个算法称为聚类与分散，在每次迭代中，它将每个聚类中最有问题的航班分配到另一个飞行高度。 实际上，我们在飞行高度之间对它们进行轮换，直到达到一个平衡配置。 然后，聚类与分散算法使用任何水平平面冲突解决算法作为子程序来解决这些平衡实例。 然而，我们开发了一种基于类似思想的新水平平面算法。 也就是说，我们使用梯度下降和社交力在相同飞行高度上对冲突点进行空间上的聚类与分散。 我们采用了一种新的机动方式，使航班沿着弧线而不是直线飞行，这基于半径到固定点的航空常规。 我们的算法可以在合理计算时间内处理高密度的航班。 我们将它们的性能与文献中的一些著名算法进行了比较。 作为一个通用框架，聚类与分散的一个显著优势是其灵活性，可以轻松集成关于飞机或环境的各种约束。 这与基于混合整数规划的模型形成对比。 显示英文摘要

摘要： We provide a general and malleable heuristic for the air conflict resolution problem. This heuristic is based on a new neighborhood structure for searching the solution space of trajectories and flight-levels. Using unsupervised learning, the core idea of our heuristic is to cluster the conflict points and disperse them in various flight levels. Our first algorithm is called Cluster & Disperse and in each iteration it assigns the most problematic flights in each cluster to another flight-level. In effect, we shuffle them between the flight-levels until we achieve a well-balanced configuration. The Cluster & Disperse algorithm then uses any horizontal plane conflict resolution algorithm as a subroutine to solve these well-balanced instances. Nevertheless, we develop a novel algorithm for the horizontal plane based on a similar idea. That is we cluster and disperse the conflict points spatially in the same flight level using the gradient descent and a social force. We use a novel maneuver making flights travel on an arc instead of a straight path which is based on the aviation routine of the Radius to Fix legs. Our algorithms can handle a high density of flights within a reasonable computation time. We put their performance in context with some notable algorithms from the literature. Being a general framework, a particular strength of the Cluster & Disperse is its malleability in allowing various constraints regarding the aircraft or the environment to be integrated with ease. This is in contrast to the models for instance based on mixed integer programming.