# Multi-UAV Area Coverage Based on Relative Localization: Algorithms and Optimal UAV Placement
## 3 Materials and Methods  
In this section, the localization of the multi-UAV-based RL algorithm and the process of coverage task performing are presented. The pseudo-code that integrates the whole process is shown at the end of the section. During the process of a coverage task, the change in the UAV's location is assumed to follow  
\[\hat{\mathbf{p}}_{i,k}=\hat{\mathbf{p}}_{i,k-1}+\mathbf{u}_{i}(k-1), \tag{5}\]  
where \(\hat{\mathbf{p}}_{i,k}\) denotes the position estimate of UAV \(i\) at time step \(k\) and \(\mathbf{u}_{i}(k-1)\) is the control input of UAVs. When all UAVs move to their targets, which are the corresponding centroids of their Voronoi partitions, UAVs exchange local information with their neighbors. The UAVs use the local information to update the Voronoi partition and target point in a given frequency. The group does not hover in place until the errors between the current estimated position and target position of every UAV are less than a predefined threshold. In the process of the coverage task performance, the EKF strategy is considered to obtain optimal position estimation for every follower UAV. The strategy is composed of two parts, i.e., the first part is the EKF algorithm used for relative localization between each UAV and its neighbors, to compose the measurement equation of the second part. The second part is used for UAV's global position estimation. The measurement equation of the UAV is obtained from the first part and motion equation of the UAVs. For relative location EKF algorithm design, it is required to determine the relative state equation and relative observation equation. The relative state equation is given by  
\[ \begin{cases}\mathbf{\chi}_{k}^{i,j}=\mathbf{\chi}_{k-1}^{i,j}+\Delta\mathbf{\chi}_{k-1}^ {i,j}+\mathbf{\xi}_{k-1}^{i,j},\\ \Delta\mathbf{\chi}_{k}^{i,j}=\Delta\mathbf{\chi}_{k-1}^{i,j}+\mathbf{v}_{k-1}^{i,j}+\mathbf{ \delta}_{k-1}^{i,j},\end{cases}  \tag{6}\]  
where \(\Delta\mathbf{\chi}_{k-1}^{i,j}\) is displacement increment of UAV \(i\) and \(j\) from time step \(k-1\) to \(k\) and \(\mathbf{v}_{k-1}^{i,j}\) is the difference of the displacement increment between UAV \(i\) and \(j\). The terms \(\mathbf{\xi}_{k-1}^{i,j}\) and \(\delta_{k-1}^{i,j}\) are the related Gaussian noise. On the other hand, the relative observation equation can be described as follows:  
\[ \begin{cases}r_{k}^{ij}=||\mathbf{\chi}_{k}^{ij}||+\eta_{k}^{ij},\\ \mathbf{\phi}_{k}^{ij}=\Delta\chi_{k}^{ij}+\
u_{k}^{ij},\end{cases}  \tag{7}\]  
where \(r_{k}^{ij}\) is the range measurement between UAV \(i\) and \(j\) at time step \(k\) and \(\mathbf{\phi}_{k}^{i,j}\) is the displacement measurement. The terms \(\eta_{k}^{ij}\) and \(\
u_{k}^{ij}\) are the corresponding Gaussian noise. Note that the only nonlinear part of the system comes from the relative range \(r_{k}^{ij}\), which needs to be linearized in the EKF:  
\[r_{k}^{ij}=\hat{r}_{k}^{ij}+\frac{\mathbf{\chi}_{k}^{ij,\tau}}{||\mathbf{\chi}_{k}^{i,j}||}(\mathbf{\chi}_{k}^{i,j}-\mathbf{\hat{\chi}}_{k}^{i,j})+\eta_{k}^{ij}. \tag{8}\]  
The state can be rewritten as \(\mathbf{s}_{k}^{i,j}= \begin{bmatrix}\mathbf{\chi}_{k}^{i,j}&\Delta\mathbf{\chi}_{k}^{i,j} \end{bmatrix} ^{T}\). The state predict and update equation can be written as  
\[\hat{\mathbf{s}}_{k}^{i,j^{-}}=\mathbf{F}_{\hat{s}_{k-1}^{i,j}}\hat{s}_{k-1}^{i,j^{+}} + \begin{bmatrix}0\\ \mathbf{u}_{i,k-1}-\mathbf{u}_{j,k-1}\end{bmatrix} , \tag{9}\]  
\[\hat{\mathbf{s}}_{k}^{i,j^{+}}=\hat{\mathbf{s}}_{k}^{i,j^{-}}+\mathbf{K}_{\hat{s}_{k}^{i,j^ {-}}}( \begin{bmatrix}r_{k}^{ij}\\ \mathbf{\phi}_{k}^{i,j}\end{bmatrix} -\mathbf{H}_{\hat{s}_{k}^{i,j}}\hat{s}_{k}^{i,j^{- }}), \tag{10}\]  
where  
\[\mathbf{F}_{\hat{s}_{k-1}^{i,j}}= \begin{bmatrix}1&0&1&0\\ 0&1&0&1\\ 0&0&1&0\\ 0&0&0&1\end{bmatrix}