2.1 Modelling of the underwater path planning problem

In this study, the underwater environment of the UUV is considered as a 2D or 3D workspace, whose dimensions vary according to the requirements of the simulation. The obstacles in the environment are represented by black circles (black spheres for 3D space) t randomly distributed in the space, where the radii of all the circles are set at one for computational convenience (see Figure 1). For the path planning problem in the underwater environment, the positions of the vehicle origin and its supposed destination are known at the beginning. The task of the path planning algorithm is to find the optimal path between the origin and the destination, by avoiding all the obstacle circles and travelling as short a distance as possible.

Figure 1.

Modelling of the 2D underwater environment for UUV path planning

In the practical case of UUV navigation, the effects of ocean currents of complex fluid status cannot be neglected. Flow from various directions and of different rates brings uncontrollable deviation to the vehicle navigation, thus resulting in the failure of the navigation. Therefore, changing directions and velocities are extracted as the two main characteristics of the ocean currents, and tuned in the simulation to evaluate the effectiveness of the proposed method when applied in the corresponding underwater environment. The direction of the current in the 2D model is represented by blue arrows marked on the map (Figure 1).

2.2 Path planning algorithm design

In response to the requirement of eliminating the effect of ocean currents for the UUV path planning, the current effect-eliminated APF (CAPF) path planning algorithm is designed. The CAPF algorithm consists of two parts: (1) an APF algorithm component that gives the shortest path between the origin and the destination meanwhile avoiding all the obstles; (2) an adjusting algorithm component that eliminates the deviation created by the effect of the ocean currents.

2.2.1 APF path planning algorithm

Based on the model defined in the previous section, a virtual APF can be established correspondingly. The proposed destination is determined as the object that has attraction to the vehicle, while the obstacles are regarded as objects that generate repulsive force to the vehicle. All the attractive and repulsive forces are quantified and presented in the form of gravity, where positive gravity is correlated with the distance between the vehicle's position and the destination and negative gravity occurs within the covering range of the obstacles.

The attractive field is defined as,

(1)\begin{equation}{U_{\textrm{att}}}(x )= \frac{1}{2}{k_{\textrm{att}}}\textrm{\; }{\rho ^2}({x,{x_d}} ).\end{equation}

where ${k_{\textrm{att}}}$ is a constant coefficient used to adjust the accuracy of the target attraction on the vehicle; $\rho ({x,\textrm{\; }{x_d}} )$ represents the distance between the current position x and the destination position ${x_d}$.

The repulsive field is,

