Keywords

1 Introduction

Autonomous Underwater Vehicles (AUVs) are designed to provide cost-effective underwater missions and largely used for different purposes over the past decades [1]. The problem associated with most of the todays AUV’s autonomous operation is that they operate with a pre-defined mission outline and require human supervision, in which a set of pre-programmed instructions is fed to vehicle for any specific mission. Considering this deficiency, obtaining a premier autonomy to manage the mission time and autonomous adaption to the environmental changes is a substantial prerequisite in this regard. A vast literature exists on AUVs’ routing and motion planning framework. Different deterministic algorithms, such as D* [2], A* [3], and FM* [4], have been used recently to address AUVs’ motion planning problem. Deterministic approaches also have been investigated on vehicle’s task allocation and routing problems, in which a multiple-target-multiple-agent framework based on graph matching algorithm has been studied by Kwok et al., in [5]. Both vehicle routing and path planning are categorized as a non-deterministic polynomial-time problem in which computational burden increases with enlargement of the problem search space. Hence, deterministic and heuristic algorithms cannot be appropriate for real-time applications as these methods are computationally expensive in large spaces [6]. Meta-heuristics are another alternative group of algorithms for solving complex problems that offer near optimal solutions in a very quick computation [7, 8] and is appropriate for the purpose of this study.

There are various examples of evolution-based applications of path planning and routing-scheduling approaches. A Non-Dominated Sorting Genetic Algorithm (NSGA-II) is employed for AUV’s waypoint guidance and offline path planning [9]. MahmoudZadeh et al., designed an online Differential Evolution (DE) based path planner for a single AUV’s operation in a dynamic ocean environment [10]. A routing-task-assigning framework is also introduced recently for an AUV’s mission planning in a large static operating network, in which the performance of genetic algorithm, imperialist competitive algorithm, and Particle Swarm Optimization (PSO) methods are tested and compared in solving the graph complexity of the routing problem [11]. Afterward, they extended their study by modelling a more complex environment where a semi-dynamic operation network is encountered in contrast and subsequently efficiency of the biogeography-based optimization and PSO algorithms are tested and evaluated in solving the dynamic routing and task allocation approach [12, 13].

Indeed, attaining a superior optimization and computationally efficient approach for addressing these complex problems is still an open area for further investigation. Assuming a waypoint cluttered graph-like environment, the AUV must be able to manage its battery lifetime to carry out a mission including specific set of waypoints; hence, a general route planning over the operation network is primary requirement for this purpose. The second essential objective is to adapt the ocean current deformations and safely guide the AUV trough the network vertices. To do so, the system should be computationally efficient to take a real-time trend over the subsea current deformations. Current research constructs a general routing system with a mounted local path planner to provide a reliable and energy efficient maneuver for the AUV. This system takes the meta-heuristics advantages of Firefly Optimization Algorithm (FOA) to meet the requirements of a long-range operation in a turbulent subsea environment. This research conducts a two dimensional turbulent current map generated by a popular predictive model based on superposition of multiple Lamb vortices [14,15,16,17].

2 Routing Problem in a Waypoint Cluttered Environment

The operation space is modelled as an undirected weighted graph (G) including a specific number of nodes denoted by P and graph connections/edges (E). The vertices of the network \( p_{xyz}^{i} \in P \) are uniformly distributed in a three dimensional volume of (x10000, y10000, z100) that represented as follows:

(1)

Any edge between pi and pj in the graph (eij) has a corresponding length of (lij) and approximated traversing time, given by (2). In the given operating graph, the AUV should meet maximum possible nodes in a restricted battery lifetime. Accordingly, the route planner tends to determine a best set of nodes in the graph to guide the AUV toward the target node and to accommodate battery restriction. With respect to given definitions, a route (ℜ) is mathematically indicated as follows:

