The paper considers the problem of searching for the source of a non-stationary physical eld. We assume that the use of swarm algorithms may be applicable in this case. A hybrid of the Whale Optimization Algorithm and Grey Wolf Optimizer is proposed in this paper. The algorithm has several advantages over its origins: a more precise solution of the optimization problem for low-dimensional functions and a higher convergence rate of the rst iterations. Two modi cations were made to adapt the algorithm to the requirements of the problem. The proposed algorithm is used as a basis for a control strategy for a group of autonomous underwater vehicles. As a result, in the vast number of cases, the group can nd the source within the given number of search iterations.
Although humanity has studied the Earth quite well, our knowledge of the underwater world is limited. Several negative factors cause this lack: the inability of a man to be in the underwater environment without special equipment, the high labor and resource intensity of research, and other physical limitations, particularly on the distance of communication and vision. Only relatively recently, with the invention of submersibles, the active phase of ocean research began.
There are many di erent challenges in this area. One of them is the physical eld survey problem (in other related works { adaptive sampling [1]). This problem includes many particular cases: mapping, search for given objects, search for areas with extreme values of the physical eld, and many others. The solution of this problem has both fundamental importance - a general study of the underwater environment and improvement of our understanding of the processes occurring in it, and practical importance, for example, the search for oil elds or localization of the consequences of human-made disasters. Besides, the results of solving this task can be used as auxiliary information in other areas of marine research.
Undoubtedly, this task can be solved with human resources. However, a more reasonable approach is to use autonomous underwater vehicles (AUV) or a coordinated group. Researchers often use a tack search algorithm or algorithms based on gradient descent to solve the trajectory physical eld survey problem. The undoubted advantages of these approaches are simplicity of implementation, computational e ciency, and acceptable work result in the vast majority of cases. Nevertheless, each of them has several disadvantages.
Tack search implies a movement of AUV or their group along a predetermined zigzag trajectory and making measurements with a given frequency. As a result, the entire survey space is covered with a network of measurements. Processing of the obtained results allows AUVs to nd an area with an extreme value of the physical eld and to build eld level lines. As can be seen from the description, this approach is not intelligent. Robots do not make any decisions during the mission and do not respond to environmental changes. Other shortcomings of the method include: accuracy dependence on both the frequency of measurement and the width of the tack; high execution time, depending on the size of the search space and the number of robots in the search group; the need to store the values and the coordinates of all taken samples in memory; the impossibility to apply the algorithm for non-stationary physical elds, because, by the moment of results analysis, the measurements may lose their relevance.
These shortcomings are partly solved, using gradient descent. However, this algorithm implies only one agent, and the work of a group of robots can be considered as a multistart. In this case, interaction and information exchange within the group is minimal or absent. Finally, if the physical eld has several local extrema, there is a high probability of hitting them.
Population (in particular swarm) optimization algorithms may become a promising approach taking the above into account. Wildlife and inanimate nature processes underlying these algorithms often imply close interaction within a group to achieve a common goal. It allows one to transfer them to the AUV subject area with minor e orts. Despite the di culty of proving the optimality of the solutions found, the swarm algorithms demonstrate high e ciency in solving practical problems. At the same time, it is often possible to dynamically in uence the process of solving a problem, increasing or decreasing the number of iterations (as a consequence, measurements) necessary to obtain an acceptable result.
This article suggests a swarm intelligence approach to a cooperative survey of non-stationary physical elds. Chapter 2 provides a brief overview of existing solutions. Chapter 3 describes the formulation of the problem with several accepted limitations and assumptions. Chapters 4 and 5 are devoted to a direct description of the developed algorithm as well as to some modi cations vital for the non-stationary physical elds survey and the problem-solution process improvement.
The physical eld survey problem is a rather popular area of scienti c research. In general, the works can be divided into two broad groups: the direct development of AUV for the physical eld survey problem and the development of problem-solving methods. The rst direction [2] includes the creation and improvement of sensors, devising robots for functioning in extreme conditions, and developing approaches to ensure communication within the group. Nevertheless, the second direction is of interest to this research.
The most signi cant number of studies relate to two-dimensional physical elds in the water body and on the surface [3]. Signi cantly fewer works touch upon three-dimensional search space [4]. First of all, it is connected with the di culty of robot vertical movement organization. Secondly, the three-dimensional space can be divided into two-dimensional layers, each of which may be examined independently.
The survey of non-stationary physical elds is of particular interest; despite this, many studies are devoted to physical elds that do not change in time [5]. Depending on the speci c task, the problem can be divided into searching for the source of a physical eld [6; 7], searching for the area with the extremal value of the physical eld (extremum) [2; 8], and mapping. Nevertheless, this division is conditional. For example, the source can simultaneously be an area with the extremum of the eld in some particular cases. A parallel solution of more than one of the described tasks is the most preferable one.
The most common approaches to the survey are the tack search [9] and algorithms based on gradient descent [10] as well as their combinations. It should be noted that swarm and other bioinspired approaches are also used [6; 11] but in a much smaller number of cases. In particular, when it is known that the physical eld is stationary or has a single source or extremum.
Establishing sustainable communication between AUVs within a research group is quite a challenge, so most of the studies are aimed at using only one robot [3; 12]. Such an approach generates limitations on the size of the search space and may lead to a complete failure to solve the task. Therefore, despite the increasing requirements to the algorithms and control strategies, some researchers o er various centralized or decentralized approaches to solve the physical eld survey problem using a homogeneous group of AUVs [13; 14].
Depending on nature, The following types of the physical elds [1] are naturally distinguished by their spatial characteristics, distribution features, and sensors required.
Chemical sources, for example, gas hydrates, dissolved salts, or oil spills. The task of nding the source or extremum value is most often considered [15].
Physical sources presented by thermoclines or upwelling. The most signi cant interest, in this case, is mapping the phenomenon and building its two or three-dimensional structure [16].
Biological sources, describing the distribution of certain biological species. It is challenging to choose the prevailing formulation of the problem because all of them are of equal interest to researchers [17].
In this article, a two-dimensional case of the physical eld survey problem is considered. In this case, the physical eld is a kind of scalar mathematical eld described by the function f (x; y; t) (Figure 1). The nature of the function is not known in advance for search agents (AUV). The function itself can be continuous, but to simplify calculations, we consider it to be de ned on a grid. The value of each cell (x0; y0) 2 F 2(F Z) is the maximum value of the objective function in the area bounded by cell borders and normalized as: f 0(x; y; t) =
f ( )
fmax( )
fmin( )
fmin( )
255
(
In this study, we discuss physical elds that are generated by several sources. Each source moves around the search space at speed, not exceeding the maximum speed of AUVs. The source trajectories are not known in advance. At the same time, the sources represent local extrema with the values xed over time. The function, in this case, describes the distribution of physical eld values at each moment.
We do not identify any particular type of physical eld at this stage of the study, considering it abstract. This assumption allows us to move away from considering speci c features of studying a particular type of physical eld, such as the sensors and sampling techniques used. Instead, we focus on solving the problem as a whole.
Another assumption often found in works in this eld is the absence of obstacles. Pathplanning and collision avoidance are the objectives of the AUV navigation system, which lies at a lower control system level than is discussed in this study. For the same reason, we will consider that robots can accurately determine their position and are not a ected by the environment, in particular currents.
The value of the physical eld at the point (x; y) can be obtained only if any robot reaches these coordinates and takes samples (measurement). We assume that there are no restrictions on communication between AUVs, and each vehicle has information about all taken measurements (measurement array).
In the current study, we consider the task of determining the source that produces the
maximum value on the physical eld. We assume that there is only one such source, which
is simultaneously the extremum of the physical eld. The problem is to determine the control
strategy that leads by the end of the mission the group to such (x ; y ) 2 F 2 at which the
objective function takes the maximum value:
f (x ; y ; T ) = max f (x; y; T )
(
The article [18] discusses the solution of a similar problem - trajectory survey of a stationary physical eld. The chosen Grey Wolf Optimizer demonstrated acceptable results. The framework of this research was proposed to create a hybrid algorithm to apply it to the current problem.
The existing swarm optimization algorithms were reviewed and compared, to select two candidates for hybridization: the Whale Optimization Algorithm (WOA) [19] and the Gray Wolf Optimizer (GWO) [20]. Both algorithms have a similar structure and also showed good results on preliminary tests. It should be noted that there were earlier attempts to combine these algorithms [21; 22]. However, the proposed approach has its unique features and is not their full analog.
The proposed hybrid algorithm (WOA-GWO) has three behavioral patterns of agents inherited from the Whale Optimization Algorithm: exploration, exploitation, and the "bubble-net attack" method. Switching between the patterns is independent for each agent at each search iteration and depends on two random variables A 2 [ a; a] and P 2 [0; 1]. In this case, a is the time function linearly changing from 2 to 0 as a = 2 (1 time
N
);
(
The exploitation pattern implies the speci cation of the found solution; in other words, attacking the prey. Activation occurs at P < 0; 5 and jAj < 1. The method for calculating the coordinates of the agent at the next iteration (target coordinates) corresponds to the one suggested in the Grey Wolf Optimizer. Three "leaders" with the maximum value of the objective function are selected among all known measurements.
F = f (x; y; t)
Next, the algorithm chooses temporary points located on lines passing through the current coordinates of the agent and the leaders (Figure 2). Thus, each temporary point is linked to one of the leaders. The location of these points is calculated separately for each dimension and depend on random variables Ah 2 [ A; A] and C 2 [0; 2]. Target coordinates in all patterns are de ned as the arithmetic mean of temporary points.
Xit = Xleadert
Ah
D; The exploration pattern describes the agents' search for a potentially more promising solution, moving away from the current ones. Activation occurs at P < 0; 5 and j j > 1. In contrast A to exploitation, the target coordinates depend on three randomly selected measurements. The location of temporary points (Figure 3) depends on random variables As 2 [ A; 1] [ [1; A] and C 2 [0; 2] and is calculated separately for each dimension as follows
Xit = Xleadert
As
D;
(
Xrandomt
(
Xit = Xleadert + D eb l
cos 2 l; D = jXrandomt
Xtj;
l = (s
1)
r + 1;
(
N where Xt is the current coordinate of the agent, Xleadert is leader's coordinate, r is a random value in the range of [0; 1], b is an adjustable parameter, adopted equal to 1, time and N are the number of the current iteration and the total number of iterations, respectively.
Several tests aimed at constrained optimization of the given functions were carried out to analyze the proposed algorithm's quality of work. Testing was performed on ve functions (Table 1) that di er in the number of dimensions, the presence of local extrema, and belonging to the classes of convex and non-convex functions.
In addition to hybrid WOA-GWO, the following swarm optimization algorithms participated in the study:
GWO | Grey wolf optimizer GSA | Gravitation search algorithm PSO | Particle swarm optimization Bat | Bat algorithm WOA | Whale optimization algorithm ABC | Arti cial Bee Colony Fire y | Fire y algorithm Gbest | Global best algorithm MVO | Multiverse optimization
SOS | Symbiotic organism search
There were three test series: the maximum number of iterations equal to 10, 100, and 1000. All series consisted of 50 independent runs of each algorithm with the same population size { 20 agents. Tests were conducted on Intel Pentium 4415U 2.3 GHz processor. Averaged results of each series are presented in tables 2{4.
ABC Bat Fire y GBest GSA GWO MVO PSO SOS WOA WOA-GWO
The following conclusions can be drawn from the results of the tests: (i) Regardless of the speci ed number of iterations, the proposed algorithm cannot cope with the optimization of Griewank and Rastrigin functions. It can be assumed that such a result will be achieved on all multidimensional functions. Since the physical eld inspection task is considered only in two-dimensional and three-dimensional versions, this disadvantage can be ignored. (ii) On Beale and Goldstein functions, WOA-GWO shows the most accurate results among most of the considered algorithms, slightly inferior only to PSO and SOS, depending on the given number of iterations. On these tasks in the vast majority of runs, the proposed algorithm is superior to both of its ancestors. (iii) The algorithm shows average results on the Colville function. In this case, there is a high dispersion, so the results are inconsistent. On average, the proposed algorithm is superior to at least one ancestor and the PSO algorithm. (iv) In average, there is an increase in algorithm runtime, depending on the task (for 1000 iterations) by 2-4 times relative to WOA and 3-6 times relative to PSO. (v) WOA-GWO has a higher convergence rate in rst iterations than all considered algorithms except PSO. However, then the speed is signi cantly reduced or stopped. (Figure 5). a) b)
In summary, we can conclude that a positive result of hybridization has been achieved. The existing shortcomings of the algorithm are either not signi cant for the problem or can be eliminated by further modi cations. The high speed of obtaining the rst acceptable approximation and the high stability of the work with the small size functions allows us to conclude that WOA-GWO is applicable to the physical eld survey problem.
As it was mentioned earlier, a survey of a non-stationary physical eld has one speci c feature. Measurements may lose their relevance over time. That is why the algorithm needs a technique distinguishing acceptable and not acceptable measurements in necessary calculations.
The proposed modi cations are based on a three-dimensional Voronoi diagram, where the third dimension is time. Voronoi diagram is a division of space into subareas (cells), in which the distance from any point of the cell to a given point (site) is less than to any other site. In this case, the sites are the measurements made by agents during the problem solution. There is no need to build and store a three-dimensional diagram for the proposed approach; it is enough to have its two-dimensional cut at particular moments. If the area of any Voronoi cell on the given cut is equal to zero, the measurement that gave birth to it is thrown out of the list. Thus the "forgetting" of old measurements, which in conditions of non-stationary physical eld lose their relevance, is simulated. It was suggested to introduce a time factor allowing to adjust the speed of "forgetting." If its value is equal to 0, this process is disabled. Thus, all performed measurements are considered. If this parameter is increased, a smaller number of measurements is considered at the same time, up to the measurements obtained only at the current iteration. This process also indirectly allows one to regulate the labor intensity of the diagram cut calculation by reducing the number of measurements known to agents.
The rst detected barrier in solving the physical eld survey problem, which is typical for both stationary and non-stationary formulations, is agent initialization. Usually, robots move to the examination area as a single group, so all agents should be situated on a small (in comparison with the whole search space) area at the rst iteration. Such restriction leads to hitting the local extremum in the vicinity of the starting point.
It was proposed to change the way of selecting "leaders" in order to avoid the mentioned
barrier. In the basic WOA-GWO algorithm, as in its parent algorithms, the leaders are three
measurements with the maximum value of the function (
F = k1
f (x; y; t)
k2
s(x; y; t);
(
Function s(x; y; t) returns a value in range [0; 1] and represents the normalized area value of the corresponding cell. Thus, an increased interest in the inspection of cells with a large area is achieved. It provides a more uniform inspection of a given area without skipping zones that have received a bad initial approximation but may potentially contain an extremum.
However, this approach negatively a ects the nal iterations of the algorithm. Therefore,
the choice of the leader determination function has been synchronized with the basic patterns
of WOA-GWO behavior: exploitation (survey) and operation ("attack"/re nement of the
solution). In the "exploration" behavior pattern, the leaders are selected according to (
Another direction of work was to change the time function (
N in such a way as to increase the exploration iterations percentage without changing the range of accepted values to eliminate this disadvantage.
There is another indirect application of the Voronoi diagram for physical elds known to be stationary. With the time coe cient equal to 0, the result is a reasonably good approximation of the diagram to a given prototype (Figure 6). Thus, the mapping problem is solved in parallel. This additional information may be useful for further researches in this area.
The proposed control strategy is to build such a trajectory of each AUV on a dynamically generated set of points to gather the entire group in a small neighborhood of the current physical eld source location. If there are several sources, the trajectory is constructed so that the source generating the maximum value of the physical eld is found. A hybrid metaheuristic optimization algorithm called WOA-GWO is responsible for the generation of key points in the trajectory. Based on a series of tests, it was found that on functions with a small number of unknowns WOA-GWO shows higher accuracy and speed than most currently popular algorithms. Since the considered problem is non-stationary, several modi cations have been proposed, in particular, the mechanism of forgetting by robots of old measurements, based on the construction of the Voronoi diagram.
Initial tests have shown that the underlying algorithms are unable to nd a su ciently good approximation to the extremum for non-stationary physical elds with any predicted probability. At the same time, proposed modi cations allow nding a value close to the extremum with an average error equal to 5{7% and not exceeding 15% (at worst) in the overwhelming number of runs.
The next step of this study is to check how the algorithm works on more complex physical elds, including both changing the coordinates of the source and its value. The reduction of the total survey time and assumptions made should also be considered. Finally, there may be a problem of losing a candidate solution on the nal iterations of the search. Work is underway to make WOA-GWO more adaptive to avoid it.
The research was partially supported by the Russian Foundation of Basic Research, project no. 20-07-00397 A. The development of modi cations for surveying non-stationary physical elds was also supported by the Russian Science Foundation, project no. 16-11-00053.