Path planning method for USVs based on improved DWA and COLREGs
0 Abstract
In the navigation of unmanned surface vehicles (USVs), various types of obstacles may be encountered, which can be categorized into real-time collision avoidance among multiple USVs and obstacle avoidance between USVs and other obstacles. Most existing autonomous obstacle avoidance algorithms do not account for the nonlinear motion characteristics of USVs, often resulting in non-compliance with the International Regulations for Preventing Collisions at Sea (COLREGs) and a tendency to fall into local optima. To address these issues, this paper proposes a path planning algorithm that integrates the dynamic window approach (DWA) considering nonlinear characteristics with COLREGs, making the USV's motion trajectory more applicable to practical engineering scenarios. A kinematic mathematical model is established based on the motion characteristics of USVs, and an evaluation function for the optimal path is constructed using DWA. The fully informed search algorithm (FISA) is employed to select the optimal set of velocities and steering angles from the velocity sampling set, based on different cost calculation methods. The USVs use a laser radar for local obstacle detection, enabling real-time dynamic obstacle avoidance. To address the real-time collision avoidance problem among multiple USVs in open waters, the algorithm filters out COLREGs-compliant avoidance maneuvers during path planning. The correctness and feasibility of the fusion algorithm were verified through comparative simulations. In the simulated environment model, the influence of ocean currents on the USV was introduced, and multiple sets of experiments under different conditions were conducted to compare the motion trajectories, average travel distances, and average travel times of the USV. The simulation results indicate that the USV can perform accurate obstacle avoidance when encountering various types of obstacles. Compared to the traditional DWA algorithm, the proposed approach demonstrates advantages in terms of travel distance and travel time, while still achieving effective obstacle avoidance.
Keywords
1. INTRODUCTION
With the continuous development of intelligent control and path planning technologies, unmanned surface vehicles (USVs) possess characteristics of high maneuverability and autonomy, enabling them to perform autonomous navigation and gradually becoming a crucial component of modern maritime operations [1]. In the complex and variable marine environment, the path planning technology of USVs is particularly critical as it not only relates to the safety and reliability of USVs but also directly affects the efficiency and success rate of task execution. USVs operate in complex environments, and when navigating along a set path, they may encounter ships, buoys, and other potential maritime obstacles [2, 3]. Given the uncertainty in the marine environment, the obstacle avoidance system of a USV must be highly adaptable. Path planning is an essential component of USV obstacle avoidance technology, which can be divided into global and local path planning. Global path planning involves charting a feasible route for the USV based on known environmental information and task objectives [4]. Local path planning, on the other hand, requires the USV to take appropriate actions to adjust speed or direction in real-time effectively when encountering static or dynamic obstacles during navigation, ensuring safe movement to the target location [5, 6]. This paper primarily focuses on the local path planning issues of USVs, especially the dynamic obstacle avoidance problem.
In the field of path planning for USVs, numerous scholars have conducted research. MahmoudZadeh et al. introduce a continuous path planning system that facilitates multi-USV operations for ocean sampling tasks, enabling the handling of multiple objectives while being computationally suitable for real-time implementation [7]. Du et al. propose a safe Lyapunov boundary deep deterministic policy gradient (SLDDPG) algorithm, analyzing the uniform ultimate bounded (UUB) stability of control systems under finite safety constraints. It applies single neuron proportional adaptive control (SNPAC) to the pre-training of deep policy networks to accelerate the training process, exhibiting superior performance in terms of stability and safety [8]. Sun et al. discuss a collision avoidance method across ships based on artificial potential fields and a strategy for ship collision avoidance following the International Regulations for Preventing Collisions at Sea (COLREGs), achieving self-organized coordination among multiple USVs in the presence of dynamic obstacle ships [9]. Chen et al. introduce a local trajectory planning algorithm based on collision hazard assessment, using the analytic hierarchy process and differential methods to determine the collision risk indices for different scenarios and incorporating fuzzy reasoning theory to provide a decision-making basis for avoidance strategies, optimizing the USV routes under unexpected encounters through COLREGs [10]. Wu et al. present an obstacle avoidance strategy based on deep reinforcement learning and the dynamic window approach (DWA), defining the action space for the proximal policy optimization (PPO) algorithm based on descriptions of linear and angular velocities of ship movements within the DWA and improving the PPO's reward function using distance, velocity, and heading evaluation functions in the DWA [11]. Gonzalez-Garcia et al. design an impulse velocity and heading variable motion control strategy based on adaptive sliding mode control, using time-varying look-ahead distance for path following guidance [12]. Zheng et al. propose a new model that utilizes partially observable Markov decision processes (POMDP) to build a decision-making model for autonomous ship collision avoidance under mixed obstacle environments, addressing the complexity and uncertainty of the environment and enhancing decision-making accuracy [13]. These documents provide references for USV path planning research, yet they do not simultaneously consider the real-time collision avoidance issues for multiple USVs nor optimize and improve path planning algorithms to address the nonlinear characteristics specific to USVs.
In response to the issues discussed above, this paper proposes a path planning algorithm that integrates the DWA and the COLREGs, considering the nonlinear characteristics of USVs. Additionally, the influence of ocean currents on the motion of the USV was incorporated into the environmental model. The speed selection within the DWA utilizes the fully informed search algorithm (FISA), which chooses the optimal (minimum cost) operational speeds and steering sets from a velocity sampling set based on different cost calculation methods. This integrated algorithm allows for more flexible obstacle avoidance within the hardware constraints of the USV, avoiding entrapment in local optima and stagnation in complex environments with multiple obstacles. Furthermore, since the motion of the USV may be affected by external factors such as ocean currents, ocean currents were incorporated into the environmental model. This allows the USV to be applicable in a wider range of scenarios. Overall, the proposed integration algorithm seeks optimal paths while ensuring obstacle avoidance for USVs. Compared to existing works, the main contributions of this paper are as follows:
(1) Utilization of the traditional DWA for obstacle avoidance can be risky if the USV approaches obstacles at high speeds, potentially failing to perform avoidance maneuvers in time and causing accidents. This paper adopts the fully informed selection algorithm and evaluation metrics for online speed and angular velocity selection, enabling the USV to choose optimal speeds within its hardware design range and perform flexible steering actions, thus preventing accidents. It also mitigates the risk of the DWA falling into local optima, alleviating the issue of the USV being unable to escape from complex local environments when facing multiple obstacles.
(2) Traditional DWA-based obstacle avoidance might lead USVs to plan trajectories that contravene the COLREGs, potentially interfering with the normal operation of other USVs and causing accidents. This paper's algorithm considers the COLREGs during obstacle avoidance, making the navigation of USVs safer.
(3) The traditional DWA is typically applied to ground mobile robots, but it has not been optimized for the unique motion characteristics of USVs. In this paper, the DWA was optimized based on the motion characteristics and control methods of USVs. Additionally, during environmental modeling, the potential impact of water currents on the USV was considered, leading to the incorporation of ocean currents in the environment.
The remainder of this paper is organized as follows. Section 2 addresses the kinematic mathematical modeling of USVs and introduces maritime collision avoidance regulations. Section 3 describes the principles of the fully informed selection algorithm and the DWA, and discusses improvements and integration of the algorithms. Section 4 presents simulation experiments of the integrated algorithm and provides a comparative analysis of the results. Finally, Section 5 summarizes our work.
2. KINEMATIC MODEL AND COLLISION AVOIDANCE RULES
2.1. Kinematic model of USVs
Figure 1 presents a two-dimensional motion model for local path planning of USVs. For the responsive model, the heading is usually defined as the angle between the USV's heading (longitudinal axis direction) and the Earth's true north direction, with a value range of 0° 360°, 0° when it coincides with the true north direction, and increases in a clockwise direction. In the navigation coordinate system a, north (N) is the x-axis and east (E) is the y-axis. P is the position of the USV in the navigation coordinate system, represented by the coordinates of its center of gravity, and is also the origin of the hull coordinate system b. The hull coordinate system b takes the heading of the USV as the x-axis and the starboard direction of the USV as the y-axis. The motion of USVs is described using six degrees of freedom: surge, sway, yaw, heave, roll, and pitch [14]. To reduce the complexity of motion control for USVs, it is often sufficient to focus on the movements within the horizontal plane, which includes only the degrees of freedom for surge, sway, and yaw. This paper primarily investigates the motion of USVs on a two-dimensional horizontal plane, disregarding the forces of disturbance caused by environmental factors such as wind and ocean currents. Consequently, the relationships for the transformation of velocity vectors between the navigation coordinate system a and the body coordinate system b, as well as the USV's three-degree-of-freedom control model, are given as [15–18]:
Figure 1. Two-dimensional motion diagram for local path planning of USV. USV: Unmanned surface vehicle.
where
The dynamic model of the USV is established as follows[19]:
where
Here,
Remark 1 It should be pointed out that there are only two control inputs
Remark 2 In engineering applications, the USV platform is often designed to be underactuated since the installation of the lateral thruster is not only costly, but also impairs hull hydrodynamic performance in high-speed scenarios. In general, most surface vessels are only equipped with propellers and rudders for surge and yaw motion. This means the contribution of this work will be meaningful for practice.
Remark 3 The vessels' hydrodynamic damping
2.2. 2-D Ocean current environment model
Due to the rapid rotation of the Earth, the horizontal scale of ocean currents is significantly larger than the vertical scale of movement. Therefore, ocean currents can be considered as motion across multiple layers of two-dimensional horizontal planes. In this paper, the numerical equations for the ocean current model are represented by the superposition of two viscous Lamb vortices. The mathematical description is given as[21]:
where
2.3. Constraints of COLREGs
The COLREGs are traffic rules established by the International Maritime Organization to prevent collisions between vessels at sea. COLREGs delineate three types of encounters: head-on, cross, and overtaking. Specifically, the cross encounter includes two scenarios: crossing from the left (cross-left) and crossing from the right (cross-right). The regional division method adopted by COLREGs in this paper is illustrated in Figure 2. Article 8 of the COLREGs outlines the fundamental principles for collision avoidance during the design of local path planning, which should adhere to the following principles: Actions should be taken as early as possible; substantial evasive actions should be taken to ensure they are observable by visual or radar means and to ensure passing at a safe distance; when sufficient space is available, steering alone should be used, as it is the most effective means of avoiding a close-quarters situation and during evasion, avoiding a series of minor changes to speed or direction; continuous monitoring of the effectiveness of the collision avoidance actions should be maintained until the other vessel has past and is clear [22–24].
Figure 2. Regional division method of COLREGs. COLREGs: International Regulations for Preventing Collisions at Sea.
Articles 13, 14, and 15 of the COLREGs specify the judgment methods and action rules for vessels in overtaking, head-on, and cross-encounter situations [25, 26], classifying the USV either as a give-way or stand-on vessel depending on the situation. Detailed action rules for the USV are as follows:
(1) Overtaking: When a USV is navigating behind a moving vessel within an angle range of [112.5°, 247.5°), and the USV is faster, it should take action to avoid the vessel by turning left or right.
(2) Head-on: A head-on encounter refers to two vessels sailing in opposite or nearly opposite directions, with the moving vessel within the bearing range of [0°, 10°) or [355°, 360°) from the USV. The USV should turn right, the oncoming vessel should turn left, and the USV should pass as far away as possible from the left side of the moving vessel.
(3) Cross-left: This encounter refers to a moving vessel being within the bearing range of [247.5°, 350°) from the USV. The USV is not the give-way vessel, so it should maintain its course.
(4) Cross-right: This type refers to a moving vessel within the bearing range of [10°, 112.5°) from the USV. The USV should turn right and navigate behind the moving vessel as much as possible, avoiding crossing in front of the other vessel.
The correct evasive routes for these four encounter scenarios are shown as dashed lines in Figure 3. The local path planning algorithm should also comply with these action rules.
Figure 3. Avoidance methods for the USV. USV: Unmanned surface vehicle.
3. IMPROVED ALGORITHM
Given the often open and complex environment in which USVs operate, not only must planning account for obstacles marked on maps, but it must also dynamically evade obstacles detected by sensors onboard the USV. Local path planning is well-suited to address this issue.
The DWA is a local planning method based on velocity sampling that enables smooth path planning and local obstacle avoidance. The core idea of DWA is to determine trajectories within a specified timeframe in the velocity space, based on the current position and velocity states of the mobile robot. These trajectories are then evaluated using a cost function, and the trajectory with the optimal evaluation is selected as the motion path for the robot. The algorithm process starts by initializing the robot's velocity, acceleration, and evaluation functions, then calculates the current velocity range, computes the predicted states at different velocities, and evaluates these states using the cost function. The cost function values are normalized, the optimal value is selected as the solution, and the robot's state is updated accordingly. This cycle continues until the robot reaches its destination [27–29]. The improved algorithm introduces FISA to pre-filter feasible paths before evaluating them with the DWA cost function, thereby generating a set of candidate paths. To enhance the USV's movement speed and reduce the travel path length, the cost function of FISA is designed to minimize changes in angular velocity while maximizing the allowable speed. Since FISA randomly generates a value in each feasible interval, the effect of this randomness is minimized through repeated iterative calculations. Compared to the traditional DWA, the selected speed set has the advantages of higher speed and shorter travel distance, while also reducing the risk of getting stuck in local optima, which is a common issue for DWA. The flowchart of the algorithm is shown in Figure 4.
Figure 4. Flowchart of fusion method.
3.1. Velocity search space
The velocity search space is a two-dimensional space of speeds derived from the constraints specific to the USV and the operational environment. The purpose of this search space is to identify the optimal movement strategy for the USV to avoid obstacles, achieve path planning, and complete tasks within the current environment. The limiting factors can be categorized into three types: intrinsic speed limits of the USV, acceleration limits, and obstacle constraints [30, 31].
Intrinsic speed limits of the USV refer to the physically feasible range of speeds for the USV, including limitations on linear and angular velocities. These limits are determined by factors such as the power structure and physical design of USVs. The intrinsic speed limits of the USV are given as
where
where
Based on the current motion state of the USV and its acceleration, the range of velocity values
The schematic diagram of velocity values is given as Figure 5.
Figure 5. The schematic diagram of velocity values.
The process of velocity search and generation of potential trajectory sets is one of the most critical processes in DWA. Only after determining the set of velocities can trajectory sets be generated and evaluated using an evaluation function, with the optimal trajectory ultimately being selected. In this algorithm, FISA is employed for velocity search within the velocity search space. Compared to traditional search methods, the use of FISA has refined the velocity search mechanism of DWA. The improved algorithm significantly reduces the likelihood of DWA getting trapped in local optima, thus alleviating issues where the USV is unable to navigate out of complex environments with multiple obstacles.
The FISA is an intelligent optimization algorithm that operates on the principle of random interactions between the best and worst solutions obtained during the optimization process, as well as among candidate solutions. It requires only common control parameters such as population size and the number of iterations, without needing any algorithm-specific control parameters. FISA relies on a difference vector obtained by subtracting the position of the worst individual from the best individual in the current iteration. This ensures that the set of solutions always progresses towards better outcomes. Compared to traditional optimization algorithms, FISA improves the optimization of the shift function while maintaining the simplicity and lack of control parameters characteristic of traditional algorithms, pushing the dataset towards superior solutions [33]. The flowchart of FISA is shown in the Figure 6, and the process is given as
Figure 6. Flowchart of FISA. FISA:
Where
In fact, in FISA, each member moves away from the average position of individuals with poorer fitness within the population and closer to the average position of individuals with better fitness than the respective member. Then, Equation (10) is used to update the position of each member. In Equation (9), the values of
where
In the application of this integrated algorithm, the current motion state's linear and angular velocity limits of the USV are input into FISA. By continuously iterating the values of
3.2. Obstacle constraints
Local planning necessitates dynamic and real-time obstacle avoidance capabilities. For the safety of USVs, it is essential to ensure that the vessel does not collide with any obstacles. The USV must maintain a sufficient distance at any given moment to allow for stopping under maximum deceleration [34]. The constraint that the USV does not collide with surrounding obstacles at any moment is given as
where
Traditional DWA uses the above methods to restrict velocities, preventing collisions between mobile robots and obstacles. However, when applying DWA for obstacle avoidance in USVs, the USV itself is also considered an obstacle, necessitating improvements to obstacle constraints. The COLREGs prescribe the division of responsibilities and avoidance strategies when two vessels meet, and based on COLREGs, priorities among multiple USVs are assigned and specific avoidance strategies are designated [35].
When assessing the motion states of other USVs, given that USVs are typically smaller and often operate in relatively open and calm waters, this paper determines the priorities and establishes avoidance strategies based on the distance and coordinate relationships between USVs. Additionally, when multiple USVs are operating together, the relationships between them are continuously changing. Therefore, it is crucial to determine whether a previous avoidance action has ended in order to improve the smoothness of the travel trajectory.
In response to multiple USVs encountering each other, this paper draws from the COLREGs to establish the following strategies for division of responsibilities when two vessels meet. The specific rules are as follows:
(1) Head-On: The vessel on the starboard (right) side generally has the right of way, while the vessel on the port (left) side should take evasive action. Head-on encounters are divided into two scenarios: USVa traveling from south to north and USVb traveling from north to south: In this case, USVa has the right of way and USVb should yield. USVa traveling from west to east and USVb traveling from east to west: Here, USVa has the right of way and USVb should yield; (2) Overtaking: If USVa is faster than USVb and is behind it with a relative angle of -10° to 10°, USVa needs to overtake USVb from either the left or right side; (3) Crossing Situations follow these rules: Cross-right: If USVa is traveling from south to north and USVb from west to east, USVa has the right of way and USVb should yield. Cross-left: If USVa is traveling from south to north and USVb from east to west, USVb has the right of way and USVa should yield.
When two USVs reach a judgment distance within a predictive range and one USV has a higher priority, its navigation is not affected by the other USV, and the traditional approach can still be used for trajectory selection using the evaluation function. The USV with lower priority needs to take evasive action, thus requiring optimization of the distance evaluation function, as given in
where
If the minimum value of
3.3. Evaluation function
After determining the velocity range constrained by the USV's capabilities, some simulated velocity trajectories may be feasible, while others may not meet the required standards. Therefore, it is necessary to evaluate and select the best trajectories from the multiple sets of sampled trajectories. By evaluating the trajectories using a standard evaluation function and comparing the scores, the optimal trajectory is selected to determine the USV's speed. The trajectory evaluation function is given as
where
where
After sampling a set of
4. SIMULATION RESULTS AND DISCUSSION
Based on the kinematic modeling and path planning algorithm, simulation experiments were conducted on the USV. Table 1 presents the basic parameters of the USV used in the simulations. The simulations in this study focused on simulating the USV's path in open waters, where actual obstacles mainly include other vessels, maritime buoys, and islands. To fully demonstrate the feasibility of the integrated algorithm and avoid any accidental suitability to specific environments, the simulations included obstacles that may be encountered in real-world operational scenarios. These obstacles were simulated by adding both known static obstacles and unknown dynamic obstacles to the map, thereby validating the correctness and feasibility of the path planning algorithm.
Basic parameters for simulated USV
| Parameters | Value |
| Size/mm | 900*630*300 |
| Mass/kg | 7 |
| Draft depth/m | 0.1 |
| Maximum speed/(m/s) | 7 |
| Maximum power per motor/W | 700 |
| Maximum motor speed/rpm | 7, 000 |
During the simulations, the USV was treated as a point mass; however, in real-world operations, the USV has a certain volume. Therefore, an obstacle inflation method was applied to account for the USV's size by expanding the dimensions of the obstacles. The simulations were designed to replicate potential obstacles that the USV might encounter during actual operations, based on its real usage scenarios. The simulations were divided into three cases: Case1: A single USV without any obstacles. Case2: A single USV navigating through multiple static obstacles. Case3: Four USVs navigating through a combination of multiple static obstacles and dynamic obstacles. The evaluation function of the DWA is composed of the weighting factors for heading score, distance score, speed score, and the time for forward trajectory simulation. These parameters were adjusted and fine-tuned through repeated simulation experiments, as the weight of each factor significantly influences the USV's navigation behavior. The parameters for the USV's DWA obstacle avoidance algorithm are shown in Table 2.
Parameters of DWA
| Parameters | Value |
| Radius of dynamic and static obstacles/m | 0.5 |
| Time resolution/s | 0.1 |
| Linear velocity resolution/(m/s) | 0.05 |
| Angular velocity resolution/(rad/s) | 0.5 |
| Proportion of heading score | 0.03 |
| Proportion of distance score | 0.2 |
| Proportion of speed score | 0.1 |
| Trajectory prediction time/s | 3 |
A higher weighting factor for the heading score will cause the USV to prioritize moving in a direction that avoids obstacles. When encountering an obstacle, the USV will preferentially adjust its heading to find a feasible, obstacle-free path. However, this might lead the USV to favor turning maneuvers, making it difficult to maintain a straight trajectory. On the other hand, a lower weighting factor for the heading score will make the USV more committed to its current heading, potentially causing it to maintain its course even when close to an obstacle, which might result in insufficient distance to complete an avoidance maneuver.
A higher weighting factor for the distance score will prompt the USV to maintain a greater distance from obstacles, leading it to choose safer paths. In this case, the USV will start to avoid obstacles while still far away, which is beneficial in narrow environments or situations where collision avoidance is critical. Conversely, a lower weighting factor for the distance score will make the USV more likely to choose paths closer to obstacles. In simulations, using a smaller distance parameter weighting might result in the USV being too close to obstacles, making it difficult to plan an avoidance route.
A higher weighting factor for the speed score will cause the USV to prefer higher speeds, enabling it to traverse the environment more quickly, which is more suitable in relatively safe, open areas. However, in simulation experiments, a higher speed parameter weighting led to the USV's linear speed being too high, preventing it from promptly completing path planning and obstacle avoidance maneuvers due to the structural limitations of the USV. A lower weighting factor for the speed score will make the USV more inclined to select lower speeds, reducing the risk of collisions in complex environments.
Through multiple sets of simulation experiments, it was observed that optimizing the obstacle avoidance algorithm hinges on determining the optimal values for these parameters. This process typically requires experimentation and adjustment, as the effectiveness of the parameters is influenced by the specific environment, USV performance, and mission requirements. In practical applications, this iterative process of experimentation and simulation involves observing the USV's responses in various scenarios, adjusting the parameters to better adapt to different environments, and thereby achieving superior obstacle avoidance performance. This parameter adjustment process is ongoing and iterative, requiring continuous tweaking and optimization based on the USV's actual performance to eventually arrive at the optimal values.
4.1. Case1: static obstacles
In this case, the planned map is a rectangular area of 4 m by 14 m, with multiple static obstacles of 0.3 m radius added to simulate small coral reefs and buoys that a USV might encounter at sea. The environment model also includes the influence of ocean currents on the USV. In this simulation, there is only one USV, with an initial pose of [0, 0, 90] and a target point of [0, 10]. To facilitate comparison of the improved algorithm with the traditional DWA, the same experimental environment was set up and the results were compared. The simulated trajectory indicates that the improved algorithm can avoid obstacles and reach the target point, whereas the traditional DWA falls into a local optimum during obstacle avoidance, colliding with obstacles and failing to reach the target. Furthermore, the improved algorithm generates a shorter and smoother path compared to the traditional DWA. The simulation time is 21.67 s, and the simulated trajectory is shown in Figure 7. Since the traditional DWA algorithm failed to reach the target point in the previous simulation, the positions of the simulated obstacles were changed for another experiment. In this case, the traditional DWA algorithm was able to avoid obstacles and reach the target point, with the simulated trajectory shown in Figure 8. Comparing the trajectories, it can be seen that the path of the traditional DWA algorithm is longer, while the improved algorithm generates a shorter and smoother path, making it easier for real-world trajectory tracking. A comparison of the USV running times during the simulations of the improved and traditional algorithms is shown in Figure 9. Based on 20 simulations, the average running time for the improved algorithm is around 20 s, whereas for the traditional DWA, it is around 35 s, indicating a reduction in running time. The comparison of running distances is shown in Figure 10. When using the improved algorithm, the average running distance for the USV is about 10 m, considering the straight-line distance between the target point and the initial position is 9.5 m (
Figure 7. Simulated trajectories of the USV. USV: Unmanned surface vehicle.
Figure 8. Simulated trajectories of the USV. USV: Unmanned surface vehicle.
Figure 9. Average travel time of the USV. USV: Unmanned surface vehicle.
Figure 10. Average travel distance of the USV. USV: Unmanned surface vehicle.
4.2. Case2: dynamic obstacles
In this case, the planned area is a 140 m by 140 m square region. The map includes two static obstacles and five dynamic obstacles, simulating larger obstacles that the USV might encounter at sea, such as large islands and bridge piers of sea-crossing bridges. The coordinates of the static obstacles are [40, 40] and [60, 60], while the dynamic obstacles start from random positions within the map area and move in random directions. The influence of ocean currents on the USV movement is also included in the environment model. This simulation involves four USVs: USV1, USV2, USV3 and USV4, with initial poses of [0, 0, 90], [100, 0, 90], [80, 100, -90], and [20, 100, -90], respectively, and target points of [100, 100], [0, 100], [20, 0], and [80, 0].
In the first step of the simulation, USV1's movement is normal, adhering to COLREGs and featuring dynamic obstacle avoidance with the improved algorithm. USV2, USV3 and USV4 exhibit abnormal movements, as they use only the traditional obstacle avoidance algorithm, with their simulated trajectories shown in Figure 11. Since only USV1 has the integrated obstacle avoidance functionality, it can reach the target point quickly and safely. At the beginning of the simulation, there is a collision risk between USV1 and USV4, but they use an improved algorithm and the motion rules comply with COLREGs. According to the rule, USV1 has higher priority and will pass in front of USV4. During the simulation, USV3 and USV4 face collision risks, having reached the minimum safe distance(
Figure 11. Simulated trajectories of the USV. USV: Unmanned surface vehicle.
Figure 12. Average travel time of the USV. USV: Unmanned surface vehicle.
Figure 13. Average travel distance of the USV. USV: Unmanned surface vehicle.
Figure 14. Simulated trajectories of the USV. USV: Unmanned surface vehicle.
Figure 15. Average travel time of the USV. USV: Unmanned surface vehicle.
Figure 16. Average travel distance of the USV. USV: Unmanned surface vehicle.
In the third step of the simulation, the experiment aimed to verify that the improved algorithm also has dynamic obstacle avoidance capabilities in an irregular environment. In this scenario, USV1 and USV4 demonstrated normal operation, using the improved algorithm and having trajectories that comply with COLREGs. USV2 and USV3, however, exhibited abnormal movement, using only the traditional algorithm. The trajectories are shown in Figure 17. During the simulation, there is a collision risk between USV1 and USV4, but they use an improved algorithm and their motion rules comply with COLREGs. According to the rule, USV1 has higher priority and will pass in front of USV4. At the same time, USV1 and USV2 also have collision risks, and changing the direction of motion of USV1 according to the rules avoids collisions. USV2, after performing an obstacle avoidance maneuver, got trapped in a local optimum, failing to move towards the target point and ultimately hitting the map's edge, unable to reach the target point, while the other three USVs successfully reached their target points. Compared to USV2, USV1 was able to promptly adjust its direction after obstacle avoidance and quickly reach the target point without hitting the irregular map edges. The USV running times are illustrated in Figure 18, and the comparison of running distances is shown in Figure 19. Based on 20 simulation runs (with all USVs reaching their target points), USV1 and USV4 had shorter running times compared with USV2 and USV3, and their running speeds were faster. Throughout the experiment, USV1 and USV4 consistently reached their target points without any issues. The comparison shows a significant improvement in the performance of the improved algorithm over the traditional algorithm.
Figure 17. Simulated trajectories of the USV. USV: Unmanned surface vehicle.
Figure 18. Average travel time of the USV. USV: Unmanned surface vehicle.
Figure 19. Average travel distance of the USV. USV: Unmanned surface vehicle.
Based on the two types of simulation experiments, it can be concluded that the USV, using the improved algorithm, can safely and accurately perform obstacle avoidance maneuvers when dealing with both dense static obstacles and complex dynamic obstacles, ultimately navigating the USV to the target point. Additionally, when faced with irregular maps, the USV is able to adjust its course in a timely manner. Compared to the traditional algorithm, the improved algorithm shows significant improvements in both average running time and average running distance.
5. CONCLUSIONS
This paper proposes a path planning method that combines an improved DWA with the nonlinear characteristics of USVs. Under the control of this algorithm, the USV can avoid dense static and complex dynamic obstacles, preventing collisions with obstacles and other USVs. By integrating the nonlinear characteristics of the USV into the velocity space and acceleration calculations of DWA, the planned trajectory becomes more suitable for real-world engineering scenarios. FISA is used to select the velocity set, and a specifically designed cost function enables DWA to choose a superior velocity set within the velocity space. This helps mitigate the problem of USVs getting trapped in a local optimum when using traditional algorithms in complex environments.
Furthermore, collision avoidance rules based on COLREGs are integrated into the path planning for multiple USVs. When multiple USVs reach the decision distance, they perform obstacle avoidance maneuvers according to the rules to prevent collisions. The simulation results verify the effectiveness of this method in addressing the USV obstacle avoidance problem. Comparative analysis with traditional algorithms demonstrates that the proposed algorithm can safely and accurately navigate USVs to their destinations in three scenarios: dense static obstacles, dynamic obstacles involving multiple USVs, and irregular environments. Through data comparison, it is shown that the improved algorithm outperforms the traditional algorithm in velocity selection, mitigating the local optimum problem and preventing the USV from getting stuck in an optimum solution, which would otherwise prevent it from reaching the target point. Moreover, the improved algorithm results in shorter average travel distance and time compared to the traditional algorithm, thereby enhancing the operational efficiency of the USV.
For future research, several aspects can be further explored to improve the performance and applicability of the proposed approach. First, the current model can be enhanced by incorporating more sophisticated sensor fusion techniques to mitigate the influence of sensor errors and noise. Sensor defects and data reliability have been recognized as critical challenges in real-world USV deployments, and addressing these issues will be key to improving robustness. Second, adaptive learning methods, such as reinforcement learning, could be integrated to enhance the adaptability of USVs in environments with highly dynamic and unpredictable elements, enabling the system to continuously learn from new experiences and improve decision-making capabilities. Lastly, real-world experiments in diverse marine conditions will be conducted to validate and further refine the proposed approach, ensuring it is capable of handling a wide range of practical challenges and conditions effectively. Overall, our future work will focus on improving sensor reliability, enhancing the adaptability of the USV's decision-making process, and validating the system through real-world testing, thereby contributing to the development of more autonomous and reliable USV path planning solutions.
DECLARATIONS
Authors' contributions
Made substantial contributions to the conception and design of the study and performed the analysis of the results: Liu S, Wang X
Carries out algorithm design and improvement and conducted theoretical analysis: Wu Y, Li Q, Yan J, Levin E
Availability of data and materials
Not applicable.
Financial support and sponsorship
This work was supported by the Shandong Provincial Natural Science Foundation (Grant No. ZR2024QF114) and the major innovation project for the science education industry integration pilot project of Qilu University of Technology (Shandong Academy of Sciences) (Grant No. 2023JBZ03).
Conflicts of interest
Wu Y is the Guest Editor Assistant of the Special Issue of "Intelligent Control and Decision-making of Unmanned Ships" of the journal Intelligence & Robotics, while the other authors have declared that they have no conflicts of interest.
Ethical approval and consent to participate
Not applicable.
Consent for publication
Not applicable.
Copyright
© The Author(s) 2024.
REFERENCES
1. Ma Y, Zhao Y, Incecik A, Yan X, Wang Y, Li Z. A collision avoidance approach via negotiation protocol for a swarm of USVs. Ocean Eng 2021;224:108713.
2. Xu X, Lu Y, Liu X, Zhang W. Intelligent collision avoidance algorithms for USVs via deep reinforcement learning under COLREGs. Ocean Eng 2020;217:107704.
3. Ali H, Xiong G, Tianci Q, Kumar R, Dong X, Shen Z. Autonomous ship navigation with an enhanced safety collision avoidance technique. ISA Trans 2024;144:271-81.
4. Wang G, Wang J, Wang X, et al. A method for coastal global route planning of unmanned ships based on human-like thinking. J Mar Sci Eng 2024;12:476.
5. Tan Z, Wei N, Liu Z. Local path planning for unmanned surface vehicle based on the improved DWA algorithm. In: 2022 41st Chinese Control Conference (CCC); 2022 Jul 25-27; Hefei, China. IEEE; 2022. pp. 3820–5.
6. Han J, Cho Y, Kim J. Coastal SLAM with marine radar for USV operation in GPS-restricted situations. IEEE J Oceanic Eng 2019;44:300-9.
7. MahmoudZadeh S, Abbasi A, Yazdani A, Wang H, Liu Y. Uninterrupted path planning system for multi-USV sampling mission in a cluttered ocean environment. Ocean Eng 2022;254:111328.
8. Du B, Lin B, Zhang C, Dong B, Zhang W. Safe deep reinforcement learning-based adaptive control for USV interception mission. Ocean Eng 2022;246:110477.
9. Sun Z, Sun H, Li P, Zou J. Self-organizing cooperative pursuit strategy for multi-USV with dynamic obstacle ships. J Mar Sci Eng 2022;10:562.
10. Chen YL, Du WK, Hu XY, Bai GQ, Zhang JB. USV collision hazard assessment and track planning algorithm. Ocean Eng 2022;261:112149.
11. Wu C, Yu W, Li G, Liao W. Deep reinforcement learning with dynamic window approach based collision avoidance path planning for maritime autonomous surface ships. Ocean Eng 2023;284:115208.
12. Gonzalez-Garcia A, Castañeda H. Guidance and control based on adaptive sliding mode strategy for a USV subject to uncertainties. IEEE J Oceanic Eng 2021;46:1144-54.
13. Zheng K, Zhang X, Wang C, Zhang M, Cui H. A partially observable multi-ship collision avoidance decision-making model based on deep reinforcement learning. Ocean Coast Manage 2023;242:106689.
14. Gan W, Qu X, Song D, Yao P. Multi-USV cooperative chasing strategy based on obstacles assistance and deep reinforcement learning. IEEE Trans Autom Sci Eng 2024;21:5895-910.
15. Zhang G, Han J, Li J, Zhang X. APF-based intelligent navigation approach for USV in presence of mixed potential directions: Guidance and control design. Ocean Eng 2022;260:111972.
16. Gao D, Zhou P, Shi W, Wang T, Wang Y. A dynamic obstacle avoidance method for unmanned surface vehicle under the International Regulations for Preventing Collisions at Sea. J Mar Sci Eng 2022;10:901.
17. Zhao Y, Qi X, Ma Y, Li Z, Malekian R, Sotelo MA. Path following optimization for an underactuated USV using smoothly-convergent deep reinforcement learning. IEEE Trans Intell Transp Syst 2021;22:6208-20.
18. Mwaffo V. Formation control and collision avoidance of unmanned water surface vehicles in maritime environments. J Franklin I 2024;361:106791.
19. Zhou B, Huang B, Su Y, Zheng Y, Zheng S. Fixed-time neural network trajectory tracking control for underactuated surface vessels. Ocean Eng 2021;236:109416.
20. Deng Y, Zhang X, Im N, Zhang G, Zhang Q. Model-based event-triggered tracking control of underactuated surface vessels with minimum learning parameters. IEEE T Neur Net Learn Syst 2020;31:4001-14.
21. Ma Y, Mao Z, Wang T, Qin J, Ding W, Meng X. Obstacle avoidance path planning of unmanned submarine vehicle in ocean current environment based on improved firework-ant colony algorithm. Comput Electr Eng 2020;87:106773.
22. Wand H, Yi H, Xiang J, Fu Y. Collision avoidance path planning algorithm research and application of medium-sized USV based on COLREGS. Chin J Sh Res 2022;17:184-95.
23. Zhang W, Yan C, Lyu H, Wang P, Xue Z, Li Z. COLREGS-based path planning for ships at sea using velocity obstacles. IEEE Access 2021;9:32613-26.
24. He Y, Jin Y, Huang L, Xiong Y, Chen P, Mou J. Quantitative analysis of COLREG rules and seamanship for autonomous collision avoidance at open sea. Ocean Eng 2017;140:281-91.
25. Lu N, Zhou W, Yan H, Fei M, Wang Y. A two-stage dynamic collision avoidance algorithm for unmanned surface vehicles based on field theory and COLREGs. Ocean Eng 2022;259:111836.
26. Liang C, Zhang X, Watanabe Y, Deng Y. Autonomous collision avoidance of unmanned surface vehicles based on improved a star and minimum course alteration algorithms. Appl Ocean Res 2021;113:102755.
27. Chang L, Shan L, Jiang C, Dai Y. Reinforcement based mobile robot path planning with improved dynamic window approach in unknown environment. Auton Robot 2021;45:51-76.
28. Wang S, Hu Y, Liu Z, Ma L. Research on adaptive obstacle avoidance algorithm of robot based on DDPG-DWA. Comput Electr Eng 2023;109:108753.
29. Yang H, Xu X, Hong J. Automatic parking path planning of tracked vehicle based on improved A* and DWA algorithms. IEEE T Transp Electr 2023;9:283-92.
30. Bai X, Jiang H, Cui J, Lu K, Chen P, Zhang M. UAV path planning based on improved A* and DWA algorithms. Int J Aerospace Eng 2021;2021:4511252.
31. Li Y, Jin R, Xu X, Qian Y, Wang H, Xu S. A mobile robot path planning algorithm based on improved A* algorithm and dynamic window approach. IEEE Access 2022;10:57736-47.
32. Ji X, Feng S, Han Q, Yin H, Yu S. Improvement and fusion of A* algorithm and dynamic window approach considering complex environmental information. Arab J Sci Eng 2021;46:7445-59.
33. Ghasemi M, Rahimnejad A, Akbari E, et al. A new metaphor-less simple algorithm based on Rao algorithms: a fully informed search algorithm (FISA). PeerJ Comput Sci 2023;9:e1431.
34. Wang X, Feng K, Wang G, Wang Q. Local path optimization method for unmanned ship based on particle swarm acceleration calculation and dynamic optimal control. Appl Ocean Res 2021;110:102588.
35. Zhou XY, Huang JJ, Wang FW, Wu ZL, Liu ZJ. A study of the application barriers to the use of autonomous ships posed by the good seamanship requirement of COLREGs. J Navigation 2020;73:710-25.
Cite This Article
Open AccessHow to Cite
Liu, S.; Wang, X.; Wu, Y.; Li, Q.; Yan, J.; Levin, E. Path planning method for USVs based on improved DWA and COLREGs. Intell. Robot. 2024, 4, 385-405. http://dx.doi.org/10.20517/ir.2024.23
Download Citation
Export Citation File:
Type of Import
Tips on Downloading Citation
Citation Manager File Format
Type of Import
Direct Import: When the Direct Import option is selected (the default state), a dialogue box will give you the option to Save or Open the downloaded citation data. Choosing Open will either launch your citation manager or give you a choice of applications with which to use the metadata. The Save option saves the file locally for later use.
Indirect Import: When the Indirect Import option is selected, the metadata is displayed and may be copied and pasted as needed.
About This Article
Copyright
Data & Comments
Data
0
Comments
Comments must be written in English. Spam, offensive content, impersonation, and private information will not be permitted. If any comment is reported and identified as inappropriate content by OAE staff, the comment will be removed without notice. If you have any queries or need any help, please contact us at support@oaepublish.com.