Review of multiple unmanned surface vessels collaborative search and hunting based on swarm intelligence

Abstract

In recent years, the research of multiple unmanned surface vessels collaboration has received great attention. More and more researchers have proposed different methods of multiple unmanned surface vessels collaboration, such as cooperative collision avoidance, formation, and rendezvous. Based on the significant advantages of biological swarm intelligence applications in these collaborative methods, this article summarizes the research methods of multiple unmanned surface vessels collaborative search and hunting from the perspective of swarm intelligence. First of all, this article summarizes the key technologies of multiple unmanned surface vessels collaborative search and hunting from the aspects of the multi-robot system, group communication, environment modeling, collaboration mechanism, and path planning. Then, it reviews some classic swarm intelligence algorithms, analyzes the advantages and disadvantages of these algorithms, and proposes optimization directions for existing disadvantages based on relevant literature. Finally, the article points out some existing problems in every stage and suggestions for future research.

Introduction

There are many amazing and ingenious “designs” in nature. ¹ The behaviors of bee colony building nests (Figure 1), ant colony cooperative handling, wolf group hunting (Figure 2), and fish swarming for food demonstrate swarm intelligence (SI). Although individuals in these groups have simple behaviors and very limited abilities, when they work together, they can emerge very complex collective intelligence characteristics. Group behavior is one of the most basic intelligent activities in the natural system. Through the coordination and cooperation of multiple entities, they can give full play to their respective advantages and complete complex tasks that are difficult for a single individual to complete.

Figure 1.

The colony of bees builds a nest.

Figure 2.

Wolf group hunting.

The wisdom of the crowd has always inspired us to bring the latest technological advances. Scientists are studying to imitate intelligence by simulating a swarm of bees. The “swarm robotics” is made up of a group of robots, which can collaborate among multiple individuals and behave as a whole. National Aeronautics and Space Administration (NASA) is preparing to form a new team of robots - “swarmies”. They consist of a group of small, well-trained runner robots that work together like ants. Maybe one day they can help humans detect aliens and dig out more oil and gas, water, rocket fuel and other resources from other planets. Each “bee colony” is equipped with a web camera, a WIFI antenna, and a GPS locator. When working, “bee colonies” act individually, and they will immediately notify other “clusters” when they find valuable resources. It is very similar to the foraging method of ants’ division of labor and cooperation. It is understood that there are currently four swarms similar to streamlined radio-controlled vehicles being tested in the parking lot of the Kennedy R&D Center. Chief Engineer Cheryle Mako said, “Our progress is already very fast, and we are currently in the stage of continuous testing and massive data collection.” Once the test is successful, the Kennedy R&D Center will send the bee colony and the mini robot Rassor to the surface of the moon or Mars.

Target search is an extremely critical technology for modern operations, civil rescue, and other activities. Unmanned aerial vehicle (UAV) has been extensively studied for their superiority in military strategy. American fighters, such as the Global Hawk and Predator, have been heavily used in various military operations. Unmanned ground vehicle (UGV) is also widely used in the field of industrial automation, planet exploring, disaster rescue, intelligent transportation, and military operation. ² After decades of research and development on the autonomy of air and underwater vehicles, people’s interest in USV has rekindled. Compared with UAV and UGV, the environment of USV is far more complex. Apart from the interference of wind, wave, and current, the USV’s inertia, in some environments, the resistance, and the response time on waters are also larger than those on the ground and in the air. ³ The control of the USV is harder than the UGV and the UAV to some extent. At present, many scholars have considered the influence of wind, waves, and currents in the research of MUSV cooperative control. ⁴ However, there are few studies on the influence of ship hydrodynamic effects in the cooperative motion control of USV. Literature ⁵ linked the research of MUSV cooperative control with hydrodynamic effects and summarized the influence of fluid dynamics on the cooperative motion control of USV. Coordination control, which includes obstacle avoidance, rendezvous, and formation, is employed to achieve the system-level coordination for a multi-agent system (MAS). ⁶ The collision avoidance method can be roughly divided into four parts: geometric method, bionic optimization algorithm, virtual vector and field theory, and artificial intelligence method. ⁷ At present, with the development of artificial intelligence, bionic optimization algorithms and artificial intelligence methods based on learning and gaming have made great progress. Rendezvous is to study the issue of collision avoidance between MUSVs. The “International Convention on Rules for Preventing Collision at Sea” (COLREGS) stipulates the navigation rules that all ships must comply with at sea to prevent collisions. However, COLREGS only considers the situation when two ships are rendezvous and lacks a quantitative standard when multiple ships are rendezvous. Kim et al. ⁸ proposed a distributed local search algorithm to achieve multi-ship collision avoidance and proposed a distributed stochastic search algorithm in the literature ⁹ to reduce the amount of information transfer between multiple ships so that the ships formation can be adjusted faster. Ma et al. ¹⁰ proposed a quantitative standard for a large number of USV’s complex collision avoidance situations under COLREGS. Formation control aims at steering a group of MUSV to form a specific geometric configuration and control their coordinated collective motion. In the USV formation, there are many research studies on the leader–follower method and the virtual structure method and relatively few research studies based on the behavior method. This is partly because the former two are easier to achieve formation and maintenance. The behavior-based approach has the advantage of multi-tasking, and it has greater development prospects in the future. In some recent studies, more and more of them combine behavior-based methods with other methods to accomplish tasks, such as formation and obstacle avoidance at the same time. ^11,12 When MUSV performs cooperative tasks, such as searching and rounding up, it usually needs to arrive at the designated meeting place first and then perform specific cooperative tasks. Feng et al. ⁶ proposed a model for rendezvous and formation tasks and realized the MUSV rendezvous and formation at a designated location.