(2)\begin{equation}{U_{\textrm{att}}}(x)= \left\{\begin{matrix} \dfrac{1}{2}{k_{\textrm{rep}}}{{\left( {\dfrac{1}{{\rho ({x,{x_o}} )}} - \dfrac{1}{{{\rho_o}}}} \right)}^2}, \rho ({x,{x_d}} )< {\rho_o}\\ 0, \rho ({x,{x_d}} )\ge {\rho_o} \end{matrix} \right. \end{equation}

where the ${k_{\textrm{rep}}}$ is the constant coefficient for tuning the repulsive effect to the vehicle; $\rho ({x,\textrm{\; }{x_o}} )$ represents the distance between the current position x and the obstacle position ${x_o}$; ${\rho _o}$ is the radius of the obstacle, all of which are set at one in this study.

Once the attractive and repulsive field are defined, the virtual potential field of the whole map can be addressed (see Figure 2). As the vehicle moves closer to the destination, the gravity decreases until its reaches the destination. Therefore the destination has the lowest gravity field but the highest gravity force for attraction (Figure 2(b) and (c)). The gravity field for the obstacles is higher such that they repulse the vehicle from approaching (Figure 2(b) and (c)).

Figure 2.

2D modelling of APF. (a) 2D map of a predefined underwater environment, (b) contour of the map after APF applied, (c) distribution of the APF on the map

Planning a path between the vehicle's origin and its destination is based on the established virtual field, whose heading direction and step magnitude are addressed through attractive and repulsive forces. These forces are achieved by taking derivatives of the predefined fields (Equations (1) and (2)),

(3)\begin{align} {F_{\textrm{att}}}(x )& =- \nabla {U_{\textrm{att}}}(x )= {k_{\textrm{att}}}\; \rho ({x,{x_d}} )\notag\\ {F_{\textrm{rep}}}(x )& =- \nabla {U_{\textrm{rep}}}(x )\notag\\ & =\left\{\begin{matrix} {k_{\textrm{rep}}}\left( {\dfrac{1}{{\rho ({x,{x_o}} )}} - \dfrac{1}{{{\rho_o}}}} \right)\dfrac{1}{{{\rho^2}({x,{x_o}} )}}\nabla \rho ({x,{x_o}} ), \rho ({x,{x_d}} )< {\rho_o}\\ 0, \rho ({x,{x_d}} )\ge {\rho_o} \end{matrix}\right. \end{align}

Therefore the summation of the force can be obtained to give instructions on finding the optimal path without collisions,

(4)\begin{equation}F(x )= {F_{\textrm{att}}}(x )+ {F_{\textrm{rep}}}(x )={-} \nabla U(x )\end{equation}

Step positions for the path planning are addressed and are correlated after reaching the destination to form the final optimal path solution (see Figure 3).

Figure 3.

Path derived by the APF method on the 2D modelling map. (a) path planning based on the distribution of the APF on the map, (b) APF path on the contour map, (c) final APF path presented on the 2D modelling map

2.2.2 Elimination of the effects of currents

The choice of the next position along the ideal path is based on the current position of the vehicle. In other words, the optimal path can be formed periodically and correlated afterwards, which is the same for the effect of currents, as given in Figure 4. It is clearly shown that the difference between the direction of the ocean currents velocity ${v_{\textrm{cur}}}$ and the direction of the vehicle's desired velocity ${v_d}$ obviously affects the navigational trajectory of the vehicle at each position, thus resulting in the large deviation from the optimal path ${v_{\textrm{act}}}$ after accumulation.

Figure 4.

Elimination of the effect of ocean currents by introducing a third party velocity vector

To eliminate the deviation, a third party velocity vector given by the vehicle, the planned velocity vector ${v_{\textrm{plan}}}$, is derived based on the parallelogram law (see Figure 4(b)). In Figure 4(b), summation of ${v_{\textrm{cur}}}$ and ${v_{\textrm{plan}}}$ results in ${v_d}$, which allows the vehicle to travel in the desired direction with the desired velocity. The current velocity vector ${v_{\textrm{cur}}}$ is obtained from the environment. The specific direction of the desired velocity vector ${v_d}$ is derived by the optimal path, based on the intelligent path planning algorithm proposed in this paper. Additionally, the size of ${v_d}$ is set at the beginning.

As the sizes of ${v_d}$ and ${v_{\textrm{cur}}}$ are known, suppose the position of ${v_d}$ is $({x_d},\; {y_d})$, and ${v_{\textrm{cur}}}$ is $({x_{\textrm{cur}}},\; {y_{\textrm{cur}}})$; then the position of the planned velocity vector ${v_{\textrm{plan}}}$ can be attained based on the parallelogram law (see Figure 4(b)),

(5)\begin{equation}{v_{\textrm{plan}}}\,{:}({{x_d} - {x_{\textrm{cur}}},\; {y_d} - {y_{\textrm{cur}}}} )\end{equation}

When extended to the 3D model, a similar mechanism is applied where the third party velocity vector ${v_{\textrm{plan}}}$ is introduced with an extra dimension added. According to the parallelogram law, ${v_{\textrm{plan}}}$ balances the effect brought by the ocean currents vector ${v_{\textrm{cur}}}$ and finally gives the result corresponding to the desired velocity vector ${v_d}$ to follow the optimal planning path. The precise direction and size of ${v_{\textrm{plan}}}$ are deducted by the positions of the separate vectors in 3D space. As the direction and speed of ${v_d}$ and ${v_{\textrm{cur}}}$ are given, suppose the position of ${v_d}$: $({x_d},\; {y_d},\; {z_d})$, and ${v_{\textrm{cur}}}$: $({x_{\textrm{cur}}},\; {y_{\textrm{cur}}},\; {z_{\textrm{cur}}})$. The position of ${v_{\textrm{plan}}}$ can then be obtained similarly on the basis of the parallelogram relationship illustrated in Figure 4(b),

(6)\begin{equation}{v_{\textrm{plan}}}\,{:}({{x_d} - {x_{\textrm{cur}}},\; {y_d} - {y_{\textrm{cur}}},\; {z_d} - {z_{\textrm{cur}}}} )\end{equation}

Therefore ${v_{\textrm{plan}}}$ is derived to complete the elimination of the effect of ocean currents in the 3D environment.

2.2.3 CAPF path planning algorithm

The two separately designed components are combined to obtain a final path planning algorithm that eliminates the effect of currents and sustains the optimal path solution (see Figure 5). The desired velocity and direction computed by the APF algorithm at each position is passed to the elimination component to plan the velocity and direction the UUV should produce. The planned velocity and direction guarantee that the vehicle will travel along the optimal path by eliminating the effect of currents neuron by neuron, thus providing a robust and efficient path planning result for the UUV. The schematic for realising the algorithm is given in Figure 5.

Figure 5.

Schematic of the proposed optimal path planning method designed for UUV in the underwater environment

3.1 2D results under currents of different directions

The path planning results in the 2D workspace deducted by the CAPF and the APF algorithm are demonstrated in this section. Input parameters are set at: ${v_d}$ = 1 m/s, ${v_{\textrm{cur}}}$ = 0.02 m/s, ${k_{\textrm{att}}}$ i= 1 and ${k_{\textrm{rep}}}$ = 50, which are obtained by trial and error. For the 2D space of size 10 × 10, the initial position of the vehicle is set as the origin, whose coordinates are (0, 0). The supposed destination is at (9, 9).

The results of the planned paths under currents of different direction given by the CAPF (in black line) and the conventional APF (in blue dot) algorithm are shown in Figure 6. The velocity of the current is set at 0⋅02 m/s for all cases, which is to address the greater distance of the APF path to reach the destination. Current directions of 0, 45, 90 and 135 degrees counterclockwise are applied to assess the effect of the fluid flow on the 2D map when tracking the path from the left bottom to the right bottom. The existence of the current, even with a very low flow rate, created inevitable deviation for the paths of the conventional APF algorithm in some of the cases, where in Figure 6(a) and (c) the vehicle fails to reach the destination. The deviation of the paths deduced by the conventional algorithm follows the direction of the current, thus sending the vehicle off-track from the ideal heading direction, and leads to accidental collisions with obstacles (see Figure 6(a) and (c)).

Figure 6.

2D comparison results of the paths given by CAPF algorithm and APF algorithm under currents of different directions. Directions of currents (all counterclockwise): (a) 0 degree, (b) 45 degrees, (c) 90 degrees, (d) 135 degrees

Moreover, compared with the CAPF algorithm, the data from the APF-derived paths show that larger distances were travelled in the navigation between the origin and the destination (see Table 1). This demonstrates that the conventional algorithm does not provide the optimal planning path, which in turn causes the vehicle to consume more energy.

Table 1.

2D moving results of the two path planning algorithms under currents of different directions

Unit: m, C: Collision, F: Fail to reach the destination.

3.2 2D results under currents of different velocities

To test the effect of the current flow rate on the results, simulations of the CAPF and the conventional APF algorithm under currents of different velocities are presented in Figure 7, with the same parameters applied as in the previous section but the current direction is set at 135 degrees counterclockwise for all cases to make a more direct comparison. As the velocity of the current increases, the paths of the APF algorithm (blue dots) deviate accordingly, while the CAPF algorithm (black line) keeps the vehicle navigating along the optimal path without any deviations. For example, when the current velocity is as low as 0⋅02 m/s, the APF path almost overlaps the optimal path with very small deviation (Figure 7(a)). When the currents velocity increases, for the path of APF algorithm, increasing deviation is produced, which leads to uncontrollable accidents such as collision (Figure 7(b)), failure to reach the destination (Figure 7(c)) and even going off the map at the early stage (Figure 7(d)). At the same time, with the CAPF algorithm, the vehicle always follows the trajectory of the optimal path regardless of the change of the current velocity. This conclusion is also supported by the results listed in Table 2, where the distances of the paths given by the two algorithms are compared. It is clearly shown that the CAPF algorithm always sustains the shortest length path distance of 14⋅5137 m, while the UUV with APF algorithm has to travel longer distances to reach the destination, and even cannot accomplish the proposed journey due to the increasing deviation brought by the change of the current velocity. Therefore the CAPF method saves more energy by guaranteeing the optimal navigation for the vehicle when operating in currents of different directions or velocities.

Figure 7.

2D comparison results of the paths given by CAPF algorithm and APF algorithm under currents of different velocities. Velocities of currents: (a) 0⋅02 m/s, (b) 0⋅05 m/s, (c) 0⋅2 m/s, (d) 0⋅5 m/s

Table 2.

2D moving results of the two path planning algorithms under currents of different velocities

Unit: m, C: Collision, F: Fail to reach the destination.

The path planning results under dynamic ocean currents with continuously changing velocities and directions are presented in Figure 8. The path of the APF algorithm (blue dots) vibrates fiercely with the currents’ flowing tendency, and finally goes out of control before reaching the destination (see the top-right part in Figure 8). The CAPF algorithm retains the optimal path (black line) throughout the whole process, unaffected by the dynamically changing currents, and exactly overlaps the path derived under the condition without currents (orange stars). This proves the effectiveness of the CAPF algorithm for eliminating the influence of the velocity of currents and shows that it successfully drives and tracks the optimal path between the supposed origin and the destination.

Figure 8.

2D comparison results of the paths given by CAPF algorithm and APF algorithm under dynamic currents. ${v_{\textrm{cur}}}$: velocity of currents

3.3 2D results under different obstacle-occupied ratios

As the underwater obstacles are distributed randomly in both size and position, the path planning results of different obstacle-occupied ratios are simulated in Figure 9 to evaluate the effectiveness of the CAPF algorithm. The obstacle-occupied ratio means the approximate ratio between the size of all obstacles and the size of the map. The same parameters are applied as in the previous simulation, and the direction of the currents is set as 135 degrees counterclockwise while the obstacle-occupied ratio varies.

Figure 9.

2D comparison results of the paths given by CAPF algorithm and APF algorithm with different obstacle-occupied ratios: (a) 10% obstacles, (b) 20% obstacles, (c) 40% obstacles

With the increment of the obstacles, the conventional APF algorithm (blue dots) tends to introduce more unpredictability during the navigating process. For instance, the APF path successfully reaches the destination with moderate deviation from the optimal path (Figure 9(a)); when the obstacle-occupied ratio rises to 20% in Figure 9(b), the vehicle controlled by the APF algorithm unexpectedly bumps into an obstacle after completing over half of the journey. The effect of the ocean currents weakens the supposed obstacle avoidance ability of the vehicle, where the deviated position information accumulates until inevitable accidents such as bumps happen. However, the CAPF algorithm eliminates the effect of the ocean currents and provides correct position information along the whole path. Increasing obstacles do not affect the CAPF algorithm's deduction of the optimal path between the origin and the destination with avoidance of all the possible obstacles (black line). This supports the effectiveness of the proposed algorithm when applied in an underwater environment of randomly distributed obstacles.

3.4 3D simulation results

Considering that the underwater environment is of three dimensions, the 3D simulation results of the CAPF and the conventional methods are demonstrated. Specific values listed in the previous simulation sections are applied, but the origin is set at (0, 0, 0) and the destination is (9, 9, 9) for 3D modelling. The direction of the ocean currents is determined by two degrees, one is the degree to the X-Y plane, and the other is the degree to the X-Z plane. The size of the 3D workspace is 10 × 10 × 10.

The path planning results of the CAPF (black line) and the conventional APF (blue dots) algorithms under the effect of dynamic currents are given in Figure 10. In Figure 10(a), projections of the partial currents direction are presented on the figure, where all the degrees to the X-Y plane are set to be 0, and the degrees to the X-Z plane are marked by the heading direction of the blue arrows. It is clearly shown that the path of the APF algorithm produces deviation following both the direction and velocity of the partial currents. For example, when the difference between the partial current direction and the supposed heading direction of the vehicle increases, the APF path is dragged farther away from the optimal path and finally cannot reach the destination; the very low flow rate of 0⋅05 m/s limits the deviation of the APF path at the beginning but inevitable divergence occurs as the partial current velocity grows, which results in collision (red cross) at the end. For Figure 10(b) where vertical currents are applied, the APF path deviates at the very beginning and never reaches the area of the destination. Meanwhile, the changing fluid status of the currents does not affect the optimal path planning of the CAPF algorithm whether the currents come in horizontal or vertical directions, where it exactly corresponds to the optimal path under the non-current condition (orange stars) and avoids all possible collisions throughout the whole process. This proves the effectiveness of the CAPF algorithm at eliminating effect of currents in a 3D environment filled with dynamic fluids, which is applicable for the practical UUV navigation.

Figure 10.

3D comparison results of the paths given by CAPF algorithm and APF algorithm under dynamic currents. (a) currents in horizontal direction (angle to the X-Y plane: 0 degree, angle to the X-Z plane: see the blue arrow); (b) currents in vertical direction (angle to X-Y plane: 135 degree counterclockwise, angle to the X-Z plane: 0 degree)