# Multi-Robot Formation Control Based on CVT Algorithm and Health Optimization Management
## 2 Multi-Robot Formation Control  
### Problem Description  
The aim of the Voronoi tessellation algorithm is to divide the area containing \(n\) generation points into \(n\) cells, where each cell contains a generation point and other points in the cell are closest to the generation point of the cell, to ensure that the cost function of the system reaches the minimum value. Centroid Voronoi tessellation is a special case of Voronoi tessellation. It sets the density function of the target area, and its generation point is the centroid of each Voronoi cell. Firstly, we assume that n virtual wireless sensors with limited energy are set in the target area. To maximize the service life of the sensor, we consider a solution where the sensor only interacts with the nearest robot, which can effectively reduce the power consumption for information transmission and obtain the surrounding environment information faster. It is assumed that a single robot in a multi-robot system has a position \(p_{i}\in Q\), \(i\in\{1,2,\ldots,n\}\), \(n\) robots move in a bounded interval, and \(Q\in S^{2}\), \(S^{2}\) is a two-dimensional grid map of the target area. The position of the wireless sensor is expressed as \(q_{i}\in S^{2}\), \(i\in\{1,2,\ldots,n\}\). Taking the robot position as the generation point of the Voronoi division, the Voronoi cell \(V=\{V_{1},V_{2},\ldots,V_{n}\}\) in region \(Q\) is expressed as in Equation (1):  
\[V_{i}=\big{\{}q\in Q\big{\|}\|q-p_{i}\|\ \leq\ \big{\|}q-p_{j}\big{\|},\forall j \
eq i\big{\}} \tag{1}\]  
If the generation point in the Voronoi cell is equal to the centroid of the Voronoi area, it is called the centroid Voronoi partition (CVT). Figure 1a,b shows the Voronoi division and centroids, respectively, where the crosses in Figure 1a represent the Voronoi cell centroids and the points and irregularities are shown in Figure 1a,b. The polygons represent the spawning point and the corresponding Voronoi cell, respectively. Let \(\rho(q)\) be the density function defined in the target region \(Q\). A larger \(\rho(q)\) value means a higher density of certain attributes or a more special location, which is usually measured by the sensor network in order to represent the attributes of some areas. The cost function in the bounded region \(Q\) is defined as in Equation (2):  
\[E(p)=\sum_{i=1}^{n}E^{i}=\sum_{i=1}^{n}\int_{V_{i}}\|q-p_{i}\|^{2}\rho(q)dq \tag{2}\]  
The number of wireless sensors is usually limited and discontinuous. Assuming that the sensor network is evenly distributed in the target area \(S^{2}\), the cost function in the bounded area \(Q\) can be expressed as in Equation (3):  
\[E(p)=\sum_{i=1}^{n}E^{i}=\sum_{i=1}^{n}\sum_{j\in V_{i}}\|q-p_{i}\|^{2}\rho(q) \tag{3}\]  
In order to ensure that multiple robots maintain a reasonable formation during the task, this study emphasizes that the formation can reduce the overall energy loss. Therefore, we transform the formation problem into the tracking problem for the Voronoi interval centroid, and make the robots maintain Voronoi cells with similar quality through the adjustment of the density function. The mass of the cells can be expressed in a continuous version and a discrete version, as shown in Equations (4) and (5), respectively. \[M_{V_{i}}=\int_{V_{i}}\rho(q)dq \tag{4}\]  
\[M_{V_{i}}=\sum_{j\in V_{i}}\rho(q_{j}) \tag{5}\]  
Assume that the average mass of all cells in area \(Q\) is \(\overline{M}\). The difference between the Voronoi cell mass and the average mass is expressed as the difference. When the difference  
Figure 1: Schematic diagram of Voronoi cell: (**a**) VT; (**b**) CVT. reaches the minimum, the mass of each cell is approximately equal by default, that is, the workloads of the robots are approximately equal.