The main contributions of this article are as follows. The key technologies and main methods of cooperative search and round-up of MUSV are reviewed. Swarm intelligence, multi-robot system, MUSV architecture, communication methods between MUSVs, environmental modeling methods, planning algorithms, and their applications in the military and civilians have been comprehensively reviewed. The main scene mode of cooperative search and round-up of MUSV is proposed in this article (see Figure 3). It is recommended to adopt a distributed architecture in the MUSV searching stage and a centralized architecture in the MUSV round-up stage. Adopting different MUSV organizational structures at different stages will help improve the efficiency of MUSV. Moreover, according to the relevant literature, the advantages and disadvantages, and development directions of several intelligent algorithms that are commonly used are summarized. This article will propose a research method for researching MUSV collaborative search and hunting from two perspectives of SI.

Figure 3.

MUSV cooperative search and round-up at sea. MUSV: multiple unmanned surface vessels.

The following arrangements for this article are as follows. The first section presents the swarm intelligence overview. The second section introduces the research methods of MUSV collaborative search and hunting from five aspects, multi-robot system, communication mode, environment modeling, cooperation mechanism, and path planning. In the third section, two methods of the round-up target are introduced, namely, a method based on game theory and a method based on probability analysis. The fourth section shows the important applications of MUSV collaborative search and swarm hunting in military and civilian applications. Finally, the fifth section gives the conclusion of the review on cooperative search and round-up of MUSV. This review is necessary for the development of MUSV, multi-robot researchers, and industry-standard elaborations.

MUSV SI overview

Since the end of the 20th century, swarm intelligence (SI) has gradually entered the field of vision of researchers. SI is a kind of soft bionics of natural groups. It simulates the social structure and interaction of the group rather than the individual structure in traditional artificial intelligence. Individuals can be regarded as agents with simple and single abilities. Some of them have the ability to evolve themselves when dealing with certain problems to obtain better compatibility. Swarm robots are a new method of MRS coordination, which is composed of a large number of simple physical robots. It is believed that the desired collective behavior is generated from the interaction between robots and the interaction between robots and the environment. This method appears in the field of artificial SI and biological research in insects, ants, and other areas where swarm behavior occurs in nature. There are two directions for SI development research on insect swarms. ¹³ One is to design SI optimization algorithms and the other is to build a distributed SI system. Swarm intelligence optimization algorithms, such as particle swarm optimization (PSO) ¹⁴ and ant colony optimization (ACO) ¹⁵ were originally a strategy to find the best food source in a certain area through group iteration. With the deepening of research, the SI algorithm is widely used to find the optimal path, ^16,17 multi-objective optimizations, ¹⁸ and task allocation decision ¹⁹ based on the essence of SI algorithm to find the optimal solution. In recent years, many researchers have tried to directly imitate the mechanism of insect division of labor, establish a distributed SI system, and apply it to multi-robot collaboration. When large-scale robots are required to collaborate to handle more complex tasks, this collaborative model inspired by populations shows great advantages. Cao and Xiao combined the bee colony excitation inhibition with the stimulus-response, realized close collaboration between individuals through the excitation inhibition principle, adjusted the distribution of robots in the unknown area, and gave full play to the role of each robot. ²⁰

According to the above two directions, there are also two applications of SI in MUSV cooperative search and hunting. One is to optimize path planning and task allocation decisions through SI optimization algorithms. The other is to build a corresponding distributed group intelligence system and directly apply the group intelligence mechanism to collaboration. In the next section, we will summarize the collaborative search and hunting methods of USV based on the above two perspectives from the aspects of MRS, group communication, environment modeling, cooperation mechanism, and path planning. The functional diagram of MUSV cooperative search and hunting is shown in Figure 4.

Figure 4.

Functional diagram of MUSV cooperative search and hunting. MUSV: multiple unmanned surface vessels.

MUSV cooperative search and round-up

MUSV collaborative search and round-up are divided into two stages: search and round-up. In the searching stage, the MUSV shares information and autonomously searches for nearby areas. In the round-up stage, the USV that found the target will lead the nearby MUSV to round up the target. A schematic diagram of the MUSV collaborative search and round-up is shown in Figure 5. In Figure 5(a), the USV performs the task of searching for suspicious ships around the island based on ground communication equipment and its sensors. When performing search tasks, the MUSV searches together in a distributed control structure. Each USV autonomously searches nearby areas. The MUSV maintains real-time communication and shares information for collaborative search tasks. In figure 5(b), when the USV1 finds the suspicious ship, MUSV turns from the search state to the round-up state. In the round-up state, each USV adopts a centralized control structure, and the USV1 leads the other USV to round up the suspicious ship.

Figure 5.

(a) MUSV collaborative search and (b) MUSV coordinated round-up. MUSV: multiple unmanned surface vessels.

To realize the MUSV autonomous distributed collaborative search and hunting, researchers mainly conduct research from the aspects of MRS, group communication, environment modeling, collaboration mechanism, and path planning. The following will be summarized from two perspectives of group intelligence algorithm optimization and distributed group intelligence system construction.

Architecture of MUSV

According to different cooperation mechanisms, MRS can be divided into conscious MRS and unconscious MRS. ²¹ These two systems correspond to two perspectives of SI research. If a conscious MUSV is used in the collaborative search and round-up of the USV, the subsequent optimization of the collaborative mechanism and path planning needs to be carried out through the SI optimization algorithm. The unconscious MUSV is a distributed swarm intelligent system built by imitating the operating mechanism of the bio-social biological community (ant colony, bee colony, etc.).

Conscious MUSV system

