Tight formation flying and sphere packing
Yoonsoo Kim, Da‐Wei Gu, Ian Postlethwaite · 2007
In this paper, we introduce a method for finding a tight formation of unmanned air vehicles (UAVs) via the classical sphere packing scheme. We first translate the tight formation finding problem to the problem of maximizing the second smallest eigenvalueλ2(G)of the graph LaplacianLG. We then show how close the formationGsobtained from the sphere packing scheme is to the optimal formationG*that maximizesλ2(G). We show thatλ2(G*)/λ2(Gs)is relatively small when the communication strength between two UAVs decays slowly with the distance between the two UAVs. This result implies thatGscan serve as a certificate that allows every graph to be quantitatively compared toG*. In the light of this tight formation result, a modelling technique is given for the optimal airborne refuelling of multiple UAVs.