# Path Planning and Real-Time Collision Avoidance Based on the Essential Visibility Graph
## 3 Obstacle Avoidance Using EVG
\begin{cases}\Phi_{i,j}=1&\forall\theta^{2}_{i,j}\cap\frac{3}{2}\pi\leq \theta^{1}_{i,j}<2\pi\\ \Phi_{i,j}=1&0\leq\theta^{2}_{i,j}\leq\frac{\pi}{2}\cap 0\leq\theta^{1}_{i,j} \leq\frac{\pi}{2}\\ \Phi_{i,j}=1&\pi\leq\theta^{2}_{i,j}<2\pi\cap 0\leq\theta^{1}_{i,j}\leq \frac{\pi}{2}\\ \Phi_{i,j}=0&\text{otherwise}\,.\end{cases}  \tag{6}\]

At any time \(t\), by evaluating the operator \(\Phi_{i,j}(t)\), \(\forall j\in\mathcal{S}_{i}(t)\), it is possible to determine the list \(\overline{\mathcal{S}}_{i}(t)\) of vehicles taking priority in accordance with the ICAO rules:

\[\overline{\mathcal{S}}_{i}(t)=\left\{j\in\mathcal{S}_{i}(t):\Phi_{i,j}(t)=1\right\} \tag{7}\]

In the prediction time horizon \([t,t+T_{d}]\), the \(i\)-th aircraft control system computes the predicted distance \(\hat{d}_{ij}(\tau|t)\), with \(\tau\in[t,t+T_{d}]\) for each vehicle \(j\in\overline{\mathcal{S}}_{i}(t)\), assuming that the intruders fly on a straight path at constant speed \(v_{j}\). If \(\hat{d}_{ij}(t)\) is less than the minimum separation distance \(d_{min}\), a collision

Figure 6: Line Of Sight (LOS) definition. can occur, and vehicle \(j\) is added to the set of colliding aircraft, namely \(\mathcal{S}_{i}^{*}\subseteq\overline{\mathcal{S}}_{i}\subseteq\mathcal{S}_{i}\). Assuming that \(t_{i,j}^{*}\) is the time of collision between \(i\) and \(j\), predicted at time \(t\), the \(i\)-th aircraft control system selects the nearest collision, i.e., aircraft \(j^{*}\) such that \(t_{i,j^{*}}^{*}\) is minimum, say \(t^{*}\) this time. ### Anti-Collision Flight Path Update

Consider that the \(i\)-th aircraft is following its nominal path \(\Gamma_{0}\), and at time \(t\), it predicts a collision with aircraft \(j^{*}\) at time \(t^{*}\). Let \(\hat{P}_{j^{*}}(t^{*})\) be the position of aircraft \(j^{*}\) at collision time \(t^{*}\). Assume a fictitious obstacle of \(m\) vertices circumscribed to a circumference with the center at \(\hat{P}_{j^{*}}(t^{*})\) and radius \(d_{min}\) (see Figure 7). If the obstacle overlaps with other existing obstacles in the scenario, consider the convex hull of the vertices of the overlapped obstacles plus the fictitious obstacle. The nominal EVG is then updated using Algorithm 2. The Right of Way rules prescribe that \"An aircraft that is obliged by the following rules to keep out of the way of another shall avoid passing over, under or in front of the other, unless it passes well clear and takes into account the effect of aircraft wake turbulence\" (Section 3.2.2.1 in [70]). For this reason, a cut of the EVG is needed to plan a path compliant with the rules. Consider a straight line \(r_{1}\) passing through \(P_{i}(t)\) and \(\hat{P}_{j^{*}}(t^{*})\):

\[r_{1}:\quad\beta\cdot(x-x_{i}(t))-\alpha\cdot(y-y_{i}(t))=0 \tag{8}\]

where \(\alpha\) and \(\beta\) are the components of the vector \(\hat{P}_{j^{*}}(t^{*})-P_{i}(t)=[\alpha,\beta]^{T}=[\hat{x}_{j^{*}}(t^{*})-x_{ i}(t)\), \(\hat{y}_{j^{*}}(t^{*})-y_{i}(t)]^{T}\). Consider a straight line \(r_{2}\) passing through \(\hat{P}_{j^{*}}(t^{*})\) and the target point \(B=(x_{B},y_{B})\):

\[r_{2}:\quad\
u\cdot\left(x-\hat{x}_{j^{*}}(t^{*})\right)-\mu\cdot\left(y-\hat{ y}_{j^{*}}(t^{*})\right)=0 \tag{9}\]

where \(\mu\) and \(\
u\) are the components of the vector \(B-\hat{P}_{j^{*}}(t^{*})=[\mu,\
u]^{T}=[x_{B}-\hat{x}_{j^{*}}(t^{*}),\quad y_{ B}-\hat{y}_{j^{*}}(t^{*})]^{T}\). To follow the Right of Way rules, the optimization algorithm over the EVG can choose only vertices in the semi-plane defined using \(r_{1}\) and \(r_{2}\) and the following conditions:

\[ \begin{cases}-\Sigma_{ij^{*}}\cdot\left[\beta\cdot(x-x_{i}(t))-\alpha\cdot(y -y_{i}(t))\right]\leq 0\\ -\Sigma_{ij^{*}}\cdot\left[\
u\cdot\left(x-\hat{x}_{j^{*}}(t^{*})\right)-\mu \cdot\left(y-\hat{y}_{j^{*}}(t^{*})\right)\right]\leq 0\end{cases}  \tag{10}\]

Figure 7: Anti-collision path update: All graph edges in the gray area are deleted in order to force UAV \(i\) to pass behind UAV \(j^{*}\), i.e., on the right of the fictitious obstacle centered at \(\hat{P}_{j^{*}}(t^{*})\).