$$ \begin{array}{*{20}l} {\forall e^{ij} \quad \exists \quad l_{ij} ,t_{ij} } \hfill \\ {l_{ij} = \left( {\left( {p_{x}^{j} - p_{x}^{i} } \right)^{2} + \left( {p_{y}^{j} - p_{y}^{i} } \right)^{2} + \left( {p_{z}^{j} - p_{z}^{i} } \right)^{2} } \right)^{{\frac{1}{2}}} } \hfill \\ {t_{ij} = \frac{{l_{ij} }}{\left| \upsilon \right|} + \delta_{ij} } \hfill \\ \end{array} $$
(2)
$$ \begin{array}{*{20}l} {e^{ij} :\left\langle {p_{xyz}^{i} ,p_{xyz}^{j} } \right\rangle \Rightarrow \Re = \sum\limits_{\begin{subarray}{l} i = 1 \\ j \ne i \end{subarray} }^{\left| E \right|} {S \times e^{ij} } ;\quad S = \left\{ {0,1} \right\}} \hfill \\ {\Re :\left\langle {\underbrace {{e^{si} , \ldots ,e^{ik} , \ldots ,e^{kj} , \ldots e^{jt} }}_{{\ell \subseteq \left\{ {1, \ldots ,\left| E \right|} \right\}}}} \right\rangle ;\quad \begin{array}{*{20}c} {e^{si} :\left\langle {p_{xyz}^{s} ,p_{xyz}^{i} } \right\rangle } \\ {e^{jt} :\left\langle {p_{xyz}^{j} ,p_{xyz}^{t} } \right\rangle } \\ \end{array} } \hfill \\ {{\rm T}_{\Re } = \sum\limits_{\begin{subarray}{l} i = 1 \\ j \ne i \end{subarray} }^{\left| E \right|} {S \times e^{ij} \times t_{ij} } = \sum\limits_{\begin{subarray}{l} i = 1 \\ j \ne i \end{subarray} }^{\left| E \right|} {S \times e^{ij} \left( {l_{ij} \times \left| \upsilon \right|^{ - 1} } \right)} } \hfill \\ \end{array} $$
(3)

here, \( \fancyscript{l} \) is the length of the route which is subset of total number existent edges in the graph (|E|). υ denotes the vehicle’s water referenced velocity in the body frame. S is a selection variable that represents selection of any arbitrary edge in the graph. \( {\text{T}}_{\Re } \) is the route time from start node of \( p_{xyz}^{s} \) to target node of \( p_{xyz}^{t} \) . The battery lifetime denoted by \( T_{\tau } \) and is started to counting inversely from the beginning of the operation. The \( {\text{T}}_{\Re } \) should approach the \( T_{\tau } \) but should not overstep that. The route should not include non-existent edges, and should not traverse a specific edge for multiple times.

3 Environmental Dynamics and Local Path Planning

In order to deal with environmental impact on vehicles motion, a local path planner is conducted in this study to operate in a smaller operating window between pairs of route nodes. This space reduction leads reducing the computation burden as a smaller window is required to be monitored. Water current is an important environmental factor that influences AUV’s motion. The local path planner aims to find a time efficient path while accommodating the current deformations. The current map data in this research is obtained from a popular numerical estimation model based of recursive Navier-Stokes equations [14] as follows:

