Resolution of conflicts involving many aircraft via semidefinite programming

Aircraft conflict detection and resolution is currently attracting the inte rest of many air transportation service providers and is concerned with the following question: Given a set of airborne aircraft and their intended tr ajectories, what control strategy should be followed by the pilots and the air traffic service provider to prevent the aircraft from coming too close to each other? This paper addresses this problem by presenting a resolution methodology whereby each aircraft proposes its desired heading while a cen tralized air traffic control authority resolves any conflict arising betwee n aircraft, while minimizing the deviation between desired and conflict-fre e heading for each aircraft. The resolution methodology relies on a combina tion of convex programming and randomized searches: It is shown that a vers ion of the planar, multiaircraft conflict resolution problem, accounting fo r all possible crossing patterns among aircraft, might be recast as a nonco nvex, quadratically constrained quadratic program. For this type of problem , there exist efficient numerical relaxations, based on semidefinite progra mming, that provide lower bounds on the best achievable objective. These re laxations also lead to a random search technique to compute feasible, local ly optimal, and conflict-free strategies. This approach is demonstrated on numerical examples and discussed.