# Path Planning and Real-Time Collision Avoidance Based on the Essential Visibility Graph
## 3 Obstacle Avoidance Using EVG
Each aircraft, in its prediction phase, considers a fictitious obstacle centered at the predicted collision point that overlaps with the existing real obstacles. Therefore, as stated in Section 4.2, a unique larger obstacle is considered by merging the existing ones. For this reason, the resulting path does not pass in the center of the scenario. The distances over time between UAVs are shown in Figure 17. As we can see, mutual distances never fall below the minimum required value. Due to the symmetry of the scenario, the distances between Aircraft 1-3 and 2-4 are superimposed, the same as the distances between Aircraft 1-2, 1-4, 2-3, and 3-4. Finally, to update the aircraft trajectories, the proposed algorithm never took more than 0.01 s for the scenarios without obstacles and 0.03 s for the scenario with static obstacles by using an Intel i7 based laptop. This feature suggests that the proposed procedure can be considered a promising approach for real-time applications. Figure 15: Scenario #6. Sixteen UAVs following parallel paths pointing to the opposite side. Dotted lines represent the UAVs’ planned paths, whereas solid lines represent the actual trajectories. ## 6 Conclusions

This paper describes a novel procedure to generate optimum flight paths in dynamic environments featuring the simultaneous presence of multiple flying vehicles and fixed or moving obstacles. A real-time collision avoidance algorithm was developed based on the Essential Visibility Graph (EVG) solving the optimization problem as a minimum cost piecewise linear path search. It was assumed that

Figure 16: Scenario #7. Four UAVs converging to the center of the airspace and pointing to the opposite side in the presence of fixed obstacles. \(A_{i}=(20\cos(\alpha_{i});20\sin(\alpha_{i}))\) km, \(\alpha_{i}=(i-1)(2\pi/4)\)\(\forall i=1,\ldots,4\), \(V_{i}(0)=V_{c}\), \(\psi_{i}=\alpha_{i}+\pi\). Dotted lines represent the UAVs’ planned paths, whereas solid lines represent the actual trajectories. Obstacles are represented as yellow boxes. Figure 17: Scenario #7. Distances over time between UAVs. The distances between UAVs 1–3 and 2–4 are superimposed, the same as the distances between UAVs 1–2, 1–4, 2–3, and 3–4. all the air vehicles present in the airspace share information about their position, speed, and direction. This way, if a possible collision is detected within a fixed time horizon, a re-planning procedure is called that updates the EVG and changes the aircraft's current trajectory, avoiding UAVs that are on a collision course. The use of Dubins' curves allows obtaining smoothed paths compliant with the flight mechanics constraints. In view of possible future applications in hybrid scenarios where both manned and unmanned aircraft share the same airspace, visual flight rules compliant with the ICAO Anne II Right of Way were implemented. To test the effectiveness of the proposed algorithm, different operational scenarios of increasing complexity were defined. All the numerical simulations proved the algorithm's capability to avoid possible collisions by quickly changing the aircraft's current trajectories, assuring a minimum safety distance between air vehicles as well. Furthermore, the low computational burden suggests that the proposed procedure can be considered a promising approach for real-time applications. Future research activities will be directed toward the implementation of this new anti-collision algorithm in a guidance and navigation system taking into account possible atmospheric disturbances and model uncertainties. This will assure the identification of real flyable trajectories. Conceptualization, methodology, investigation, formal analysis, and writing, E.D., I.N., L.B., and M.M. Data curation, visualization, and software development, E.D. and I.N. All authors read and agreed to the published version of the manuscript. This research was partially funded by REGIONE CAMPANIA, SCAVIR Project \"Advanced Configurations Studies for an Innovative Regional Aircraft\" CUP B43D18000210007. The authors declare no conflict of interest.