Keywords

1 Introduction

This paper fosters the meta-heuristics research on Underwater Glider Path Planning (UGPP) [13] and Differential Evolution (DE) [24], as initially proposed in the first study on DE and UGPP [26]. Compared to this first study [26], two additional mechanism are included now into the DE metaheuristic and used for the UGPP, (1) the population size reduction from [5, 24] and (2) interchangeable use of two types of DE strategies (DE/best and DE/rand) from [24]. The extended abstract of this paper was published in [25]. The proposed improvement aims in contributing to extend the operational capabilities of the glider vehicle and to improve its value as a marine sensor, facilitating the implementation of flexible sampling schemes.

2 Related Work

In this section, related work on optimization with differential evolution and the underwater glider path planning challenge are presented, defined in [5, 26].

2.1 Differential Evolution and Optimization

Differential Evolution (DE) was introduced by Storn and Price [22] with a floating-point encoding evolutionary algorithm [10] for global optimization over continuous spaces. Its main performance advantages over other evolutionary algorithms [3, 4] lie in floating-point encoding and a good combination of evolutionary operators, the mutation step size adaptation, and elitist selection. The DE has a main evolution loop in which a population of vectors is computed for each generation of the evolution loop. During one generation g, for each vector \(\mathbf{x}_i\), \(\forall i \in \{1,2,..., NP \}\) in the current population, DE employs evolutionary operators, namely mutation, crossover, and selection, to produce a trial vector (offspring) and to select one of the vectors with the best fitness value. \( NP \) denotes population size and \(g\in \{1,2,...,G\}\), the current generation number [26].

Mutation creates a mutant vector \(\mathbf{v}_{i,g+1}\) for each corresponding population vector. Among many proposed, one of the most popular DE mutation strategies [19, 22] are the ‘rand/1’:

$$ \mathbf{v}_{i,g+1} = \mathbf{x}_{r_{1},g}+F (\mathbf{x}_{r_{2},g}-\mathbf{x}_{r_{3},g}) $$

and the ‘best/1’:

$$ \mathbf{v}_{i,g+1} = \mathbf{x}_{best,g}+F (\mathbf{x}_{r_{1},g}-\mathbf{x}_{r_{2},g}), $$

where the indexes \(r_{1}\), \(r_{2}\), and \(r_{3}\) represent the random and mutually different integers generated within the range \(\{1,2,..., NP \}\) and also different from index i. The \(\mathbf{x}_{best,g}\) denotes the currently best vector. F is an amplification factor of the difference vector within the range [0, 2], but usually less than 1. The first term in the mutation operators defined above is a base vector. Following, the difference of two chosen vectors denotes a difference vector which after multiplication with F, is known as amplified difference vector. The simple DE mutation ‘rand/1’ is by far most widely used [8], however, a form of ‘best/1’ mutation has also been signified beneficial, especially in more restrictive evaluation scenarios [2, 15, 24, 26].

After mutation the mutant vector \(\mathbf{v}_{i,g+1}\) is taken into recombination process with the target vector \(\mathbf{x}_{i,g}\) to create a trial vector \(\mathbf{u}_{i,g+1}=\) \(\{u_{i,1,g+1}\), \(u_{i,2,g+1}\),\(...,u_{i,D,g+1}\}\). The binary crossover operates as follows:

