# OADC: An Obstacle-Avoidance Data Collection Scheme Using Multiple Unmanned Aerial Vehicles
## 4 Algorithms
### A Genetic-Algorithm-Based Path Planning with VRAOA (GA w/VRAOA)
#### 4.2.3 Selection, Crossover, and Mutation Operators
Average data delivery latency \(L_{avg}\) is represented as \[L_{avg}=\frac{\mathcal{T}}{c}\] (18) where \(\mathcal{T}\) is the total time needed to deliver the data to the BS by the UAVs, and \(c\) is the number of UAVs. * Energy consumption gap among UAVs \(\left(K\right)\): A statistic that expresses how far apart the UAVs' energy consumption levels are from one another, which expresses how much UAV energy consumption is balanced. The energy consumption gap \(V\) is represented as \[V=\sqrt{\frac{\sum\left(X_{i}-\bar{X}\right)^{2}}{n}}\] (19) where \(X_{i}\) is the value of UAV energy consumption, \(\bar{X}\) is the mean of the energy consumption of all UAVs, and \(n\) is the number of UAVs. ### Description of the Compared Algorithms

The GA w/VRAOA algorithm was compared with five other baseline algorithms, which is described below. #### 5.2.1 Genetic Algorithm with COA (GA w/COA)

Circle-Based Obstacle Avoidance Algorithm (COA)

Given the connected edges of a polygon-shaped obstacle in a set \(\mathbb{E}\) and all coordinates which connect the edges in a set \(\mathbb{C}\), the steps of COA are given below. * First, select two coordinates \(A(x_{min},y_{min})\) and \(B(x_{max},y_{max})\), where \(x_{min}\), \(y_{min}\), \(x_{max}\), and \(y_{max}\) are the minimum value in the x-axis, the minimum value in the y-axis, the maximum value in the x-axis, and the maximum value in the y-axis, respectively, in \(\mathbb{C}\). * Then, from these two points, calculate a midpoint \(M\), where \(M=(\frac{x_{min}+x_{max}}{x_{min}},\frac{y_{min}+y_{max}}{2})\). Calculate the euclidean distances from \(M\) to all other points in \(\mathbb{C}\), and from those distances, take the maximum distance as the radius \(r\). * Finally, using \(M\) as the origin and the radius \(r\), make a circle. Figure 5 shows the sample inputs and outputs of the COA algorithm. The genetic algorithm with COA (GA w/COA) is similar to the GA w/VRAOA, which is described in the algorithm section. The only difference is in how the fitness value is obtained. In GA w/COA, the traveling distance \(d_{ij}\) between the sensors \(i\) and \(j\) is determined by the arc-based distance calculation (ADC) algorithm when there is an obstacle between sensor \(i\) and \(j\). Otherwise, \(d_{ij}\) is the Euclidean distance from sensor \(i\) to sensor \(j\). The ADC algorithm is explained below. Arc-based distance calculation (ADC) algorithm for calculating the distance between two sensors: Arc-based distance calculation (ADC) uses COA to obtain the detour path of a UAV if an obstacle exists in the path from sensor \(i\) to \(j\). The input of the ADC is as follows: origin \(O\) and radius \(r\) from COA, the source sensor node \(S\) (sensor \(i\)), and destination sensor node \(D\) (sensor \(j\)). The output of ADC is the path from \(S\) to \(D\), which ensures that the UAV avoids the obstacle between two sensors, \(S\) and \(D\). Figure 6 shows the output path for the ADC algorithm, where the path starts from \(i\) to \(j\) by visiting the arc \(L\). Here, the arc \(L\) starts at point \(P_{s}\) and ends at point \(P_{d}\). The steps of the ADC algorithm, according to Figure 6, are given below:

* At first, consider a unit vector, \(\vec{u}=<1,0>\), from origin \(O\). Calculate the angle from \(\vec{u}\) to vector \(\vec{OS}\) according to the equation \(\theta=cos^{-1}\bigg{(}\frac{\vec{u}\vec{OS}}{||\vec{u}||+|\vec{OS}|}\bigg{)}\); \(\theta\) is in degrees. Here, \(\vec{OS}\) is a vector from the origin \(O\) to the source-sensor-node \(S\). Consider the coordinates of \(O\) and \(S\) are \((O_{x},O_{y})\) and \((S_{x},S_{y})\), respectively. In this case, if \(O_{y}\leq S_{y}\)

Figure 5: Sample inputs and outputs of COA. (**a**) Input sample 1. (**b**) Output sample 1. (**c**) Input sample 2. (**d**) Output sample 2.

the actual angle will be \(P_{\theta 1}=\theta\); otherwise, \(P_{\theta 1}=-\theta\).