# Path Planning and Real-Time Collision Avoidance Based on the Essential Visibility Graph
## 3 Obstacle Avoidance Using EVG
Dashed lines indicate nominal paths; dashed-dotted lines indicate \(r_{1}\) and \(r_{2}\) straight lines; solid lines indicate the actual UAVs’ trajectories. where the operator \(\Sigma_{i,j}=1\) if the UAV \(i\) must turn to the left in accordance with Right Of Way rules, otherwise \(\Sigma_{i,j}=-1\) if \(i\) must turn to the right:

\[ \begin{cases}\Sigma_{i,j}=1&0\leq\theta^{1}_{ij}\leq\frac{\pi}{2}\quad\theta^{1 }_{ij}<\theta^{2}_{ij}\leq\frac{\pi}{2}\\ \Sigma_{i,j}=1&\frac{3}{2}\pi<\theta^{1}_{ij}<2\pi\quad 0\leq\theta^{2}_{ij} \leq\theta^{1}_{ij}-\pi\\ \Sigma_{i,j}=1&\frac{3}{2}\pi<\theta^{1}_{ij}<2\pi\quad\theta^{1}_{ij}\leq \theta^{2}_{ij}<2\pi\\ \Sigma_{i,j}=-1&\text{otherwise}.\end{cases}  \tag{11}\]

Figure 7 shows the nominal path of two UAVs. UAV \(i\) predicts a collision with UAV \(j^{*}\) at time \(t^{*}\) in \(\hat{P}_{j^{*}}(t^{*})\). Since UAV \(i\) does not have the right of way, it must re-plan its trajectory. Before updating the graph, a fictitious obstacle is added to the environment, centered at the point \(\hat{P}_{j^{*}}(t^{*})\) where the collision is expected. In order to force the UAV \(i\) to avoid the collision with the UAV \(j^{*}\), passing on the right of fictitious obstacle, all arcs of the updated graph in the gray area are considered unfeasible and deleted from he graph. ## 5 Numerical Results

An extensive campaign of numerical simulations was carried out whose results are presented in this section. Several operational scenarios were set to verify the effectiveness of the proposed technique. The selected scenarios are among the most complex ones to suitably test our anti-collision algorithm. Both the planned paths and the actual trajectories, as modified by the collision avoidance system, are shown. Mutual distances between UAVs over time are also shown for scenarios with few aircraft. For the sake of clarity, by increasing the number of aircraft involved, only the minimum distances reached between UAVs are reported in tabular format. Finally, all the vehicles have the same cruise speed and minimum turn radius. Table 1 summarizes the simulation parameters used for Scenarios #1-#6. ### Scenario #1: Two Converging UAVs

In this scenario, two UAVs follow perpendicular flight paths intersecting at one point. When UAV 2 detects a possible collision at time \(t^{*}\), in order to respect the right of way rules (see 3.2.2.3, in ICAO Anne II), it re-plans its path, giving the way to UAV 1, which does not change its planned trajectory. Figure 8 shows the planned paths (dotted lines) and the actual trajectories followed (solid lines) of both UAVs. As can be seen, UAV 2 passes on the right of the expected collision point, in order to pass behind UAV 1, according to the right of way rules. In Figure 9, the distance between the aircraft over time is reported. As we can see, the collision avoidance system is able to guarantee a mutual distance not below the prescribed minimum value of 200 m. \begin{table}
\begin{tabular}{l c} \hline \hline \(d_{min}\) & 200 m \\ \hline Turning Radius \(R_{min}\) & 100 m \\ \hline Cruise Speed \(v_{c}\) & 10 m/s \\ \hline Sample Time \(\Delta t\) & 0.5 s \\ \hline Prediction Time Horizon \(T_{d}\) & 20 s \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Simulation parameters of Scenarios #1–#6. ### Scenario #2: Two Opposite UAVs

In this scenario, two aircraft are approaching from opposite directions following the same path. As prescribed by ICAO Rule 3.2.2.2, in Annex II [70], both UAVs must deviate, re-planning their trajectory in order to turn to the right. Figure 10 shows the vehicles' planned paths (dotted lines) and the actual trajectories followed (solid lines). As can be seen, both UAVs turn on the right near the left. Figure 8: Scenario #1. Two converging UAVs. UAV 1’s initial position \(\mathbf{A_{1}}(0)=(5\) km; 0 km), \(V_{1}(0)=V_{c}\), \(\psi_{1}(0)=\pi\) rad. UAV 2’s initial position \(\mathbf{A_{2}}(0)=(0\) km; \(-5\) km), \(V_{2}(0)=V_{c}\), \(\psi_{2}(0)=\pi/2\) rad. \(t^{*}\) represents the predicted collision time instant.