Path Planning of USV Based on the Improved Differential Evolution Algorithm

Authors: zhongming  xiao
baoyi  hou
jun  ning
bin  lin
zhengjiang  liu
Venue: IEEE_org_ICIST_2024_Conference
Published: 2024-07-25 09:47:49

Abstract: Planning a reasonable path and avoiding collisions with surrounding obstacles are among the most critical aspects of Unmanned Surface Vehicle (USV) navigation, which has drawn considerable attention from researchers in recent years, with various heuristic and intelligent optimization algorithms being applied to path planning. However, most existing algorithms have not sufficiently integrated safety and economy, leading to the planned paths that may not align with maritime practice. Therefore, to tackle the aforementioned issues, this paper introduces a differential evolution algorithm (DE) with an adaptive crossover factor for path planning and collision avoidance in USV. The collision risk index (CRI) is integrated with the DE, and the CRI is improved by introducing a restriction factor when selecting the degree of membership for the distance to closest point of approach (DCPA). The experimental results demonstrate that, compared with the other three algorithms, the improved DE exhibits greater advantages in terms of minimum distance to the target ship, minimum distance to obstacles, and total yaw distance, thereby validating the effectiveness of the algorithm.

Main paper: 
 i. introduction: 
 Unmanned surface vehicles (USVs) are intelligent control system that integrates path planning, communications, autonomous decision-making, and automatic target recognition, as well as a range of other advanced technologies. USVs utilize radar and AIS to continuously monitor their surroundings, enabling dynamic adjustments in course and speed to effectively avoid collisions with other ships or unknown obstacles at sea. With the continuous development of USV technology, the operational capabilities of USVs in various complex marine environments have steadily improved. Consequently, USVs are being increasingly used in diverse domains of daily life, such as waterway patrol and safety monitoring, ocean exploration and geological surveys, and marine biodiversity conservation.Path planning and collision avoidance technologies, as the core technologies of USV, have played a crucial role in their development. In light of this, scholars have conducted extensive research on the technologies. In past studies, many researchers have applied various heuristic algorithms to USV path planning, such as the A* algorithm [1] and the Dijkstra algorithm. With continuous development, many intelligent optimization algorithms have gradually been applied to the problem of path planning, such as the Ant Colony Optimization (ACO) [2] algorithm, Particle Swarm Optimization (PSO), Genetic Algorithm (GA) [3] , Rapidly-exploring Random Tree (RRT) algorithm [4] , Velocity Obstacle method (VO) [5] , and Dynamic Window Approach (DWA). These algorithms derive feasible paths through specific operational strategies. However, during path planning, they often encounter issues such as falling into local optima or planning paths that are too close to obstacles, resulting in suboptimal solutions. Therefore, many researchers have improved various algorithms, such as the improved RRT algorithm [6] , which introduces adaptive step size and target attraction mechanisms, allowing the USV to adaptively adjust its step size based on different waters and to adjust its direction of movement accordingly. The improved DWA [7] introduces the concept of obstacle search angle, enhancing the USV's obstacle avoidance capabilities in different scenarios.To fully utilize the advantages of various algorithms, scholars have combined different algorithms. For example, the combination of the PSO and Artificial Potential Field (APF) method [8] first plans a global path using the improved PSO, and the improved APF method is used for local path planning when dynamic obstacles are detected during navigation, which effectively reduces the collision risk. The combination of the GA and the ACO [9] uses the solution from the ACO as the initial population for the GA, thereby accelerating the convergence speed. However, most existing algorithms have not sufficiently integrated safety and economy, leading to paths that may not align with maritime practice.To address the various issues associated with the aforementioned algorithms, this paper proposes an Improved Differential Evolution algorithm (I-DE) and integrates it with the Collision Risk Index (CRI). Simulation experiments demonstrate that the I-DE, compared with the other three algorithms, can more effectively avoid collisions with target ships and obstacles while reducing deviation distance, ensuring both safety and economy. The primary contributions of this paper are outlined as follows:(1) The crossover factor CR in the Differential Evolution algorithm (DE) is adaptively improved, enhancing population diversity while maintaining the relative independence of individuals. This allows the algorithm to search the solution space appropriately according to the different iteration stages.(2) The CRI is integrated with the DE, and a restriction factor is added when selecting the degree of membership for the Distance to the Closest Point of Approach (DCPA). This makes the calculation of collision risk more aligned with maritime practice.Differential Evolution(DE) [10] is an algorithm used to solve continuous optimization problems. It primarily involves five steps: population initialization, fitness evaluation, differential mutation, crossover operation, and selection of new individuals.Initially, a population of size M is formed by randomly generating M individuals, where each individual is composed of n-dimensional vector. The size of the population affects the search capabilities of the algorithm and the use of computational resources. Generally, a larger population enhances the algorithm's global search capabilities but also increases computational costs. ,(0) ( (0), (0), (0),..., (0))EQUATION, min max min (0) (0,1)( )EQUATION1, 2, 3,..., , 2) Fitness evaluation: When calculating the fitness of the population individuals (the objective function value), it is necessary to define the objective function based on the specific problem. By designing appropriate objective functions, the algorithm can adapt to various optimization needs and complex problem environments, demonstrating high flexibility and adaptability. In this paper, the fitness is employed to assess the quality of the path points.3) Differential mutation: Below are descriptions of several mutation strategies that have been extensively researched: DE/rand/1:EQUATIONDE/best/1:EQUATIONUsing DE/rand/1 as an illustration, 1 ( ) r X G , 2 ( ) r X G , and 3 ( ) r X G are three different vectors randomly selected from the parent generation, { }1 2 3 1, 2, 3......, r r r i M ≠ ≠ ≠ ∈, F is the scaling factor, and F ranges from 0 to 2, typically set to 0.5. ( ) i V G is a new vector generated through the mutation strategy. Different mutation strategies have different population optimization abilities. To better understand the common properties of various mutation strategies, Feoktistov summarized them in a general form as follows:i i i V F β δ = + ×, where i β serves as the base vector and i δ acts as the differential vector. 4) Crossover operation:EQUATIONThe crossover factor CR ranges from 0 to 1. j is the current vector's dimension and jrand is a dimension randomly selected within the range from 1 to n. Adding the condition = j jrand guarantees that at least one dimension of the new individual comes from the mutant individual, thereby avoiding being identical to the initial individual. The crossover process is illustrated in Fig. 1 .The selection operation evaluates the fitness values of individuals to steer the population toward a better direction. The direction of population evolution is determined by the following formula:EQUATIONHere, ( ( )) i f U G and ( ( )) i f X Gare the fitness of the new individual and the initial individual, respectively.In areas with good visibility, collision avoidance behavior should comply with Rules 8, 13, 14, and 15 of the International Regulations for Preventing Collisions at Sea (COLREGs). Rule 8 explicitly stipulates the actions to be taken to avoid collisions, while Rules 13 to 15 define the different encounter situations: overtaking, head-on, and crossing encounters. Therefore, this paper incorporates the COLREGs and fully considers the implications of the ship encounter situations on collision avoidance behavior. Based on the course angles and positions of the two ships, the encounter between ships is classified into four scenarios. The classification is detailed in Table Ⅰ .When encountering another ship head-on, both ships share equal responsibility to give way. In overtaking situations, the overtaking ship has the responsibility to give way, while the ship being overtaken should preserve its original state. In a leftcrossing scenario, the own ship should preserve the original state, with the other ship bearing the responsibility to give way. Conversely, in a right crossing situation, the own ship has the duty to give way, while the other ship should preserve the original state. This section introduces the I-DE. Firstly, the crossover factor CR in the crossover operation is adaptively improved [11] . Concurrently, enhancements are made to the traditional CRI model by incorporating a restriction factor when selecting the membership function for DCPA, thus aligning the calculation of CRI more closely with maritime practices. Finally, the COLREGs and CRI are incorporated into the fitness function evaluation, forming an evaluation set based on safety, economy, compliance with COLREGs, and optimal collision avoidance timing. The safety factor is determined by the CRI.) ( ) ( ) i i i X G U G V G TABLE Ⅰ. SHIP ENCOUNTER SITUATION CLASSIFICATIONThe crossover factor CR determines the likelihood of each dimension of an individual being altered. A larger CR value facilitates the more effective transfer of information from the mutant individual to the initial individual, while a smaller CR value, although reducing the transfer of information, enhances the independence between individuals. Therefore, an adaptive CR mechanism is proposed to balance the above two effects, with the following improvements: EQUATIONThe CRI [12] is a fuzzy index used to assess collision risk, representing the likelihood of a collision occurring between ships. It is affected by external factors like the speed and course of the ship, along with the subjective factors of the operator. This paper constructs a collision risk model using three factors: DCPA, TCPA, and the inter-ship distance D. Additionally, a restriction factor is added when selecting the membership function of DCPA to improve the rationality of the selection. The set of factors for the CRI is established as follows:EQUATIONDefine the membership functions for each factor: 1) Membership function of DCPA Take the own ship(OS)'s position as the origin to establish a spatial right-angled coordinate system, the OS's coordinates are set at ( , ) O Ox y , and the speed and heading are set to O v and O ϕ , respectively; similarly, the target ship(TS)'s position, speed and heading are set to ( , )T Tx y , T v and T ϕ , respectively. The true bearings of OS to the TS and the TS to OS are OT a and TO a , respectively. The relative speed between the two ships is R v .In previous studies, the selection of the membership function for DCPA only considered the safe distance of approach (SDA) 1 r and the absolute safe distance of approach 2 r , without considering whether the ship domains of OS and the TS were infringed upon. Fig. 2 illustrates various situations where the ship domains of OS and the TS are infringed upon. Therefore, the membership function for DCPA is improved to address this issue. Establish a coordinate system with the TS as the origin, the direction of the bow as the positive y-axis, and the direction perpendicular to the bow to the right as the positive x-axis. Perform a coordinate transformation for the position of OS:1 0 1 0 0 1 sin , cos , , O O OT T x D y D a β β β ϕ γ = = = -+ (10) 1 360, 0 0, 0 OT T OT T a a ϕ γ ϕ -≤  =  ->  (11)Based on the transformed coordinates 1 1O Ox y , the relative motion line equation of OS relative to the TS is obtained:EQUATIONarctan 90 0, 0 270 0, 0OTx OTy R OTx OTy OTx OTy v otherwise v v v v v θ ϕ  +    = ≥ =   < =    (13) 0 0, 0 180 0, 0 0, 0 360 0, 0 OTx OTy OTx OTy OTx OTy OTx OTy v v v v o r v v v v θ  ≥ >  = ≥ < < <   < >  (14)Due to the change in the coordinate system, the relative motion line equation also needs to be transformed: As shown in Fig. 3 , when OS intrudes into the TS's domain, the relative motion line of OS to the TS will intersect with the boundary of the TS's domain. Therefore, by calculating the existence of an intersection point, can determine whether OS has intruded into the TS's domain.EQUATIONSimilarly, by analyzing whether the relative motion line of the TS to OS intersects with the boundary of OS's domain, can determine whether the TS has intruded into OS's domain. The improved membership function is as follows: < > >     + ° = - - < <    -     ≥  (16)Here, 1 p is the number of intersection points between OS's relative motion line to the TS and the boundary of the TS's domain, 2 p is the number of intersection points between the TS's relative motion line to OS and the boundary of OS's domain. ≤     -  = < ≤   -     > >  (17) 2 2 3 3 1 3 3 , , R R d DCPA DCPA d v T DCPA d DCPA d v  -  ≤  =  -  >   (18) 2 2 4 2 R d DCPA T v - = (19)Here, 3 d represents the latest avoidance distance for the burdened ship, 4 d represents the distance over which the ship is capable of taking evasive actions.The boundary of ship domainx y Fig. 3 The relative motion lines of the two ships intersect at the boundary of the ship domain. EQUATIONwhereEQUATIONIncorporate the COLREGs and the CRI into the evaluation of the fitness function, forming an evaluation set F based on factors of safety, economy, compliance with COLREGs, and optimal collision avoidance timing. The CRI determines the safety factor in the fitness function, while the voyage distance and the degree of turning together determine the economic factor in the fitness function.Constructing CRI-based objective function:EQUATIONIn path planning issues, the total voyage determines the consumption of cost during navigation and serves as an important economic assessment index. In the process of navigation, ( , ) i ix y represents the current point, and 1 1i ix y --is the previous point adjacent to ( , ) i ix y , with the total number of path points being n and the destination point being ( , ) n nx y . Constructing total voyage-based objective function:EQUATIONConstructing degree of turning-based objective function:EQUATIONBased on the encounter situations and responsibility allocation described earlier, the objective function constructed according to the COLREGs is: The timing of collision avoidance depends on the CRI value. Therefore, based on previous research, an objective function for optimal collision avoidance timing is constructed with a threshold value of 0.3:5 1 0.3 0 0.3 CRI F CRI ≥  =  <  (27) 1 1 2 2 3 3 4 4 5 5 Fitness W F W F W F W F W F = + + + + (28)where 1 2 3 4 5W W W W W 、 、 、 、are the weights for safety, total voyage, degree of turning, COLREGs, and optimal collision avoidance timing, respectively.This paper validates the effectiveness of the proposed Improved Differential Evolution (I-DE) algorithm through simulation experiments on the Matlab platform. The algorithm is compared with the traditional DE, PSO, and GA, using safety and economy as evaluation criteria.The simulation experiments are set in open waters with good visibility, ignoring external factors such as wind, waves, and currents. The experiments simulated scenarios involving twoship and three-ship encounters, incorporating static obstacles in the two-ship encounters to more comprehensively assess the autonomous obstacle avoidance capability of the algorithm. In open waters with ample space, changing course is the most effective measure to prevent collisions at close range, provided that timely and effective evasive maneuvers do not result in the two ships coming closer than the safe distance again. Therefore, to facilitate the study, when considering encounter situations and avoidance methods, and following the collision avoidance rules and the usual practices followed by seafarers at sea, the USV, when acting as the give-way ship, avoids a collision by changing course instead of reducing speed or stopping. The parameters and initial states of the experimental objects are displayed in Table Ⅱ to Table Ⅳ.To ensure that the algorithms are tested under fair conditions, the parameters used in the experiments are uniformly set as follows: total iteration times K = 50 , initial population size The outcomes of the simulation are illustrated in Fig. 4 5 . Fig. 4 displays the complete paths planned by the various algorithms, while Fig. 5 displays the states of the ships at specific time intervals, reflecting the real-time distance between the OS and the TS, providing data support for evaluating safety. In these figures, the blue ship represents OS, the black ship represents the TS, and the black hexagons represent the static obstacles. The simulation results are detailed in Table Ⅳ . By comparing the minimum distances(MD) between the OS and the TS and between the OS and the obstacle, the safety of the paths can be evaluated. The total deviation distance between the planned path and the initial path can be used to assess the economy of the path. Additionally, the table also shows the runtime of each algorithm.As evidenced by the experimental data, the PSO algorithm and the traditional DE algorithm perform poorly in terms of navigational safety. The paths planned by these two algorithms result in OS maintaining a relatively close distance to the TS during navigation, posing a higher collision risk. In contrast, the paths planned by the I-DE algorithm and the GA maintain a greater distance between the ships, better ensuring navigational safety. By comparing the MD between OS and the obstacle, it is evident that the I-DE algorithm also performs best in avoiding collisions with an obstacle, presenting the lowest collision risk.As shown in Fig. 4 , in the initial stage, there is a considerable distance between the OS and the obstacle, and no evasive action is needed. However, the path planned by the GA deviates from the original route at the outset. This premature maneuver increases the deviation distance of OS, thereby reducing the path's economic efficiency. In contrast, the paths planned by the I-DE algorithm, the PSO algorithm, and the traditional DE algorithm closely adhere to the original path when far from the obstacle. These algorithms start taking evasive actions at approximately 1 nautical mile from the obstacle, adjusting the course to avoid collisions and passing the obstacle from a greater distance. Once the obstacle is safely passed, the ship gradually returns to the original path and eventually reaches the target point. According to the data in Table Ⅴ, the total deviation distance for the GA is the largest, while the other three algorithms have relatively smaller deviation distances, indicating better economic efficiency.Similar to the two-ship encounter scenario, the simulation results are presented in Fig. 6 and Fig. 7 . The experimental findings indicate that the I-DE algorithm, along with the other three algorithms, ensures that the ship safely navigates through encounters with target ships, successfully avoiding collisions and demonstrating good safety performance.However, there are significant differences in economic performance among the four algorithms. The PSO algorithm results in the ship deviating significantly from its original course after avoiding TS2, with the total deviation distance reported in Table Ⅵ being 47.65 nautical miles, which compromises the economic efficiency of the path. In contrast, the paths planned by the I-DE, DE, and GA algorithms show a tendency to approach the original course after the avoidance maneuver with TS2. As shown in Fig. 6 , the I-DE algorithm enables the ship to smoothly return to its original course after avoidance. According to the data in Table Ⅵ, the total deviation distances for the I-DE, DE, and GA algorithms are 22.76 nautical miles, 28.40 nautical miles, and 31.22 nautical miles, respectively, indicating that the path planned by the I-DE algorithm exhibits better economic efficiency.Since the runtime is of lower importance in path evaluation and the differences in runtime among the algorithms are minimal, the impact of runtime is not considered. Considering both safety and economy, the I-DE algorithm demonstrates better performance in planning safe, economical paths, significantly outperforming the other algorithms. Therefore, the simulation experiments confirm the effectiveness of the improved differential evolution algorithm.To address the issue of path planning and collision avoidance for USVs in open waters, this paper proposes an improved adaptive differential evolution algorithm. This algorithm adaptively adjusts the crossover factor (CR) in the crossover operation, enhancing population diversity while increasing the independence among individuals. Additionally, the CRI is incorporated into the fitness function evaluation. A restriction factor is added when selecting the membership function of DCPA, making the calculation of the collision risk more consistent with maritime practices. Simulations were conducted on the Matlab platform, comparing the I-DE algorithm with the PSO algorithm, the GA, and the traditional DE algorithm under two-ship encounter and three-ship encounter scenarios. Safety is determined by the minimum distance between own ship and the obstacle and the target ship, and economy is determined by the total deviation distance. The experimental outcomes indicate that the I-DE algorithm outperforms others in terms of safety and economy, thereby validating its effectiveness.In future research on path planning and collision avoidance for USVs, it is essential to fully consider the interference of external factors as well as the maneuverability of the USV. Furthermore, attention should be given to aspects such as communication delays, human factors in decision-making, and integration with existing maritime traffic management systems, thereby ensuring closer alignment with maritime practices. 
 
 Appendix:  



Reviews: review: title: title: comment
main_review: main_review: This paper introduces a differential evolution algorithm (DE) with an adaptive crossover factor for path planning and collision avoidance in USV. The collision risk index (CRI) is integrated with the DE, and the CRI is improved by introducing a restriction factor when selecting the degree of membership for the distance to closest point of approach (DCPA). The experimental results demonstrate that, compared with the other three algorithms, the improved DE exhibits greater advantages in terms of minimum distance to the target ship, minimum distance to obstacles, and total yaw distance. In reviewer's opinion, this paper is acceptable.
title: title: Accept
main_review: main_review: This paper focuses on introducing an improved adaptive differential evolution algorithm. Overall, the paper presents a novel study that introducing this algorithm can effectively solve the issue of path planning and collision avoidance for USVs in open waters. However, several aspects could benefit from clarification, revision, or additional analysis.
1. Some figures could be improved by reorganizing data or adding labels.
2. The author should consider additional comparative experiments or simulations to strengthen conclusions.
3. The discussion of limitations and future work could be expanded to more fields.
title: title: This article is well written, but there are still some minor errors.
main_review: main_review: The 'where' in the text should be lowercase and cannot be indented before it. Please read the entire text carefully and correct this error.