# Comparison of Heuristic Algorithms in Discrete Search and Surveillance Tasks Using Aerial Swarms
## 2 Problem Formulation  
### Scenario  
The task proposed consists of observing a given two-dimensional search space, which is a rectangular area subdivided into cells of fixed size. The movement of the agents is restricted to those cells, so that each agent is allowed to move from the center of each cell to the center of any of the eight adjacent cells. As already mentioned, this assumption is convenient, since it converts the search into a discrete problem, simplifying it.  
We consider that the search is carried out by flying robots, more specifically, multicopters. The agents are capable of flying at a constant altitude and at given commanded velocity \(v_{n}\) and are equipped with a camera capable of detecting targets within a circular area of radius \(R_{f}\). This area is called the sensor footprint. The team of robots is made up by \(N_{a}\) of equal multicopters, initially deployed randomly in non-coincident positions in the search area. Each agent will be configured equally, i.e., the control parameters will be the same for each one.  
Having divided the search space into a grid, with a total area of \(A_{s}\) (m\({}^{2}\)), we allow the robots to move to any adjacent cell. In order to ensure that the cells are completely observed by the sensor footprint, they must be inscribed in it. Therefore, the number of cells in each direction is:  
\[n_{x} =\lceil\frac{L_{x}}{\sqrt{2}R_{f}}\rceil \tag{2a}\] \[n_{y} =\lceil\frac{L_{y}}{\sqrt{2}R_{f}}\rceil \tag{2b}\]  
where \(\lceil\ \rceil\) indicates the ceil function, and the dimensions of each search cell are:  
\[\Delta L_{x} =\frac{L_{x}}{n_{x}} \tag{3a}\] \[\Delta L_{y} =\frac{L_{y}}{n_{y}} \tag{3b}\]  
When flying in any direction, part of the adjacent cells is observed; see Figure 1. Those cells, which we will denominate from now on search cells, should be then subdivided into thinner cells to take into account whether those portions of space have been observed or not. We will refer to these other cells as discretization cells. Therefore, the movement will be restricted to the search cells, but not the search task itself, since a search cell can be completely observed without visiting it. We consider for the rest of the work a size of the discretization cells of \(2\times 2\) m, i.e., \(\Delta l_{x}=\Delta l_{y}=\Delta l=2\) m.  
In Figure 1, both types of cells have been represented. We define observing a cell as placing an agent so that at least half of that discretization cell is inside the sensor footprint. We also define visiting a cell as placing an agent in the center of that search cell. Since the search cells are inscribed in the sensor footprint, visiting a search cell implies observing the discretization cells inside it.  
In Table 1, the parameters that define the scenarios with their considered range of values have been presented. Note that instead of limiting the total search area \(A_{s}\), it is more sensible to limit the search area per agent, \(A_{s}/N_{a}\). On the other hand, we define the aspect ratio \(f_{A}\) of the search space as:  
\[f_{A}=\frac{L_{x}}{L_{y}} \tag{4}\]