Optimal UAV Swarm Reconstruction Strategy Based on Minimum Cost Maximum Flow Algorithm

Unmanned Aerial Vehicle (UAV) swarm is becoming an important part of the future battlefield. Due to the high confrontation and the multiplicity types of interference in the battlefield environment, ensuring the topology integrity of the UAV formation becomes the premise of achieving the target mission. In this paper, we propose an optimal swarm reconstruction strategy for scenarios where some UAVs are destroyed. Our strategy reorganizes the remaining isolated UAVs into UAV clusters through reconstruction. We formulate the problem as an integer linear programming problem and propose a minimum-cost maximum-flow-based algorithm to solve it to optimality in polynomial time. Numerical results show that the proposed strategy can find the optimal path-cost solution, and the solution also takes into account the remaining energy and topoloaical change,