CN117406717A - Polar region ship dynamic path planning method with double-objective optimization of distance and risk - Google Patents

Abstract

The invention provides an improved D X Lite polar region ship dynamic path planning method, which specifically comprises the following steps: s1: constructing a grid environment map, and calculating a comprehensive navigation risk value RIO of each grid; s2: performing grid classification and introducing a safety coefficient omega; s3: introducing nodes and node variables in a D-lite algorithm into the grid environment map and improving an edge cost function c (s, s') and a cost function rhs(s); s4: expanding the neighborhood searching direction of the node into 32 neighborhoods; s5: minimizing the cost function rhs'(s) value to an optimal path; s6: re-planning the path; the invention fully utilizes the characteristic and rule that the sea ice risk value continuously changes in the actual sailing, combines the path planning and the comprehensive sailing risk value of the ship, optimizes the path length, the path smoothness and the path safety while being more fit with the actual sailing path, and has stronger practicability and adaptability.

Description

A dynamic path planning method for polar ships with dual-objective optimization of distance and risk

Technical field

The invention relates to the field of safe navigation path planning for ships in polar sea areas, and is specifically a dynamic path planning method for polar ships with dual-objective optimization of distance and risk.

Background technique

In polar navigation, due to the special factors of the ocean and natural geographical environment, the safety of ships in polar navigation is particularly important, and the demand for reliable path planning is becoming higher and higher. Although there has been a lot of research on ship route planning, there is a lack of application in polar waters.

Path planning methods can be divided into raster map-based and non-raster map-based methods according to the use of rasters. Among the path planning algorithms based on raster maps, A* and Dijkstra are most frequently used, and both are suitable for static environments. Due to limitations in search directions, planning algorithms not based on raster maps, such as genetic algorithms and RRT, are widely used. Ship route planning. Polar ship path planning is different from other sea-going ship path planning in that it requires comprehensive consideration of ice conditions such as sea ice density, sea ice thickness, and ship ice class information. However, the environmental sea ice data of polar ships are changing all the time, causing their navigation index to change. This requires that the path re-planning speed is fast enough to meet the real-time requirements of ship navigation. Among them, the principle of D*Lite dynamic path planning algorithm Simple and easy to implement, it meets the requirements of ship re-planning in real-time waterways.

However, in a rasterized environment, if the traditional D*Lite algorithm is directly applied to ship path planning and the four-neighborhood or eight-neighborhood search method is used to search for the path, the path generated in this way will not only be unsmooth, but also make the path impractical. , and does not conform to the conditions in polar seas.

Contents of the invention

In order to solve the problems in the traditional path planning algorithm, a single parameter cannot be directly applied to polar ship path planning. The node expansion range is too large and there are a large number of repeated calculation nodes, resulting in low computational efficiency of the algorithm. The planned path has a large number of inflection points and the path is not smooth. , the present invention discloses a polar ship dynamic path planning method with distance and risk dual-objective optimization, which realizes adding factors that affect polar navigation safety into the algorithm, and combines the POLARI system with the improved D*lite algorithm to achieve safety and security. The dynamic path planning of distance dual-objective optimization improves path safety while shortening the path length, has strong operability, and improves the applicability of the dynamic path planning algorithm.

The specific plan is as follows:

A dynamic path planning method for polar ships with dual-objective optimization of distance and risk,

S1: Construct a grid environment map and calculate the comprehensive navigation risk value of navigation in each grid. RIO _V : Obtain the sea ice longitude and latitude data, sea ice type data and sea ice density data in the planned path area, and use the sea ice longitude and latitude The data constructs a grid environment map composed of grids of the same size, selects the ship V for navigation, and uses the sea ice type data to find the ship navigation risk index RV _{V of the ship V under various types of sea ice in the POLARIS system. T} , the sum of the products of the ship navigation risk index RV _{V, T} and the sea ice density data is weighted and calculated to obtain the comprehensive navigation risk value RIO _V of the ship V sailing in each grid under complex ice conditions;

S2: Carry out grid classification and introduce safety factor ω: classify the grids in the grid environment map into dangerous grids, risk grids and free grids according to the comprehensive navigation risk value RIO _V ; set the constant ω as the safety factor , perform segmentation processing on the comprehensive navigation risk value RIO _V according to the type and safety factor of the grid classification to obtain the classified grid navigation risk value RIO';

S3: Introduce the nodes and node variables in the D*lite algorithm into the grid environment map. The nodes include the starting node, the target node and the intermediate node. The node variables include the edge cost function c(s,s') , cost function rhs(s), cost function estimate g(s) and heuristic function h(s,s'), for the edge cost function c(s,s') and cost function rhs(s) in the node variables ) to make improvements;

S31: Improve the edge cost function c(s,s'): Improve the independent variable of the edge cost function c(s,s') in the D*lite algorithm from the node connection distance to the unit grid distance. The unit grid distance generated by moving one grid horizontally or vertically is defined as 1, and the unit grid distance generated by moving one grid diagonally along the grid is defined as The sum of the unit grid distances generated between node s and its adjacent node s' is used as the improved edge cost function c'(s,s');

S32: Improve the cost function rhs(s): use the cost function rsh(s) in the D*lite algorithm as the path cost, and introduce the classified grid navigation risk value RIO' in S2 into the path cost as Risk cost, use the path cost weight I ₁ and the risk cost weight I ₂ to perform a weighted sum of the path cost and risk cost to obtain the improved cost function rhs'(s);

S4: Improve the node expansion neighborhood for node expansion: the neighborhood creates a priority queue U based on the node expansion process in the D*lite algorithm, puts the target node described in S3 into the priority queue U and starts node expansion of surrounding nodes. The range of node expansion in the D*lite algorithm is improved from 8 neighborhoods to 32 neighborhoods. The 32 neighborhoods are 32 node areas in different directions among the surrounding nodes of each node in the grid environment map;

S5: Minimize the value of the cost function rhs'(s) to obtain the optimal path: use the improved edge cost function c'(s,s') described in S32 and the improved cost function rhs'(s) described in S33 in sequence Perform node expansion on each intermediate node and starting node in the raster environment map and obtain the minimum value of the cost function rhs'(s) of each node, and add the node cost function of each path in the starting node and target node. The path with the smallest sum of rhs'(s) values is regarded as the optimal path;

S6: Replan the optimal path: The ship V starts to move from the initial node along the optimal path in S5. Each time a node is moved, it is checked whether new obstacles appear in the grid environment map, that is, whether new dangerous grids appear. If a new dangerous grid appears, update the node variables of the node where the dangerous grid is located and the affected nodes, and repeat step S5 to re-plan the optimal path until the ship V sails to the target location.

Preferably, the calculation process of the comprehensive navigation risk value RIO _V of the ship in each grid navigation process in S1 is:

RIO _V =∑C _T ×RV _V,T

Among them, V represents the ship type, T represents the sea ice type, C _T refers to the density of T type sea ice in the grid, and the value range is [0,1]; RV _{V, T} refers to the situation of ship V in T type sea ice. The navigation risk index of ships sailing in ice-covered areas, RIO _V is the comprehensive navigation risk value of ship V sailing in each grid under complex ice conditions.

Preferably, the grid classification method in S2 is: mark the grids whose comprehensive navigation risk value RIOV is less than 0 in S1 as dangerous grids, and mark the 8 grids on the first layer around the dangerous grids as risks. Grids, unlabeled grids are free grids.

Preferably, the grid navigation risk value RIO’ described in S2 is expressed in the following form:

Among them, RIO _risk is the comprehensive navigation risk value corresponding to the risk grid, RIO _freedom is the comprehensive navigation risk value corresponding to the free grid, and RIO _danger is the comprehensive navigation risk value corresponding to the danger grid.

Preferably, the positional relationship between the nodes in the 32-neighborhood described in S4 is represented by different values of each element in the 7*7 matrix N _32. The expression of the matrix N ₃₂ is:

Among them, the most central element in the 7*7 matrix N ₃₂ , that is, the element in the fourth row and fourth column represents the current node S, and the other elements respectively represent the neighborhood of the corresponding element position in the three layers around the previous node S. In the matrix N32 The neighborhood corresponding to the element with an element value of 1 is the 32 extendable neighborhoods of the current node S.

Preferably, the edge cost function c’(s,s’) obtained after the improvement of S31 is:

Among them, s and s' are adjacent nodes, and node s can move to the position of node s'. x _s and y _s are the abscissa and ordinate values of node s respectively. x _s' and y _s' are respectively The horizontal and vertical coordinate values of node s'.

Preferably, the improved cost function rhs’(s) described in S32 is:

Among them, s is the current node, RIO' is the navigation risk value RIO' of the classified grid described in S2, Succ(s) is the set of all other nodes that can be traveled from the current node s, I ₁ is the path cost weight, I ₂ is the sea ice risk cost weight, c'(s,s') is the improved edge function described in S31, and g(s') is the function estimate at node s'.

Preferably, the implementation process of node expansion described in S4 is:

S41: Create a priority queue U and set the key value k, select the node with the smallest key value K in the priority queue U as the expansion node, and use the nodes in the 32-neighborhood around the expansion node as the node to be expanded;

S42: Taking the target node as the starting point, initialize the cost function value rhs'(s) of the target node to 0, initialize the cost function rhs'(s) of other nodes except the target node to ∞, and set the keys of all nodes to ∞. The initial value of the value K and the cost function value g(s) is ∞. Put the target node into the priority queue U, assign a value to the expansion node in the priority queue U and assign the cost function value rhs' of the node to be expanded. (s) and key value K are updated, and the nodes to be expanded whose updated rhs'(s) value and g(s) value are not equal are put into the priority queue U, and the expansion continues until the node to be expanded becomes the starting node.

Preferably, the process of assigning values to the extension node in S42 is: assigning the extension node's own cost function value rhs'(s) to its own cost function value estimate g(s);

Preferably, the process of updating the cost function value rhs'(s) and key value K of the node to be extended in S42 is: using the function value estimate g(s) of the extended node and the improved edge cost The sum of functions c'(s,s') calculates the cost function value rhs'(s) of the expansion node, using the cost function value rhs'(s) of the expansion node and the heuristic function h(s,s') Calculate the K value of the extended node.

The invention has the following beneficial effects:

The present invention proposes an improved D*Lite polar ship dynamic path planning method. Combined with POLARIS, the comprehensive navigation risk value RIO _V of ships sailing under complex ice conditions is introduced into the traditional D*lite algorithm, and combined with the path cost weights I1 and The risk cost weight I2 constructs a path planning algorithm for dual-objective optimization of risk and distance, thereby obtaining a smoother, safer, and more implementable dual-optimization path of risk and distance. Specifically, S1 builds a grid environment map based on the acquired sea ice data, uses the POLARIS system to quantify the navigation risk value of each grid, and makes a preliminary classification of the grids based on the quantification results. It can more accurately judge and locate dangerous grids in the environment, and optimize the path in time when the environment changes; S2: Grid classification of the grid environment map described in S1 introduces a safety factor W: Passed The eight grids adjacent to the danger grid are marked as risk grids, and a safety factor ω is introduced in the risk grid to expand the comprehensive navigation risk value of the risk grid by ω times, reducing the risk of the risk grid being The probability of selecting the optimal path avoids the dangerous situation of the ship passing through the obstacle vertex diagonally, which greatly improves the safety of the ship in actual navigation; S3: Expand the search neighborhood: In the grid environment, use N32 The matrix form expands the neighborhood search direction of the target point from 8 neighborhoods to 32 neighborhoods, allowing the ship to move in 32 different directions during navigation, reducing the angle between the ship's sailing directions, thus greatly improving the path Smoothness. When the path smoothness, path length and time performance of the 32-neighborhood search algorithm and the 48-neighborhood and 56-neighborhood algorithms are equivalent, the 32-neighborhood search algorithm achieves lower complexity and higher efficiency; maximizing the single-time improvement The search range of the neighborhood reduces the number of searches during the entire voyage, shortening the length of the path and the voyage time. S4: Construct the edge function c'(N,N _m ) between adjacent nodes under sea ice risk, using the different distances between horizontal and vertical movement along the grid and diagonal movement along the grid in the grid environment map, Distinguishing the actual distance costs generated by moving in different directions corresponding to the 32 neighborhoods avoids the reduction in search efficiency caused by multiple expansion nodes with equal path costs during node expansion, and is also closer to reality. The path cost value during navigation greatly improves the calculation efficiency and accuracy; S5: Construct the comprehensive cost function rhs ₁ (N) of each node under the sea ice risk environment: By introducing the sea ice comprehensive navigation risk value, high latitude, weather, Sea ice and other factors that have a greater impact on the actual navigation of ships are added to the D*lite algorithm. The original distance cost of the original D*lite algorithm is used as the path cost, and the classified navigation risk value RIO' of each grid under the sea ice risk environment is As the risk cost, the path cost weight I1 and the risk cost weight I2 are introduced to construct the comprehensive cost function rhs ₁ (s). The original D* algorithm only considers the distance cost and improves it to consider the cost of distance and risk at the same time to achieve the distance With the purpose of dual optimization of risk and risk, the pre-planned route can avoid most high-risk sea ice areas in actual navigation, greatly improving the safety of navigation in polar seas. S6: Use the D*lite algorithm and the edge function c'(N,N _m ) and comprehensive cost function rhs ₁ (N) constructed by S4 and S5 to compare the comprehensive cost function values of all nodes in the raster environment map mentioned above. Neighbor node iteration, in each adjacent node iteration, select the node with the smallest comprehensive cost function value as the iteration starting point of the next iteration, so that the comprehensive cost function value passed to the predecessor node of the next iteration is as small as possible, thus obtaining The optimal path is optimized with the dual objectives of distance and risk, and when the environment changes, the parameter information of each node is updated in a timely manner to quickly re-plan the path, which can reduce navigation risks while taking into account navigation efficiency.

Description of the drawings

Figure 1. Flowchart of an improved D*Lite polar ship dynamic path planning method.

Figure 2 POLARIS system’s RV value lookup table for ice navigation risk assessment of various types of ships.

Figure 3 Position relationship diagram between risk grid and hazard grid.

Figure 4 Traditional D*lite algorithm edge path calculation process diagram.

Figure 5 is a diagram of the edge path calculation process after improving the edge cost function.

Figure 6 Traditional 4-neighbor D*Lite algorithm path diagram.

Figure 7. Improved 32-neighborhood D*Lite algorithm path diagram.

Figure 8 Comparison of path lengths using different algorithms for path planning.

Figure 9 Comparison of the number of path inflection points using different algorithms for path planning.

Figure 10 Comparison of sea ice risk numbers using different algorithms for path planning.

Detailed ways

The present invention will be further described below in conjunction with the accompanying drawings and examples.

A dynamic path planning method for polar ships with dual-objective optimization of distance and risk. The overall flow chart of the specific method is shown in Figure 1. The specific steps are as follows:

S1: Construct a grid environment map and calculate the comprehensive navigation risk value of navigation in each grid. RIO _V : Obtain the sea ice longitude and latitude data, sea ice type data and sea ice density data in the planned path area, and use the sea ice longitude and latitude The data constructs a grid environment map composed of grids of the same size, selects the ship V for navigation, and uses the sea ice type data to find the ship navigation risk index RV _{V of the ship V under various types of sea ice in the POLARIS system. T} , the RV table of ice navigation risk assessment for various types of ships in the POLARIS system is shown in Figure 2. The complex ice is calculated by weighting the sum of the products of the ship navigation risk index RV _{V, T} and the sea ice density data. The comprehensive navigation risk value RIO _V of ship V sailing in each grid under the conditions;

S2: Carry out grid classification and introduce safety factor ω: classify the grids in the grid environment map into dangerous grids, risk grids, and free grids according to the comprehensive navigation risk value RIO _V ; risk grids and dangerous grids The position relationship diagram of is shown in Figure 3. The constant ω is set as the safety factor. The comprehensive navigation risk value RIO _V is processed segmentally according to the type and safety factor of the grid classification to obtain the classified grid navigation risk value RIO. ';

S3: Introduce the nodes and node variables in the D*lite algorithm into the grid environment map. The nodes include the starting node, the target node and the intermediate node. The node variables include the edge cost function c(s,s') , cost function rhs(s), cost function estimate g(s) and heuristic function h(s,s'), for the edge cost function c(s,s') and cost function rhs(s) in the node variables ) to make improvements;

S31: Improve the edge cost function c(s,s'): The traditional D*lite algorithm edge path calculation process is shown in Figure 4. The independent variables of the edge cost function c(s,s') in the D*lite algorithm are The distance from the node connection is improved to the unit grid distance. The unit grid distance generated by moving one grid along the horizontal or vertical direction of the grid is defined as 1, and the unit grid distance generated by moving one grid along the diagonal direction of the grid. defined as The sum of the unit grid distances generated between node s and its adjacent node s' is used as the improved edge cost function c'(s,s'), and the improved edge path calculation process diagram of the edge cost function is: As shown in Figure 5;

S32: Improve the cost function rhs(s): use the cost function rsh(s) in the D*lite algorithm as the path cost, and introduce the classified grid navigation risk value RIO' in S2 into the path cost as Risk cost, use the path cost weight I ₁ and the risk cost weight I ₂ to perform a weighted sum of the path cost and risk cost to obtain the improved cost function rhs'(s);

S4: Improve the node expansion neighborhood for node expansion: the neighborhood creates a priority queue U based on the node expansion process in the D*lite algorithm, puts the target node described in S3 into the priority queue U and starts node expansion of surrounding nodes. The range of node expansion in the D*lite algorithm is improved from 8 neighborhoods to 32 neighborhoods. The 32 neighborhoods are 32 node areas in different directions among the surrounding nodes of each node in the raster environment map. Figure 6 shows the traditional D*lite algorithm neighborhood diagram, Figure 7 is the path diagram after improving the neighborhood range neighborhood to 32 neighbors;

S5: Minimize the value of the cost function rhs'(s) to obtain the optimal path: use the improved edge cost function c'(s,s') described in S32 and the improved cost function rhs'(s) described in S33 in sequence Perform node expansion on each intermediate node and starting node in the raster environment map and obtain the minimum value of the cost function rhs'(s) of each node, and add the node cost function of each path in the starting node and target node. The path with the smallest sum of rhs'(s) values is regarded as the optimal path;

S6: Replan the optimal path: The ship V starts to move from the initial node along the optimal path in S5. Each time a node is moved, it is checked whether new obstacles appear in the grid environment map, that is, whether new dangerous grids appear. If a new dangerous grid appears, update the node variables of the node where the dangerous grid is located and the affected node, and repeat step S5 to re-plan the optimal path until the ship V sails to the target location, using different algorithms for path planning. The comparison of path length, path inflection point number and sea ice risk number are shown in Figures 8, 9 and 10 respectively.

Preferably, the calculation process of the comprehensive navigation risk value RIO _V of the ship in each grid navigation process in S1 is:

RIO _V =∑C _T ×RV _V,T

Among them, V represents the ship type, T represents the sea ice type, C _T refers to the density of T type sea ice in the grid, and the value range is [0,1]; RV _{V, T} refers to the situation of ship V in T type sea ice. The navigation risk index of ships sailing in ice-covered areas, RIO _V is the comprehensive navigation risk value of ship V sailing in each grid under complex ice conditions.

Preferably, the grid classification method in S2 is: mark the grids whose comprehensive navigation risk value RIOV is less than 0 in S1 as dangerous grids, and mark the 8 grids on the first layer around the dangerous grids as risks. Grids, unlabeled grids are free grids.

Preferably, the grid navigation risk value RIO’ described in S2 is expressed in the following form:

Among them, RIO _risk is the comprehensive navigation risk value corresponding to the risk grid, RIO _freedom is the comprehensive navigation risk value corresponding to the free grid, and RIO _danger is the comprehensive navigation risk value corresponding to the danger grid.

Preferably, the positional relationship between the nodes in the 32-neighborhood described in S4 is represented by different values of each element in the 7*7 matrix N _32. The expression of the matrix N ₃₂ is:

Among them, the most central element in the 7*7 matrix N ₃₂ , that is, the element in the fourth row and fourth column represents the current node S, and the other elements respectively represent the neighborhood of the corresponding element position in the three layers around the previous node S. In the matrix N32 The neighborhood corresponding to the element with an element value of 1 is the 32 extendable neighborhoods of the current node S.

Preferably, the edge cost function c’(s,s’) obtained after the improvement of S31 is:

Among them, s and s' are adjacent nodes, and node s can move to the position of node s'. x _s and y _s are the abscissa and ordinate values of node s respectively. x _s' and y _s' are respectively The horizontal and vertical coordinate values of node s'.

Preferably, the improved cost function rhs’(s) described in S32 is:

Among them, s is the current node, RIO' is the navigation risk value RIO' of the classified grid described in S2, Succ(s) is the set of all other nodes that can be traveled from the current node s, I ₁ is the path cost weight, I ₂ is the sea ice risk cost weight, c'(s,s') is the improved edge function described in S31, and g(s') is the function estimate at node s'.

Preferably, the implementation process of node expansion described in S4 is:

S41: Create a priority queue U and set the key value k, select the node with the smallest key value K in the priority queue U as the expansion node, and use the nodes in the 32-neighborhood around the expansion node as the node to be expanded;

S42: Taking the target node as the starting point, initialize the cost function value rhs'(s) of the target node to 0, initialize the cost function rhs'(s) of other nodes except the target node to ∞, and set the keys of all nodes to ∞. The initial value of the value K and the cost function value g(s) is ∞. Put the target node into the priority queue U, assign a value to the expansion node in the priority queue U and assign the cost function value rhs' of the node to be expanded. (s) and key value K are updated, and the nodes to be expanded whose updated rhs'(s) value and g(s) value are not equal are put into the priority queue U, and the expansion continues until the node to be expanded becomes the starting node.

Preferably, the process of assigning values to the extension node in S42 is: assigning the extension node's own cost function value rhs'(s) to its own cost function value estimate g(s);

Preferably, the process of updating the cost function value rhs'(s) and key value K of the node to be extended in S42 is: using the function value estimate g(s) of the extended node and the improved edge cost The sum of functions c'(s,s') calculates the cost function value rhs'(s) of the expansion node, using the cost function value rhs'(s) of the expansion node and the heuristic function h(s,s') Calculate the K value of the extended node.

It should be noted that the above-described specific embodiments can enable those skilled in the art to understand the present invention more comprehensively, but do not limit the present invention in any way. Therefore, although the present invention has been described in detail with reference to the accompanying drawings and examples, those skilled in the art will understand that the present invention can still be modified or equivalently substituted, and in short, nothing departs from the scope of the present invention. Technical solutions and improvements within the spirit and scope of the invention shall be covered by the protection scope of the invention patent.

Claims (10)

1. A polar region ship dynamic path planning method with double-target optimization of distance and risk is characterized in that,

s1: constructing a grid environment map and calculating a comprehensive navigation risk value RIO of navigation in each grid _V : acquiring sea ice longitude and latitude data, sea ice type data and sea ice concentration data of a planned path area, and constructing a grid structure with the same size by utilizing the sea ice longitude and latitude dataSelecting a ship V for sailing, and searching a ship sailing risk index RV of the ship V under various sea ices in a POLARIS system by utilizing the sea ice type data _V，T The ship navigation risk index RV _V，T Weighting the sum of products of the sea ice concentration data to obtain a comprehensive navigation risk value RIO of the ship V sailing in each grid under the complex ice condition _V ；

S2: grid classification is performed and a safety factor omega is introduced: according to the comprehensive navigation risk value RIO _V Classifying grids in the grid environment map into dangerous grids, risk grids and free grids; setting a constant omega as a safety coefficient, and classifying the comprehensive navigation risk value RIO according to the type of the grid classification and the safety coefficient _V Carrying out segmentation processing to obtain a classified grid navigation risk value RIO';

s3: introducing nodes and node variables in a D-lite algorithm into the grid environment map, wherein the nodes comprise an initial node, a target node and an intermediate node, the node variables comprise an edge cost function c (s, s '), a cost function rhs(s), a cost function estimated value g(s) and a heuristic function h (s, s '), and improving the edge cost function c (s, s ') and the cost function rhs(s) in the node variables;

s31, improving the edge cost function c (S, S'): the argument of the edge cost function c (s, s') in the D-lite algorithm is modified from the node connection distance to a unit grid distance, the unit grid distance generated by moving one grid in the horizontal or vertical direction of the grid is defined as 1, and the unit grid distance generated by moving one grid in the diagonal direction of the grid is defined asTaking the sum of unit grid distances generated between the node s and the adjacent node s ' as an improved edge cost function c ' (s, s ');

s32: improving a cost function rhs (S), namely taking a cost function rsh (S) in the D-lite algorithm as a path cost, introducing S2 the classified grid navigation risk value RIO' into the path cost as a risk cost, and utilizing a path cost weightI ₁ And risk cost weight I ₂ The path cost and the risk cost are weighted and summed to obtain an improved cost function rhs'(s);

s4, improving a node expansion neighborhood to perform node expansion: creating a priority queue U based on a node expansion process in a D-lite algorithm, putting the target node in the priority queue U, starting node expansion of surrounding nodes, and improving the node expansion range in the D-lite algorithm from 8 neighbors to 32 neighbors, wherein the 32 neighbors are node areas in 32 different directions in surrounding nodes of each node in the grid environment map;

s5, minimizing a cost function rhs' (S) value to obtain an optimal path: sequentially performing node expansion on each intermediate node and each starting node in the grid environment map by using the improved edge cost function c ' (S, S ') of S32 and the improved cost function rhs ' (S) of S33 to obtain a minimum value of the cost function rhs ' (S) value of each node, and taking a path with the minimum sum of the node cost function rhs ' (S) values of each path in the starting node and the target node as an optimal path;

s6: re-planning the optimal path: and (3) starting to move the ship V from the initial node along the optimal path in the step S5, checking whether a new obstacle appears in the grid environment map or not, namely whether a new dangerous grid appears, updating node variables of the node where the dangerous grid is located and the affected node if the new dangerous grid appears, and re-planning the optimal path in the step S5 until the ship V sails to the target position.

2. A polar vessel dynamic path planning method optimized by distance and risk double objectives as claimed in claim 1, characterized by said integrated navigation risk value RIO of the vessel during each grid voyage in S1 _V The calculation process is as follows:

RIO _V ＝∑C _T ×RV _V,T

wherein V represents the type of ship, T represents the type of sea ice, and C _T Refers to the concentration of T-type sea ice in the grid, and the value range is 0,1]；RV _V，T Refers to the ship V is inShip navigation risk index, RIO, for sailing in T-type sea ice covered area _V Is a comprehensive navigation risk value of the ship V sailing in each grid under the complex ice condition.

3. The polar vessel dynamic path planning method optimized by double targets of distance and risk according to claim 1, wherein the method of grid classification in S2 is: the comprehensive navigation risk value RIO of S1 _V Grids smaller than 0 are marked as dangerous grids, 8 grids of a first layer around the dangerous grids are marked as risk grids, and unlabeled grids are free grids.

4. The polar vessel dynamic path planning method optimized by double objectives of distance and risk as claimed in claim 1, wherein the grid navigation risk value RIO' in S2 is expressed in the following form:

wherein RIO _{Risk of} Is the comprehensive navigation risk value corresponding to the risk grid, RIO _{Free of} Is the comprehensive navigation risk value corresponding to the free grid, RIO _{Risk of} Is the comprehensive navigation risk value corresponding to the dangerous grid.

5. A polar vessel dynamic path planning method optimized by distance and risk double objectives as claimed in claim 3, characterized in that the positional relationship between nodes in said 32 neighbors of S4 is represented by 7*7 matrix N ₃₂ Represented by different values of the elements of the matrix N ₃₂ The expression mode of (2) is as follows:

wherein 7*7 matrix N ₃₂ The element in the center of the three layers, namely the element in the fourth row and the fourth column, represents the current node S, and the other elements respectively represent pairs in three layers around the previous node SAnd the neighborhood corresponding to the element with the element value of 1 in the matrix N32 is the 32 expandable neighborhood of the current node S.

6. The polar vessel dynamic path planning method optimized by double objectives of distance and risk according to claim 1, wherein the edge cost function c '(S, S') obtained after the improvement of S31 is:

wherein s and s 'are adjacent nodes, the node s can move to the position of the node s', and x _s And y _s Respectively the horizontal and vertical coordinate values of the node s, x _s’ And y _s’ Respectively the horizontal and vertical coordinate values of the node s'.

7. The polar vessel dynamic path planning method with distance and risk double objective optimization according to claim 1, wherein the modified cost function rhs' (S) of S32 is:

where S is the current node, RIO 'is the classification grid navigation risk value RIO' of S2, and Succ (S) is the set of all other nodes that can travel to from the current node S, I ₁ To be path cost weight, I ₂ For sea ice risk cost weight, c '(S, S') is the modified edge function of S31, and g (S ') is the function estimate at node S'.

8. The polar vessel dynamic path planning method with double optimization of distance and risk according to claim 1, wherein the implementation process of the node expansion in S4 is as follows:

s41, creating a priority queue U, setting a key value K, selecting a node with the minimum key value K in the priority queue U as an expansion node, and taking nodes in the 32 adjacent areas around the expansion node as nodes to be expanded;

s42, initializing a cost function value rhs '(S) of a target node to be 0 by taking the target node as a starting point, initializing cost functions rhs' (S) of other nodes except the target node to be ≡, setting the initial values of a key value K and a cost function value g (S) of all the nodes to be ≡, putting the target node into a priority queue U, assigning values to the expansion nodes in the priority queue U, updating the cost function value rhs '(S) and the key value K of the nodes to be expanded, putting the nodes to be expanded with unequal updated rhs' (S) values and g (S) into the priority queue U, and continuing expansion until the nodes to be expanded are the starting nodes.

9. The method for planning a dynamic path of a polar vessel with double optimization of distance and risk according to claim 8, wherein the assigning process of the expansion node in S42 is as follows: the own cost function value rhs'(s) of the extension node is assigned to its own cost function value estimate g(s).

10. The polar vessel dynamic path planning method with double optimization of distance and risk according to claim 8, wherein the updating process of the cost function value rhs' (S) and the key value K of the node to be expanded in S42 is as follows: calculating a cost function value rhs '(s) of the expansion node by using the sum of the function value estimated value g(s) of the expansion node and the improved edge cost function c ' (s, s '), and calculating a K value of the expansion node by using the cost function value rhs '(s) of the expansion node and a heuristic function h (s, s ').