# Distributed Weighted Coverage for Multi-Robot Systems in Non-Convex Environment
## 2 Problem Statement  
We suppose that \(n\) ground mobile robots \(p_{i}\) with limited communication ranges are randomly distributed in a 2D convex region \(Q\) containing fixed obstacles. \(P=p_{1},p_{2},\ldots,p_{n}\) represents the robots' positions, and each robot has the same dynamic model and size with radius \(r\). If the region \(Q\) is divided into convex polygon regions \(v_{i}\), each polygon contains only a single robot whose position is referred to as the generating point of the polygon, and the distance from any point in the polygon to the generating point is less than that to any other point in \(Q\). If \(v_{i}\cap v_{j}=\phi,i\
eq j\) and \(\{v_{i}\}_{i=1}^{n}=Q\), the Voronoi partition of the region is generated, where the generating point \(p_{i}\) corresponds to the Voronoi cell \(v_{i}\), and the partition structure is called the Voronoi diagram. The Voronoi partition \(v_{i}\) generated by the robot \(p_{i}\) can be described by the equation:  
\[v_{i}=\{x\in Q\;|\;\|\;q-p_{i}\;\|^{2}{<}\|\;q-p_{j}\;\|^{2},i,j=1,2\ldots n,i \
eq j\}. \tag{1}\]where \(q\) is any observation point in \(Q\), and \(||\cdot||\) is the Euclidean distance between two points in \(Q\). If the Voronoi cells of two robots share one edge, they are called neighbors, and the neighbors of robot \(p_{i}\) are represented by \(N_{i}\).  
Suppose that the coverage priority of different points in the region is specified by the region density function \(\rho(q)\), and the function value in this function is non-negative. For the region point q that can be directly observed by the robot, the cost of monitoring the point by the robot is expressed in. For different robots, the function may be different. However, for any points with an equal distance to the same robot, the function is the same, that is \(\parallel q-p_{i}\parallel^{2}=\parallel q-p_{j}\parallel^{2},q_{j},q_{k}=Q\).  
Let a group of robots divide the task area into n areas, then place each agent in the appropriate position in the area, so that each point in the area is monitored by one robot. The cost function (the objective function to be optimized) for multiple robots to form the optimal configuration in the task area can be expressed as:  
\[F(P,V)=\sum_{i=1}^{n}\int\limits_{q\in v_{i}}\rho(q)\parallel q-p_{i}\parallel^ {2}dq. \tag{2}\]  
The CVT is a special case of a Voronoi partition. Suppose that in a given region, the density function in the environment region is \(\rho(q)\); the centroid of the Voronoi cell of the \(i\)-th robot can be obtained as  
\[c_{v_{i}}=\frac{\int_{p\in v_{i}}q\rho(q)dq}{\int_{p\in v_{i}}\rho(q)dq},\quad i =1,\ldots,n. \tag{3}\]  
Where the density function \(\rho(q)\) refers to a distribution of interesting attributes in the environment. As the function value increases, the density value of an attribute increases. When the generating point of a Voronoi cell is the same as the centroid of the cell, it is called a centroid Voronoi tessellation. According to relevant convergence and stability proofs, when the robot moves to the centroid position, the cost function can be minimized, thus rendering the algorithm convergent and stable [32].  
Figure 1a,b show the Voronoi tessellation and CVT, respectively. The \"+\" sign in Figure 1a represents the centroid \(c_{v_{i}}\) of the Voronoi cells, and the \".\" sign and irregular multilaterals in Figure 1a,b represent the generating points and corresponding Voronoi cells, respectively.  
When the position errors of the robots are zero, the robots' sizes are negligible, no obstacles are found in the task area, and the robots can communicate mutually. If for the same point in a region, all the robots have the same detection cost, then the traditional CVT can provide the best division for the robots. However, when considering the abovementioned problems, the traditional CVT is no longer the best solution.