1. INTRODUCTION
Autonomous Underwater Vehicles (AUV) are important tools for marine resource exploitation and marine scientific research (Zhu et al., Reference Zhu, Hua and Sun2014; Paull et al., Reference Paull, Saeedi, Seto and Li2014; Yang et al., Reference Yang, Zhu and Zhao2014). Due to AUVs' limited energy, communication range/bandwidth, and sensing range, many applications have outgrown a single AUV's capability. Multi-AUV systems, with high parallelism, robustness and collaboration have gradually become a discrete research field (Fiorelli et al., Reference Fiorelli, Leonard, Bhatta, Paley, Bachmayer and Fratantoni2006; Kulkarni and Pompili, Reference Kulkarni and Pompili2010; Millan et al., Reference Millan, Orihuela, Jurado and Rodriguez2014).
There have been some significant achievements in the cooperative target search field in the last 20 years. Gabriely and Ramon (Reference Gabriely and Rimon2003) presented a spiral tree search method. Gonzalez et al. (Reference Gonzalez, Alvarez and Diaz2005) put forward a backtracking spiral algorithm. Polycarpou et al. (Reference Polycarpou, Yang and Passino2001) adopted the traversal exploration method to make a continuous linear search. Though these methods are simple, they only suit searches in static environments rather than dynamic ones.
Zhu et al. (Reference Zhu, Liang and Guan2011) introduced a Particle Swarm Optimisation (PSO) -inspired searching algorithm to lead multi-robot teams to find the desired targets. Since it does not require global information, this saves storage space. However, in target searching, targets' locality are considered to be already known or known to move in a regular way, and thus the fitness function is simplified only to the distance between robots and their targets. In the presence of more complex situations, such a simple evaluation is proved to not be competent.
For complicated environments with obstacles, Ni and Yang (Reference Ni and Yang2011) proposed a search algorithm based on a bioinspired neural network model that is applied in searching and hunting tasks for mobile robots. Although this method is capable of planning collision-free searched paths in unknown environments and gets some good results in the multi-robot scenario (Luo and Yang, Reference Luo and Yang2008), its workspace is totally different from the practical underwater environment.
Compared with multi-robot scenarios on land, there are two main challenges for multi-AUV collaborative searches. One is, on account of limited energy carried by each AUV, to complete the given assignment as fast as possible; the other is how to avoid underwater obstacles and offset the effects of ocean current.
Yoon and Qiao (Reference Yoon and Qiao2011) proposed a cooperative rendezvous scheme called Synchronization-Based Survey (SBS) to facilitate cooperation among a large number of AUVs when surveying a large area. In SBS, AUVs form an intermittently connected network (ICN) in that they periodically meet each other for data aggregation and control signal dissemination. This approach enables the work team to search large areas even with mechanical failures of some team members. However, for its centralised control and lawn-mowing search paths, it mainly is applied to static target search, and its search efficiency is not high (Paley et al., Reference Paley, Zhang and Leonard2008; Yoerger et al., Reference Yoerger, Jakuba, Bradley and Bingham2007).
Couillard et al. (Reference Couillard, Fawcett and Davison2012) developed a local sequential path planning algorithm combined with a global simulated annealing algorithm allowing a multi-AUV team to search for more targets while minimising the total distance covered. However, this method was concerned only with static targets whose positions are already known in advance, and the effects of obstacles and ocean current for searches in practical use were not considered (Li and Landa-Silva, Reference Li and Landa-Silva2011; Masehian and Nejad, Reference Masehian and Nejad2010).
To solve the ocean current effect problem, Alvarez et al. (Reference Alvarez, Caiti and Onken2004) proposed a Genetic Algorithm (GA) to offset the effects of ocean current on the AUV movement. This algorithm can find a safe path that takes the vehicle from its starting location to a mission-specified destination, minimising the energy cost. This algorithm is suitable for situations in which the vehicle has to operate energy-exhaustive missions. Though the GA can offset the effect of ocean current, it needs an iterative process, which not only takes a long time but may not be optimal for all applications (Lorenzo and Glisic, Reference Lorenzo and Glisic2013; Roberge et al., Reference Roberge, Tarbouchi and Labonte2013). Zhu et al. (Reference Zhu, Huan and Yang2013) and Huang et al. (Reference Huang, Zhu and Ding2014) made a combination of velocity synthesis algorithm and Self-Organising Map (SOM) neural network algorithm for three-dimensional (3-D) workspaces subjected to ocean current. This integrated algorithm can control a multi-AUV team to reach all designated locations and guarantees low total energy consumption in the presence of ocean current. It not only worked out the optimal search paths but also effectively offset the effects of ocean current. However it assumed that the underwater workspace is ideal, and it did not take obstacles into consideration.
Considering multi-AUV actual work conditions: a dynamic underwater environment with ocean current and obstacles, this paper proposes an integrated algorithm for multi-AUV cooperative target search by combining the Biological Inspired Neurodynamics Model (BINM) and Velocity Synthesis algorithm (VS). It is expected to provide shorter paths than other algorithms in underwater environments with ocean current and obstacles. The BINM algorithm is developed to coordinate AUV cooperation, and plans their search paths to avoid obstacles. The velocity synthesis algorithm is applied to make a shorter search path to offset the effect of ocean current. Effectiveness and applicability of the proposed integrated cooperative target search method are proved by simulation.
The advantages of the proposed algorithm can be summarised as follows. 1) BINM requires no specimen learning information and is thus easier to apply to practice. In addition, the BINM algorithm is able to plan collision-free search paths. 2) By adjusting AUVs' moving directions to offset ocean current effect for optimal search paths, the VS algorithm is adaptable to different dynamic environments.
This paper is organised as follows. In Section 2, the problem statement is given. In Section 3, the proposed multi-AUV integrated search algorithm is presented. The simulation experiments for various situations are given in Section 4. Concluding remarks are given in Section 5.
2. PROBLEM STATEMENT
The fundamental problem of multi-AUV search systems is how to control all the vehicles to search to their target along the optimised paths cooperatively. Figure 1 shows an underwater search area with obstacles, AUVs, ocean current and targets. In the search area, AUVs, targets and obstacles are randomly distributed. Each AUV is represented by a point without size. The turning radius of the AUV is negligible compared with the underwater environment, thus the AUV is assumed to be able to move omni-directionally. To reduce energy consumption, each AUV should be steered to offset the effect of ocean current. AUVs navigate as short a distance as possible to achieve maximum work efficiency. At the same time, since there are obstacles in the area, the search paths must be collision-free. When the target moves into any AUV's sensing range, this target is regarded as being found and the search task ends.
Figure 1. The underwater search areas.
3. PROPOSED ALGORITHM
The architecture of the proposed search algorithm is shown in Figure 2. It involves three phases. The first is to set the underwater environment as a finite set of maps. Then BINM is used to plan search paths. Finally, VS is added to offset ocean current effect on AUVs to optimise search paths.
Figure 2. Architecture of the proposed algorithm.
3.1. Biological inspired neurodynamics model
In the search process, search paths are determined by BINM. Firstly, a biological inspired neural network is built according to the underwater environment (as shown in Figure 3).
Figure 3. Schematic diagram of BINM.
Firstly, an AUV two-dimensional (2-D) grid coordinate map of working environment is represented by a 2-D Biological Inspired Neural Network (BINN). There is one-to-one correspondence between each neuron in the neural network and the position of the grid map. Secondly, the path strategy of AUV is set on the basis of the distribution of neurons' active output value in the BINM. In Figure 3, the receptive field R is chosen as 2. The receptive field of the l-th neuron is represented by a circle with a radius of R. w kl is the connection weights between neuron k and its neighbour l. Thus, it has lateral connections only to its eight neighbouring neurons within its receptive filed. The AUV may move to one of eight corresponding positions of the grid map next in Figure 3. The real next position of AUV motion is determined by the neurons' active output value of the eight neighbouring neurons within its receptive field. In this model, each individual neuron is connected with the adjacent ones to form a network for their transmission of activity. The dynamic characteristics of the neurons' activity value x k can be denoted as (Ögmen and Gagné, Reference Ögmen and Gagné1990):
$$\displaystyle{{d{x_k}} \over {dt}} = - A{x_k} + (B - {x_k})S_k^e (t) - (D + {x_k})S_k^i (t)$$
setting 
$S_k^e = {[{I_k}]^ +} + \sum\limits_{l = 1}^M {{w_{kl}}{{[{x_l}]}^ +}} $, S ki = [I k]−, then Equation (1) can be converted to (Li et al., Reference Li, Yang and Seto2009):
$$\eqalign{\displaystyle{{d{x_k}} \over {dt}} & = - A{x_k} + \left( {B - {x_k}} \right)\left( {{{[{I_k}]}^ +} + \sum\limits_{l = 1}^M {{w_{kl}}{{[{x_l}]}^ +}}} \right) \cr & \quad - \left( {D + {x_k}} \right){[{I_k}]^ -}} $$where x k represents the activity value of the k-th neuron, x l represents the activity value of those connected to k, M the numbers of the neighbouring neurons, and I k the external signals input in k. The external input I k to the k-th neuron is defined as
$${I_k} = \left\{ \matrix{E, & {if \, it \, is \, a \, target} \hfill \cr - E, & {if \, it \, is \, an \, obstacle} \hfill \cr 0, & otherwise \hfill } \right.$$A, B and D are positive constants, -A reflects the passive decay rate of neuron k's activity, B and D are upper and lower limits of x k, i.e. x k ∈ [−D,B].
In Equation (2), w kl is the connection weights between neuron k and its neighbour l, which can be defined as (Yang and Luo, Reference Yang and Luo2004):
$${w_{kl}} = f\,(\left\vert {{q_k} - {q_l}} \right\vert) = \left\{ {\matrix{ {{\mu / {\left\vert {{q_k} - {q_l}} \right\vert,}}} & {0 \lt \left\vert {q_k - {q_l}} \right\vert \lt R} \cr {0,} & {\left\vert {{q_k} - {q_l}} \right\vert \ge R} \cr } } \right.$$where |q k − q l| is the Euclidean distance between vector q k and q l on the state space, μ and R are both positive constants, and generally, 0 ≤ w kl ≤ 1. As the connections between neurons are not directional, the connection weight coefficients are symmetrical, that is w kl = w lk.
From Equation (2), the neuronal excitatory input signal S ke includes [I k]+ and 
$\sum\limits_{l = 1}^M {{w_{kl}}{{[{x_l}]}^ +}} $. That means one part of the excitation signals comes from external input while the other part comes from internal incremental gains of interconnecting neurons. If I k ≤ 0, then 
$S_k^e = \sum\limits_{l = 1}^M {{w_{kl}}{{[{x_l}]}^ + }} $, which means there is not any external input for neuron k and all its excitation signals are transmitted through the neuronal network. In contrast, S ki = [I k]− means all the inhibitory input for signals k are external. Therefore, the excitation signals transmit between neurons, the value of positive activity of neurons in a neural network has a global effect while the inhibitory signals do not transmit and the negative activity of neurons has only a local effect.
In the search task, the AUV keeps moving toward the location with maximum neural activity in the search area. The strategies of AUVs' paths selection can be denoted as follows:
$${P_n} \Leftarrow {x_{{P_n}}} = \max \{ {x_l},l = 1,2,...,M\} $$where P n represents AUVs' location at the next moment in the map.
Figure 4 shows the process of path selection. When an AUV makes a selection of its path, it compares the activity value of the neuron of its current location with its neighbours and chooses the one with the highest value as the next step. The target and obstacles remain at the peak and valley of the activity landscape of the neural network, respectively. Repeating this process, the AUV keeps moving towards the targets. Thus, the AUV should be able to search for the target efficiently with obstacle avoidance until the search task ends. By this way, the AUVs can realise cooperative searching efficiently.
Figure 4. Process of path selection. (a) Process of path selection in the map (b) Process of path selection in the neural network
In the BINM-based path planning approach above, BINM requires no specimen learning information and parameter adjustment, thus is relatively simple to apply in practice. In addition, the BINM algorithm is able to plan collision-free search paths. It does not offset for the effects of ocean current so the next step is to apply the velocity synthesis algorithm to the optimal search path for each AUV in the ocean current environment.
3.2. Velocity synthesis algorithm
Taking into consideration the effect of ocean currents in a real underwater environment, AUVs may deviate from their search paths planned by BINM, resulting in a failure of the search task, particularly in cases where the current is opposite to AUV's moving direction (Soulignac, Reference Soulignac2011; Jan et al., Reference Jan, Chang and Parberry2008). To solve this problem, the VS algorithm, simple but effective, is included (Sahbani et al., Reference Sahbani, Sahar and Philippe2012; Yang et al., Reference Yang, Chao and Cheng-Kuo2011). Figure 5 shows how VS is applied to modify the search paths.
Figure 5. Velocity synthesis algorithm.
In Figure 5, vector L represents the planned direction by BINM. The angle between L and the x-axis is ai. Vector V c represents the ocean current, and vector V denotes the AUV's velocity whose magnitude is given and can be adjusted according to different requirements. ai2 represents the angle between V and the x-axis. The angle between V c and the x-axis is ai1. The goal is to control the direction of vector V to make sure the resultant vector directly points to the desired direction. The implementation of the velocity synthesis algorithm is based on the precondition that |V c| < |V|. Let |V cn| = |V c|cos(ai − ai1) be the ocean current component assisting motion along vector L and |V cd| = |V c|sin(ai − ai1) be the ocean current component that is perpendicular to the vector L. Similarly, we make |V n| = |V|cos(ai2 − ai) the AUV's velocity component along the vector L and |V d| = |V|sin(ai2 − ai) is the AUV's velocity perpendicular component. Staying on the planned direction requires V d to cancel V cd, which can be interpreted by the following expression (Zhu et al., Reference Zhu, Huan and Yang2013):
$$\left\vert V\right\vert \sin (ai2 - ai) = \left\vert V_c\right\vert \sin (ai - ai1)$$In accordance with vector inside accumulate theorem, another equation is given as follows:
$$ai2 = \arcsin (\left\vert {{V_c}} \right\vert\sin (ai - ai1)/\left\vert V \right\vert) + ai$$Summarising what we have discussed earlier and combining Equations (6) and (7), we can easily calculate ai2.
4. SIMULATION STUDIES
To demonstrate the effectiveness and applicability of the proposed integrated algorithm, several different cases, including searches for dynamic targets in constant and variable current, are implemented on the software platform MATLAB R2011a. For each simulation case, there are four AUVs, one target and several obstacles of different size and shape. In the simulations, underwater environments are put into a search area of 35 × 35 in all cases. The sensing range of each AUV is 1. The velocity of each AUV is set 0·5. The parameters of the proposed algorithm in all simulation cases are shown in Table 1.
Table 1. Control parameters.
4.1. Static target in constant ocean current
The first case deals with a search for a static target in constant ocean current with fixed speed and direction. In this simulation, we set the speed of the ocean current to 0·2 and an angle of ai1 = 135°. According to the principle, the effect of ocean current is equal to neurons activity value increased by 0·2. Since BINM follows the principle of moving towards neurons with a higher activity value for search paths, when the ocean current occurs, AUVs will change their direction towards the target.
Figure 6(a) clearly shows this process. At the beginning of the search task, four AUV members all move with the ocean current at an angle of ai1 = 135°, after a while, R2 and R4 are more affected by neural activity of the target rather than the ocean current and thus gradually turn to the target. On the other hand, because R1 and R3 are much farther from the target than R2 and R4, the target could not overcome the effect with enough activity. Even when R2 has finally finished the search task, R1 and R3 are still fighting against the ocean current.
Figure 6. Search for static target in constant ocean current. (a) Search process by BINM. (b) Search process by BINM & VS.
In Figure 6(b), however, the assistance of the VS algorithm leads to a quite different result. According to Equation (7), VS re-adjusts the AUV's direction by making the AUV's vertical velocity component equal to the currents. In this way, the current's effect is counteracted. As shown in Figure 6(b), four AUVs all move smoothly towards the target during the searching process before R4 finally finds it. Making a comparison between Figure 6(a) and 6(b), the total length of the search paths, either covered by each single AUV or the work team as a whole, are much shorter based on the improved BINM algorithm. It thus realises the goal of improving work efficiency and saving energy.
4.2. Static target in variable ocean current
Variable ocean current refers to current whose speed and direction will change. In this simulation, the variable current is first set a speed of 0·2 and an angle of ai1 = 45°, then 20 seconds later, it changes to a speed of 0·3 and an angle of ai1 = −45°. During the search process, the working principle is similar to that in constant ocean current. The only difference is that when there is a change in the ocean current speed and direction, the neurons that are affected by it will also correspond. In this case, it is initially the neuron whose θ = 45° is affected but then the one whose θ = −45°.
In Figure 7(a), it is clearly shown that AUV's search direction swings from ai1 = 45°to ai1 = −45° at Location 1 where the ocean current's direction changes. However, in Figure 7 (b), with the integration of BINM and VS, AUVs are rarely affected no matter how the current changes but move straight ahead for their target.
Figure 7. Search for static target in variable ocean current. (a) Search process by BINM. (b) Search process by BINM & VS.
4.3. Mobile target in constant ocean current
In a real maritime environment, targets may not necessarily remain stationary. This will undoubtedly cause more difficulties for the search task if ordinary algorithms are adopted. But the biological inspired neural network proposed in this paper avoids this problem. This is because according to the pre-definition, the neural activity value of the target is set as the highest, and AUVs must keep tracking for locations of the highest activity value in the whole dynamic search process. Real-time information about the ever-changing locations of the mobile target can be obtained immediately by each AUV. BINM can constantly re-plan new search paths according to changes of the target's neural activity value and re-assign tasks for each multi-AUV team member no matter how the target swings around.
We set the speed of the constant ocean current to 0·3, the angle ai1 = −45°, and the target moves along a straight line southward at a speed of 0·1. The simulation results are presented in Figure 8. Comparing Figure 8(a) and 8(b), it can be found that due to the effect of ocean current, BINM takes much longer search paths than the proposed algorithm. Particularly, R2 appears confined in a very small search area and zigzags at random with repetitive coverage of the same area.
Figure 8. Search for mobile target in constant ocean current. (a) Search process by BINM. (b) Search process by BINM & VS.
4.4. Comparison
In order to make a comparison between simulation cases in dynamic underwater environments with ocean currents, Table 2 lists the search path length for each AUV as well as for each multi-AUV team as a whole. By analysing these figures, we can make the following conclusions:
1) In all three cases, BINM takes a much longer search path compared with BINM and VS, which proves to be inferior in time and energy saving.
2) As to BINM, the total path lengthens from 100, 105, to 124 when searching for static target in constant current, static target in variable current, or mobile target in constant current. Also the increase rate widens from cases for static targets to mobile ones. This means that BINM is susceptible to the dynamic environment and the more complicated the ocean current is, the lower work efficiency it presents.
3) By BINM and VS, the total path length varies little from 73, 70, to 77, which shows that velocity synthesis algorithm could effectively offset the effect of ocean current and is more adaptable to the dynamic underwater environment.
Table 2. Path length for four cases by the two algorithms.
To better illustrate this, see Figure 9. It is easy to find that the proposed BINM and VS algorithm not only takes a shorter search path in all cases but also shows little distinction between them. Compared with BINM that varies greatly in amplitude, it turns out to be more stable.
Figure 9. Comparison of total path length by the two algorithms.
5. CONCLUSION
In this paper, an integrated algorithm combining a biological inspired neurodynamics model and velocity synthesis algorithm is proposed to deal with cooperative search by a multi-AUV team in dynamic underwater environments. On the one hand, it makes full use of the advantages of BINM, i.e. no prior knowledge, pre-learning procedure or parameter adjustment are needed. In addition the velocity synthesis approach could optimise the path of BINM and offset the effect of ocean current. Despite these advantages, there are still practical problems to be further researched. For example, the real underwater environment is three-dimensional, while in this paper many factors are simplified into a two-dimensional simulation.
ACKNOWLEDGEMENTS
This project is supported by the National Natural Science Foundation of China (51279098), Creative Activity Plan for Science and Technology Commission of Shanghai (13510721400, 14JC1402800) and the Innovation Program of Shanghai Municipal Education Commission (13ZZ123).
