# A Relative Coordinate-Based Topology Shaping Method for UAV Swarm with Low Computational Complexity
## 1 Introduction  
The unmanned aerial vehicle (UAV) swarm, first introduced by [PERSON] et al. in 1993 [1], is an intelligent cooperative system that provides the advantages of multi-functional integration, flexible adaptation to dynamic scenarios and increased mission efficiency compared with traditional single UAV platforms [2; 3]. The UAV swarm has been extensively employed in the civil and military mission scenarios such as remote sensing [4; 5; 6; 7], precision agriculture [8], emergency rescue [9; 10], cooperative reconnaissance [11], confrontation [12], and emergency wireless communication [13; 14; 15]. The system capabilities of a UAV swarm rely on the functional topology [16]. Based on the functional topology, the swarm systems empower physically discrete nodes with system capabilities through a distributed cooperative network, which improves the overall system's robustness and survivability [17]. The functional topology of a UAV swarm is always mission-oriented, which calls for the swarm system to dynamically and rapidly form a functional topology adapted to new scenarios and mission requirements [18]. In the case of multi-mission scenarios, the UAV swarm needs to achieve the required functional topology for specified missions, which highlights the significance of the functional topology construction method [19]. The process of functional topology construction can be divided into the following two steps [20]: (1) topology shaping, i.e., the determination of all UAV's optimal target positions for the desired topology shape while considering the global energy consumption. (2) topology forming, i.e., the motion trajectory control from the initial locations to the target positions based on the corresponding relationship derived from the topology shaping. Various methods have been proposed to address the problem of UAV swarm topology shaping. [PERSON] et al. [15] designed three static topology shaping strategies for constructing specified triangle topologies from straight lines, slashed lines, and large triangles, which only apply to small-scale UAV swarms. Another topology shaping method was presented in [21], which tried to find the optimal initial target positions of the UAVs by sequentially assigning the shortest distance to the target location for each UAV. However, the global energy consumption of this method may not be optimal. In order to strengthen the robustness and survivability of the swarm systems, it is essential to take energy consumption into account in the process of topology shaping [22; 23]. [PERSON] et al. [24] introduced a strategy based on the Hungarian algorithm to determine the optimal corresponding assignment relationship from the initial formation to the target formation to solve optimal topology shape transformation of UAV swarms. To address the automatic swarm takeoff problem for vertical takeoff and landing type UAVs, [PERSON] et al. designed a heuristic strategy based on position assignment, i.e., assigning each target position in the flight formation to the nearest UAV [25], and improved by implementing the Kuhn-Munkres (KM) algorithm in the assignment process [26]. The evaluation of assignment algorithms for vertical takeoff- and landing-type UAVs [27] shows that the KM algorithm performs best despite some increase in computational complexity compared with the heuristic strategy proposed in [25]. Based on the assumption that each node knows the costs, i.e., its distance to any target position, a distributed topology shaping method is proposed in [20] by [PERSON] et al. The target positions of UAVs are assigned through a distributed Auction algorithm. [PERSON] et al. proposed a concurrent assignment strategy based on the KM algorithm for multiple robots in [28] to address the problem of target position determination. [PERSON] et al. [28] proposed another concurrent assignment method and employed the KM algorithm to achieve the optimal solution. In [29], [PERSON] et al.