A conscious MRS can also be called a planning-based MRS. ²² In a conscious MUSV, each USV has its own “brain,” that is, each USV has a structure for perception, planning, and motion control. MUSVs are essentially driven by the MUSV agent system. In this system, each USV is regarded as an independent agent, and then, the coordinated control of MUSV is realized through a specific architecture. Conscious MUSVs are often composed of a group of relatively small and possibly heterogeneous USV. The individual intelligence level is relatively high, and the knowledge of the environment, tasks, and other USVs are relatively comprehensive. At the same time, individuals will have a global goal and plan their own behavior according to the goal, so as to perform tasks more directly and efficiently.

The consciously MUSV mainly uses the multi-robot architecture to determine the information flow relationship between the system and each USV and its logical topological structure and through the system structure to determine the operation mechanism of task decomposition, role assignment, planning, and execution. At the same time, it also provides a framework for robot activities and interaction. ²³ Choosing an appropriate architecture is the key to the normal and efficient operation of MUSV, and it is also the primary issue for building a MUSV. Asama ²⁴ proposed the famous ACTRESS system. Beni and Jing developed the classic SWARM ²⁵ system. Wang et al. proposed a layered architecture for multi-robot formations. ²⁶ From the perspective of collaboration, the multi-robot system architecture can be divided into three types: centralized, decentralized, and hybrid. ²⁷

Centralized structure for MUSV

As the centralized structure, there is a “leader” USV in the MUSV system, which distributes and manages the tasks of the others “follower” USV in the group. The leader USV shares information through a dedicated message transmission channel. The advantage of this system structure is that the internal information of the system is consistent, and the management and scheduling are relatively simple. The disadvantage is that the robustness of the system is low. If the leader USV experiences a failure, the entire MUSV system may fail to operate. At the same time, as the dynamic characteristics of the output of the USV become more and more complex, the control of the system will become more and more difficult. The centralized structure for MUSV is shown in Figure 6.

Figure 6.

Centralized structure for MUSV. MUSV: multiple unmanned surface vesselss.

Decentralized structure for MUSV

In the decentralized structure of MUSV, each USV has equal status, regardless of priority. There are multiple intermediary agencies in the system to provide services for USV to find cooperative partners. The disadvantage of this architecture is that it is difficult to reach an agreement on the internal information of the system, and each USV can only obtain a certain range of partial information. Its advantage is that it significantly improves the stability and reliability of the MUSV system and reduces the difficulty of complex control systems. The distributed structure for MUSV is shown in Figure 7.

Figure 7.

Distributed structure for MUSV. MUSV: multiple unmanned surface vessels.

Hybrid structure for MUSV

The hybrid structure mixes the centralized structure and the decentralized structure together. According to task requirements, different architectures are adopted in different stages or different parts. Most USVs in the system are equal to each other. At the same time, there are also a small number of management USVs responsible for managing other USVs, participating in solving the task division and configuration between USVs, and sharing resource tasks and management, conflict coordination, etc. This method can balance the advantages and disadvantages of centralized and decentralized structures, but the balance of the two structures is a difficult problem. The hybrid structure for MUSV is shown in Figure 8.

Figure 8.

Hybrid structure for MUSV. MUSV: multiple unmanned surface vessels.

Unconscious MUSV system

The unconscious MUSV system mainly mimics the operating mechanism of social biological communities (e.g. ant colonies and bee colonies). The characteristic of the unconscious MUSV is distributed control. An individual USV is a completely autonomous body and does not need any centralized controller to coordinate other autonomous USV. Just as individuals in a biological group, they are only partially and indirectly affected by other individuals or the environment. Therefore, individuals can quickly and flexibly respond to dynamically changing environments without waiting for centralized control signals. Although this kind of individual behavior seems to have no overall purpose, the combination of many individual behaviors in the same environment can produce a group of collaborative behavior. Typical systems are as follows, Alice from the Swiss Federal Institute of Technology, ²⁸ CEBOT from Nagoya University in Japan, ²⁹ and an evolutionary multi-robot organism from the University of Stuttgart in Germany. ³⁰

Unconscious MUSV can be further divided into cluster USV systems based on emergent behavior and reconfigured MUSV systems. The difference between them is that the latter requires a combination of specific linkages and joint modules to form a special configuration and complete the specified functions. The characteristics of distribution and autonomy make the unconscious MUSV capable of large-scale and large-scale collaborative tasks. For example, reconnaissance, monitoring, and search of unknown environments. In recent years, with the further improvement of computer calculation speed, centralized control has been easier to achieve. The research enthusiasm for conscious MUSV has not diminished, and the research on unconscious MUSV based on bionics needs to be deepened.

Group communication for MUSV

In MUSV collaboration, reasonable communication can greatly improve the operating efficiency of the system. To achieve task assignment and behavior coordination, information interaction between USV is essential. The communication methods between USV can be divided into two types: explicit communication and implicit communication. ²⁷

MUSV explicit communication

Explicit communication refers to the direct information exchange behavior of USV through dedicated hardware communication equipment and complex information representation models as shown in Figure 9. Explicit communication can be further divided into direct communication and indirect communication. Direct communication requires the sender and receiver to be consistent, that is, the sender and receiver are online at the same time during communication, so a communication protocol is required.

Figure 9.

MUSV explicit communication. MUSV: multiple unmanned surface vessels.

Indirect communication does not require the sender and receiver to be consistent. The blackboard is a type of indirect communication. It does not require a receiver nor does it guarantee that the information is correctly transmitted to the receiver. In the study of coordinated round-up of MUSV, Wang announced missions in the form of blackboard mode communication. Each USV chooses whether to participate through its own decision-making, which improves the cooperation efficiency of MUSV. ³¹

