Coordination and Control of Multiple UAVs

This paper addresses the problems of autonomous task allocation and trajectory planning for a fleet of UAVs. Two methods are compared for solving the optimization that combines task assignment, subjected to UAV capability constraints, and path planning, subjected to dynamics, avoidance and timing constraints. Both sub-problems are non-convex and the two are strongly-coupled. The first method expresses the entire problem as a single mixed-integer linear program (MILP) that can be solved using available software. This method is guaranteed to find the globally-optimal solution to the problem, but is computationally intensive. The second method employs an approximation for rapid computation of the cost of many different trajectories. This enables the assignment and trajectory problems to be decoupled and partially distributed, offering much faster computation. The paper presents several examples to compare the performance and computational results from these two algorithms.