Simulated Annealing-Based Optimization for the Coverage Path Planning of Multiple Unmanned Surface Vehicles in ECDIS

Authors: yunwei  li
nan  gu
dan  wang
Venue: IEEE_org_ICIST_2024_Conference
Published: 2024-07-30 12:15:29

Abstract: This paper addresses the coverage path planning of multiple unmanned surface vehicles (USVs) based on electronic chart displays and information system. An optimized coverage path planning method is proposed to improve the coverage percentages and the coverage area of each USV leaves an additional degree of freedom for the operator to adjust further. Specifically, a grid representation method is proposed to fully cover the polygonal work area where three kinds of grids, namely, ``Free'', ``Obstacle'', and ``Initial USV Position'' are obtained. Next, a simulated annealing-based optimization method is proposed to optimize the placement of the grid by moving and rotating such that a more ``Free'' grid can be obtained. Then, an improved divide area based on the robot's initial position method is proposed to achieve proportional area division. Finally, the coverage paths are generated by using a spanning tree coverage method. Simulation results verify the effectiveness of the proposed simulated annealing-based optimization for the coverage path planning of multiple USVs.

Main paper: 
 : 
 omy, serves as pivotal tools in the exploration and development of the oceans [1] [2] [3] [4] . Multi-USV systems have a wider range of applications in ocean survey, sea rescue, marine scientific research, water patrol, and underwater equipment deployment compared to single USV [5] [6] [7] . Coverage path planning is a key component in the motion control of multiple USVs, which is to plan multiple paths such that an area can be fully covered.Many coverage path planning methods are proposed in recent years. In [8] [9] [10] , a coverage path planning method based on binary interval neighborhood network algorithm is proposed, which processes good adaptability and parallelism. In [11] , [12] , a coverage path planning method based on cell decomposition method is proposed, but this method needs to segment the map more precisely, which leads to higher computational complexity and reduces the path planning efficiency. In [13] [14] [15] [16] , a spanning tree coverage (STC) based coverage path planning method is proposed for multiple robots. The coverage path generated by this method does not repeat, but the search path depends on the initial position of each robot, which is prone to the problem of path overlap. In [17] , an STC method based on auction and bidding process is presented, which balance the coverage path length of each robot. In [18] , a divide areas based on robots initial positions (DARP) method is combined with STC method, which improves the coverage efficiency of multiple robots. However, each of these methods suffers from insufficient coverage or high computational requirements.Based on the above discussions, this paper studies the coverage path planning of multiple USVs in electronic chart display and information system (ECDIS). An optimized coverage path planning method is proposed to improve the coverage percentages and reduce the number of turns. First, based on three types of grid including "Free", "Obstacle", and "Initial USV Position", a grid map is established over a selected polygonal work area. Next, a simulated annealing optimization method is used to optimize the established grip map by moving and rotating the grids. Then, an improved DARP method is proposed to achieve the proportional area division and the coverage paths are generated by using a spanning tree coverage method. Finally, based on the ECDIS platform, simulation verifies the effectiveness of the proposed optimization based coverage path planning for multiple USVs.ECDIS is a navigation information system with an electronic chart database, as well as navigational and piloting information. This information is required to navigate for USV, a multiple USVs coverage path planning optimization method is applied to ECDIS. Firstly, the initialization setup is performed. Next, the map model is transformed, optimized and solved. Finally, the coverage path for each USV is generated. The framework of the proposed optimized coverage path planning method of multiple USVs is shown in Fig. 1 . Selecting PWA  Selecting Q  Initial Position  Number of USVsGrid RepresentationGrid Placement OptimizationArea DivisionFig. 1 . Framework of the proposed optimized coverage path planning method of multiple USVs based on ECDIS.Specifically, a polygonal work area (PWA) is selected manually in ECDIS, then obstacle areas can be selected in the selected PWA. PWA vertex coordinates and obstacle Q coordinates are expressed in the format of the world geodetic system coordinate system 1984 (WGS84) , as shown in the following:EQUATIONEQUATIONwhere X, Y represent latitude and longitude coordinates; n is the number of polygon vertices; o i (i = 1, ...q) denotes the ith obstacle; p i (i = 3, ...q) is the number of vertices in each obstacle region, and q is the number of obstacles. The initial positions of the USVs in the PWA, which can also be represented in WGS84 format:EQUATIONwhere m is the USV number; s i (i = 1, ...m) denotes the ith USV. As an output of this method, a set of paths is generated, one path for each USV involved in the mission, thus providing complete coverage of the PWA:EQUATIONwhere r i (i = 1, ...t) is the number of waypoints per USV; z i (i = 1, ...m) denotes the ith path.This section presents simulated annealing-based optimization for the coverage path planning of multiple unmanned surface vehicles in ECDIS. It includes the grid representation, grid placement optimization, and area division and coverage path generation.Traditional ECDIS-based USV path planning algorithms need to read the chart information of all points in the work area to create a grid map. In this paper, the optimization for coverage path planning based on simulated annealing involves extracting PWA vertex information and obstacle area vertex information. These are subsequently converted into a grid map based on the desired planning accuracy. This greatly decreases the computation time and lowers the requirement on computer configuration. After the conversion, a node is created at the center of each grid cell in grid map. Through the nodes, the minimum spanning tree is constructed, and eventually the coverage paths are generated with it. Considering different task requirements, set the planning accuracy in meters (δ), i.e., half the distance between neighboring trajectories. Thus, the distance between two nodes is ∆ = 2 × δ.To represent the PWA, creat a rectangular border that holds a × b grids of side length ∆. As shown in Fig. 2 (red border):EQUATIONEQUATIONand k denotes the floor of k (largest integer less than the given real number).After that, grids are incorporated, where each grid center represents a node. These nodes can exist in three states: F ree, Obstacle, and Initial U SV s P osition. These states dictate their treatment in the path planning process, illustrated in Fig. 3 with green, black, and red colors respectively.Limitations of the grid map-based path planning method include the inability of the grid map to fully select the planning area for representation, which leads to insufficient coverage of the planning area. To address this limitation, a common adopted solution is to generate more accurate grid maps by lowering the size of the accuracy, but it will also lead to a significant increase in time and cost to perform the tasks, and higher requirement on computer configuration. In this paper, an optimization method based on a simulated annealing algorithm is proposed to optimize the representation of grid maps.The method is that by rotating and moving standard rectangular border, there will be more F ree nodes contained in PWA, which will effectively increase the overall coverage. For example, the number of F ree nodes before optimization is 45 shown in Fig. 4 , and after rotation and movement, the number of F ree nodes increases to 49 in Fig. 5 . Based on this, optimization is performed using the simulated annealing algorithm to maximize the overall coverage of the PWA. Define the translation of the polygon's X-axis to be C x , in a range [0, ∆], the translation of the polygon's Y-axis to be C y , in a range [0, ∆], and the angle of rotation of the polygon to be C θ , in a range [0, 90 • ].Define an optimization index F to denote the model associated with PWA coverage potential given a certain planning accuracy, and is expressed as:• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • Fig. 4. Grid map before optimization. • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •EQUATIONF consists of three independent normalized F i terms satisfying:EQUATIONThe term F 1 denotes the basic objective of the whole optimization process, i.e., fitting the maximum number of nodes possible within a given PWA, defined as follows:EQUATION)where β represents the number of nodes placed within the polygon; S p represents the area of the polygon. The theoretical maximum number of nodes that can be accommodated within a given polygon is denoted as:EQUATIONboth S p and ∆ are constants after region selection. Therefore, maximizing the F 1 term results in the maximal placement of nodes within the polygon. In addition, the F 2 term provides better options for node placement within the polygon, increasing the coverage of the PWA edge region. The definition of F 2 is given as:EQUATIONwhere S s represents the area of the enhanced bounding box.In the example in Fig. 2 , S p represents the blue area of the polygon and S s represents the area of the yellow rectangular bounding box. Because PWA is constant, S s can be minimized by maximizing the overall F 2 term. The purpose of adding this term is mainly to control the rotation angle C θ to optimize. as a result, the F 2 item is also normalized. Finally, the F 3 term improves the location of nodes within a selected PWA, allowing for path alignment at the boundaries of the region and increasing the coverage of the range of the edge region. F 3 is defined as follows:EQUATIONwhere {X maxs , X mins , Y maxs , Y mins } are the vertices of the augmented rectangular border (yellow border in Fig. 2 ), and {X max , X min , Y max , Y min } are the vertices of the standard rectangular border (red border in Fig. 2 ). The F 3 term is used to reconcile the absolute difference between the edge of the polygon and the augmented rectangular border in each axis, i.e., to fine-tune C x and C y so that the resulting paths are centered, and F 3 is normalized as well.In order to optimize the node representation and placement for a given PWA and planning accuracy, a simulated annealing algorithm is used to find a solution of (C x , C y , C θ ) that maximizes F . F 1 and F 2 contribute positively to the overall optimization index and act as rewards, while F 3 acts as a penalty by appropriately reducing the F 1 and F 2 terms. k 1 , k 2 , and k 3 are constants to regulate each term, and they are allowed to take values in the following range:EQUATION)An overview of the grid placement optimization algorithm is given in Algorithm 1, where T is the initialization temperature, T min is the minimum temperature, α is the temperature drop rate, K is the number of iterations at each temperature, γ is a constant, P is the acceptance probability of solution, and the algorithm returns the global optimal solution F max and C x , C y , C θ when the optimal solution is reached.In this section, the DARP algorithm is first improved to achieve proportional area division. The divided area is then combined with the STC algorithm to provide an independent path for each USV.Input: T , T min , α, K, δ, k 1 , k 2 , k 3 , γ Output: F max , C x , C y , C θ 1: Initialize: C x = δ; C y = δ; C θ = 0; F max = 0 2: while T > T min do 3:while (i <= K -1) do 4: ifF cur = k 1 • F 1 + k 2 • F 2 -k 3 • F 3 ; // Get(i = K -1) then 9:Create a new state for new solution 10:C xnew = C xcur + random(0, 1) × 2 × δ;11:C ynew = C ycur + random(0, 1) × 2 × δ; 12:C θnew = C θcur + random(0, 1) × 90; if (random(0, 1) > γ) then 16: if (random(0, 1) > γ) then 21:C xnew = C xcur + random(0, 1) × δ/4;C ynew = C ycur + random(0, 1) × δ/4; 22:else 23:EQUATIONif (random(0, 1) > γ) then P = e (Fcur-Fnew)/T ) ; // Calculate the acceptance probability 32:if P > random(0, 1) then 33: T = T × α; // Update temperature 37: end whileF max = F new ; //The traditional DARP method provides equal area partition, which means that all USVs will be assigned exactly the same proportion of area. In this work, DARP is extended and now capable to perform proportional area division, where the percentage is defined by the user, facilitating the simultaneous operation of heterogeneous USVs with different energies in the same task:EQUATIONwhere G i denotes the percentage of regions of the ith USV.Each sub-region is generated to cover the path after completing the task area division. In this paper, the STC method is used as the basic method for generating coverage path planning. The principle of the STC method is to generate a minimum spanning trees (MSTs) in each subregion and then generate paths around each MST.In this section, simulation results are presented to illustrate the effectiveness of the simulated annealing based optimized coverage path planning method for multiple USVs. In the simulation, a part of Dalian harbor is selected in ECDIS as PWA. In order to validate the effectiveness of the method, the number of USV is selected as 1, and planning accuracy as 20m. The simulation results can be seen in Fig. 6 . Fig. 6 (a) shows the coverage path without optimization; Fig. 6 (b) shows the optimization results under F 1 term; Fig. 6 (c ) shows the optimization results under F 1 term and F 2 term; Fig. 6 (d) shows the optimization results under F 1 term, F 2 term and F 3 term. Table I compares five criteria under different methods. It shows that the proposed method is able to increase percentage of coverage (POC), path length, and normalized path length (N-Length) ( m 1000m 2 ), as well as decrease in number of turns and normalized number of turns (N-Turns) ( T urns 1000m 2 ). Specifically, the number of turns without optimization is 26, the coverage is 76.35%, and the path length is 3.84 km. After the introduction of the F 1 term the number of turns is 16, the coverage is 81.36%, and the path length is 4.48 km. It can be seen that the number of turns is significantly decreased and the coverage is significantly improved. After the introduction of the F 1 term and the F 2 term, the number of turns is 16, the coverage is 83.67% and the path length is 4.48 km. F 2 term is mainly used for the rotation of the generated path to obtain the optimal C θ . After the introduction of the F 1 ,F 2 and F 3 , the number of turns is 16, the coverage rate is 91.42%, and the path length is 4.8 km. F 3 term makes the generated path centrally placed, which is more conducive to the coverage of the edge region.Therefore, the introduction of the optimization index F has a major improvement on both the number of turns and the coverage. Apart from that, planning accuracy is also a key factor affecting the coverage. For the same PWA, optimized coverage can reach more than 97% when the planning accuracy is 10 meters, at the expense of more computing time.In addition, in order to verify whether the number of USVs has impact on the effectiveness of the optimization method, and also to verify the planning effect of proportional area division. 20km 2 sea area near West Ant Island of Dalian is selected as PWA, and the planning accuracy is defined as 50 meters. The coverage paths are planned for the number of USVs as 5, 10, 20, and 50 respectively. The planning results for 5 USVs and 50 USVs are shown in Fig. 8 and Fig. 9 , where the red area is the PWA and the yellow areas are the obstacle areas. The area division proportions of the 5 USVs in Fig. 7 are set to 10%, 10%, 20%, 20%, 40%. Table II indicates optimized data for different number of USVs. The results show that the number of USVs has no significant effect on the coverage of the generated paths, while the algorithm running time rises significantly when USVs number reaches 50. V. CONCLUSION This paper investigates the coverage path planning of multiple USVs in ECDIS. A simulated annealing-based optimization for the coverage path planning of multiple USVs is proposed. Simulations of multiple target sea areas are conducted to verify the effectiveness of the proposed coverage path planning method for increasing coverage percentages, reducing the number of turns, and increasing the operator's degree of freedom. The simulated annealing-based optimization for the coverage path planning of multiple USVs in ECDIS proposed herein may provide a feasible method for future large-scale maritime coverage operations of multiple USVs. 
 
 Appendix:  



