# Comparison of Heuristic Algorithms in Discrete Search and Surveillance Tasks Using Aerial Swarms
## 1 Introduction
### Search with Swarms  
From the very beginning of the development of swarm robotics, researches have focused on implementing behaviors in robots to solve simple tasks [7]. Those behaviors are mainly inspired by how natural swarms act, and the missions may be used as test beds for more complex and useful tasks. Typical examples of them are aggregation (gathering in a common place), flocking, foraging (collecting items scattered in the space), path formation (establishing a path of robots between two points) and deployment (expanding and occupying the available space). Note that all of these behaviors are very common in animal swarms such as fish schools, bird flocks, ants and bees. Besides those basic tasks, more complex missions have been also studied in the past. Exploration of unknown areas, search, surveillance, patrolling, collaborative manipulation and self-assembly are only some examples of missions that have been carried out with robotic swarms. In this work, the focus is on the search task, where multiple and different solutions have been proposed over the years. Most of these methods may be assigned to one of the following categories:  
* Virtual pheromones: Inspired by the chemicals dropped by some insects, the search is led using them in their virtual version [8; 9]. They are conveniently created and eliminated, and in many cases, their transportation in the area of interest is calculated by means of the diffusion equation. * Potential fields: The agents are subjected to virtual potential fields created by them or by other objects (such as obstacles) and react to them [10]. * Flocking techniques: Mimicking flocks of birds and schools of fishes, the agents move coordinately, keeping appropriate distances between them [11]. * Probabilistic maps: Making use of prior knowledge of the locations of the targets, the robots search according to it [12]. Adapting the decisions depending on the data acquired during the process is also possible [13]. * Patterns: These comprise a wide range of methods and techniques that try to organize the search to achieve high efficiencies [14; 15; 16]. As can be seen, all the previous solutions are heuristic methods, since they do not guarantee optimal solutions. There have been approaches trying to optimally solve the search, although they require high computational loads, and the calculations only reach reduced time horizons. Note that the number of solutions increase exponentially with the number of agents, making the finding of optimal solutions almost intractable. Some of these methods will be briefly reviewed in Section 1.4. In this paper, we propose an algorithm based on a behavioral network, made up by different behaviors that act together to obtain a common decision in order to lead each agent. On the one hand, this type of control responds quickly to changes in the environment (which is a typical property of reactive systems). On the other hand, the behaviors are capable of constructing representations of the world (they have memory, a typical property of the deliberative controls). Decisions are taken as a result of the interactions between the behaviors and the environment and between the behaviors. All this results in a good trade-off between reactive and mid-term decisions [17]. Behavior-based architectures turn out to be adequate for changing and stochastic environments, and therefore, they are also very suitable for multi-agent systems. Note that if each agent makes its own decisions (there is no central planning), the state of the task changes rapidly, and planning at the individual level becomes likely unfeasible. The search task is an interesting challenge not only because of its direct application in real-world situations, but also because it may be extended to similar, but more complex tasks such as surveillance, exploration, patrolling, area coverage and the so-called traveling salesman problem:  
* Exploration: This differs from search in that there does not exist a previous map of the area. * Surveillance: This is basically persistently searching a given area.