# Multi-UAV Area Coverage Based on Relative Localization: Algorithms and Optimal UAV Placement
## 3 Materials and Methods
The state predicted and updated equations can be written as  
\[\mathbf{\hat{p}}_{i,k}^{-}=\mathbf{\hat{p}}_{i,k-1}^{+}+\mathbf{u}_{i}(k-1), \tag{19}\] \[\mathbf{\hat{p}}_{i,k}^{+}=\mathbf{\hat{p}}_{i,k}^{-}+\mathbf{K}_{\hat{\mathbf{ \rho}}_{i,k}}(\mathbf{z}_{i,k}-\mathbf{H}_{\hat{\mathbf{\rho}}_{i,k}}\mathbf{\hat{p}}_{i,k}^{- }), \tag{20}\]  
where  
\[\mathbf{H}_{\hat{\mathbf{\rho}}_{j,k}}=[C_{k}^{i,1},C_{k}^{i,2},...,C_{k}^{i,j},...], \tag{21}\]  
\[\mathbf{K}_{\hat{\mathbf{\rho}}_{j,k}}=\frac{\mathbf{\Sigma}_{\hat{\mathbf{\rho}}_{j,k}}\mathbf{H} _{\hat{\mathbf{\rho}}_{j,k}}^{T}}{\mathbf{H}_{\hat{\mathbf{\rho}}_{j,k}}\mathbf{\Sigma}_{\hat {\mathbf{\rho}}_{j,k}}^{-}\mathbf{H}_{\hat{\mathbf{\rho}}_{j,k}}^{T}+\mathbf{R}_{\hat{\mathbf{\rho }}_{j,k}}}, \tag{22}\]  
\[\mathbf{\Sigma}_{\hat{\mathbf{\rho}}_{j,k}}^{-}=\mathbf{\Sigma}_{\hat{\mathbf{\rho}}_{j,k-1}} ^{+}+\mathbf{Q}_{\hat{\mathbf{\rho}}_{j,k-1}}, \tag{23}\]  
\[\mathbf{R}_{\hat{\mathbf{\rho}}_{j,k}}=E(\mathbf{\psi}_{i,k}\mathbf{\psi}_{i,k}^{T})=\sum \limits_{j\in N_{i}}C_{k}^{i,j}(\mathbf{\Sigma}_{\hat{\mathbf{\rho}}_{j,k}}+\mathbf{ \Sigma}_{\hat{\mathbf{\chi}}_{k}^{i,j}}), \tag{24}\]  
\[\mathbf{Q}_{\hat{\mathbf{\rho}}_{j,k-1}}=E(\mathbf{\varphi}_{i,k-1}\mathbf{\varphi}_{i,k-1}^{ T}). \tag{25}\]  
where \(\mathbf{K}_{\hat{\mathbf{\rho}}_{j,k}}\) is the Kalman gain of Equation (18) and \(\mathbf{\Sigma}_{\hat{\mathbf{\rho}}_{j,k}}\) is the global position estimation matrix of UAV \(i\). \(\mathbf{R}_{\hat{\mathbf{\rho}}_{j,k}}\) and \(\mathbf{Q}_{\hat{\mathbf{\rho}}_{j,k-1}}\) are Gaussian noise matrices of KF Equations (9) and (10). The global location covariance matrix update equation can be derived as  
\[\mathbf{\Sigma}_{\hat{\mathbf{\rho}}_{j,k}}^{+}=(\mathbf{I}-\mathbf{K}_{\hat{\mathbf{\rho}}_{j,k}} \mathbf{H}_{\hat{\mathbf{\rho}}_{j,k}})\mathbf{\Sigma}_{\hat{\mathbf{\rho}}_{j,k}}^{-}. \tag{26}\]  
The process of simultaneous coverage task and relative localization is summarized in Algorithm 1 shown below. We also tested the algorithm in numerical simulation by using MATLAB and robot operating systems (ROS). The process noise and measurement noise of the environment are obtained by comparing the optimtrack system measurements with the measurements of sensors equipped in UAVs. The experimental values are the mean of many tests to close the randomness of a real environment. The physical characteristics such as the velocity of UAVs, etc., are obtained from real flight and measurements. More details about the test can be seen in Section 5. ```
1:Before Performing Coverage Task
2: Before performing coverage task, the global position estimation of UAVs which can not obtain its global position is randomly given and their estimation covariance have a larger initial value. 3:Performing Coverage Task
4: Set difference between final online expected coverage point position and UAV \(i\) as err and positive threshold of the difference as \(\varepsilon\). 5:while perform coverage task do
6: Every UAV \(i\) receives the global position of neighboring UAVs to compute its Voronoi region and move to the target position obtained by the distributed control law and the optimal solution of constrained nonlinear optimization problem
7: Carry out relative location EKF
8: Predict \(\hat{\mathbf{s}}_{k}^{i,j}\leftarrow(8)\)
9: Compute \(\mathbf{h}_{k,i}^{i,j}\)\(\mathbf{K}_{\hat{\mathbf{s}}_{k}^{i,j}}\)\(\mathbf{\Sigma}_{\hat{\mathbf{s}}_{k}^{i,j}}^{-}\leftarrow(11)(12)(15)\)
10: Update \(\hat{\mathbf{s}}_{k}^{i,j^{\prime}}\)\(\mathbf{\Sigma}_{\hat{s}_{k}^{i,j}}^{+}\leftarrow(9)(16)\)
11: Carry out position location KF
12: Predict \(\hat{\mathbf{p}}_{i,k}^{-}\leftarrow(13)\)
13: Compute \(\mathbf{H}_{\hat{\mathbf{p}}_{i,k}}\)\(\mathbf{K}_{\hat{\mathbf{p}}_{i,k}}\)\(\mathbf{\Sigma}_{\hat{\mathbf{p}}_{i,k}}^{-}\leftarrow(20)-(22)\)
14: Update \(\hat{\mathbf{p}}_{i,k}^{+}\)\(\mathbf{\Sigma}_{\hat{\mathbf{p}}_{i,k}}^{+}\leftarrow(19)(25)\)
15: if \(|\mathbf{err}|<\varepsilon\) then break
16:endwhile
```  
**Algorithm 1** Area coverage placement algorithm based on relative localization