## 4 Plume Tracing Algorithm
### Metaheuristic Algorithms  
The metaheuristics algorithms compared are Simulated Annealing (SA) [30], Tabu Search (TS) [29] and an Improved Simulated Annealing strategy (ISA). Besides these methods, the greedy search strategy (GS) is also implemented, which allows to define the lower bound of the performance for the algorithms studied. The metaheuristics use the pollutant measurements and the vehicle direction to compute a new direction of movement, such that the UAV remains inside the plume and at the same time navigates towards the source location. All the studied metaheuristic algorithms follow the same general structure and use similar parameters. An explanation of the SA structure is given and then, it is used to define the equations for the other techniques. The SA algorithm designed follows the increasing concentration of the pollutant, based on the instantaneous information measured by the sensor in each position. Figure 1 shows the methodology. According to Figure 1, when reading the contaminant concentration \(\psi_{k}\) and recovering the sample \(\psi_{k-1}\), taken at positions \(p_{k}\) and \(p_{k-1}\) respectively, the gradient is calculated as follows:  
\[\Delta\psi=\psi_{k}-\psi_{k-1} \tag{6}\]  
If \(\Delta\psi\) is greater than \(\epsilon\), defined according the sensor characteristic (avoiding the noise), the direction of motion of the UAV is towards a higher contamination concentration. Otherwise, the UAV moves in the wrong direction. However, since the system is stochastic, there is a probability that the current direction will remain as the correct one. This probability is assigned as:  
\[\Lambda(T)=e^{(\Delta\psi-\epsilon)/T} \tag{7}\]  
where \(T\), called the current system temperature (initially assigned as \(T_{0}\)), decreases at each iteration as:  
\[T=T-\Delta T \tag{8}\]  
where \(\Delta T\), is selected to maintain \(T\) greater than zero during the whole searching routine. If \(\lambda\) (defined over the uniform probability distribution \(U(0,1)\)) does not exceed the evaluation of \(\Lambda(T)\) given by Equation (7), the UAV stays in the current direction. Figure 2 shows the behavior of the proposed solution, where the squares (\(\lambda\)) below the curve of \(\Lambda\) means that the SA algorithm has accepted the direction of decreasing concentration of the pollutant. These directions are evaded when the execution time of the algorithm increments. Besides, to compensate the stochastic behavior of the plume of pollutant, this approach allows the UAV to avoid continuous heading. Based on the structure shown in Figure 1, all the other strategies are described. The GS approach does not allow movements of the UAV towards the negative gradient of the pollutant, instead it selects a new random direction of movement. The TS approach disables the vehicle returning to the last direction and disable also following the direction towards the lowest level of pollutant concentration found. Finally, the ISA approach adds, in the calculus of the UAV direction, a component of the velocity towards the positions of the higher concentration of pollutants found during the UAV navigation. The following equations show the algorithm's designs. Figure 1: Simulated annealing algorithm. Greaty Search:  
\[p_{k+1}=\left\{ \begin{array}{ll}p_{k}+\mathbf{\theta}_{k}\
u&\text{if }\Delta\psi\geq e\\ p_{k}+\mathbf{\kappa}\
u\zeta&\text{if }\Delta\psi<e\end{array} \right. \tag{9}\]  
Simulated Annealing:  
\[p_{k+1}=\left\{ \begin{array}{ll}p_{k}+\mathbf{\theta}_{k}\
u&\text{if }(\Delta\psi \geq\epsilon\vee\lambda<\Lambda)\\ p_{k}+\mathbf{\kappa}\
u\zeta&\text{if }(\Delta\psi<\epsilon)\end{array} \right. \tag{10}\]  
Tabu Search:  
\[p_{k+1}=\left\{ \begin{array}{ll}p_{k}+\mathbf{\theta}_{k}^{\prime}\
u&\text{if } \Delta\psi\geq\epsilon\\ p_{k}+\mathbf{\kappa}^{\prime}\
u\zeta&\text{if }\Delta\psi<\epsilon\end{array} \right. \tag{11}\]  
Improved Simulated Annealing:  
\[p_{k+1}=\left\{