# A Self-Organizing Area Coverage Method for Swarm Robots Based on Gradient and Grouping
## 4 The Coverage Mechanism Based on Grouping
### Deadlock Detection and Release  
In addition to collision avoidance, the grouping method can also cause deadlock. As shown in Figure 9b, if the robot \(\alpha_{5}\) detects that the robot \(\alpha_{4}\) with the Coverage status in its \(d_{cover}\) range, then the robot \(\alpha_{5}\) will stop moving until the robot \(\alpha_{4}\) has left. The robot \(\alpha_{4}\) cannot leave because the robot \(\alpha_{5}\) is in the way, then the robot \(\alpha_{4}\) is hovering in the same position. While \(\alpha_{4}\) and \(\alpha_{5}\) are waiting for the other to move first, which leads to the deadlock. Therefore, it is necessary to detect and release the deadlock in time.  
**(1) Deadlock detection**  
The position information of the robot is recorded once every time after time \(T_{r}\), and the position information of the two adjacent times is constantly compared. If the Euclidean distance between the two robots is less than the distance threshold \(\theta\), it is considered that there is a deadlock that is shown in Equation (3):  
\[\|\alpha\cdot\mathbf{x}(\mathbf{t})-\alpha\cdot\mathbf{x}(\mathbf{t}+T_{r})\| \leq\theta \tag{3}\]  
where \(\alpha.\mathbf{x}(t)\) is the current position of robot \(\alpha\), \(\alpha.\mathbf{x}(t+T_{r})\) represents the position of the robot after the time \(T_{r}\), and \(\theta\) is the distance threshold. Since the two robots in deadlock must be moving within the \(d_{cover}\) range, the maximum value of \(\theta\) should not exceed \(2*d_{cover}\). The deadlock detection algorithm is shown in Algorithm 5.  
```
0: the robot \(\alpha\) in Coverage status
0: update the status of the robot \(\alpha\)
1. if \(\exists\alpha^{\prime}\in A\wedge\|\alpha.\mathbf{x}-\alpha^{\prime}.\mathbf{x }\|\leq d_{cover}\wedge\alpha.status=\) Coverage then
2. \(\alpha.status\) = Stop;
3. end if
4. if \(\|\alpha.\mathbf{x}(\mathbf{t})-\alpha.\mathbf{x}(\mathbf{t}+T_{r})\|\leq\theta\) then
5. if \(\exists\alpha^{\prime}\in A\wedge\alpha^{\prime}.status!=\) Stop \(\wedge\alpha.\mathbf{x}\in D\) then
6. \(\alpha.status\) = Arrive;
7. else
8. \(\alpha.status\) = Stop;
9. end if
10. end if
```  
**Algorithm 5** Deadlock detection algorithm.  
**(2) Deadlock release**  
**Input:** the robot \(\alpha\) in Coverage status  
**Output:** update the status of the robot \(\alpha\)  
1. if \(\exists\alpha^{\prime}\in A\wedge\|\alpha.\mathbf{x}-\alpha^{\prime}.\mathbf{x }\|\leq d_{cover}\wedge\alpha.status=\) Coverage then
2. \(\alpha.status\) = Stop;
3. end if
4. if \(\|\alpha.\mathbf{x}(\mathbf{t})-\alpha.\mathbf{x}(\mathbf{t}+T_{r})\|\leq\theta\) then
5. if \(\exists\alpha^{\prime}\in A\wedge\alpha^{\prime}.status!=\) Stop \(\wedge\alpha.\mathbf{x}\in D\) then
6. \(\alpha.status\) = Arrive;
7. else
8. \(\alpha.status\) = Stop;
9. end if
10. end if ```
**Algorithm 6** Deadlock detection algorithm.  
**(3) Deadlock release**  
A robot that detects a deadlock will switch to a Stop status. Unlike a robot that detects a collision and switches to a Stop status, the robot that detects a deadlock may meet the above-mentioned conditions for restoring the cover state, so it should wait for a while before switching to the cover state. The robot that detects the deadlock may meet the conditions for restoring the Coverage status, so it should wait for some time before switching to the Covered status. The deadlock release algorithm is shown in Algorithm 6.