# Multi-UAV Area Coverage Based on Relative Localization: Algorithms and Optimal UAV Placement
## 4 Optimal Multi-UAV Placement for Coverage  
After every UAV calculates its global position, they perform the coverage task cooperatively. However, it is well known that the performance of the RL algorithm is highly related to the relative geometries of the group of UAVs, which will heavily influence the precision of location estimates. If the control input of the UAVs is determined only by factors of coverage task, that may cause relative localization performance to worsen. Hence, the compromise between the relative localization sensor placement and area coverage placement is quite important.  
To achieve the goal, the control input \(\mathbf{u}_{i}(k)\) is considered to be comprised of two parts. One is obtained by minimizing the locational optimization function \(\mathcal{F}^{{}^{\prime}}(\mathbf{u}_{i}(k))\), which is used for area coverage. This part is represented by \(\mathbf{u}_{i}^{\prime}(k)\), and the corresponding cost function is formulated as follows:  
\[\min_{\mathbf{u}_{i}^{\prime}(k)}\mathcal{F}^{{}^{\prime}}(\mathbf{u}_{i}(k))=\sum_{i=0 }^{n}\int_{\mathbf{\mathcal{W}}_{i,k}}||\mathbf{q}-\hat{\mathbf{p}}_{i,k}||_{2}^{2}d\mathbf{q}. \tag{27}\]  
The other part is denoted by \(\mathbf{u}_{i,k}^{{}^{\prime\prime}}\), which is obtained by minimizing the trace of uncertainty matrix of location estimates:  
\[\mathcal{F}^{{}^{\prime\prime}}(\mathbf{u}_{i}(k))=\text{Tr}(\mathbf{\Sigma}_{\hat\mathbf{{p}}_{i,k}}^{+}). \tag{28}\]  
When optimizing the above localization-related cost function, UAVs' motion and communication constraints have to be considered. The resulted constrained nonlinear optimization function can be formulated as follows:\[\min_{\mathbf{u}_{i}^{n^{\prime\prime}_{i}}(k)}\mathcal{F}^{\prime^{\prime}}(\mathbf{u}_{ i}(k))=\text{Tr}(\Sigma_{\mathbf{\dot{p}}_{i,k}}^{+}),\] (29) subject to \[||\mathbf{u}_{i}(k)-\mathbf{u}_{i}(k-1)||\ \leq\ u_{max}, \tag{30}\] \[\exists j\in N_{i} ||\mathbf{\dot{p}}_{i,k+1}-\mathbf{\dot{p}}_{j,k+1}||\ \leq\ m_{d},\] (31) \[\forall j\in N_{i} ||\mathbf{\dot{p}}_{j,k+1}-\mathbf{\dot{p}}_{j,k+1}||\ \geq\ n_{d},\] (32) \[x_{min}\leq x_{\mathbf{\dot{p}}_{j,k+1}}\leq x_{max},\] (33) \[y_{min}\leq y_{\mathbf{\dot{p}}_{j,k+1}}\leq y_{max}, \tag{34}\]  
where the condition (30) presents the UAV input constraint, e.g., its turning rate constraint. The condition (31) addresses the case that UAV \(i\) has to maintain communication with at least one of its original neighbors. The condition (32) presents UAV \(i\) as maintaining collision avoidance distance \(n_{d}\) with its neighbors. The conditions (33) and (34) present that UAV \(i\) will always move within the given region.  
From the problem formulation (29)-(34), we can see that the optimization problem is nonlinear with linear and nonlinear constraints. Gradient methods cannot be directly used for this problem. Instead, the SQP algorithm can be utilized to solve such an optimization problem.  
The expected control input can be considered the join force using the coverage control and relative localization parts shown in Figure 2. The control input \(\mathbf{u}_{i}(k)\) of each part can be calculated by adjusting the weight \(\alpha_{i,k}(0\leq\alpha_{i,k}\leq 1)\), which is given by  
\[\mathbf{u}_{i}(k)=\alpha_{i,k}\times\mathbf{u}_{i}^{{}^{\prime}}(k)+(1-\alpha_{i,k}) \times\mathbf{u}_{i}^{{}^{\prime\prime}}(k), \tag{35}\]  
where weight \(\alpha_{i,k}\) is given by  
\[\alpha_{i,k}=\frac{\text{Tr}(\Sigma_{\mathbf{\dot{p}}_{i,k}}^{+})}{\text{Tr}( \Sigma_{\mathbf{\dot{p}}_{i,k}}^{+})+T}-\frac{1}{2}, \tag{36}\]  
where \(T\) is a judgement threshold, which can be set according to the converge performance of the RL, i.e., when \(\text{Tr}(\Sigma_{\mathbf{\dot{p}}_{i,k}}^{+})\) drops to \(T\).  
Combined with Algorithm 1, the optimal RL-based coverage placement algorithm is summarized in Algorithm 2.  
Figure 2: The composition of the control input.