$$ \upsilon_{c} = \left( {\upsilon_{c,x} ,\upsilon_{c,y} } \right) \Rightarrow \left\{ {\begin{array}{*{20}l} {\upsilon_{c,x} = \left| {\upsilon_{c} } \right|\cos \theta_{c} \cos \psi_{c} } \hfill \\ {\upsilon_{c,y} = \left| {\upsilon_{c} } \right|\cos \theta_{c} \sin \psi_{c} } \hfill \\ \end{array} } \right. $$
(4)

here, the υc is current velocity vector and the υc,x and υc,y are the x−y components of the υc. The physical model used by the AUV to diagnose the current velocity field can be found in [18, 19]. AUV’s motion in six degree of freedom is provided by state variables of body and NED frames [20], as follows:

$$ \begin{aligned} \eta :\left( {X,Y,Z,\phi ,\theta ,\psi } \right) \hfill \\ \upsilon :\left( {\upsilon_{x} ,\upsilon_{y} ,\upsilon_{z} ,p,q,r} \right) \hfill \\ \end{aligned} $$
(5)

where, the η and υ denote vehicle’s dynamics and kinematic over the time. X, Y, Z denote AUV’s position along the path. φ, θ, ψ are the Euler angles of roll, pitch, and yaw, respectively. The υ is AUV’s velocity vector in the body frame; υx, υy, υz are directional velocities of surge, sway and heave; and p, q, r are the rotational velocities. In this study, the local path ℘ is generated using B-Spline curves captured from number of control points while the water current velocity is continuously taken into account. The local path curve ℘ is calculated by:

$$ \begin{array}{*{20}l} {\theta_{t} = tan^{ - 1} \left( { - \left| {\Delta Z_{i,t} } \right|/\sqrt {\Delta X_{i,t}^{2} + \Delta Y_{i,t}^{2} } } \right)} \hfill \\ {\psi_{t} = tan^{ - 1} \left( {\left| {\Delta Y_{i,t} } \right|/\left| {\Delta X_{i,t} } \right|} \right)} \hfill \\ {\upsilon_{x,t} = \left| \upsilon \right|\cos \theta_{t} \cos \psi_{t} + \left| {\upsilon_{c} } \right|\cos \theta_{c} \cos \psi_{c} } \hfill \\ {\upsilon_{y,t} = \left| \upsilon \right|\cos \theta_{t} \sin \psi_{t} + \left| {\upsilon_{c} } \right|\cos \theta_{c} \sin \psi_{c} } \hfill \\ {\upsilon_{z,t} = \left| \upsilon \right|\sin \theta_{t} } \hfill \\ {\wp = \left[ {X,Y,Z,\psi ,\theta ,\upsilon_{x} ,\upsilon_{y} ,\upsilon_{z} } \right]} \hfill \\ \end{array} $$
(6)

The AUV is presumed with a constant thrust power; hence, the path time T℘ has a linear relation to path length. The water current deviates the vehicle from its desired trajectory; hence, the resultant path should meet the kinematic constraints of the vehicle in dealing with current force. Therefore, AUV’s surge-sway velocities and its yaw-pitch orientation should be constrained to υx,max, [υy,min, υy,max], θmax, and [ψmin, ψmax] in all states along the path. Accordingly, the path cost is calculated by (7).

$$ \begin{aligned} & \forall \wp_{x,y,z}^{i} \\ & T_{\wp } = \sum\limits_{{i = p_{x,y,z}^{a} }}^{\left| \wp \right|} {\left( {\Delta X_{i,t}^{2} + \Delta Y_{i,t}^{2} + \Delta Z_{i,t}^{2} } \right)^{{\frac{1}{2}}} } \times \left( {\left| \upsilon \right|} \right)^{ - 1} \\ & C_{\wp } = T_{\wp } + \varepsilon_{{\upsilon_{x} }} \text{max}\left( {0;\upsilon_{x,t} - \upsilon_{x,\hbox{max} } } \right) + \ldots \\ & \quad \quad \quad \ldots + \varepsilon_{{\upsilon_{y} }} \text{max}\left( {0;\left| {\upsilon_{y,t} } \right| - \upsilon_{y,\hbox{max} } } \right) + \ldots \\ & \quad \quad \quad \ldots + \varepsilon_{\theta } \,\text{max}\left( {0;\theta_{t} - \theta_{{\text{max}}} } \right) + \ldots \\ & \quad \quad \quad \ldots + \varepsilon_{\psi } \text{max}\left( {0;\left| {\dot{\psi }_{t} } \right| - \psi_{{\text{max}}} } \right) \\ \end{aligned} $$
(7)

The ευx, ευy, εθ, εψ denote the impact of each constraint violation in determination of the local path cost C℘.

4 Mission Evaluation Criterion

The generated route (ℜ) is composed of distances between nodes (lij) and the path planner generates time efficient trajectory along those distances (lij∝℘ij); hence, the path cost of C℘ directly impacts the route cost of Cℜ. As mentioned earlier in Sect. 2, the rout time Tℜ should approach the total battery lifetime Tτ, but should not overstep that. Therefore, the Cℜ gets penalty when the Tℜ for a particular route exceeds the Tτ. The local path may take longer time in dealing with environmental dynamic changes. In such a case, the lost time should be compensated by a proper re-routing process, while its computation cost is considered in total mission cost calculation. Thus, the Cℜ and total mission cost of Cτ in the proceeding research is calculated by (8).

$$ \begin{array}{*{20}l} {C_{{\wp_{ij} }} \; \approx \;{\rm T}_{\wp }^{ij} \propto t_{ij} \Rightarrow C_{{\wp_{ij} }} \propto t_{ij} } \hfill \\ {{\rm T}_{\Re } \; = \;\sum\limits_{\begin{subarray}{l} i = 0 \\ j \ne i \end{subarray} }^{\left| E \right|} {S.e^{ij} \times t_{ij} } } \hfill \\ {C_{\Re } \; = \;\left| {{\rm T}_{\Re } - {\rm T}_{\tau } } \right| \times \text{max}\left( {0,\frac{{{\rm T}_{\Re } }}{{{\rm T}_{\tau } }}} \right)} \hfill \\ {C_{\Re } \; = \;\left| {\sum\limits_{\begin{subarray}{l} i = 0 \\ j \ne i \end{subarray} }^{\left| E \right|} {S.e^{ij} \times \left( {C_{{\wp_{ij} }} + \delta_{{\wp_{ij} }} } \right)} - {\rm T}_{\tau } } \right| \times \text{max}\left( {0,{\rm T}_{\Re } {\rm T}_{\tau }^{ - 1} } \right)} \hfill \\ {C_{\Re } \propto f\left( {C_{{\wp_{ij} }} ,{\rm T}_{\tau } } \right)} \hfill \\ {C_{\tau } \; = \;C_{\Re } \left( {C_{{\wp_{ij} }} ,{\rm T}_{\tau } } \right) + \sum\limits_{1}^{r} {T_{compute} } } \hfill \\ \end{array} $$
(8)

Where, Tcompute is the re-routing computation time, and r is the number of re-routing in a mission. δ℘ij is the delayed time during the local path planning between \( p_{xyz}^{i} \) and \( p_{xyz}^{j} \).

5 FOA on Mission Routing and Path Planning

Firefly Optimization Algorithm is a meta-heuristic algorithm inspired from the flashing patterns of fireflies, in which the fireflies attract each other based on their brightness [21]. The fireflies’ brightness decreases by distance and the brighter fireflies attract the less bright ones; hence, their attraction is proportional to their brightness and their relative distance. Attraction of a firefly i toward the brighter firefly j is calculated as follows:

$$ \begin{aligned} & \partial_{ij} = \left\| {\chi_{j} - \chi_{i} } \right\| \\ & \chi_{i,t + 1} = \chi_{i,t} + \beta_{0} e^{{ - \gamma {\kern 1pt} {\kern 1pt} \partial_{ij}^{2} }} \left( {\chi_{j,t} - \chi_{i,t} } \right) + \alpha_{t} \varsigma_{i}^{t} \\ & \alpha_{t} = \alpha_{0} \kappa^{t} ,\quad \kappa \in \left( {0,1} \right) \\ \end{aligned} $$
(9)

the ∂ij is the distance between fireflies i and j; β0 is the attraction factor at ∂ = 0, α0 and αt are the initial randomness scaling value and the randomization parameter, respectively. αt tunes the randomness of fireflies’ movement in each iteration. κ is a damping factor. The \( \varsigma_{i}^{t} \) is a randomly generated vector at time t. The γ light absorption factor. In a case that β0 approaches zero the movement turns to a simple random walk, while γ = 0 turns the FOA to a variant of PSO; thus, a proper balance should be set between the engaged parameters [21]. The FOA is efficient due to applying an automatic subdivision approach that enhances convergence rate of the algorithm, and iteratively prevents fireflies from trapping into local optima. This accommodates FOA to efficiently deal with highly nonlinear continuous problems, and makes it flexible in dealing with multimodality [22]. The control parameters in FOA can be tuned iteratively, which is another reason for its fast convergence. Similar to other metaheuristic algorithms, the FA also has two inner loops through the population imax and iteration tmax, so at the extreme case the algorithms complexity is \( {\text{O}}(i_{ \hbox{max} }^{2} \; \times \,t_{ \hbox{max} } ) \) ; hence, the computation cost is respectively low as its complexity is linear to time. The cost evaluation is the most computationally complex part of almost all optimization problems. To the purpose of AUV global routing, first step in using the FOA algorithm is to provide the initial population in the format of feasible routes, which has a great impact on algorithms performance. Fireflies in this context are defined as feasible routes in the graph [23, 24].

The solutions take variable length limited to number of vertices in the graph that are generated using graph adjacency information. Accordingly, the algorithm stars to optimize the solutions based on defined cost function for routing problem. In the case of local path planning, the fireflies in the initial population are assigned with candidate local path solutions that are generated by a set of B-Spline control points. Then the FOA tends to efficiently locate the control points of a candidate ℘ curve in the solution space according to the defined cost function for the local path. The FOA process of AUV routing, path planning and re-planning is provided by a pseudo-code in Fig. 1.

Fig. 1.
figure 1

Pseudocode of FOA-based routing, path planning, and re-planning

Full size image

The battery lifetime Tτ should be managed adaptively. Accordingly, the local path time \( {\text{T}}_{\wp }^{ij} \) gets compared to expected path time of tij after visiting each node in the route sequence and if it exceeds that, re-routing flag gets triggered. The Tτ gets updated simultaneously. The given process in the pseudo code of Fig. 1 continues until the AUV reaches to the target node.

6 Discussion on Simulation Results

First we turn to evaluate the performance of FOA-based local path planner according to given cost function in (7). The vehicle is assumed to move with a standard thrust power of maximum υ = 5.5 (knots). The battery consumption for a path is a constant multiple of the path time and path length due to proportional relation of current velocity to the cube root of the thrust. A static current map data is used to evaluate the behaviour of local path planner to water currents deformations. The current map is generated using a Gaussian distribution of 11 vortices in 100 × 100 grid. The paths’ curvature is acquirable by the AUV’s directional velocity components and radial acceleration. Figure 2 represents the local path behavior with respect to water current flow.

Fig. 2.
figure 2

The local path adaption to current arrows in a static map

Full size image

As depicted in Fig. 2, it is noteworthy to hint the efficient capability of the FOA-based planner in conforming current arrows either in using accordant current arrows or in avoiding turbulent (vortices). According to path cost function, the path planner aims to determine the shortest battery efficient path between nodes and adapting water current deformations while the actuators boundary conditions and vehicular constraints are considered.

With respect to (7), the path cost function gets penalty when the generated path is violated the boundaries on vehicle’s surge, sway, theta rate, yaw rate constraints, which here is defined as follows: υx,max = 5.25 (knots); [υy,min, υy,max] = [−0.97,0.97] (knots); θmax= 20 (deg/s); and [ψmin, ψmax] = [−17,17] (deg/s). Figure 3 presents the local path planner’s performance in reducing the path cost and satisfying the above mentioned constraints.

Fig. 3.
figure 3

(a) Cost variations of path population over 100 iterations; (b) Path violation of υx, υy, θ, and ψ over 100 iterations;

Full size image

The generated path, as illustrated in plot Fig. 3, shows a great fitness regarding all defined path constraints. The cost variation of path population experiences a moderate convergence to the minimum cost and the variation range narrows down iteratively. It is further outstanding from Fig. 3(b), the FOA-based path planner accurately manages the path toward eliminating the violation factors as the violation of the path population diminishes over the 100 iterations.

On the other hand, the routing model should select an efficient set of nodes restricted to battery life time Tτ to ensure on-time mission termination. A critical factor for concurrency of the routing and path planning models is having a short computational time to keeps any of them from dropping behind the process of the other one. Figure 4 presents the computational performance of the both FOA-based route planner and path planner in 25 simultaneous runs. Moreover, compatibility of the expected time tij and the path time T℘ for traversing lij is another significant performance metric impacts the system synchronism. Hence, there should not be a huge difference between variations of these two parameters. This concurrency also impacts on-time re-routing procedure. The concurrency of tij and T℘ in 25 experiments is depicted by Fig. 5. Routing and path planning computational time variations, as presented in Fig. 4, are fairly drawn in a narrow range of seconds for all 25 experiments, which hint the real-time performance of the proposed connective FOA-based model in handling the environmental changes.

Fig. 4.
figure 4

Computational time variation of route-path planning model over the 25 experiments

Full size image
Fig. 5.
figure 5

Compatibility of the value of T℘ and tij in a quantitative manner over the 25 experiments

Full size image

Analysis of the captured result from multiple experiences, indicates model’s consistency in preserving the conformity between tij (depicted by gray transparent box plot) and T℘ (depicted by blue compact box plot) as their average variations is relatively close in each experiment. This confirms the accurate synchronization of the routing and path planning system. The whole process of one experiment is illustrated by Fig. 6 for better understanding, in which this single mission includes three re-routing and 11 local path planning passing through the 12 nodes. The routing system provides an initial efficient route. The remained time is initialized with battery life time Tτ and is counted inversely during the mission. The local path planner incorporates local environmental changes and if the T℘ oversteps the tij the re-routing flag is triggered and controller shifts to the routing system to compensate the lost time.

Fig. 6.
figure 6

Routing, path planning, and re-routing procedure by re-arrangement of edges’ order in a single mission. (Color figure online)

Full size image

As presented in Fig. 6, the final optimum route (black line) is generated through the three re-planning process, in which the first route (presented by dashed red line) is discarded after passing two nodes; the second one (shown by pink dashed line) is discarded after visiting 5 nodes from the starting point, and the third route (depicted by green dashed line) is discarded in the node 6. These re-planning are carried out to compensate the lost time in the local path planning process.

The most important performance metric in this study is model’s accuracy in mission timing and ensuring on-time completion of the mission. Thus, the best outcome of the model is to take a maximum use of battery life time and to fulfill a mission with minimum residual time. The model’s capability of mission timing is examined through the 25 individual experiments (missions) presented by Fig. 7, in which the battery life time is set on Tτ = 7.2 × 103(s) and the terrain is modelled as a realistic underwater environment encountering static ocean current map.

Fig. 7.
figure 7

Statistical analysis of the model’s timing performance in 25 missions.

Full size image

It is outstanding from Fig. 7, the Tremained is positive and it is approached to zero in all 25 missions, which means all missions completed before vehicle runs out of battery. Accordingly, the mission time (TRoute) maximized to approach upper bound of TTotal (presented by pink horizontal line in Fig. 7), but it doesn’t overstep the line in any of experiments. It is noted from analyzing the results, the model accurately satisfies mission timing constraints along with other considerations. This is a significant achievement toward having a successful and reliable operation through the excellent mission time management.

7 Conclusion

In this study a connective model of AUV routing and local path planning based on firefly optimization algorithm (FOA) is presented, in which the model is advantaged with a reactive re-routing capability that manages the mission time by re-organizing the order of nodes in a way to be fitted to the battery life time. The local path planner, at the same time, tends to generate energy/time efficient paths along the selected nodes in a route encountering desirable and adverse water current flow. To validate the proposed connective model, the vehicle’s operation is simulated in large-scale three-dimensional volume and the static water current map is added to consideration. The FOA performance on the proposed model is tested through the 25 individual mission trials. It is inferred from simulation results that the offered connective model proposes an efficient computational performance (in range of seconds) for both vehicle routing and local path planning that affirms the real-time performance of the model in long range mission management. The local planner also shows a great current resilient efficiency that leads remarkable energy saving in vehicle’s continuous deployments. As inferable from the simulation results, the re-planning facilitates the vehicle to have a reliable and energy efficient operation by having an excellent mission timing. The future research will concentrate on expanding the proposed model in terms of upgrading the planners’ capabilities and environmental influences on small and long-range missions. It is planned to expand the current study and to prepare a full version as a journal paper.