# On Unmanned Aerial Vehicles Light Show Systems: Algorithms, Software and Hardware
## 2 Formation Transformation in UAVs-LS
### A Dynamic Formation Transformation Algorithm
#### 2.3.2 Dynamic Formation Transformation Algorithm  
The Hungarian algorithm minimizes the total flight distance of all UAVs. One of the limitations of the Hungarian algorithm is that the minimum flight distance is obtained by statically considering straight lines between the initial and the target formations. However, UAVs deviate from such straight-line trajectory when avoiding collisions, thus may result in longer flight distance if the task assignment result remains the same. To address this issue, we propose a dynamic formation transformation algorithm by solving the TAP in a conditional-triggering manner during real-time trajectory planning using APF, as shown in Figure 2. To avoid heavy computational cost, a global TAP is first solved off-line and local TAPs are then formulated and solved on-line based on latest formation information. Specifically, for each formation transformation (in general, a UAVs-LS animation contains a series of formation transformations), a global TAP in the form of (6) is firstly formulated off-line, seeking a match between the initial and the target formation coordinates of all UAVs, which includes\[\mathbf{X}_{g} =[\mathbf{x}_{g,1}{}^{\top},\mathbf{x}_{g,2}{}^{\top},\dots, \mathbf{x}_{g,N_{g}}{}^{\top}]^{\top}, \tag{13}\] \[\mathbf{T}_{g} =[\mathbf{t}_{g,1}{}^{\top},\mathbf{t}_{g,2}{}^{\top},\dots, \mathbf{t}_{g,N_{g}}{}^{\top}]^{\top}, \tag{14}\]  
where \(\mathbf{X}_{g}\) represents the current formation position coordinates and \(\mathbf{T}_{g}\) represents the target formation position coordinates. \(N_{g}\) is the total number of UAVs. The optimal match \(\varphi_{g}^{*}\) is obtained by using Algorithm 1 to solve the global TAP. A global APF is constructed by attracting UAVs to move along its negative gradient direction towards the target formation. During on-line operation, local repulsion fields are generated by the UAVs within a component. When UAVs are moving in the air, the members of each component and the number of components may vary. The target position appointed by the current TAP may thus be affected in a component due to deviation from the original straight trajectory to avoid collisions. Therefore, a local TAP based on a conditional-triggering manner must be formulated and solved. In particular, the local TAP is triggered when there is a component. The connected components of undirected graph can be obtained by the adjacent matrix \(A_{N\times N}\)[18; 19]. An improved version of depth-first search has been proposed to solve the connected components in [19], and the method is employed to obtain the connected components of undirected graph. An illustrative example is given in Figure 3, where three components are formulated for six UAVs according to the adjacent relationship given in Table 1. Table 2 presents the solutions of the connected components. Figure 2: Detailed flow chart of the hybrid algorithm. Given a component \(k\), \(k=1,2,\ldots,m\) and its UAVs, we define the local TAP matching objectives \(\mathbf{X}_{l}^{k}\) and \(\mathbf{T}_{l}^{k}\) as:  
\[\mathbf{X}_{l}^{k} =[\mathbf{x}_{l,1}^{k}\,{}^{\top},\mathbf{x}_{l,2}^{k}\,{}^{\top},\ldots,\mathbf{x}_{l,N_{k}}^{k}\,{}^{\top}]\,{}^{\top}, \tag{15}\] \[\mathbf{T}_{l}^{k} =[\mathbf{t}_{l,1}^{k}\,{}^{\top},\mathbf{t}_{l,2}^{k}\,{}^{\top},\ldots,\mathbf{t}_{l,N_{k}}^{k}\,{}^{\top}]\,{}^{\top}. \tag{16}\]  
where \(\mathbf{X}_{l}^{k}\) and \(\mathbf{T}_{l}^{k}\) are the current and assigned target position of the \(k\)-th component. The local TAP solves the matching relationship between the current positions and target positions of the neighboring UAVs at discrete sampling instants while they are moving. Minimum flight distance can be maintained by using Algorithm 1 to solve the local TAP. Consequently, a UAV-LS formation transformation (UAVs-LSFT) method is developed by combining the Hungarian algorithm and the APF dynamically, as summarized in Algorithm 2, which is simple enough for real-time computations.