# Path Planning and Real-Time Collision Avoidance Based on the Essential Visibility Graph
## 3 Obstacle Avoidance Using EVG
If \(\mathfrak{P}_{I}\subset\mathfrak{P}_{E}\), \(\mathfrak{P}_{I}\) has at least one side that is not coincident with any side of \(\mathfrak{P}_{E}\). Without loss of generality, we start prolonging this side, to intersect two sides of \(\mathfrak{P}_{E}\). With reference to Figure 3, let us consider the prolongation of sides \(Y_{1}Y_{2}\) that intersect the sides \(X_{1}X_{6}\) and \(X_{2}X_{3}\) of \(\mathfrak{P}_{E}\) at points \(H_{1}\) and \(H_{2}\), respectively. Polygon \(\mathfrak{P}_{1}\), defined by vertices \(\{H_{1}H_{2}X_{3}X_{4}X_{5}X_{6}\}\) in a clockwise sense, is such that \(\mathfrak{P}_{I}\subseteq\mathfrak{P}_{1}\subset\mathfrak{P}_{E}\). Since \(d_{H_{1}H_{2}}<d_{H_{1}X_{1}}+d_{X_{1}X_{2}}+d_{X_{2}H_{2}}\) (\(d_{X_{i}X_{k}}\) is the length of segment \(\overline{X_{j}X_{k}}\)), then \(\Lambda(\mathfrak{P}_{1})\)\(<\ \Lambda(\mathfrak{P}_{E})\). With the same procedure, we can generate polygon \(\mathfrak{P}_{k+1}\subseteq\mathfrak{P}_{k}\) prolonging the other sides of \(\mathfrak{P}_{I}\) to intersect the sides of \(\mathfrak{P}_{k}\) and demonstrate that \(\Lambda(\mathfrak{P}_{k})\)\(\geq\ \Lambda(\mathfrak{P}_{k+1})\). Therefore, we can build a sequence of \(n\) polygons such that \(\Lambda(\mathfrak{P}_{1})\geq\Lambda(\mathfrak{P}_{2})\geq\cdots\geq\Lambda( \mathfrak{P}_{n-1})\geq\Lambda(\mathfrak{P}_{n})\) with \(\mathfrak{P}_{I}\equiv\mathfrak{P}_{n}\). **Theorem 1**. : _Shortest path connecting two points in the presence of one obstacle: Given two points \(A\) and \(B\), \(B\) being not reachable from \(A\), and one single obstacle \(\mathfrak{P}_{I}\), whose vertices are also nodes of the graph (set of nodes \(\mathcal{I}_{i}\)), then the optimal path connecting node \(\overline{V}_{0}=A\) to \(\overline{V}_{n+1}\ =\ B\) is a piecewise linear path defined by the sequence of \(n+2\) nodes \(\overline{V}_{0},\overline{V}_{1},\ldots,\ \overline{V}_{n+1}\) with \(\overline{V}_{i}\in\mathcal{T}_{\mathfrak{P}_{1},\overline{V}_{i-1}}\cap \mathcal{T}_{\mathfrak{P}_{1},\overline{V}_{i+1}},\ \ \forall i=1,\ldots,n\)._  
Proof. : Let us prove by contradiction, assuming that there exists an optimal piecewise linear path defined by the sequence of nodes \(\overline{V}_{0},\ \ldots,\overline{V}_{i-1},\overline{V}_{i}^{*},\overline{V}_{i+1}, \ldots,\ \overline{V}_{n+1}\) with \(\overline{V}_{i}^{*}\
otin\mathcal{T}_{\mathfrak{P}_{1},\overline{V}_{i-1}} \cap\mathcal{T}_{\mathfrak{P}_{1},\overline{V}_{i+1}}\). Case 1. \(\overline{V}_{i}^{*}\
otin\mathcal{I}_{I}\). Case 1a. \(\overline{V}_{i}^{*}\) is reachable from nodes \(\overline{V}_{i-1}\
otin\mathcal{I}_{I}\) and \(\overline{V}_{i+1}\
otin\mathcal{I}_{I}\) (Figure 4a). Let us define triangular polygon \(\mathfrak{Q}_{1}\) with vertices \(\{\overline{V}_{i-1},\overline{V}_{i},\overline{V}_{i+1}\}\) and triangular polygon \(\mathfrak{Q}_{2}\) with vertices \(\left\{\overline{V}_{i-1},\overline{V}_{i}^{*},\overline{V}_{i+1}\right\}\). Segment \(\overline{V}_{i-1}\overline{V}_{i+1}\) necessarily cuts the obstacle, otherwise the optimal sequence of nodes would have been \(\overline{V}_{0},\ \ldots,\overline{V}_{i-1},\overline{V}_{i+1},\ldots,\ \overline{V}_{n},\ \overline{V}_{n+1}\), then \(\mathfrak{Q}_{1}\subset\mathfrak{Q}_{2}\), and by virtue of Lemma 1, \(\Lambda(\mathfrak{Q}_{1})\)\(<\Lambda(\mathfrak{Q}_{2})\). Since \(\mathfrak{Q}_{1}\) and \(\mathfrak{Q}_{2}\) share one side, we have:  
\[d_{\overline{V}_{i-1},\overline{V}_{i}}+d_{\overline{V}_{i},\overline{V}_{i+1 }}\leq d_{\overline{V}_{i-1},\overline{V}_{i}^{*}}+d_{\overline{V}_{i}^{*}, \overline{V}_{i+1}} \tag{4}\]  
which implies that the length of the piecewise linear path through the sequence of nodes \(\overline{V}_{0},\ \ldots\overline{V}_{i-1},\overline{V}_{i}^{*},\overline{V}_{i+1}, \ldots,\ \overline{V}_{n+1}\) is not shorter than the length of the piecewise linear path through nodes \(\overline{V}_{0},\ \ldots\overline{V}_{i-1},\overline{V}_{i},\overline{V}_{i+1}, \ldots,\ \overline{V}_{n+1}\), contradicting the optimality of the first sequence. Case 1b.