# Path Planning and Real-Time Collision Avoidance Based on the Essential Visibility Graph
## 3 Obstacle Avoidance Using EVG
For this test case, given the large number of aircraft, we preferred not to report the entire table with the minimum distances between aircraft, which, anyway, were never below 221 m.

### Scenario #5: Four Converging Pairs of UAVs

In this scenario, eight vehicles grouped into four pairs are involved. All the aircraft follow parallel nominal paths pointing to their own destination points on the opposite side. The distance between parallel paths is 0.3 km. This scenario represents a challenging test case for our collision avoidance algorithm as any turn maneuver of one vehicle can affect the behavior of the others. The planned (dotted lines) and actual trajectories (solid lines) are shown in Figure 14. As can be seen, compliance with the ICAO right of way rules forces all the UAVs to turn right of the colliding aircraft near the center of the airspace. This makes the actual trajectories possibly deviate greatly from the planned ones. Again, as previously done, only the minimum distances between aircraft are resumed in Table 3. In this case as well, the collision avoidance algorithm is able to assure the required minimum value. Figure 13: Scenario #4. Twenty UAVs uniformly distributed as a circular pattern converging at the center of the airspace and reaching the destination points on the opposite side. UAVs’ initial position \(A_{i}=(5\cos(\alpha_{i});5\sin(\alpha_{i}))\) km, \(\alpha_{i}=(i-1)(2\pi/20)\quad\forall i=1,\dots,20\), \(V_{i}(0)=V_{c}\), \(\psi_{i}=\alpha_{i}+\pi\). Dotted lines represent the UAVs’ planned paths, whereas solid lines represent the actual trajectories. Circular markers indicate the UAVs’ positions at the time the collision is predicted. ### Scenario #6: Sixteen Converging UAVs

In this scenario, to further test our anti-collision algorithm, sixteen aircraft, grouped into four formations of four UAVs each, are involved following parallel paths pointing to their own destination points on the opposite side. The distance between parallel paths is 0.3 km. Planned paths (dotted lines) and actual trajectories (solid lines) are shown in Figure 15. As we can see, with the exception of UAVs on the right side of the flight formations (UAVs 4, 8, 12, and 16), all the others are forced to deviate strongly from their planned trajectories to avoid a collision with other vehicles while complying with the ICAO rules. In this test case as well, given the large number of aircraft, we preferred not to report the entire table with the minimum distances between aircraft, which, anyway, were never below 213 m.

Figure 14: Scenario #5. Four pairs of UAVs following parallel paths pointing to the opposite side. Dotted lines represent the UAVs’ planned paths, whereas solid lines represent the actual trajectories. \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline
**1** & **2** & **3** & **4** & **5** & **6** & **7** & **8** \\ \hline
1 & - & 294 & 643 & 526 & 221 & 372 & 372 & 702 \\
2 & - & 930 & 643 & 658 & 702 & 221 & 658 \\
3 & & - & 294 & 658 & 221 & 702 & 658 \\
4 & & & - & 702 & 372 & 372 & 221 \\
5 & & & & - & 294 & 643 & 930 \\
6 & & & & & - & 526 & 643 \\
7 & & & & & & - & 294 \\
8 & & & & & & & - \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Scenario #5: Minimum distances between UAVs (m). ### Scenario #7: Four Converging UAVs in the Presence of Fixed Obstacles

In this scenario, four UAVs are involved following perpendicular flight paths in the presence of four fixed obstacles placed near the center point of the airspace where collision is expected. All the aircraft have to reach their own destination points placed on the opposite side. In this scenario, the desired minimum distance was chosen equal to \(d_{min}=4\) km and the minimum turn radius \(R_{min}=400\) m. All nominal paths (dotted lines) converge towards the center and pass through the two narrow perpendicular channels created by the four obstacles. Each vehicle must re-plan its trajectory to avoid a collision by performing a turn maneuver in order to fly out of the area occupied by the obstacles (see Figure 16).