Reviews: review: title: title: The topic under consideration is interesting. This paper can be accepted after minor modifications.
main_review: main_review: This paper investigates the coverage path planning of multiple unmanned surface vehicles based on electronic chart displays and information system. The topic under consideration is interesting. Detailed comments and suggestions are listed as follows.
1.	The English writing of the paper needs to be further polished, and some typos should be fixed. 
2.	In (5) and (6), $X_{max}$, $ X_{min}$, $Y_{max}$ and $Y_{min}$ should be defined detailedly. 
3.	 Suggest adding the latest references. In addition, the manuscript format of references should be standardized.
title: title: Accept
main_review: main_review: This paper focuses on the coverage path planning of multiple unmanned surface vehicles and mainly includes the study of an optimized coverage path planning method and a simulated annealing-based optimization method. This paper gives details of the design process for the grid representation, grid placement optimization, and area division and coverage path generation, which improves the coverage of each USV and adds additional adjustment degrees of freedom. Simulation results verify the effectiveness of the proposed simulated annealing-based optimization for the coverage path planning of multiple USVs. But there are still two suggestions:
1. The innovation of this paper can be clearly expressed in Section Ⅰ;
2. The superiority of this paper to other published articles can be demonstrated in simulation.
title: title: Simulated Annealing-Based Optimization for the Coverage Path Planning of Multiple Unmanned Surface Vehicles in ECDIS
main_review: main_review: This paper addresses the coverage path planning of multiple unmanned surface vehicles (USVs) based on electronic chart displays and information system. This work is well organized. Below are some comments.
1.	The innovation is not clear. It is suggested that the authors restate the innovation and contributions.
2.	The careful proofreading should be further accomplished.
title: title: All in all good, but there are still some small problems.
main_review: main_review: This paper discusses a simulated annealing-based optimization method for coverage path planning of multiple unmanned surface vehicles (USVs) within an electronic chart display and information system (ECDIS). The study proposes an optimized coverage path planning approach that enhances coverage percentages, reduces the number of turns, and provides operators with increased flexibility. The method involves grid representation, grid placement optimization, area division, and coverage path generation. Simulation results demonstrate the effectiveness of this approach, showing significant improvements in coverage rates and path efficiency across various maritime scenarios. On the whole, the paper is good, but there are still some problems that need to be corrected.

Comments:

1.The structure of the article is generally clear, but it may benefit from a more distinct separation between the background introduction and the discussion of existing methods in the introduction section, making it easier for readers to identify the novelty of the study.

2.The overall language is fluent, but some sections with technical jargon might be simplified to improve readability, particularly in the more detailed technical discussions.

3.The research content is well constructed. But there are grammatical errors and incorrect English writing in the current manuscript. Please make the necessary corrections.