# Comparison of Heuristic Algorithms in Discrete Search and Surveillance Tasks Using Aerial Swarms
## 1 Introduction  
### Multi-Agent and Swarm Robotics  
In nature, as well as in our societies, it is easy to find individuals that act together to achieve a specific goal. In some cases, a good performance cannot be achieved without a coordinated action of various agents. In some other cases, it may be even mandatory to use more than one agent. With the development of robotics, it has been possible to cover increasingly complex tasks by using groups of intelligent agents that coordinately act as a team. In many circumstances, subdividing those tasks not only speeds up their fulfillment, but also allows specialization by allocating specific tasks to agents designed for those purposes. On the other hand, multi-agent systems present important complexities that must be correctly addressed, among which we can highlight the coordination of the agents, the communications between them and how to make the team learn in order to improve the performance.  
There are several cases in which the use of multi-agent systems may be desirable. In [1], three types of tasks are considered: tasks that require multiple agents (for example, a task that needs the simultaneous presence of an agent in two places separated by a great distance); tasks that are traditionally multi-agent (e.g., because they can be naturally divided); and tasks that might benefit from the use of multiple agents. Search, surveillance and exploration belong to this last group. Some other tasks might not benefit from the use of more than one robot, either because they are simple or because the development of the coordination and the communication between the members is a barrier not worth overcoming.  
Some examples in nature show that individually, simple animals have been capable of surviving during millions of years all over the Earth. Consider for example the most well known of these animals, ants. Ants have a very simple nervous system made up by 250,000 neurons and very limited sensing and communication capabilities. Communications are achieved mostly by pheromones [2], chemicals spread in the environment used to mark trails, warn other members of the nest and confuse enemies. It is obvious how difficult it would be for them if they had to survive individually. However, acting as a coordinated group, they have survived for 130 million years and form around 15-25% of the terrestrial animal biomass. The reason why such a simple creature has been so successful is because of their collective behavior. Every ant acts in a very simple way that turns out to be very inefficient individually. However, collectively, because of the high number of members, an efficient behavior emerges. Similar social structures and interactions may be found in other species, such as bees, termites, fishes (forming schools), ungulates and birds (flocks).  
Swarm behaviors are a particular case of collective behavior, in which a large number of members is involved, requiring very limited communications between them and being individually simple. Some researches started bringing the ideas of swarms in nature to the robotics field. Goals are achieved using a high number of homogeneous robots, which behave following simple and mostly reactive rules. The pioneers of swarm robotics appeared in the late 1980s and the beginning of the 1990s [3; 4; 5]. Swarm robotic systems present some well-known advantages such as robustness, simplicity, scalability and flexibility, while it is difficult to achieve a good global performance [6]. More recently, many researchers have used the term swarm robotics to name or classify these works. Hardware miniaturization and cost reduction have made possible new research lines in this direction, and hundreds of papers developing all sorts of algorithms have been published.