Safe and wind-aware synchronous path planning for a fleet of fixed-wing constant speed aircraft

Path planning for multiple unmanned aerial vehicles is a difficult task, and even more for a fleet of fixed-wing aircraft. One specific case is the transition to, or between, formation flight patterns, which requires synchronous arrivals while ensuring minimal separation, and ideally maintaining cruise speed. We present a centralized method to solve this problem based on enumerating different Dubins paths. Given a travel time for the fleet, it builds a set of possible paths for each aircraft. Then, it checks in parallel separation between each path pair. This yields coefficients for an Integer Linear Programming problem determining if a fleet-wide conflict-free solution exists. This process is repeated for different travel times sampled with increasing resolution until the user-defined accuracy is met. The method is benchmarked with Monte-Carlo simulations considering up to 20 aircraft simultaneously, achieving an 95% success rate for an average 8 seconds computation time.