# 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
From this \(P_{\theta 1}\), find the nearest point \(P_{s}(x,y)\) in the circle from \(S\), where \(x\) and \(y\) are determined from the equations: \(x=O_{x}+(r\times cos(P_{\theta 1}\times(\Pi/180)))\) and \(y=O_{y}+(r\times sin(P_{\theta 1}\times(\Pi/180)))\), respectively. * Similarly, the other nearest point \(P_{d}\) in the circle is obtained using two vectors \((\vec{u},\vec{O}\vec{D})\). Here, \(\vec{O}\vec{D}\) is a vector from the origin \(O\) to destination-sensor-node \(D\), and \(\vec{u}\) is the unit vector. In Figure 6, \(P_{s}\) and \(P_{d}\), are the two nearest points in the arc from \(S\) and \(D\), respectively. The arc angle \(\theta_{a}=|P_{\theta 1}|+|P_{\theta 2}|\) in the origin (\(O\)) of the circle is calculated, where \(|P_{\theta 1}|\) and \(|P_{\theta 2}|\) are the positive angles from unit vector \(\vec{u}\) to \(S\) and \(D\), respectively. Generally, the total angle in an origin of a circle is \(360^{\circ}\), and the remaining arc angle of the circle is \(\theta_{r}=(360^{\circ}-\theta_{a})\). From the two arc angles, choose the smallest arc angle for planning the path; i.e., \(\theta_{s}=min(\theta_{a},\theta_{r})\). * Then, calculate the smallest arc distance \(L_{a}\) between \(P_{s}\) and \(P_{d}\), where \(L_{a}=(\Pi\times r\times(\theta_{s}/180))\). * Finally, the path from \(S\) to \(D\), considering the arc, is found with the traveling distance, \(T_{d}=SP_{s}+L_{a}+P_{d}D\). Here, \(SP_{s}\) and \(P_{d}D\) are the Euclidean distances from \(S\) to \(P_{s}\) and \(P_{d}\) to \(D\), respectively, where \(L_{a}\) is the smallest arc distance from \(P_{s}\) to \(P_{d}\). #### 5.2.2 Greedy with VRAOA (Greedy w/VRAOA)

A greedy approach is proposed for UAV trajectory planning with a fitness function, \(F(i,j)=\mathrm{D}_{ij}\). Here, \(\mathrm{D}_{ij}\) is the traveling distance from sensor \(i\) to \(j\); \(i,j\in\mathbb{N}\). In Greedy w/VRAOA, for each group of sensors, at each step, the path with the smallest \(\mathrm{D}_{ij}\) is selected, whereas \(\mathrm{D}_{ij}\) is calculated from the Dijkstra algorithm together with VRAOA. Otherwise, \(\mathrm{D}_{ij}\) is the Euclidean distance between them. Here, the sensors are grouped using the K-means algorithm. #### 5.2.3 Greedy with COA (Greedy w/COA)

The greedy algorithm with COA is similar to the Greedy w/VRAOA. In the Greedy w/COA, the proposed fitness value between two sensors, \(i\) and \(j\), is calculated from the ADC algorithm together with COA if there is an obstacle between them. Otherwise, the fitness value is calculated from the Euclidean distance formula. #### 5.2.4 ACO with VRAOA (ACO w/VRAOA)

The ant colony optimization (ACO) algorithm [38] is a probability-based approach where ants are randomly placed in cities. Each ant starts its tour by selecting a random city. The next city is chosen by the ant based on a pheromone, i.e., a probability, based on the length of the tour. The pheromone is updated for each visited city using the local pheromone updating rule [39]. The ant complete the tour by visiting one city after another. After each iteration, using a modified global pheromone updating rule [39], only the best ant is permitted to update the trails. The procedure continues until the algorithm has gone through the maximum iterations or the solutions have not changed in recent iterations. After finishing the tour, the ants move back to the starting city. In ACO w/VRAOA, first, we group the sensors using the K-means algorithm. Then, the ACO operation is performed

Figure 6: Graph representation for the ADC algorithm. for each group of sensors. We took the concept from ACO, where ants and cities are considered UAVs and sensor nodes, respectively, and the UAV starts and ends the tour to the base station. The tour lengths between two sensor nodes are calculated using the Dijkstra algorithm together with VRAOA when there is an obstacle between the sensors. Otherwise, the length between them is calculated using the Euclidean distance formula.