# Path Planning and Real-Time Collision Avoidance Based on the Essential Visibility Graph
## 3 Obstacle Avoidance Using EVG
\(\overline{V}_{i}^{*},\overline{V}_{i+1}^{*},\ldots,\overline{V}_{i+p}^{*}\) is a sequence of nodes \(\
otin\mathcal{I}_{l}\) replacing \(\overline{V}_{i},\overline{V}_{i+1},\ldots,\ \overline{V}_{i+m-1}\in \mathcal{I}_{l},\overline{V}_{i-1},\)\(\overline{V}_{i+m}\
otin\mathcal{I}_{l}\) (Figure 4b). Let us define polygon \(\mathfrak{Q}_{1}\) with vertices \(\{\overline{V}_{i-1},\overline{V}_{i},\ldots,\overline{V}_{i+m-1},\overline{ V}_{i+m}\}\) and polygon \(\mathfrak{Q}_{2}\) with vertices \(\left\{\overline{V}_{i-1},\overline{V}_{i}^{*},\ldots,\overline{V}_{i+p}^{*}, \overline{V}_{i+m}\right\}\). As for Case 1a, \(\mathfrak{Q}_{1}\subset\mathfrak{Q}_{2}\), and by virtue of Lemma 1, \(\Lambda(\mathfrak{Q}_{1})\)\(<\Lambda(\mathfrak{Q}_{2})\). We have:  
\[ \begin{array}{ll}d_{\overline{V}_{i-1},\overline{V}_{i}}+d_{\overline{V}_{i} \overline{V}_{i+1}}&+\ldots\\ &+d_{\overline{V}_{i+m-1},\overline{V}_{i+m}}<d_{\overline{V}_{i-1},\overline{ V}_{i}}+\\ &+d_{\overline{V}_{i}^{*},\overline{V}_{i+1}^{*}}+\cdots+d_{\overline{V}_{i+p}^{* }\overline{V}_{i+m}}\end{array}  \tag{5}\]  
contradicting the optimality of path \(\overline{V}_{0},\ldots,\overline{V}_{i-1},\overline{V}_{i}^{*},\ldots, \overline{V}_{i+p}^{*},\overline{V}_{i+m}\ldots V_{n}\). Case 2. \(\overline{V}_{i}^{*}\in\mathcal{I}_{l}\) (Figure 4c). Assume that \(\overline{V}_{i}^{*}\in\mathcal{T}_{\mathfrak{P}_{i},\overline{V}_{i-1}}\) and \(\overline{V}_{i}^{*}\
otin\mathcal{T}_{\mathfrak{P}_{i},\overline{V}_{i+1}}\) (or vice versa). Without loss of generality, assume that \(\overline{V}_{i}^{*}\) lies on the same side that \(\overline{V}_{i}\) belongs to and that \(\overline{V}_{i}\) is reachable from \(\overline{V}_{i}^{*}\). Since \(\overline{V}_{i+1}\) is not reachable from \(\overline{V}_{i}^{*}\), at least one additional node belonging to \(\mathcal{M}_{\mathfrak{P}_{i},\overline{V}_{i+1}}\cap\mathcal{M}_{\mathfrak{P} _{i},\overline{V}_{i}^{*}}\) must be added to the sequence \(\overline{V}_{0},\ \ldots\overline{V}_{i-1},\overline{V}_{i}^{*},\overline{V}_{i+1}, \ldots,\ \overline{V}_{n+1}\). This is by construction vertex \(\overline{V}_{i}\). It turns out that the new sequence of nodes \(\overline{V}_{1},\ldots\overline{V}_{i-1},\overline{V}_{i}^{*},\overline{V}_{ i},\overline{V}_{i+1},\ldots,\ \overline{V}_{n+1}\) defines a trajectory that is longer than that one identified by \(\overline{V}_{0},\ \ldots,\overline{V}_{i-1},\overline{V}_{i},\overline{V}_{i+1}, \ldots,\ \overline{V}_{n+1}\). The following two straightforward corollaries of Theorem 1 hold. **Corollary 1**. : _Given an optimal sequence of nodes \(\overline{V}_{0},\ \ldots,\ \overline{V}_{n+1}\), with (\(\overline{V}_{i}\in\mathcal{I}_{l}\,\ i=1,\ldots,n\)), then this sequence must be a set of clockwise or counterclockwise ordered and adjacent vertices of the \(l\)-th obstacle's convex hull._  
**Corollary 2**. : _Shortest path connecting two points in the presence of \(N_{o}\) obstacles: given two points \(A\) and \(B\), \(B\) being not reachable by \(A\), and \(N_{o}\) obstacles, the optimal piecewise linear trajectory connecting \(A~{}=~{}\overline{V}_{0}\) to \(B~{}=~{}\overline{V}_{n+1}\) is defined by the sequence of \(n+2\) nodes \(\overline{V}_{0},\dots,~{}\overline{V}_{n+1}\), where each intermediate node \(\overline{V}_{i}\), with \(i=1,\dots,n\), belongs to \(T_{\overline{\varphi}_{i},\overline{V}_{i-1}}\cap T_{\overline{\varphi}_{i}, \overline{V}_{i+1}}\) with obstacle \(\mathfrak{P}_{l}\in\mathcal{O}_{\overline{V}_{i-1}}\cap\mathcal{O}_{\overline {V}_{i+1}}\)._  
The Essential Visibility Graph (EVG) \(\mathcal{G}=\{\mathcal{W},\mathcal{E}\}\) can be then computed using a branching algorithm reported in the form of pseudo-code in Algorithm 1.