In general, this expensive communication method can improve the efficiency of collaboration between USVs. However, limited by communication bandwidth and real-time interaction, it is difficult to handle a large-scale, long-distance transmission. ³² It is possible to ensure certain communication effectiveness and real-time performance by designing a dedicated communication mechanism ³³ and communication language ³⁴ for MUSV.

MUSV implicit communication

Implicit communication means that each USV obtains the required information through the external environment and its own sensors and realizes mutual cooperation. There is no direct exchange of information between each USV. The important feature of this communication method is that the USV leaves certain information in the environment through a certain medium and obtains the information left by other USV through sensors as shown in Figure 10. There is no explicit exchange of data between them. This communication method is inspired by the exchange of pheromones left by ants in nature. Wu et al. imitated the method of ant foraging and secreting pheromone and proposed a collaborative search algorithm for USV based on pheromone decision-making. ³⁵

Figure 10.

MUSV implicit communication. MUSV: multiple unmanned surface vessels.

Because there is no explicit exchange of data between individuals in group USVs that adopt implicit communication, advanced coordination and collaboration strategies cannot be used. ³⁶ At the same time, this also reduces the ability to complete complex tasks. In addition, the design and implementation of implicit communication systems are also difficult.

Environmental modeling for MUSV

According to whether the environmental information of the search area is known, the MUSV search is divided into search in a known environment and search in an unknown environment. The search of the known environment relies on the environmental map to divide the target area. According to the results of the area division, the USV is assigned to each area to perform tasks and then plan the optimal path for each USV to traverse the assigned area. The search for the unknown environment requires each USV to rely on the detection equipment carried by itself to coordinate the construction of the environment map as shown in Figure 11. In recent years, MUSV search and round-up in unknown environments have attracted much attention. It involves the perception and recognition of the search environment and the creation of a map of the environment. Commonly used unknown environment modeling methods include grid method, ³⁷ cell decomposition method, ^38,39 topological logic diagram method, ^40,41 and so on.

Figure 11.

Environmental collaboration modeling for MUSV. MUSV: multiple unmanned surface vessels.

1. Grid method: The continuous environment map is discretized into a fixed-size grid space. After the USV explores, the grid where the obstacle is located is marked as 1, and the passable area is marked as 0, then the environment map can be obtained.

2. Cell decomposition method: The environment is represented as a collection of geometric features, such as points, lines, and surfaces. This method can reflect environmental information concisely and completely, but it is difficult to represent a very complex environment.

3. Topological logic diagram method: The important feature information in the environment is abstracted into points, lines, and surfaces in a topological map. For example, if the USV is abstracted as a node in the topological graph and the communication capability is abstracted as a line, the topology of the USV cluster is formed. This method is more suitable for large and simple environments. It can realize fast path planning and has good feasibility.

In the research of MUSV collaborative search and hunting, environmental modeling is essential no matter from the perspective of group intelligence optimization or the perspective of group intelligence system construction. At present, many research studies on MUSV collaboration are based on the grid method for discrete environmental modeling. The advantage of grid method modeling is that the representation method is simple, easy to implement, and can better express the distribution of object positions in actual space. However, it is not suitable for the grid method applicated in high-latitude environments.

Cooperation mechanism for MUSV

For the MUSV system, the collaboration mechanism refers to the task allocation problem of MUSV collaboration. Task allocation is a process in which each USV reasonably coordinates task allocation according to its own function, location, and energy surplus so as to perform tasks efficiently and avoid waste of resources. The task allocation problem of MUSV can be regarded as optimal allocation problem, integer linear programming problem, scheduling problem, network flow problem, and combination optimization problem in different situations. ⁴² Many scholars have applied behavior-based method, ^43,44 market method, ^{45 –47} SI method, ^{48 –51} emotion-based method, ⁴⁸ and so on to multi-robot task distribution.

This article mainly studies the task allocation mechanism of MUSV collaborative search and round-up from the perspectives of SI optimization and SI systems. From the perspective of SI optimization, Li used an improved bacterial foraging optimization algorithm to optimize the positive team affective tone model based on team collaboration, which improves team collaboration capabilities and the effectiveness of the system. ⁴⁸ Zitouni et al. ⁴⁹ used an artificial bee colony (ABC) algorithm, firefly algorithm, and genetic algorithm to optimize the task allocation scheme based on the auction method, which greatly improved the efficiency of task allocation. From the perspective of the SI system, Su et al. ⁵⁰ designed an ant colony algorithm based on the division of labor mechanism to solve the task assignment problem on the basis of the multi-sub-colony ant colony algorithm. Li and Zhang ⁵¹ used the mixed-integer linear programming method to construct the optimization function and used the particle swarm algorithm to find the optimal solution, which effectively solved the task assignment problem.

Path planning methods for MUSV

The path planning of the USV is to find an optimal path from the starting position to the target position under certain constraints. ⁵² In the coordinated search and round-up of MUSV, the path planning of each USV is relatively complicated. It is not only required to find the optimal path from the starting point to the target position under the constraints of avoiding obstacles, minimum turning radius, maximum acceleration, maximum energy consumption but also needs to consider the dynamic characteristics of the USV maneuverability as shown in Figure 12. The existing path planning methods are mainly divided into four categories ⁵³ : methods based on geometric model search, ^54,55 algorithms based on probability sampling, ^56,57 artificial potential field algorithms, ^58,59 and intelligent algorithms. ^60,61 Literature ⁶² divides USV path planning into three stages: route planning, trajectory planning, and motion planning. In the route planning stage, the USV is treated as a particle and only considers the optimal route from the starting point to the endpoint of the geographical constraint planning. In the trajectory planning stage, kinematic constraints, such as the shape and speed of the USV, are considered to optimize the planned route. The motion planning stage needs to fully consider the dynamic constraints of the USV and expect to obtain an actual motion path from the start point to the endpoint. Currently, fully autonomous USV motion planning has not yet been implemented. This part mainly reviews the path planning in MUSV collaborative search and round-up from the perspective of SI. At present, the most researched SI algorithms are shown as follows.

