# Event-Based Path-Planning and Path-Following
## 3 Two-Level Control System
### Event-Based Path-Planning
#### 3.3.1 Discrete-Event System
Changing the state of the DES entails the execution of a sequence of actions, which can be regarded as a program that consists of a sequence of self-contained functions. As a result of these actions, a new path \(\mathcal{P}\) is built and/or the active segment \(j_{r}\) is changed. Function \(\mathcal{Q}_{out}=\textsc{SelectObstacleLeftP}(\mathcal{Q}_{in},i)\) generates an obstacle \(\mathcal{Q}_{out}\) from a set of points \(\mathcal{Q}_{in}\) that are produced by FLS by adding all points \(Q_{i_{1}}\) from \(\mathcal{Q}_{in}\) that meet two conditions:  
\[1\leq i_{1}<i\quad\text{and}\quad\exists i_{2}:(i_{1}<i_{2}\leq i\text{ \& }\rho_{i_{2}}\
eq\infty)\quad\text{dist}(Q_{i_{1}},Q_{i_{2}})\leq d_{o}\]  
provided that \(i_{2}=i\) or the point \(Q_{i_{2}}\) also meets these conditions. The order in which the points are added to \(\mathcal{Q}_{out}\) is preserved. Similarly, the function \(\mathcal{Q}_{out}=\textsc{SelectObstacleRightP}(\mathcal{Q}_{in},i)\) is defined, with the only difference that the added points should satisfy  
\[i>i_{1}\geq|\mathcal{Q}_{in}|\quad\text{and}\quad\exists i_{2}:(i\geq i_{2}>i_ {1}\text{ \& }\rho_{i_{2}}\
eq\infty)\quad\text{dist}(Q_{i_{1}},Q_{i_{2}})\leq d_{o}.\]  
Unlike function SelectObstacleLeftP, which forms an obstacle by starting from the point \(i\) and including this point in the output sequence, function \(\mathcal{Q}_{out}=\textsc{SelectObstacleLeft}(\mathcal{Q}_{in})\) determines the obstacle to detour it from its left side. The function chooses from all of the obstacles identified based on FLS data the one for which the direction to its leftmost point deviates least from the heading direction of the AUV. When identifying a set of obstacles, two adjacent points \(Q_{i}\) and \(Q_{i+1}\) of \(\mathcal{Q}_{in}\) are considered to belong to the same obstacle if they satisfy. \[\text{dist}(Q_{i},Q_{i+1})\leq d_{o}.\]  
Similarly, function SelectObstacleRight selects an obstacle for detouring it from its right side. Function InitVTstate initializes the state of the VT after performing a bypass manoeuvre and returning to the reference path. The VT state includes the segment on which the VT is located as well as its curvilinear coordinate, forward speed, and acceleration. Function \(\mathcal{P}=\textsc{AvoidPath}(\mathcal{Q}_{in},\mathcal{D})\) builds a path \(\mathcal{P}\) to detour a selected obstacle \(\mathcal{Q}_{in}\) on the left (\(\mathcal{D}=\)'L') or on the right (\(\mathcal{D}=\)'R'). The path is planned in two steps. First, the convex outline of the obstacle is built while using the RCOA algorithm presented in Section 3.3.2, and then the obtained outline is used to construct an avoidance path by applying a path-planning algorithm that is presented in Section 3.3.3. Finally, function \([\mathcal{P}_{out},j_{out}]=\textsc{DubinsPath}(\mathcal{P}_{in},j_{in}, \mathcal{D}_{s},\mathcal{D}_{f})\) constructs a Dubins path that connects the AUV's current position to the part of the path \(\mathcal{P}_{in}\) that begins with segment \(j_{in}\). The constructed path consists of three segments, each of which corresponds a left-turn arc (L), a right-turn arc (R), or a straight line (S). The function can build the following paths: LSL, LSR, RSL, or RSR. In Figure 7, one can find examples of RSL (red line) and RSR (blue line) paths. Arguments \(\mathcal{D}_{s},\ \mathcal{D}_{f}\subseteq\{\)'L','R'\(\}\) define the allowable motion primitives for the first and third segments of the path. Function DubinsPath works, as follows. First, it tries to find the path to segment \(j_{in}\). If the attempt is unsuccessful, it takes the next segment \(j_{in}+1\) and searches for the path to it. This action is sequentially repeated for all segments of the selected path fragment until a path is found. The function returns the found path \(\mathcal{P}_{out}\) and the index \(j_{out}\) of the segment to which the path is built. A path-planning algorithm that builds a path to a segment is described in detail in Section 3.3.4.