# Multi-UAV Area Coverage Based on Relative Localization: Algorithms and Optimal UAV Placement
## 2 Problem Formulation  
As mentioned in the Introduction section, we consider a relative localization-based area optimal multi-UAV coverage placement problem. Only one of the UAVs can access its global position, i.e., GPS signals, and other UAVs have to estimate their global position and perform the coverage task simultaneously. The position estimation algorithm uses the extended Kalman filter (EKF) strategy, which comprises cooperative localization and the motion of the UAVs. The cooperative localization is implemented in a decentralized way through a communication topology, as shown in Figure 1.  
For the group of UAVs, the UAV that can access its global position is the leader, say node 0, and all others are followers labeled by nodes \(1,...,n\). UAVs exchange location estimates only with their neighbors through ultra-wide band (UWB) communication modules. The communication topology can be described by a undirected topology graph, i.e., the UAVs as the vertices of the graph. They only communicate with their neighbor UAVs that are within the communication range, as shown in Figure 1.  
Every UAV is equipped UWB and visual odometry to measure the distance to their neighbors and their short-time movement displacement. Because of the large bandwidth (from 3.1 to 5.3 GHz), UWB can provide a reliable long-distance range with an accuracy of 10 cm. We use the DJI F450 (SZ DJI Technology Co., Ltd., Shenzhen, China) radio-controlled (RC) quadcopter, for which the dimensions are 50 cm \(\times\) 50 cm \(\times\) 20 cm. The test area is several tens of square meters, so an accuracy of 10 cm is complete enough. By using our RL algorithm, which will be presented in Section 3, the measurement can be used to compute the relative position between UAV and its neighbors. After obtaining their relative position, the UAVs can estimate their global position by exchanging local information with their neighbors. We can calculate the control inputs for every UAV to obtain the optimal multi-UAV area coverage placement. More details will be addressed in Section 4. We use \(\mathbf{p}_{i,k}=(x_{i,k},y_{i,k})\) to represent the global position of UAV \(i\) at time step \(k\). \(\mathbf{\chi}_{k}^{ij}=(x_{i,k}-x_{j,k},y_{i,k}-y_{j,k})\) denote the estimation of relative position between UAVs \(i\) and \(j\). \(||\mathbf{\chi}_{k}^{ij}||=\sqrt{(x_{i,k}-x_{j,k})^{2}+(y_{i,k}-y_{j,k})^{2}}\) represents the relative distance between UAVs \(i\) and \(j\). The locational optimization function of coverage control is defined as  
\[\mathbf{\mathcal{H}}\{\mathbf{\mathcal{P}}_{k},\mathbf{\mathcal{W}}_{k}\}=\sum_{i=0}^{n} \int_{\mathbf{\mathcal{W}}_{i,k}}||\mathbf{q}-\mathbf{p}_{i,k}||_{2}^{2}d\mathbf{q}. \tag{1}\]  
Figure 1: The communication topology of unmanned aerial vehicles (UAVs). To find an optimal locational configuration of all UAVs that minimizes the locational cost function, with \(\mathbf{\mathcal{H}}\) representing the set of UAVs' configuration, which includes the positions and the Voronoi partitions of multi-UAVs, let \(\mathbf{Q}\) be a convex polytope in \(\mathbb{R}^{N}\) and set \(\mathbf{\mathcal{P}}_{k}=(\mathbf{p}_{0,k},\mathbf{p}_{1,k},...,\mathbf{p}_{n,k})\) as the location of UAVs, which each move in \(\mathbf{Q}\). \(q\) is a point in Voronoi partition and the partition set is described by  
\[\mathbf{\mathcal{W}}_{k}=\{\mathbf{\mathcal{W}}_{1,k},\mathbf{\mathcal{W}}_{2,k},...,\mathbf{ \mathcal{W}}_{i,k},...,\mathbf{\mathcal{W}}_{n,k}\}, \tag{2}\]  
where \(\mathbf{\mathcal{W}}_{i,k}\) denotes the Voronoi region generated by UAV \(i\) at time \(k\) and two UAVs are defined as neighbors when their Voronoi regions are adjacent. The Voronoi region is shown as  
\[\mathbf{\mathcal{W}}_{i,k}=\{\mathbf{q}\in\mathbf{Q}|||\mathbf{q}-\mathbf{p}_{i,k}|||<||\mathbf{q}-\bm {p}_{j,k}||,\forall i\
eq j\}, \tag{3}\]  
The partial derivative of the cost function is shown as  
\[