# Event-Based Path-Planning and Path-Following
## 3 Two-Level Control System
### Event-Based Path-Planning
#### 3.3.3 Path-Planning Algorithm for Detouring Obstacles  
This section proposes a path-planning algorithm for detouring a single obstacle or a group of obstacles considered as a single one. Given a sequence of points \(\mathcal{Q}_{in}=(Q_{1},Q_{2},\ldots,Q_{N_{0}})\) that represents a convex outline of an obstacle, the algorithm finds a collision-free path \(\mathcal{P}\), which consists of line and arc segments, which satisfies the turning radius constraint \(R_{\text{min}}\) and passes no closer than the safe distance \(D_{s}\) from the obstacle. We restrict ourselves to the case when the AUV detours the obstacle on the left side. Without a loss of generality, we assume that the last point \(Q_{N_{0}}\) of \(\mathcal{Q}_{in}\) is the point with minimum \(R_{\text{max}}\), i.e., \(i_{r}^{\perp}=N_{0}\).  
Figure 4: Building a convex obstacle outline.  
* Take \(i=N_{o}\). Construct the arc segment of radius \(R_{\text{max}}^{i}\) that connects the AUV's current position \(P_{V}\) with the point \(P_{i}^{\prime}\) located at the distance \(D_{s}\) (or \(D_{s}+D_{m}\) after applying the RCOA algorithm) from the obstacle point \(Q_{i}\) (see Figure 5). Add this segment to the avoidance path \(\mathcal{P}\).
* Construct an arc segment \(\langle P_{i}^{\prime},P_{i}^{\prime\prime},\pm R_{\text{min}}\rangle\) that rotates the AUV around its vertical axis until its longitudinal axis is directed along vector \(\vec{v}(Q_{i},Q_{i-1})\) that is drawn from point \(Q_{i}\) to point \(Q_{i-1}\). The direction of the rotation is selected depending on the sign of the angle between vector \(\vec{v}(Q_{i},Q_{i-1})\) and the tangent vector of the constructed segment at point \(P_{i}^{\prime}\). Add the constructed segment to the avoidance path \(\mathcal{P}\).
* Take \(R=R_{\text{min}}\) and calculate \[D_{i-1}=R-(R-D_{i})/\cos\delta,\] where \(D_{i}\) is the distance from point \(P_{i}^{\prime\prime}\) to line \(Q_{i}Q_{i-1}\) and \(\delta\) is the angle between vectors \(\vec{v}(Q_{i},Q_{i-1})\) and \(\vec{v}(Q_{i-1},Q_{i-2})\). The specified \(R\) and \(D_{i}\) uniquely define the arc with center \(O\) and start point \(K\) that wraps around the point \(Q_{i-1}\), as shown in Figure 6a.
* If \(D_{i-1}\geq D_{s}\) then \[R=(D_{i}-D_{s}\cos\delta)/(1-\cos\delta),\quad D_{i-1}=D_{s},\] and we have a new arc with center \(O^{\prime}\) and start point \(K^{\prime}\) (see Figure 6b); otherwise, shift points \(O\) and \(K\) along the vector \(e_{i}\) (the unit vector of \(\vec{v}(Q_{i},Q_{i-1})\)) by \[\Delta=(D_{s}-D_{i-1})/\cos\delta\] to obtain new points \(O^{\prime}\) and \(K^{\prime}\) (see Figure 6c).
* Construct a line segment \(\langle P_{i-1}^{\prime},P_{i-1}^{\prime\prime},0\rangle\) with \(P_{i-1}^{\prime}=K^{\prime}\) and an arc segment \(\langle P_{i-1}^{\prime},P_{i-1}^{\prime\prime},-R\rangle\) with center \(O^{\prime}\) and radius \(R\). Add both segments to path \(\mathcal{P}\).
* If \(i>3\) (point \(Q_{i-2}\) is not the first in \(\mathcal{Q}_{in}\)) then \(i=i-2\) and go to Step 3.
* Supplement path \(\mathcal{P}\) with the line segment \(\langle P_{i-1}^{\prime\prime},P_{i-2}^{\prime},0\rangle\), which is parallel to vector \(\vec{v}(Q_{i-1},Q_{i-2})\), where \(P_{i-2}^{\prime}\) is the point on a line passing through the point \(P_{i-1}^{\prime\prime}\) and parallel to the line \(Q_{i-1},Q_{i-2}\), which is closest to the point \(Q_{i-2}\).  
Figure 5: Building a path that detours obstacle from its left side.