$$ u_{i,j,g+1}= {\left\{ \begin{array}{ll} v_{i,j,g+1} &{} \mathrm{if~} rand(0,1) \le CR \mathrm{~or~} j=j_{rand}\\ x_{i,j,g} &{} \mathrm{otherwise}\\ \end{array}\right. }, $$

where \(j \in \{1,2,...,D\}\) denotes the j-th search parameter of D-dimensional search space, \(rand(0,1) \in [0,1]\) denotes a uniformly distributed random number, and \(j_{rand}\) denotes a uniform randomly chosen index of the search parameter, which is always exchanged to prevent cloning of target vectors. \( CR \) denotes the crossover rate [23].

Finally, the selection operator propagates the fittest individual [7] in the new generation (for minimization problem):

$$ \mathbf{x}_{i,g+1}= {\left\{ \begin{array}{ll} \mathbf{u}_{i,g+1} &{} \mathrm{if~} f(\mathbf{u}_{i,g+1}) < f(\mathbf{x}_{i,g})\\ \mathbf{x}_{i,g} &{} \mathrm{otherwise}\\ \end{array}\right. }. $$

In [5], population size reduction was introduced, where population size is reduced by half, when number of generations exceeds ratio between the number of function evaluations allowed and the population size:

$$ G_p>{N_{max\_Feval} \over p_{max} NP _p }. $$

2.2 Underwater Glider Path Planning

An ocean glider is an autonomous vehicle that propels itself changing its buoyancy. The resultant vertical velocity is transformed into an effective horizontal displacement by means of the active modification of the pitch angle and the effect of the control surfaces. The glider motion pattern is constituted by a series of “v” descending/ascending profiles between two target maximum and minimum depths, after which the vehicle returns to surface to transmit data and update its target way-points [26].

Ocean gliders constitute an important advance in the highly demanding ocean monitoring scenario. Their efficiency, endurance, and increasing robustness make these vehicles an ideal observing platform for many long-term oceanographic applications [20]. Nevertheless, they have proved to be useful as well in the opportunistic short-term characterization of dynamic structures. Among these, mesoscale eddies are of particular interest due to the relevance they have in many oceanographic processes [13]. The characterization of pollution and harmful algal bloom episodes have been also included as part of recent glider missions. Having the potential of fully autonomous operation, usual control scheme of ocean gliders does not exploit this capacities too much and relies mainly in a human-in-the-loop approach.

Path planning plays a main role in glider navigation [9] as a consequence of the special motion characteristics these vehicles present. Indeed, ocean current velocities are comparable to or even exceed low speed of a glider, typically around 1 km/h (0.28 m/s). In such situations a feasible path must be prescribed to make the glider reach the desired destination. This can be accomplished by analyzing the evolution of the ocean currents predicted by a numerical model. The problem is not trivial, as the planner must take into account a 4D, spatio-temporally varying field over which to optimize. Also, since increasing the number of function evaluations (FES) degrades the optimization execution time and jeopardizes mission planning time (limiting the optimization time to minutes), it is inevitable to put a restriction on FES, e.g. limit to roughly 2000 FES which may compute in a few minutes.

Different solutions to the glider path planning problem can be found in the literature. Inanc et al. [14] propose a method that applies Nonlinear Trajectory Generation (NTG) on a Lagrangian Coherent Structures (LCS) model to generate near-optimal routes for gliders on dynamic environments. Alvarez et al. [1] use Genetic Algorithms (GA) to produce suitable paths in presence of strong currents while trying to minimize energy consumption. Other authors have put the focus on the coordination of glider fleets to define optimal sampling strategies [17]. A multi-objective GA was also applied to autonomous underwater vehicles for sewage outfall plume dispersion observations [18], which considered two objectives, i.e. the maximum number of water samples besides total travel distance minimization.

In the particular case of eddies, the complexity of the path planning scenario is aggravated by the high spatio-temporal variability of these structures and their specific sampling requirements [12]. Garau et al. [11] use an A* search algorithm to find optimal paths over a set of eddies with variable scale and dynamics. Smith et al. [21] propose an iterative optimization method based on the Regional Ocean Modeling System (ROMS) predictions to generate optimal tracking and sampling trajectories for evolving ocean processes. Their scheme includes near real-time data assimilation and has been tested both in simulation and real field experiments. The current state-of-the-art for glider path planning uses optimization based on a Nelder-Mead algorithm [6] (the fmisearch Matlab implementation [16]) or genetic algorithms (GA) [13]. In [26], UGPP was addressed using DE and other evolutionary algorithms, where it was suggested that the use of DE is beneficial on the 12 test scenarios, and a real mission was carried out to confirm the viability of the approach.

3 Approach Extension

The population size reduction [5] is used inside DE in this study. Two mechanism are included now into the DE metaheuristic and used for the UGPP, extending the initial approach [26]:

  1. 1.

    the population size reduction from [5, 24]

  2. 2.

    interchangeable use of two types of DE strategies (DE/best and DE/rand) from [24].

All other parameter are kept same as in [26]. In the following section, we present the performance differing with the parameterization of the population size reduction mechanism for different NP, pmax, and \(NP_\mathrm{min}\) parameter values. Also, the difference among using DE/best and DE/rand with different parameter sets, is studied.

Fig. 1.
figure 1

Phenotype paths obtained using DE/best (Color figure online).

Full size image

4 Results

In Fig. 1, phenotype paths obtained using DE/best are shown. Trajectory simulations for the 12 bearings computed with best taking population size (NP) as the study factor. For DE/best and NP values are 8 (blue), 32 (purple), 128 (yellow), and 512 (green). Shown are the 120 runs subsampled with step 10 (one run drawn per NP, resulting in 12 trajectories shown).

In Fig. 2, different population sizing settings impact on mean final fitness value for different minimal NP (\(NP_\mathrm{min}\)) and number of reductions (pmax) are shown for DE/best, aggregated on 10 independent runs. Also, standard deviation values of the means values are drawn.

In Fig. 3, Bonferroni-Dunn’s statistical test of DE/best and DE/rand with some selected different parameter sets are presented. The control algorithm is DE/best setting #47, i.e. DE/best with NP=64, pmax=5, \(NP_\mathrm{min}\)=20), this is a setting #47 out of 84. The control algorithm (we propose this one as favorable) outperforms some DE/best and all DE/rand variants. The sample index identifiers are denoted using the Sample number, listing \(NP_\mathrm{min}\) values and then repeating these for different values of pmax (as indicated in Fig. 2). The value Sample No equals the zero-based index number in the \(NP_\mathrm{min}=\{40,20,10\}\) array, added the zero-based index in the \(pmax=\{20,15,10,5\}\) array multiplied by 3 and added the zero-based index in the initial \(NP=\{512,256,128,64\}\) array multiplied by 12, e.g. for the setting #47 this is \(47 = 1 + 0*3 + 3*12\): these indices are 1, 0, and 3, respectively, i.e. \(NP_\mathrm{min}=20\), \(pmax=20\), and \(NP=64\).

Fig. 2.
figure 2

Different population sizing settings impact on mean final fitness value for DE/best.

Full size image
Fig. 3.
figure 3

Bonferroni-Dunn’s statistical test of DE/best and DE/rand with different parameter sets.

Full size image

5 Conclusion

In this paper, we presented an extension of our meta-heuristics research on Underwater Glider Path Planning (UGPP) [13] and Differential Evolution (DE) [24], as initially proposed in the first study on DE and UGPP [26]. Compared to this first study [26], two additional mechanism are included now into the DE metaheuristic and used for the UGPP, (1) the population size reduction from [5, 24] and (2) interchangeable use of two types of DE strategies (DE/best and DE/rand) from [24]. The extended abstract of this paper was published in [25].

All other parameter are kept same as in [26]. We presented experimental results for the performance differing with the parameterization of the population size reduction mechanism for different NP, pmax, and \(NP_\mathrm{min}\) parameter values. Also, the difference among using DE/best and DE/rand with different parameter sets, was presented and the DE/best proposed as a better candidate in the test framework. Thereby, the proposed confirmed improvement contributes to extend the operational capabilities of the glider vehicle and to improve its value as a marine sensor, facilitating the implementation of flexible sampling schemes.

In the future work, the approach could be extended using even more aspects of evolutionary algorithm features, including multi-objective optimization and constraint handling.