# On Unmanned Aerial Vehicles Light Show Systems: Algorithms, Software and Hardware
## 2 Formation Transformation in UAVs-LS
### Task Assignment Problem  
In general, given \(N\) initial nodes and \(N\) target ones, there are in total \(N!\) possible matches among them. The purpose of task assignment is to find the optimal assignment minimizing a certain criteria.  
Define the position of the \(i\)-th UAV in the initial formation and the \(j\)-th way-point in the target formation as  
\[\mathbf{x_{i}} =[x_{i}^{0},y_{i}^{0},z_{i}^{0}]^{\top},\,i\in\{1,2,3,\ldots,N\}, \tag{1}\] \[\mathbf{t_{j}} =[x_{j}^{j},y_{j}^{j},z_{j}^{\top}]^{\top},\,j\in\{1,2,3,\ldots,N\}. \tag{2}\]  
The initial and the target formation of all UAVs can be stored in vectors as  
\[\mathbf{X} =[\mathbf{x_{1}}^{\top},\mathbf{x_{2}}^{\top},\ldots,\mathbf{x_{ N}}^{\top}]^{\top}, \tag{3}\] \[\mathbf{T} =[\mathbf{t_{1}}^{\top},\mathbf{t_{2}}^{\top},\ldots,\mathbf{t_{ N}}^{\top}]^{\top}. \tag{4}\]  
Define the assignment map \(\varphi:\{1,2,3,\ldots,N\}\rightarrow\{1,2,3,\ldots,N\}\), which specifies the target position corresponding to each UAV with  
Figure 1: An example of formation transformation in the UAV-LS.  
\[\varphi=[\varphi_{1},\varphi_{2},\ldots,\varphi_{N}], \tag{5}\]  
where \(\varphi_{i}=j(i=1,\ldots,N,j=1,\ldots,N)\) means the \(j\)-th target position is assigned to the \(i\)-th UAV. The TAP is to obtain the optimal match \(\varphi^{*}\) by solving the following optimization problem  
\[\varphi^{*}=\arg\min_{\varphi}\sum_{i=1}^{N}\parallel\mathbf{x}_{i}-\mathbf{ t}_{\varphi_{i}}\parallel, \tag{6}\]  
where \(\mathbf{t}_{\varphi_{i}}\) is the target position assigned to the \(i\)-th UAV according to \(\varphi_{i}\).  
Since the number of UAVs and target nodes are equal, problem (6) is linear and can be solved by the Hungarian algorithm within bounded time [17]. The pseudo code of the Hungarian algorithm is presented in Algorithm 1.  
```
0: initial formation \(\mathbf{X}\), target formation \(\mathbf{T}\)
1:for Each UAV do
2:for Each target position do
3:\(C(i,j)=\parallel\mathbf{x}_{i}-\mathbf{t}_{j}\parallel\)
4:endfor
5:endfor
6: Subtract the minimum value in each row from all the values of its row and get \(C^{{}^{\prime}}\)
7: Subtract the minimum value in each column from all the values of its column and get \(C^{{}^{\prime\prime}}\)
8:for Each row and column do
9: Repeat Draw lines through appropriate rows and rows and columns
10: Until All the zero entries of the cost matrix are covered. The minimum number of such lines is \(m\)
11:endfor
12:if\(m<N\)then
13: Determine the smallest entry not covered by any line. Subtract this entry from each uncovered row, and then add it to each covered column. Return to Step 8
14:endif
15:if\(m=N\)then
16: Obtain the optimal assignment matrix \(\varphi^{*}\)
17:endif
```  
**Algorithm 1** The Hungarian algorithm for the TAP  
Note that the optimal match obtained from the Hungarian algorithm generates straight lines connecting the initial position \(\mathbf{x}_{i}\) and the optimal target position \(\mathbf{\hat{t}}_{i}\) without crossovers [11]. However, since the volume of UAVs cannot be ignored, collision-free trajectory planning is necessary which would result in trajectory deviations from the straight lines.