# A Self-Organizing Area Coverage Method for Swarm Robots Based on Gradient and Grouping
## 4 The Coverage Mechanism Based on Grouping
### Grouping Method  
The robots in the swarm robotic system are randomly distributed on the two-dimensional plane and they are divided into several different groups by grouping method. Then each group can perform the covering action in parallel during the covering process, to improve the coverage speed. Some problems need to be considered in the grouping process. (1) The leader robot in the right position should be selected quickly. (2) The number of robots in each group should be about the same. (3) The distance between the groups is large enough to reduce collisions between the robots. For the initial random distribution of swarm robots, we should first determine the number of groups \(K\), and then \(K\) robots will be selected as the current leaders. Each leader robot has a different group number. The leader of the robot broadcasts its group number and location information to other robots. All robots are not isolated, and the communication range of robots is defined as \(R_{c}\) means that all robots in the communication range of robot \(\alpha\) are their neighbors. The swarm robot system will randomly select \(K\) robots as the leader robots firstly, and set as \(L=\{l_{k}\}_{k=1,2,\ldots,K}\), but the distribution of the initial selected leader robots is not necessarily reasonable. For example, the distance may be close, which will affect the effect of grouping. Therefore, it is necessary to update the leader robots automatically. The leader robot chooses a neighbor as the new leader according to the neighbor's position and the current position of other leaders. The sum of the distance to other leaders of the new leader robot \(l_{k}^{\prime}\) should be greater than the old leader robot \(l_{k}\), which satisfies the following equation. \[l_{k}^{\prime}=\left\{\alpha\mid\alpha\in l_{k}\cdot N\wedge\alpha\
otin L \wedge\sum\
olimits_{l_{j}\in L\wedge j\
eq k}\left\|\alpha.\mathbf{x}-l_{j} \cdot\mathbf{x}\right\|>\sum\
olimits_{l_{j}\in L\wedge j\
eq k}\left\|l_{k} \cdot\mathbf{x}-l_{j}\cdot\mathbf{x}\right\|\right\} \tag{2}\]  
where \(\alpha.N\) represents all neighbor robots within the communication range of robot \(\alpha\), and \(\alpha.\mathbf{x}\) represents the position of robot \(\alpha\) in two-dimensional space. Once a new leader robot satisfies Equation (2), the original leader robot will be replaced. The new leader will find the next robot which satisfies Equation (2) as the next leader robot, so as to complete the update of the leader robot of the whole swarm robot system. To update the leader robot quickly, we define one farthest hop number \(h\) according to the lifetime of the network packet. The message specifying the next new leader should contain \(h\), and \(h\) will decrease after finding the new leader. The leader whose \(h\) value is 0 is the final leader. If there is no new leader in \(l_{k}\)'s neighborhood, \(h\) should be reduced  
Figure 6: Group-based area coverage process status transition diagram. automatically within a certain period of time. The self-organizing updating algorithm of the leader robot is shown in Algorithm 3. ```
0: the swarm robots \(A\), leader robot number \(K\)
0: the new leader robot
1. \(\alpha.\_leder=\) false, \(\alpha.g=0\); //Initialize all robots
2. \(\alpha.\_leder=\) true, \(\alpha.g=\{1,2,\ldots,k\}\) //Randomly select k robots as the leader robots
3. if \(\alpha.\_leder==\) true then //Set the number of hops for all robots
4. \(\alpha.h=h_{max}\);
5. else \(\alpha.h=0\);
6. \(\mathrm{while}(\alpha.\_l!=0)\)
7. Broadcast robot position \(\alpha.\mathbf{x}\) and hop number \(h\);
8. Calculate the sum of the distances \(\sum\)d between \(\alpha\) and all its neighbors and other leader robots;
9. \(\alpha^{\prime}.h=\alpha.h-1\);
10. \(\alpha.\_leder=\) false;
11. \(\alpha^{\prime}.\_leder=\) true;
12. if \(\alpha.\_leder==\) false then
13. \(\alpha.\_l=0\);
14. end if
15. end while
```  
**Algorithm 3** Leader robot self-organizing update algorithm. The self-organizing grouping algorithm borrows the idea of the breadth-first search.