# 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
In ACO w/VRAOA, the tour length is used while updating the pheromone for the visited sensors, where the pheromone is the reciprocal value of the tour length. Thus, the shortest edge with a large amount of pheromone is selected. #### 5.2.5 ACO with COA (ACO w/COA)

The ACO w/COA is similar to the ACO w/VRAOA. The only difference is that, when calculating the total tour length for each pair of sensor nodes, the distance between them is calculated using the ADC algorithm together with COA when there is an obstacle between the sensors. Otherwise, the tour length for each pair is calculated using the Euclidean distance formula. ### UAVs Trajectories Obtained by Our Approach

In this subsection, the trajectories of UAVs obtained by GA with VRAOA (GA w/VRAOA) and GA with COA (GA w/COA) are presented for the proposed OADC scheme in a simple scenario. The performance of GA w/VRAOA and GA w/COA is displayed in a \(10\times 10\) km\({}^{2}\) area in Figure 7, where six different obstacles (dark blue colored) and fifteen sensors in two different clusters (excluding BS) are considered. For Figure 7a, the red convex polygon around each obstacle shape is generated using the VRAOA algorithm. On the other hand, for Figure 7b, the COA algorithm generated the red circle around each obstacle shape. Here, the red dot in each circle indicates the midpoint of each obstacle shape, which considers the origin, to draw the circle around the obstacle. In Figure 7a,b, the sky blue and green trajectories show the trajectories for two UAVs, which are obtained by GA w/VRAOA and GA w/COA, respectively. The UAVs' total traveling distance results obtained by GA w/VRAOA and GA w/COA are 32.263 and 33.133 km, respectively, as shown in Table 3, indicating that the GA w/VRAOA performs better than the GA w/COA in terms of traveling distance. ### Performance Evaluation by Changing the Simulation Parameters

In this subsection, we analyze the GA w/VRAOA's performance compared with other baseline methods--i.e., GA w/COA, ACO w/VRAOA, ACO w/COA, Greedy w/VRAOA, and Greedy w/COA--using different simulation parameters, such as different numbers of sensors, UAVs, and obstacles. Figure 7: Trajectories of the UAVs. (**a**) Trajectory obtained by GA w/VRAOA. (**b**) Trajectory obtained by GA w/COA. #### 5.4.1 Effects of the Different Numbers of Sensors

This study compares the performances of algorithms for different numbers of sensors, where the number of sensors varied from 20 to 100. Figure 8a illustrates that the total energy consumption of UAVs increases consistently with the increasing number of sensors. This is because when the number of sensors increases, UAVs need to visit more places, which increases the traveling distance and energy consumption. Among all the algorithms, the GA w/VRAOA performs better for all cases. In Figure 8a, it is clear that if we consider the path planning algorithms, GA, ACO, and greedy, GA performs better than ACO and greedy with both obstacle avoidance algorithms. Considering the obstacle avoidance algorithms VRAOA and COA, VRAOA performs better than COA for all the path planning algorithms GA, ACO, and greedy. For example, the total energy consumption of UAVs with GA w/VRAOA is 6811.22 KJ when there are 60 sensors. On the other hand, in the solution obtained by other algorithms, UAVs consume more energy than GA w/VRAOA. For example, the total energy consumption of the UAVs in GA w/COA, ACO w/VRAOA, ACO w/COA, Greedy w/VRAOA, and Greedy w/COA are 7171.22, 7354.82, 8232.02, 9145.22, and 9660.02 kiljoules, respectively. Furthermore, the total energy consumption gap increases with the increasing number of sensors. For instance, when the number of sensors is 100, the energy consumption gap is the highest among all the cases of different numbers of sensors. The reason is that UAVs need to consume more energy to collect data when the pool of sensors is large. Figure 8b shows that as the number of sensors increases, the average data delivery latency for all four algorithms increases. The reason is as follows.