1. Introduction
USVs can be deployed in hazardous situations to perform specialized tasks, thereby minimizing potential casualties. They can also be utilized for monotonous and repetitive tasks, effectively reducing the workload on humans. In extreme marine environments, the capabilities of a single USV may not be sufficient. Therefore, it becomes necessary to integrate multiple USVs into a cluster, to tackle complex tasks through information integration. A cluster of USVs have stronger perception ability, larger operating range, and stronger risk resistance compared to a single USV [
1]. Multiple USVs can be effectively deployed in complex and hazardous water areas where manned vessels cannot be dispatched or where individual USVs may not be able to complete tasks. These areas could include high-risk environments or areas contaminated by nuclear, biological, or chemical agents [
2]. Multiple-USV collaborative formation operations are capable of performing a wide range of tasks, including coastal patrols and maritime rescue, without endangering the safety of naval personnel.
A cluster of USVs can be regarded as a multi-agent system, which refers to a system composed of multiple interacting agents that can jointly complete certain tasks [
3]. In a multiple-USV system, each USV has a certain range of perception ability and can independently perform relatively simple tasks. When faced with complex tasks, they need to collaborate in order to complete the task. This collaboration typically requires information sharing and task allocation. For example, in a USV formation collision avoidance mission, each USV in the formation provides information support for optimized path planning and formation maintenance by sharing their respective perceived information. Usually, the information will be gathered by the USV designated as the leader. The leader makes collision avoidance decisions and updates the formation based on global information, and sends these decisions and formation information to the members of the formation [
4,
5,
6].
In multi-agent systems, the collaborative formation is a fundamental issue as it plays a decisive role in efficiently executing specific tasks [
7,
8,
9]. Formation collision avoidance aims to guide a group of USVs to form specific geometric configurations and control the motion of the formation. In the past few decades, collaborative formation research has mainly focused on unmanned aerial vehicles and intelligent robots, with relatively few studies on collaborative formation of USVs. With the expansion of the application range of USVs, research on the collaboration of multiple USVs has received much attention. Researchers have gradually deepened their research on formation control, continuously improving the performance of formation control algorithms, making multiple-USV formations suitable for various marine environments. The main problems for collaboration among multiple USVs include collaborative collision avoidance, formation, intersection, etc. [
10]. Basic formation control approaches include behavior-based methods, virtual structure methods, artificial potential field methods, graph theory methods, and leader–follower methods [
11].
The complex and dynamic marine environment, along with the presence of moving obstacles, presents significant challenges in designing formation control strategies. Factors such as the interference of wind, waves, and water flow, particularly the resistance of water, further complicate the problem. Many scholars have considered the effects of these interferences in the research of multiple-USV collaborative formations [
12]. With the development of artificial intelligence, biomimetic optimization algorithms and artificial intelligence methods based on learning and gaming have made significant progress [
4,
13,
14,
15]. As a type of ship, USVs must comply with maritime traffic regulations in practical applications. The Convention on International Regulations for Preventing Collisions at Sea (COLREGs) stipulates the navigation rules that all ships must comply with at sea to prevent collisions. To expand the application range of USVs, scholars have introduced COLREGs into the research of USV technology. Kim [
16] proposed a distributed local search algorithm to achieve multiple-ship formations and a distributed random search algorithm to reduce the amount of information transmission among multiple ships, thereby adjusting the formation faster. Ma [
17] proposed quantitative standards for a wide range of complex collision avoidance situations involving a large number of USVs under COLREGs.
While researchers have conducted extensive research about USV formations and obtained promising results, the pursuit of simple and effective methods has always been a primary goal. Given the challenges of obstacle avoidance and formation maintenance, this paper uses an artificial potential field for collision avoidance and the virtual structure method for formation maintenance. The formation control adopts the leader–follower method. The leader independently avoids collisions based on the artificial potential field, using the position of the target as attractor, and generates the ideal position of each follower in the formation based on its own position, heading angle, and the formation structure. The follower selects the position of the target or its ideal position as the attractor during movement based on whether it is being repelled by obstacles or not. In order to quickly leave the obstacle area, this paper modified the attractive force model of the traditional artificial potential field (APF). This includes a limitation on the maximum value of the attractive force when it is influenced by the repulsive force, limiting the maximum value of the attractive force when subjected to the repulsive force. Taking into account the dynamic characteristics of USVs, this paper limits the maximum linear speed and maximum angular speed of USVs. For maintaining the stability of the formation, the leader moves at a constant speed, and the linear speed of the follower varies during the movement process, which may be greater than the speed of the leader, but must be smaller than the maximum linear speed.
The rest of this article is organized as follows: the APF method is described in
Section 2; The formation control methods are described in
Section 3;
Section 4 presents the USV formation control and obstacle avoidance method; The simulation results and analysis are presented in
Section 5; and
Section 6 contains the conclusion.
2. Artificial Potential Filed
The APF method for path planning is a virtual force method proposed by Khatib [
18]. The basic idea is to design the motion of a robot in its surrounding environment as an abstract artificial potential field. The target point generates “gravity” or “attractive force” on the mobile robot, and obstacles generate “repulsive force” on the mobile robot. Finally, the motion of the mobile robot is controlled by finding the resultant force. The path planned using an APF is generally relatively smooth and safe.
The goal point in the environment produces a gravitational potential field, guiding the USV toward it. Each obstacle in the environment produces a repulsive field, which in turn exerts a repulsive force on the USV, pushing the USV away from the obstacle. All the attractive forces produced by the goal and the repulsive forces produced by the obstacles generate a combined force, whose direction is the moving direction of the USV. A diagram of force analysis for an APF is depicted in
Figure 1.
is the attractive force generated by the goal,
is the repulsive force generated by the obstacle, and
F is the combined force.
The potential function of the goal can be represented through
where
is the potential field at the position
, the goal is at the position
,
is the attractive gain, and
is the shortest distance between
and
.
As the USV approaches the goal position, the potential field intensity generated by Equation (
1) decreases, and the field intensity becomes 0 when it reaches the goal position. The potential fields generated with two different attractive gains are shown in
Figure 2.
The force
generated by the goal potential field is the gradient of Equation (
1),
where
is a vector whose direction is from
to
, ∇ is the gradient operator. The variation in the magnitude of
with the distance
d between the goal and the USV is illustrated in
Figure 3. From Equation (
2) and
Figure 3, it can be observed that the force has a linear relationship with the distance when the potential field function is described using Equation (
2).
The potential function of the obstacle can be represented through
where
is the potential field of the USV at the position
, the obstacle is at the position
,
limits the influence range of the potential field, and
is the repulsive gain. As the USV approaches the obstacle, the field intensity generated by Equation (
3) increases rapidly.
The intensity approaches infinity when
approaches 0. When
, the field intensity is 0. The potential fields generated by the two different repulsive gains and
m are shown in
Figure 4.
From
Figure 4, it can be observed that the potential field of the obstacle decays rapidly with increasing distance, and the repulsive gains only affect the intensity of the repulsive field within a very close range of the obstacle.
The repulsive force
generated by the obstacle is the gradient of Equation (
3),
where
is a vector whose direction is from
to
. The variation in the magnitude of
with the distance
d between the obstacle and the USV is depicted in
Figure 5.
When the potential field is generated by one goal and multiple obstacles, the combined force
received by the USV is
where
M is the number of obstacles in the potential field. The direction
is the moving direction of the USV.
3. Formation Control Method
3.1. Behavior-Based Method
The behavior-based method controls the behavior of the entire formation by weighting the expected behaviors, including avoiding obstacles, maintaining the desired formation, and reaching the target point. In reality, for an USV fleet in formation, it is often necessary to simultaneously achieve multiple control objectives, such as formation maintenance and target search.Formation maintenance means that the USV fleet maintains a certain relative positional relationship when the USV fleet is moving. Target search means that the members of the formation search for the target area through the collaborative movement of the members and find the target object or location. These two control objectives have different impacts on the behavior of the formation members, so the behavior of the formation needs be adjusted accordingly. The behavior-based method compromises multiple control objectives and weights each control behavior to enable the formation members to coordinate and complete various tasks [
19,
20].
3.2. Virtual Structure Method
The virtual structure method utilizes the position and attitude information of each target point to form the formation. These target points usually correspond to the points on a rigid body. Compared to other formation methods, the control concept of this method is easier to understand and more convenient to implement. However, centralized control is required and the flexibility of the formation is insufficient, which also poses significant problems in obstacle avoidance [
21,
22].
3.3. Graph Theory Method
The graph theory method uses a control graph to define the shape of USV formations, where each node represents an USV and the directed edges between nodes represent the relative relationship between two USVs. The distributed nature of graph theory determines that it can be used for large-scale USV formations, making it easy to handle the addition or deletion of USV nodes in occasional queues. Using graph theory to describe the formation and the relationship between USVs, facilitating the main exchange between different formations. One disadvantage is that it is mainly limited to simulation research, and the implementation is relatively complex [
23,
24].
3.4. Leader–Follower Method
The basic idea of the leader–follower method is that, in a group composed of multiple USVs, one USV is designated as the leader and the other USVs are its followers. The followers follow the position and orientation of the leader USV at a certain distance interval. This method can also be extended on the basis of the above description, which can, not only specify one leader, but also specify multiple leaders. However, in the control of group formation, the leader is often designated as one. According to the relative positional relationship between leaders and followers, different network topologies can be formed, which means forming different formations. In a system that employs this method to control the formation of USVs, collaboration is achieved by sharing knowledge such as the state of the leader. The advantage of the leader–follower method is that simply giving the leader’s behavior or trajectory can control the behavior of the entire USV population. The main drawback is that there is no clear formation feedback in the system. For example, if the USV leader advances too quickly, the following USV may not be able to track in time. Another drawback is that if the leader fails, the entire formation cannot be maintained [
24,
25,
26,
27,
28].
4. USV Formation Control and Obstacle Avoidance Method
In this paper, we utilize a leader–follower and virtual structure method for formation control, and use an APF for obstacle avoidance. For simplicity, we simplify the dynamic description of the USVs by limiting the maximum linear speed and maximum angular speed. The leader is moving at a constant speed. To address the issue of limited flexibility in maintaining formation using virtual structure methods and to enhance the stability of the formation, the linear speed of the follower can be adjusted based on the distance between the follower and the object being tracked, which may be greater than the speed of the leader but must be smaller than the maximum linear speed.
The USV leader is influenced by the attractive force generated by the task target, as well as the repulsive force generated by all obstacles in the environment and other USVs in the fleet. The USV leader calculates its position and the heading angle in the next moment based on the combined direction of the attractive and repulsive force, combined with the linear speed and maximum angular speed constraints of the formation movement.
After determining the position and the heading angle of the leader in the next moment, the leader uses the virtual structure method to calculate the ideal position of each follower based on the position and the heading angle of the leader itself. The followers are attracted by the forces generated by their respective ideal positions or the target position, depending on whether they are repelled by obstacles or not, as well as the repulsive forces generated by all obstacles and the other USVs in the environment. The followers are guided by the direction of the combined forces generated by the attractive and repulsive forces. The followers calculate their heading angles in the next moment by combining the maximum linear speed and the maximum angular speed constraints during the follower’s movement.
In order to quickly leave the obstacle area, this paper modifies the attractive force model of the traditional APF. We restrict the maximum magnitude of the attractive force when influenced by the repulsive force, to modify the direction of the combined force.
There are three points to note: first, the speed of the USV formation is the same as the speed of the leader, but the speed of the follower can be greater than the formation speed to meet the needs of maintaining the formation; second, the follower may be pulled by the target position or the ideal position, depending on whether they are repelled by obstacles or not; third, when a USV is subject to a repulsive force, the magnitude of its attractive force is restricted by that of the repulsive force. This restriction can impact the heading angle of the USV.
Below, we elaborate on the principles of the method proposed in this article.
4.1. Formation Representation
This article uses the body coordinate system of the leader to represent the formation. The heading direction of the leader is taken as the positive direction of the x-axis, and the y-axis coordinate direction of the leader is determined using the right hand rule. The origin O of the coordinate system can be specified as needed.
We represent the position of the follower
i in the formation with
.
is the azimuth in the leader body coordinate system, and
is the distance between the follow
i and the origin, as shown in
Figure 6. The coordinate
of the follower
i in the leader body coordinate system can obtained through
When the positions of all followers are specified, the formation of the USVs is determined.
4.2. Obstacle Avoidance and Formation Update
Assume that the USV formation contains N USVs, which consist of 1 leader and followers, and there are M obstacles in the task scenario. We number the USVs, the id represents the USV, and the id of the leader is 0. We also number the obstacles, the id represents the obstacle. Assume that represents the ideal position of the USV i in the world coordinate system, and represents the actual position of the USV i in the world coordinate system, and represents the position of the obstacle j in the world coordinate system.
4.2.1. The Unit Vector of the Combined Force on the Leader
The repulsive force on the leader is
In order to quickly leave the obstacle area, we limit the maximum of the attractive force when subjected to the repulsive force to modify the direction of the combined force. We adjust the magnitude of the attractive force using
where
is the weighting coefficient that can modify the direction of the combined force.
Now, we can calculate the unit vector of the combined force on the leader. From Equation (5), the combined force on the leader is
Thus, the unit vector of
is
4.2.2. The Next Moment Position and the Heading Angle of the Leader
Assume that
represents the heading angle of the USV formation, which is also the heading angle of the leader. Assume that
is the maximum angular speed of the USV. The next moment heading angle
of the leader can be obtained through
where
represents the real part, and
represents the imaginary part.
The heading angle difference
between two consecutive moments is
Update the heading angle
using the maximum angular speed
of the USV,
not only represents the ideal position of the leader but also the actual position of the next moment of the leader. In other words,
. Assume that the linear speed of the USV formation is
, which is a scalar.
can be obtained using the heading angles
and
,
4.2.3. The Ideal Position of the Follower
Now the ideal formation position of the follower can be updated based on the position and the heading angle of the leader using the virtual structure.
The ideal position
of the follower
i can be obtained using
The relationships among the formation representation
in the leader body coordinate system and the leader position
and the follower position
are shown in
Figure 7.
4.2.4. The Unit Vector of the Combined Force on the Follower
The repulsive force on the follower
i is
We adjust the magnitude of the attractive force for the follower
i through
where
is the position
of the target or the ideal position
of the follower
i based on whether it is repelled by obstacles or not.
Now, we can calculate the unit vector of the combined force on the follower. From Equation (5), we can obtain the combined force on the follower
i. If the follower is repelled by some obstacles, the combined force is
Thus, the unit vector of
is
4.2.5. The Next Moment Position and the Heading Angle of the Follower
Assume that
represents the heading angle of the follower
i at the moment. The next moment heading angle
of the follower
i can be obtained through
The heading angle difference
between two consecutive moments is
Update the heading angle
using the maximum angular speed of the USV,
When the heading angle of the USV formation changes significantly, this has a significant impact on the position changes of the follower at the edge of the formation. For the stability of the formation, we allow the follower’s linear speed to be greater than the formation speed.
The distance
between the follower
i and the traction object is
or
depending on whether the follower is repelled by obstacles or not.
Assume that the maximum linear speed of the USV follower is
, which is a scalar. We adjust the follower’s speed
based on
,
can be obtained using the heading direction angle
,
4.3. Algorithm
The formation control and obstacle avoidance algorithm is summarized in Algorithm 1.
Algorithm 1: Formation Control and Obstacle Avoidance Algorithm |
|
5. Simulation Studies
For the sake of simplicity, we assume that USVs have the formation shown in
Figure 8. The USV fleet consists of 6 USVs, with an equilateral triangle formation and three USVs evenly spaced on each edge.
The id of each USV is shown in
Figure 8. The width of each USV is 0.8 m, and their length is 1.0 m. The formation parameters are shown in
Table 1.
Table 2 shows the performance parameters of the USVs.
5.1. Experiment without Obstacles
We first verified the formation maintenance effects of the algorithm when there is no obstacle.
In
Figure 9, the black solid circle represents the starting position of the formation, the red solid circle represents the target position, the circle with numbers indicates the ideal position of the USV, and the solid triangle stands for the actual position of the USV.
Figure 9b–d depicts the formations of USVs after 20, 40, and 80 iterations. From the figures, it can be observed that the USV formation reached stability after a brief adjustment.
5.2. Experiment with Obstacles
The parameters used in the APF approach in this simulation are shown in
Table 3. The formation parameters are depicted in
Table 1. The performance parameters of the USV are shown
Table 2. The positions and radius of the obstacles are shown
Table 4.
In
Figure 10, the black solid circle represents the starting position of the formation, the red solid circle indicates the target position, the circle with numbers stands for the ideal position of the USV, the solid triangle depicts the actual position of the USV, the blue solid circle represents the obstacle, and the dashed circle means the limit distance of the obstacle.
Figure 10b–f show the formations of the USVs after 150, 280, 350, 450, and 613 iterations.
Figure 10f shows the final state of the USV formation after reaching its goal position. From the figures, it can be observed that the USV formation could effectively avoid obstacles and endeavored to maintain the stability of the formation during the movement.
The variation in the linear speed of the USVs over time is depicted in
Figure 11. The leader moved at a constant linear speed, and the speed was 0 when it reached the target position. The linear speeds of follower 1, follower 2, and follower 5 exhibited rapid changes during specific time intervals when the USVs were maneuvering to avoid obstacles. The follower 4 encountered almost no obstacles throughout the entire process, so the time interval for rapid speed changes was very short. The time intervals during which the followers moved at their maximum speed corresponded to the adjustment periods of the formation. These can be observed from
Figure 10.
In order to enhance the stability of the formation, this study allowed the maximum linear speed
of the followers to exceed the linear speed
of the leader (
is also the linear speed of the formation), and the linear speed
of the follower
i was adjusted according to Equation (
25).
Figure 12 shows the variation in positional errors over time when the leader moved at a linear speed 0.1 m/s, the followers moved at the maximum linear speeds of 0.1 m/s (which is equal to
) and 0.2 m/s (which is greater than
), respectively.
As depicted in
Figure 12, when the follower was restricted to moving at the maximum linear speed of the leader, the positional errors of the follower were large during almost the whole movement process. When the leader reached the target position, the followers required a long time to adjust to reach their respective ideal positions. When the linear speed of the follower surpassed that of the leader, the follower reached the ideal position more quickly. So when the formation changed slightly, the followers could be at the ideal positions. Under the constraints of two different maximum linear speeds, the times needed for the USV fleet to reach the target position and form a stable formation were not the same. Moreover, as evidenced by
Figure 12; when the linear speed of the follower exceeded that of the leader, the time required was significantly reduced.
6. Conclusions
In order to seek a simple and effective method to address the challenges of formation control and obstacle avoidance for multiple USVs, this study proposed a method that combines the artificial potential field method, virtual structure method, and leader–follower method. The artificial potential field method is used to tackle the obstacle avoidance problem for USVs, while the virtual structure method is utilized to generate the ideal position of the follower within the formation. The leader–follower method is employed to maintain the formation. The modifications were made to both the artificial potential field approach and the leader–follower scheme. To ensure the combined force deviates from obstacles and swiftly moves away from the obstacle area, the attractive force is constrained so as not to exceed the repulsive force when encountering obstacles. For effectively avoiding obstacles and maintaining formation, the followers select the target’s position or their ideal position as the reference point based on whether they are repelled by obstacles or not. Additionally, followers can adjust their linear speed depending on their distance from the reference point, without exceeding their maximum speed, to better maintain the formation. Simulation experiments showed that this method could effectively avoid obstacles and maintain the formation. However, further research is needed to address several remaining issues, including incorporating the dynamic model of the USV, considering various types of obstacles, and refining the motion trajectory of the USV to achieve smoother movements.