# Path Optimization Using Metaheuristic Techniques for a Surveillance Robot
## 4 Optimization Methodology
### Optimization Problem  
The optimization of the trajectory requires the definition of a cost function that the three algorithms must minimize. It differentiates the three different cases already mentioned: searching no shock; maximizing coverage without shock; and reducing time without shock and 100% coverage.  
What the optimization algorithm should aim for is to find the trajectory without collisions and with total coverage of the surface, that is, case (iii), and in the minimum time.  
Equation (7) shows the definition of the fitness function for the three cases, where the first row corresponds to the one in which intersections with obstacles occur (it will always be greater than 2). The second row represents the case of no collision, but the coverage is not 100% (values between 1 and 2). Finally, if there are no collisions and the entire space is covered, time is minimized (third row). The value of this last case is below 1 since the constant of the denominator (\(k\)) is calculated according to the time it takes for a standard route to be completed in the scenario that is evaluated.  
\[f_{c}=\begin{cases}2+\sum_{i=1}^{n}D_{i}&\quad\text{if }\sum_{i=1}^{n}D_{i}\
eq 0 \\ 1+\frac{1000-\varphi_{\text{Filled}}}{100}&\quad\text{if }\sum_{i=1}^{n}D_{i}=0 \text{ \& }\%_{\text{Filled}}<100\\ \frac{\sum_{i=1}^{n}T_{i}}{10^{k}}&\quad\text{if }\sum_{i=1}^{n}D_{i}=0 \text{ \& }\%_{\text{Filled}}=100\end{cases} \tag{7}\]  
In Equation (7), \(n\) is the number of obstacles and \(D_{i}\) is the distance that the trajectory of the vehicle crosses the obstacle \(i\).  
The percentage of visualization of the environment %Filled is defined by Equation (8), considering that \(Nx\) is the number of cells in the x-axis and \(Ny\) is the number of cells in the y-axis of the map. It is noteworthy to remember that \(V_{M}\) denotes the matrix with the cells of the map which represents the simulation environment, and a value one in a cell means that the cell has been sensed by the sensor.  
\[\%_{\text{Filled}}=\frac{V_{M}(i,j)=1}{Nx\times Ny}\quad\quad(i,j)e(\mathbb{ N}<Nx,\mathbb{N}<Ny) \tag{8}\]  
The time it takes the robot to get from one point to its next waypoint is \(T_{i}\), and \(n_{w}\) is the number of waypoints; thus, \(\sum_{i=1}^{n_{w}}T_{i}\) is the total time it takes to complete the trajectory. Finally, \(k\) is a constant that defines the denominator of the third case of the cost function as a multiple of 10. In this way, \(k\) ensures that the cost function in this case is always less than one.  
In addition, a number of constraints are imposed on the values of the parameters to be optimized. These parameters correspond to the Cartesian coordinates \(\{x,\ y\}\) in the \(\{X,\ Y\}\) plane, with values belonging to the intervals \(\{x_{\rm min},\ x_{\rm max}\}\) and \(\{y_{\rm min},\ y_{\rm max}\}\), respectively.  
It should be noted that the speed of the robot has been set to 0.5 m/s in the trajectory simulation algorithm, as this is the maximum speed of the real mobile robot that will perform the surveillance task. In this robot the command to reach a new point receives \(\{x_{r},y_{r},\theta_{r}\}\). However, in order to accelerate the optimization process, the angle \(\theta_{r}\) is set to 0. This does not affect the surveillance as the sensing range of the sensor is 360\({}^{\circ}\). If the sensing pattern was different than 360\({}^{\circ}\), it would be recommended to include the angle as a variable to be optimized.