# Comparison of Heuristic Algorithms in Discrete Search and Surveillance Tasks Using Aerial Swarms
## 1 Introduction
### Search Patterns  
In order to organize the search, most of the past works based on patterns have made use of dividing the area into cells, taking into account if they have been visited or not. The sensed area is frequently restricted to those cells, and therefore, the search implies visiting all the existing cells. The agent's movement is restricted, and they are only allowed to travel between the centers of adjacent cells. With these assumptions, the search is simplified since it becomes a discrete problem. In the following, the main works addressing this kind of mission by implementing movement patterns are analyzed. In [20], the task is addressed with an algorithm made up by four behaviors that act together:  
* Contour following: This leads the agent along boundaries, i.e., cells that have at least one non-visited cell surrounding them. This is the behavior with the highest priority. * Avoidance: When two agents are within a given range, this behavior is triggered. The velocity command is perpendicular to their mutual collision course, and it is added to the contour following the behavior output. * Gradient descend: Having defined a distance field, computed at each cell as the distance to the closest non-visited cell, when this behavior is active, it leads the agent along the gradient. It is activated when an agent is completely surrounded by visited cells. * Random movement: The agent decides randomly which cell to visit next. It is activated when none of the other behaviors are active. The distance matrix is treated here as a pheromone field. The members of the swarm share information with the agents within a communication range, updating the distance matrix (i.e., which cells have been visited). Assuming a constant velocity and considering that traveling diagonally requires the same time as traveling in the other directions, the minimum needed time is then \(O\left(\frac{m\cdot m}{I}\right)\), where \(m\cdot n\) is the number of cells and \(I\) is the number of agents. The algorithm is tested for different numbers of agents, as well as for different avoidance and communication ranges. The needed time to accomplish the mission is used as the performance measurement. The influence of implementing a central communication point, which distributes the state of the search grid among the agents, is analyzed. Having distributed the agents randomly, the results show that the time needed to finish the mission is higher than the theoretical lower bound, even with the centralization of the information. However, even with short communication ranges, the overtime to complete the search is less than 50%, with a standard deviation of 6% on average due to the variability in the initial conditions. With only one agent, the time needed is close to the minimum bound. Furthermore, another performance measurement criterion is proposed:  
\[E=\frac{1}{1+\frac{N_{m}}{N}} \tag{1}\]  
where \(N_{m}\) are the number of cells visited more than once and \(N\) is the total number of cells. Again, for only one member, this ratio is close to one, whereas for the higher number of agents, this figure decreases. If the communication range increases, the solution converges to the centralized map, as expected. In another work [21], three search strategies are compared in a mission in which the agents are deployed in an area that contains targets to be localized and destroyed, forming coalitions. The three studied strategies are:  
* Random search: Each agent follows its current heading until one boundary is reached. At that moment, it changes its direction to re-enter the search area. * Search lanes: The area is organized into lanes, and each agent is assigned to a unique one. Once a lane has been traveled, a new one is assigned. * Grid-based search: The agents go to the closest non-visited cell. Since in this work, targets to be destroyed are considered, the search task stops to pursue and destroy them.