Optimal Reconfiguration Planning for Large UAV Groups

Today, the use of copter-type UAVs in various sectors is economically justified and sometimes has no alternative. The next step toward increasing the efficiency of this technology is to use groups of UAVs united by a single task. If such groups contain a large number of drones located quite densely, they are called swarms. A well-known example of the use of quadcopter swarms is the creation of visual images in the sky and their transformation according to a specific program. Obviously, the possibilities of such structures are much wider and they have very good prospects in the future. But to realize such opportunities, a number of tasks need to be solved, ranging from methods of obtaining and exchanging current information between group members to strategic planning and operational management of individual devices. These tasks are burdened by additional security conditions for optimal functioning. In this article, we consider the problem of geometric reconfiguration of a large group of UAVs from the actual initial state to the desired final state. For each vehicle, it is necessary to determine the endpoint to which it will move. Such a problem has more than one solution, so the optimality criterion was added as minimization of the complete reconfiguration duration. The problem is considered under the conditions of the same and constant flight speed of a copter type UAV. It is impossible to analyze all possible options, since the computational complexity of this method is proportional to N factorial, where N is the number of UAVs in the group. A quasi-optimal method has been developed, the complexity of which is proportional to N. By statistical modeling, its effectiveness has been proved, which can be compared with the effectiveness of the optimal method. Indirect estimates of its efficiency in the general case are also obtained. Specific examples of swarm reconfiguration are considered. The centralized structure of the UAV swarm is described, which should ensure optimal planning of the reconfiguration of a group of UAVs in practice.