# Path Planning and Real-Time Collision Avoidance Based on the Essential Visibility Graph
## 3 Obstacle Avoidance Using EVG
If \(N_{n}\) new obstacles are detected, let be \(\mathcal{I}_{l}\) the subset of nodes being vertices of the new \(l\)-th obstacle, with \(l=N_{o}+1,\ldots,N_{o}+N_{n}\). Algorithm 2 is run to update the nominal EVG with a lower computational cost compared to the cost required to compute the nominal starting EVG. Figure 5: Optimal path between \(A=\)(\(-3\) km; \(3\) km) and \(B=\)(\(3\) km; \(-3\) km) with initial heading angle \(\psi_{A}=\pi/2\) rad, final heading angle \(\psi_{B}=-\pi/2\) rad, and turn radius \(R_{min}=80\) m.  
```
1 Data: Starting point \(P^{*}\), new obstacles' vertices \(\mathcal{I}_{N_{o}+1},\ldots,\mathcal{I}_{N_{o}+N_{n}}\), nominal EVG \(G=\{\mathcal{W},\mathcal{E}\}\) Result: Updated EVG graph \(G_{new}=\{\mathcal{W}_{new},\mathcal{E}_{new}\}\) Add \(P^{*}\) to \(\mathcal{W}\); \(\mathcal{W}_{new}=\mathcal{W}\); \(\mathcal{E}_{new}=\mathcal{E}\); \(n=1\); ifB is not visible fromP\({}^{*}\)then \(\mathcal{K}_{n}=\{P^{*}\}\); foreacharc \((X,Y)\) in \(\mathcal{E}\)do ifY is not reachable fromXthen  remove arc \((X,Y)\) from \(\mathcal{E}_{new}\);  add X and Y to \(\mathcal{K}_{n}\);  end if  end for ifB\(\in\mathcal{K}_{n}\)then  remove B from \(\mathcal{K}_{n}\) end if while\(\mathcal{K}_{n}\
eq\emptyset\)do \(n=n+1\); \(\mathcal{K}_{n}=\emptyset\); foreachX\(\in\mathcal{K}_{n-1}\)do ifX\(\in\mathcal{I}_{p}\) with \(p=1,...,N_{o}\)then  compute the set \(\mathcal{O}_{X}\) of new obstacle \(\mathfrak{P}_{l}\) (with \(l=N_{o}+1,...,N_{n}\)) reachable from \(X\); foreach\(\mathfrak{P}\in\mathcal{O}_{X}\)do  compute the set of transition nodes \(\mathcal{T}_{\mathfrak{P},X}\); foreachY\(\in\mathcal{T}_{\mathfrak{P},X}\)do ifY\(\
otin\mathcal{W}_{new}\)then  add Y to \(\mathcal{W}_{new}\);  add Y to \(\mathcal{K}_{n}\);  end if  add \((Y,X)\) to \(\mathcal{E}_{new}\);  end if  end if  end for else ifB is visible fromXthen  add arc \((X,B)\) to \(\mathcal{E}\);  else  compute the set of all obstacle \(l\) (with \(l=1,...,N_{n}\)) reachable from \(X\), \(\mathcal{O}_{X}\); foreach\(\mathfrak{P}\in\mathcal{O}_{X}\)do  compute the set of transition nodes \(\mathcal{T}_{\mathfrak{P},X}\); foreachY\(\in\mathcal{T}_{\mathfrak{P},X}\)do ifY\(



procedure based on the EVG and Dubins' paths, to avoid UAVs that are on a collision course. The algorithm is computationally efficient as it makes use of the procedures previously described. When an aircraft predicts multiple future collisions, it selects the nearest one in accordance with a typical reactive scheme [39], and it calls the EVG updating procedure assuming a fictitious additional obstacle centered at the predicted collision position. To avoid ambiguity (i.e., it is possible to overcome the obstacle on the left or on the right), the EVG is cut according to the Right of Way rules prescribed in the Annex II of International Civil Aviation Organization (ICAO). ### Collisions Prediction

In our work, we assume that UAVs know the position, speed, and heading of neighboring aircraft, within a given sensing range given by ADS-B, TCAS, or other sensing devices. Consider the \(i\)-th controlled aircraft and the set \(\mathcal{S}_{i}\) of vehicles in the sensor range. Let \(P_{i}(t)=(x_{i}(t),y_{i}(t))\) and \(P_{j}(t)=(x_{j}(t),y_{j}(t))\in\mathcal{S}_{i}\) be the position of the \(i\)-th and \(j\)-th UAV, respectively. The line of sight vector between aircraft \(i\) and \(j\) is defined as \(LOS_{i,j}=P_{j}-P_{i}\) (see Figure 6). \(\theta^{1}_{i,j}\in[0,2\pi[\) is the angle between the velocity vector of aircraft \(i\) and \(LOS_{i,j}\), and \(\theta^{2}_{i,j}\in[0,2\pi[\) is the angle between the velocity vector of the vehicle located in \(P_{j}\) and \(LOS_{i,j}\) (see Figure 6). The ICAO Right of Way rules can be formalized by defining an operator \(\Phi_{i,j}\), such that \(\Phi_{i,j}=1\), if the \(j\)-th vehicles has the right of way, and \(\Phi_{i,j}=0\) in other cases:

\[