Figure 12.

Collaborative path planning for MUSV. MUSV: multiple unmanned surface vessels.

PSO algorithm

The first group heuristic algorithm was proposed by Kennedy and Eberhart in 1995. They drew inspiration from the flying birds in nature and proposed the PSO algorithm. ¹⁴ The PSO algorithm treats each problem solution as a particle in the search range, and each individual particle has its corresponding position vector and velocity vector. At the same time, the fitness value of the particle is determined by the objective function. The particles search for generations in the solution area according to the current optimal particles, judge whether the current position value is the best position according to its own fitness value, and then search generation by generation to obtain the optimal solution.

This algorithm is characterized by fast convergence, high efficiency, and a simple algorithm and is suitable for real-value processing. However, the search accuracy is low, and it is easy to fall into the local optimum. To improve the quality of the results, the speed of convergence, or even just to adapt to a certain problem, researchers have proposed many variants of the PSO algorithm. The asynchronous PSO algorithm proposed by Carlisle and Dozier ⁶³ in 2001 converges faster in the case of large neighborhoods and results in higher quality. In the literature ⁶⁴ , the DPSO algorithm was proposed for the optimal solution of discrete space problems. This algorithm has the advantage of being easy to combine with other algorithms and has a good development prospect. Aiming at the problem of poor optimization in the later stage of the algorithm, there are currently two main solutions. One is that the literature ⁶⁵ , and the literature ⁶⁶ adjust the parameters according to the adaptive principle and use different inertia weights and learning factors in different periods of the algorithm to improve the problem of premature convergence of the PSO. However, the adaptability of the parameters to the scale of the environment is insufficient, and it is still difficult to get rid of the local extreme phenomenon under the influence of external environments, such as water flow and other factors. The other is the algorithm that combines PSO and AFSA in literature, ⁶⁷ literature ⁶⁸ combines the PSO with the Bacterial Foraging Algorithm(BFA), and the hybrid algorithm can greatly improve the later optimization ability of the algorithm and has certain environmental adaptability.

ACO algorithm

In 1999, based on the basis of bionics, Dorigo et al. first proposed an ACO algorithm to deal with some combinatorial optimization problems. ¹⁵ When MUSV performs the search task, it does not simply find the shortest path from the current position to the target, but also considers the obstacles on the path and the complex terrain environment, which brings a huge amount of computation. Researchers thought of applying the ACO to the path planning of MUSV. The individual ant is used to replace USV. In addition, the concentration and visibility of pheromone released by ants in searching for food sources are correlated with the probability of MUSV moving from one place to another, so as to plan a MUSV collaborative search optimal path.

The ACO algorithm can solve many complex combinatorial optimization problems only through simple collaboration between individuals. It is easy to program and does not involve complex mathematical operations. It also has good robustness and parallelism and is popular among researchers. However, its performance is affected by the pheromone update model, and the early convergence process is longer. It is easy to cause the population to lose diversity and fall into a local optimum, resulting in poor local searchability. Angus ⁶⁹ proposed crowding population-based ACO, and the pareto strength ACO algorithm is proposed by Thantulage ⁷⁰ by selecting different weight parameters or changing the pheromone update rule. Ma and Jin ⁷¹ used weighted optimization of transition probabilities in different environments and proposed multi-objective path planning based on the pursuit of the shortest path, which greatly reduced the probability of local extreme values. It makes the USV can search in a more complex environment, which improves the practical significance of the ant colony algorithm. The glowworm swarm optimization is combined with the ACO in the literature, ⁷² which not only exerts the advantages of the ACO in discrete optimization problems but also uses it to solve some continuous optimization problems. It improves the use-value of the algorithm.

ABC algorithm

The origin of the ABC was discovered by the Nobel Prize winner and Austrian K von Frisch. In 2005, Karaboga ⁷³ of the Turkish University formally proposed the ABC based on the mutual division of labor between bees and the local sharing of information to find the best nectar source. In the path planning of the MUSV, the optimal path of the USV can be compared to the optimal nectar source. The length of the path is used as the function value of the problem. The process of problem-solving is finding the optimal path.

Compared with other population-based algorithms, the ABC algorithm does not require many important external control parameters, and these parameters are difficult to determine in advance before starting the search process. For example, acceleration coefficients and inertia weights are used in PSO. Therefore, this algorithm has attracted the attention of many researchers. Moreover, this algorithm has the advantage of being easy to implement and has achieved a good balance between the exploration and development process. However, it is prone to premature maturity. When approaching the global optimal solution, it is easy to fall into the local optimal, resulting in slower convergence in the later stage. Karabaoga and Gorkemli ⁷⁴ modified the behavior of onlookers, introduced the radius of the neighborhood as a control parameter, and proposed a quick ABC algorithm, which significantly improved the local search performance. To solve the local extremum problem, Aslan ⁷⁵ et al. proposed an improved quick ABC algorithm to improve global searchability. Liang et al. ⁷⁶ combined the ABC algorithm and ant colony algorithm and proposed an improved ABC algorithm to improve the ability of later optimization. Ding et al. ⁷⁷ combined the ABC algorithm and the cuckoo algorithm and used the chaotic search mechanism to traverse the global environment to promote the algorithm to get rid of the local extreme value phenomenon.

Table 1 summarizes the advantages and disadvantages of the above three SI algorithms. Based on these advantages and disadvantages, the current optimization methods for the local extreme phenomenon of SI algorithms and their advantages and disadvantages are summarized in Table 2.

