# 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
On the other hand, algorithm variants based on GA obtain better solutions, as GA uses genetic operators (selection, crossover, and mutation) that mitigate the influence of the sub-optimal issue. Among the GA with VRAOA and COA, the GA w/VRAOA performs better. This is because the GA w/VRAOA selects the detour points by making a convex polygon around the obstacle and finds the shortest path among the detour points using the Dijkstra algorithm. On the other hand, the GA w/COA selects the route by making a circle around the obstacle based on an arc-based ADC algorithm,

Figure 10: Effects of the number of obstacles: (**a**) effect on total energy consumption of UAVs, (**b**) effect on average data delivery latency, and (**c**) effect on energy consumption gap (standard deviation) among UAVs. which leads to a longer traveling distance than GA w/VRAOA. Furthermore, the ACO combinations (ACO w/VRAOA and ACO w/COA) perform in the middle of GA and greedy algorithm variants by using the probabilistic technique. ## 6 Concluding Remarks

This study evaluated an obstacle-avoidance data collection (OADC) scheme, where multiple UAVs are appointed to collect data from the sensors. An optimization problem called obstacle-constrained distance minimization (OCDM) is formulated as an ILP problem. The problem aims to find the trajectories for UAVs that minimize the total traveling distances of UAVs in an obstacle-constrained environment, ensuring obstacle avoidance in their traveling paths. A possible detour-points-selection algorithm named VRAOA is proposed for when there is an obstacle in the path, which makes a convex polygon around each obstacle select the possible points for detouring. Then, the UAV trajectories are planned using a genetic algorithm with VRAOA (GA w/VRAOA) that ensures the UAVs' obstacle avoidance with the convex polygons generated by the VRAOA algorithm. To the best of our knowledge, the proposed OADC scheme is much different from existing method, which do not consider that a UAV's path is a Hamiltonian path, and there are also obstacles in the path. In our work, five baseline algorithms are also developed: GA w/COA, ACO w/VRAOA, ACO w/COA, Greedy w/VRAOA, and Greedy w/COA. Simulations are performed in different scenarios to show the effects of different parameters in the presence of obstacles in the environment and to analyze the performance of the proposed method GA w/VRAOA compared to other baseline algorithms under various scenarios. The simulation results show that the trajectory length of a UAV changes depending on the number of obstacles in its path; hence, the energy consumption of the UAV and data delivery latency also change. Therefore, the number of sensors a UAV can visit within the given flight time and the number of UAVs needed to visit all the sensors in the environment will vary depending on the number of obstacles. Furthermore, when the numbers of sensors and UAVs increase, the total energy consumption of UAVs tends to increase, whereas the average data delivery latency increases for an increasing number of sensors and decreases with an increment in the number of UAVs. Moreover, the GA w/VRAOA can achieve a lower traveling distance of UAVs while gathering data with obstacle avoidance compared to other baseline methods. For future work, we plan to consider a machine-learning-based approach, i.e., a reinforcement learning-based method, expecting further minimization of the energy consumption of UAVs. We also plan to take 3D modeling of the obstacles and deadline for the data delivery of the sensors into account. Conceptualization, S.R., S.A. and S.Y. ; methodology, S.R., S.A. and S.Y. ; software, S.R. ; validation, S.R. ; formal analysis, S.R., S.A. and S.Y. ; investigation, S.R., S.A. and S.Y. ; resources, S.R., S.A. and S.Y. ; data curation, S.R., S.A. and S.Y. ; writing--original draft preparation, S.R., S.A. and S.Y. ; writing--review and editing, S.R., S.A. and S.Y. ; visualization, S.R., S.A. and S.Y. ; supervision, S.Y. ; project administration, S.Y. ; funding acquisition, S.Y.