# A Relative Coordinate-Based Topology Shaping Method for UAV Swarm with Low Computational Complexity
## 1 Introduction
presented a decentralized topology shaping method and controlled the UAVs to form the desired shape via decentralized Markov decision processes. In this method, the UAVs know the exact target location and randomly select the target location to form the desired topology shape. [PERSON] et al. [30] presented another distributed topology shaping method based on the Auction algorithm and consensus algorithm, but the number of iterations required to form the desired topology is more than 900, which leads to high computational complexity. To solve the problem of topology forming, some bio-inspired methods have been proposed in recent years. In [31], [PERSON] et al. proposed a topology forming method to control UAVs' flight from initial positions to target positions based on improved particle swarm optimization. In [32], [PERSON] et al. employed pigeon-inspired optimization in the topology shaping controller to solve the problem of driving UAVs from initial positions to target positions. In [33], [PERSON] et al. presented a hybrid particle swarm optimization and genetic algorithm to tackle the topology shaping problem. However, these bio-inspired topology forming methods are computationally prohibitive if the number of the UAVs in the swarm is large. The methods mentioned above have successfully achieved topology shaping from different perspectives. However, these methods are commonly based on the assumption that the target locations of the nodes are known or have been pre-defined. In contrast, the topology shape is usually specified rather than providing an exact location for each UAV. Additionally, the external localization information is not available everywhere, and it will be degraded or completely unavailable in hostile areas, building structures etc. [34; 35]. On the other hand, the UAV swarm network is a field-level network and therefore requires the swarm to achieve a swarm topology without relying on external localization information. Furthermore, the computational complexity of existing algorithms is still high, which is unacceptable for large-scale UAV swarms. From the studies reviewed here, how to obtain the specific position information of each UAV through the topology shape in the absence of external localization information (e.g., in a GPS-denied environment) and how to determine the optimal target position in low computation time while considering the global energy consumption remains to be thoroughly studied. In this paper, for arbitrary topology shapes of UAV swarms, an optimal topology shaping method is proposed to determine each node's target position in ultra-low computation time with minimum global energy consumption. The topology shaping is formulated into a mapping of a three dimensional (3D) coordinate system from a global system perspective. First, the initial and target topology coordinate system is obtained based on the inter-distance of nodes derived from the topology shape without external localization information. Second, the problem of determining the nodes' optimal target positions in the topology shaping process is transformed into a problem of optimal coordinates mapping from initial to target topology with minimized global energy consumption, which is solved by the Jonker-Volgenant (LAPJV) algorithm. Finally, the validity and efficiency of the proposed method are shown through simulations. The contributions of this paper are as follows:  
* From a global system perspective, a system optimization model for topology shaping of UAV swarm in 3D space is developed without relying on any external localization information, in which the topology shaping and global energy consumption minimization are considered. * Under the framework of the topology shaping optimization model, the topology shaping problem is transformed into a problem of relative coordinate mapping. The topology shaping with minimum global energy consumption is achieved by obtaining the optimal mapping relationship of the relative coordinates. The LAPJV algorithm is employed to solve this optimization model.