Table 1.

Advantages and disadvantages of SI algorithm.

Swarm intelligence algorithm	Advantages	Disadvantages
PSO	Fast convergence and high efficiency in the early stage	Low search accuracy and easy to fall into local optima
ABC	Few parameters Fast convergence in the early stage	Slow convergence in the later stage
ACO	High robustness and parallelism No complicated mathematical operations	Poor local search ability Easy to fall into local optima

PSO: particle swarm optimization; ABC: artificial bee colony; ACO: ant colony optimization; SI: swarm intelligence.

Table 2.

Review of local extremum optimization method for SI algorithm.

Optimization	PSO	ABC	ACO	Advantages	Disadvantages
Modify parameter weight	64,66	74,75	69,70,71	Fast convergence in the later stage Global optimization is good	Poor environmental adaptability Large amount of calculation
Hybrid algorithm	67,68	76,77	72,76	Have a certain environmental adaptability	Large amount of calculation in complex environment

PSO: particle swarm optimization; ABC: artificial bee colony; ACO: ant colony optimization; SI: swarm intelligence.

Unresolved issues

1. Compared with traditional algorithms, the three heuristic algorithms proposed above have significant advantages in dealing with multiple goals and facing complex dynamic environmental problems. However, when there are many optimization targets, the environment is complicated, and the calculation amount is too large, it will converge prematurely and fall into a local extreme value.

2. When the heuristic algorithm is used to plan the path of MUSV, the individual size and maneuverability of each USV are not considered. It is because the individuals studied by these population-based algorithms are usually small, and they are generally abstracted as a single mass point.

3. When the heuristic algorithm is used to plan the path of MUSV, it is not combined with the COLREGS, which lacks practical significance.

4. There is less research on multiple heterogeneous USV. When a certain task allocation mechanism is introduced according to the energy and function of each USV, the calculation amount of the algorithm will be greatly increased. It will make the algorithm difficult to implement in reality, and its practicability needs to be improved.

Development proposals

1. At present, the direction of optimizing local optimal problems can be divided into two categories. One is to improve the global optimization by adding some weight parameters or changing some of the corresponding mechanisms, such as literature. ^64,74,71 . The other is to combine multiple algorithms and use hybrid algorithms to make up for the deficiencies of each algorithm, such as literature. ^67,77,72 It is recommended to use a mixture of classic algorithms and heuristic algorithms or a mixture of multiple intelligent algorithms to reduce local optimum and improve the robustness and stability of the system.

2. It is recommended to add the size and state of the USV itself as well as environmental parameters, such as wind, waves, and currents, into the modeling and simulation of the USV collaborative search.

3. In Zeng et al., ⁷⁸ in accordance with the requirements of the COLREGS, comprehensively considering the safety and economy of ship navigation, a hybrid optimal collision avoidance decision algorithm based on particle swarm-genetic is proposed. The literature assumes that all MUSVs comply with the collision avoidance rules and believe that the ships will obtain the avoidance actions of the surrounding MUSV in real time. However, in the actual situation of MUSV rendezvous at sea, there may be situations such as human error or uncoordinated collision avoidance measures between MUSVs. Therefore, it is necessary to consider the collision avoidance decision of the group intelligence algorithm under COLREGS in future work.

MUSV collaborative round-up methods

The MUSV coordinated round-up has attracted much attention because of its important role in the military field. In the 1990s, Yamaguchi first proposed the use of feedback control rate to coordinate the movement of multiple USV and used formation vectors to control the group to achieve the purpose of capturing the target. ⁷⁹ From the perspective of collaboration, the MUSV collaborative round-up is just a more complex collaboration based on the MUSV collaborative search, adding more constraints. The idea of formation control can be used to solve this unique problem. MUSV can compress the target’s range of movement by maintaining a certain formation, thereby achieving the purpose of capturing the target as shown in Figure 13. At present, the commonly used formation control methods include the leader–follower method, virtual structure method, and behavior-based method.

Figure 13.

Collaborative round-up for MUSV. MUSV: multiple unmanned surface vessels.

In the leader–follower method, one of the robots can be considered as the leader and has global navigation information. Using it as a reference, other USVs will follow the leading USV at the desired relative distance and direction to obtain the desired formation. Literature ⁸⁰ uses the leader–follower method to experiment on the cooperative operation of two USVs to perform predetermined tasks in a complex marine environment. It successfully realized the process of maintaining the formation of two USVs in the real environment to avoid collisions. In Dong and Chen, ⁸¹ an observer was constructed based on a nonlinear internal model, and then, a local controller was designed based on the observer to realize the asymptotic tracking of the leader’s attitude and angular velocity, which has great reference significance. The basic idea of the virtual structure method is to treat the entire formation as a virtual structure of a rigid body. Each formation member regards the structural points on the rigid body as their respective tracking reference points. When the rigid body is sailing along the set route, the formation members track their respective references points. So it achieves the desired formation of each member approaching the formation. Ghommem et al. ⁸² proposed a formation structure combining the virtual structure method and the path following method. During the path tracking of each USV, the following speed is adjusted to achieve coordination between MUSVs. Behavior-based methods refer to specific behaviors, such as avoiding obstacles, maintaining the desired formation, driving to the target point, and obtaining the formation behavior of the entire group through the weighted average of each desired behavior. In the actual task, the formation may have multiple control objectives, such as formation maintenance, target search, and obstacle avoidance. The behavior of the formation members is the result of the weighted superposition of each control behavior, and its coordinated movement is a variety of behaviors compromise. Literature ⁸³ combined the null-space-based (NSB) behavioral method and COLREGS on the basis of behavior method to simultaneously complete the formation maintenance, collision avoidance, and rendezvous problems of MUSV.

