## 5 Experimental Setup
### Comparison Heuristics
#### 5.2.2 Pheromone-Based Heuristics  
As explained in Section 2, different techniques based on pheromone have been used in the context of area coverage by a swarm of robots/UAVs. Two have been implementedhere to assess the quality of the coverage provided by the generated heuristic. For both heuristics, the behaviour is very similar to the one described in Algorithm 1. However, they do not belong to the space of low-level heuristic since the choice of the next position \(v\) for a UAV at a position \(v_{curr}\) is stochastic and thus depends on a probability \(\mathbb{P}(v\mid v_{curr})\).  
Heuristic \(\Phi\): The first heuristic, referred to as \(\Phi\), is based on repulsive pheromones [16], i.e., UAVs drop pheromones on their way to indicate visited places. The probability of a UAV going to a position is then inversely proportional to the amount of pheromones at that position (i.e., the more pheromones, the less chance). The environment in which UAVs are evolving is a grid, and at each iteration, UAVs assign the current coverage time to their current position. So each position is assigned a value that corresponds to the last time a UAV has visited it. As with repulsive pheromones, the lower the value assigned to a position, the higher the chance that UAVs have of choosing that position. Given a position \(v\), let \(t_{v}\) be the time assigned to that position and \(\mathcal{N}(v)\) be the set of adjacent positions. The probability of going to a position \(v\) for a UAV at position \(v_{curr}\) is  
\[\mathbb{P}(v\mid v_{curr})=\left\{\begin{array}{ll}\dfrac{T-t_{v}}{(| \mathcal{N}(v_{curr})|-1)\cdot T}&\text{if }v\in\mathcal{N}(v_{curr})\\ 0&\text{otherwise}\end{array}\right.\]  
with \(T=\sum\limits_{v\in\mathcal{N}(v_{curr})}t_{v}\).  
Heuristic \(\Phi\)-K: The drawback of the heuristic \(\Phi\)is that it does not consider the connectivity of the swarm. That is the purpose of the work, [18] which adds a dynamic clustering algorithm, the so-called KHOPCA [34], to maintain connectivity within the swarm of UAVs. Let this heuristic be \(\Phi\)-K. KHOPCA algorithm dynamically assigns a state value \(s(u)\) to each UAV \(u\) that represents the distance to the cluster head (\(s(u)=0\) if \(u\) is the cluster head). For a UAV \(u\), let \(\mathcal{N}(u)\) be the set of UAVs in the communication range of \(u\). Then, \(s(u)\) is iteratively updated by following four simple rules:  
\[s(u)=\left\{\begin{array}{ll}\min\limits_{u^{\prime}\in\mathcal{N}(u)}s(u^{ \prime})+1&\text{if }\min\limits_{u^{\prime}\in\mathcal{N}(u)}s(u^{\prime})<s(u)\\ 0&\text{if }\min\limits_{u^{\prime}\in\mathcal{N}(u)}s(u^{\prime})=k\\ s(u)+1&\text{if }s(u)\
eq 0\wedge s(u)<\min\limits_{u^{\prime}\in\mathcal{N}(u)}s( u^{\prime})\\ s(u)+1&\text{if }s(u)=0\wedge\min\limits_{u^{\prime}\in\mathcal{N}(u)}s( u^{\prime})=0\end{array}\right.\]  
where \(k+1\) is the number of UAVs (\(k\) is the biggest possible distance from the cluster head). At initialisation, \(s(u)=k\) for every UAV \(u\). At each iteration, UAVs which are not cluster heads follow their cluster with a certain probability PK, otherwise they choose their next position according to the probability defined in the heuristic \(\Phi\). When a UAV follows its cluster, it decides to go to the position of its neighbour (a UAV in its communication range) with the lowest state value. Since the value of PK has a high impact on the quality of the coverage, let \(\Phi\)-K\({}_{\text{PK}}\) denote this heuristic with a certain value for PK.