How to achieve MUSV tracking a predefined geometric path while maintaining the formation of the required form is the key. Literature ⁸⁴ designed a dynamic controller to realize marine vehicle trajectory tracking by incorporating the first-order filter into the dynamic surface control. Considering the external disturbances in the complex ocean environment, literature ⁸⁵ developed a coordinated guidance law to guide the unmanned underwater vehicles’ surge speed and yaw speed and adopted the path update law based on neighbor information to achieve synchronous tracking. It successfully realized the process of multiple unmanned underwater vehicles tracking multiple parameterized paths in a complex environment. To improve the convergence time of the formation control system, literature ⁸⁶ designed a distributed surge and heading dynamics controller based on an uncertainty observer under physical constraints to ensure that the USV tracks the guidance signal within a limited time.

Most scholars have conducted research on the above-mentioned issues and have achieved excellent results. To improve the practical significance of the MUSV round-up, the current research on the round-up problem also needs to consider the escape strategy of the pursued object. Literature ⁸⁷ used adaptive networks and diffusion adaptation mechanisms to simulate the behavior of fish avoiding predators. Literature ⁸⁸ studied the ability of prey with different visual ranges to avoid predators. Regarding the complex problem of capturing smart targets, Benda et al. ⁸⁹ put forward research on the problem of “chasing the game.” Based on the contest between round-up and anti-round-up in the military, this issue has become an important research topic. Study two types of agents, predators and preys, and how predators can effectively capture preys through collaboration. At present, the research on this problem mainly has the following three methods.

Collaborative hunting method based on game theory

Game theory is actually a kind of competition mechanism. It is a mathematical theory and method for multiple participants who study the conflict of interests and goals to find the optimal strategy under the condition of theoretical confrontation and cooperation and collusion. There are two ways to apply game theory to the problem of “chasing the game.” The first is to establish a competition mechanism within the hunter team to capture different targets through mutual competition between hunters. This method can optimize the overall performance of the hunter team. The second is to establish a competition mechanism between the hunter and the escaper and use non-game theory to study the optimal strategy for both hunting and running away. Ni et al. ⁹⁰ combined the two competition mechanisms and proposed a dual competition strategy. The pursuers compete with the evaders through the distance between them and the evaders, the safe distance between the pursuers, and the speed of the pursuers. At the same time, the evader with the least time in the hunting group will be selected as the easiest target to be pursued and should be captured first. Literature ⁹¹ established the escapee’s trajectory based on learning the escapee’s strategy choice and adjusted the trajectory to the hunter’s strategy set. Then, the cooperative hunting game is solved to obtain the Nash equilibrium solution to complete the hunting task.

Collaborative hunting method based on probability analysis

The probabilistic analysis method uses information space and Bayesian theory to deal with the “chasing game” problem. The MUSV relied on the data of various sensors to infer the position of the escapee and the obstacle according to the Bayesian rule. Based on this estimate, Vidal et al. ⁹² proposed two greedy hunting strategies. Among them, the local maximum strategy means that the pursuer moves to the adjacent state with the greatest probability of capturing the escape. The global maximum strategy refers to the state where the pursuer moves to the vicinity of the entire state space with the greatest probability of capturing the escape. Zhong et al. ⁹³ proposed a Markov chain target motion prediction model, which is based on the search information graph to predict the next move of the target. Finally, on the basis of distributed model predictive control, a greedy iterative decision-making method is used to select the best decision-making plan. It effectively reduces the amount of communication and calculation.

Multi-agent reinforcement learning methods

Multi-agent learning is a key technique in distributed artificial intelligence. Multi-agent learning aims to achieve goals when most agents work together, while preventing self-interested agents from disrupting the rest of the global task. Scientists have been working on extending reinforcement learning (RL) to MASs to identify appropriate behavior in complex systems. Markov games ⁹⁴ have been widely recognized as the prevalent model of multi-agent reinforcement learning (MARL). MARL is the learning technique of multiple agents trying to maximize their expected total discounted reward while coexisting within a Markov game environment whose underlying transition and reward models are usually unknown or noisy. ⁹⁵ In recent years, researchers have applied RL to the collaboration of multiple unmanned devices. Zhu et al. ⁹⁶ proposed a novel swarm deep reinforcement learning (DRL), which is a decentralized, autonomous federated DRL approach based on blockchain to achieve collaborative control of multiple robots of the same type. Wei et al. ⁹⁷ designed a reward and punishment function according to the search efficiency function, used the RL method to generate online multi-UAV collaborative search paths, and proposed a multi-UAV search method using a reinforcement learning scheme in an unknown environment. Hu et al. ⁹⁸ proposed a novel multi-mobile robot collaborative exploration strategy based on DRL, which can reduce the overall task completion time and energy cost compared to traditional methods.

At present, the research on cooperative hunting of multi-smart targets is still in the theoretical stage, and the simulation environment of researchers is relatively ideal. First of all, the current research lacks consideration of wind, waves, currents, and sudden environmental factors. Second, the agents used in the simulation are based on the visual range of sensors when performing search and round-up tasks and need to transmit airborne sensor data in real time. Therefore, as the number of robots or evaders increases, cooperation becomes difficult, and algorithms become complicated. Finally, current round-up algorithms mostly target simple targets. However, in reality, we need to face smart targets that have the ability to evade and pursue, and we need to study and pursue targets with high intelligence.

Application of MUSV collaborative search and hunting

Military applications

MUSV collaborative search and round-up technology can be applied to tasks such as mine clearance, anti-submarine, information operations, reconnaissance and surveillance, target indication, communication relay, and counter-terrorism attacks. Its combat styles mainly include as follows.

Anti-mine warfare. MUSV can be used for mine reconnaissance and mine clearance operations in shallow and very shallow waters. The tasks performed include remote launching, towing, and recovery of mine hunting sonar, checking the waterway and providing details of the seabed image, and transmitting video images and sonar data to the mine anti-mine ship to provide port escorts for the anti-mine ship entering and exiting the port.

Anti-submarine warfare. MUSV can be used to expand the navy’s ability to detect enemy submarines and can perform maritime defense, channel protection, port reconnaissance, and anti-submarine missions to protect the navy’s surface battle groups.

Support maritime information operations. MUSV can carry different functional loads and reach the enemy’s information platform. They can perform combat tasks, such as electronic interference, communication relay, electronic deception, and maritime anti-radiation attacks in dangerous sea areas.

Support surface warship operations. MUSV can be used to provide protection for naval vessels and perform tasks, such as maritime blockade/arrest, suspicious target strikes, special operations, logistics support and supplies, battlefield assessment, and evidence collection.

The U.S. Navy conducted Control Architecture for Robotic Autonomous Command and Sensing (CARCaS) ⁹⁹ technology demonstrations in 2014 and 2016. As shown in Figure 14, the 2016 demonstration successfully enabled the USV cluster to coordinate and autonomously implement patrol tasks. The task execution process is only monitored by remote personnel, without direct personnel control. In the 2014 demonstration, all MUSVs were preset with the same procedure, but due to a lack of coordinated planning, the behavior of USV was congested. Experiments in 2016 showed that CARCaS has added new capabilities, such as coordinated task assignment, more behaviors and tactics, and automatic ship identification. The USV cluster can make plans and divide tasks. The behavior engine enables programmers to create a library of complex behavior patterns, making it easier to update the behavior of the CARCaS software. Redding et al. ¹⁰⁰ proposed an efficient Collaborative Mission Planning, Autonomy and Control Technology (CoMPACT) for multiple unmanned surface vehicles. CoMPACT is based on finite-state machine-based task execution, which enables efficient conflict resolution, dynamic task/task re-planning, and efficient vehicle-to-target assignment. CoMPACT enables autonomous collaboration, coordination, and control and is characterized by a multifunctional system architecture suitable for different collaborative decision-making methods. The application of MUSV in cooperative search and hunting is becoming more and more reliable.

Figure 14.

Performing MUSV collaborative tasks. ⁹⁹ MUSV: multiple unmanned surface vessels.

Civilian applications

The civilian applications of MUSV collaborative search and hunting are mainly embodied in frontier patrols, resource exploration, sea fishing, and the search for fugitives. A single USV can complete the search task well when the search area is relatively small, but when the search area is large, due to the limited execution efficiency of the single USV, the search task cannot be completed in time. If the target is moving, it is likely to make the target escape the search area and fail to complete the search task. The MUSV system can cooperatively search a larger area, and the MUSV cooperative search can reduce the chance of target escape. When the target location is uncertain, the MUSV system can also complete the search task well. In addition, the MUSV system has higher fault tolerance than a single USV and has higher robustness. When one or more USVs fail, the MUSV system can redistribute tasks according to the actual situation. It can adjust the formation in real time to continue the search task. As shown in Figure 15, Ocean infinite used the USV C-Worker8 ¹⁰¹ as a surface communication node and an underwater navigation and positioning support system to search for the Malaysian Airlines MH370 wreckage. It collaborates with the AUV network equipped with acoustic detection. MUSV has important applications in the civilian field. It will play an important role in the security of ports and islands, and the protection of life and property of offshore operating platforms.

Figure 15.

Collaborative search for MH370. ¹⁰¹

Conclusion

This article mainly summarizes the research methods of MUSV collaborative search and hunting. Three main architectures of MUSV have been studied, namely centralized structure, decentralized structure, and hybrid structure. Two communication methods of MUSV are introduced, which are explicit communication and implicit communication. It also reviewed and summarized MUSV’s environmental modeling, cooperation mechanism, path planning, and other technical methods. The important methods of round-up algorithms were studied, such as method based on game theory and method based on probability analysis. Finally, the application of MUSV cooperative search and hunting in military and civilian aspects is analyzed. The important conclusions are briefly summarized as follows:

The current research is relatively simple and lacks systematic research on MUSV collaborative search and hunting in unknown dynamic environments.

It is necessary to consider the overall impact of the maneuverability of a single USV on the MUSV, the real-time communication of the long-distance USV, and the influence of wind, waves, currents, and other practical factors.

It is recommended to adopt a distributed architecture in the MUSV searching stage and a centralized architecture in the MUSV round-up stage. The MUSV collaborative search and hunting algorithm is very complicated, and the advantages of various architectures and search algorithms can be concentrated to realize the function of MUSV search and hunting.

In the path planning of the large-scale complex dynamic environment, SI algorithm has great advantages over traditional algorithms, but there is a problem of local extremum. The heuristic algorithms combined with traditional algorithms or multiple heuristic algorithms combined together can be considered. By learning from each other, it will improve the feasibility and practicality of the MUSV collaborative search and hunting algorithm.

In summary, the research of MUSV can enable USV to deal with complex marine environments. For many tasks that cannot be completed by a single USV, MUSV can be used to complete, which greatly improves the mission types and operating radius of USV. The research on the MUSV search problem makes the USV more intelligent. The MUSV system can complete the search task autonomously without the participation of personnel. MUSV collaborative search and swarm hunting have strong environmental information perception and detection capabilities, higher execution efficiency, higher completion efficiency, and higher self-adaptability. In particular, it will be widely used in the safety of islands and ocean platforms, and the protection of marine life and property.