Global path planning of unmanned vehicle based on fusion of A^* algorithm and Voronoi field

Abstract

Purpose

Since many global path planning algorithms cannot achieve the planned path with both safety and economy, this study aims to propose a path planning method for unmanned vehicles with a controllable distance from obstacles.

Design/methodology/approach

First, combining satellite image and the Voronoi field algorithm (VFA) generates rasterized environmental information and establishes navigation area boundary. Second, establishing a hazard function associated with navigation area boundary improves the evaluation function of the A^* algorithm and uses the improved A^* algorithm for global path planning. Finally, to reduce the number of redundant nodes in the planned path and smooth the path, node optimization and gradient descent method (GDM) are used. Then, a continuous smooth path that meets the actual navigation requirements of unmanned vehicle is obtained.

Findings

The simulation experiment proved that the proposed global path planning method can realize the control of the distance between the planned path and the obstacle by setting different navigation area boundaries. The node reduction rate is between 33.52% and 73.15%, and the smoothness meets the navigation requirements. This method is reasonable and effective in the global path planning process of unmanned vehicle and can provide reference to unmanned vehicles’ autonomous obstacle avoidance decision-making.

Originality/value

This study establishes navigation area boundary for the environment based on the VFA and uses the improved A* algorithm to generate a navigation path that takes into account both safety and economy. This study also proposes a method to solve the redundancy of grid environment path nodes and large-angle steering and to smooth the path to improve the applicability of the proposed global path planning method. The proposed global path planning method solves the requirements of path safety and smoothness.

Citation

Zhao, J., Ma, X., Yang, B., Chen, Y., Zhou, Z. and Xiao, P. (2022), "Global path planning of unmanned vehicle based on fusion of A^* algorithm and Voronoi field", Journal of Intelligent and Connected Vehicles, Vol. 5 No. 3, pp. 250-259. https://doi.org/10.1108/JICV-01-2022-0001

1. Introduction

Unmanned vehicles include unmanned surface vehicle (USV), unmanned aerial vehicle (UAV) and unmanned ground vehicle (UGV). In recent years, with the development of computer technology and the improvement of ship intelligence level, USV as a small marine autonomous navigation ship has attracted more and more attention. At present, USV is mainly applied to the field of civil and military, such as marine exploration, maritime rescue, environmental monitoring and military reconnaissance and so on (Liu et al., 2016; Liu and Bucknall, 2018; Zhou, 2020). To accomplish these tasks accurately and effectively, USV needs to complete the corresponding global path planning in different scenarios, so that USV can avoid surface obstacles to reach the designated task operation waters. Therefore, global path planning is the key of USV autonomous navigation on the water surface, which has great research value. Scholars at domestic and abroad have do a large number of studies on the global path planning of USV. Taking into account the safety and endurance of USV maritime navigation, the research is mainly carried out from two aspects: path length and path safety.

The research on path length is the studies of the economy of planning paths. In the study of USV’s path length, Chen et al. (2019) used A^* Algorithm to search for the shortest path close to the obstacle in the raster experimental environment. Song et al. (2019) propose a smoothness method for A^* algorithm path planning, which can shorten the path length, but the path close to obstacles cannot guarantee the safety of navigation. Long et al. (2018) improve the genetic algorithm (GA) by optimizing the initial population and designing the self-adaptive crossover probability and mutation probability, and the path planned by the improved GA is shorter than that of the traditional GA. Long et al. (2020) proposed a bacterial foraging optimization algorithm (BFOA) based on A^* Algorithm. The improved BFOA solves the problem of path discontinuity and obtains a path that is superior to ant colony algorithm (ACA) and GA in both time and distance. Zhang et al. (2019a) used the evaluation value of the turn as a part of the evaluation function when planning the path with the A^* algorithm and reduced the number of turns by increasing the cost of the turn, thereby further optimizing the search path. In the process of global path planning, the above methods can find a short path that can be navigated. But, most of these paths show the characteristics of not smooth enough and large steering angle, etc. In addition, due to the blind pursuit of the shortest path, the navigation path generated by the above method is closer to the obstacle, and there may be a certain risk of collision during the navigation. However, most of the above methods and experiments only aim to generate the shortest path and the optimal path, with less consideration given to the safe distance between the path and the obstacles.

The research on path safety is to ensure that the planned path maintains a certain safe distance from obstacles. Thus, in the study of USV’s safety as the main purpose, Xia et al. (2019) set up circular boundary for obstacles and use quantitative ACA (QACA) to search the area outside the circle boundary to achieve the goal of safe navigation. However, this method has certain limitations when the USV navigates in areas with long obstacles. Guo et al. (2019) use the Cumulative Detection Probability (CDP) as the objective function and fitness function of the search path of GA. The improved GA generates the planning path in the environment with a single obstacle. Zhou (2019) use Dijkstra’s algorithm to plan the path on the topological navigation map with boundary and expand the obstacle area by adding boundary to achieve the purpose of safe path planning. Fu et al. (2019) propose a method of artificial potential field (APF), which uses sensor information to solve local minimum. The method has got better path, but the navigation effect in “U” shape region is inefficiency. Bibuli et al. (2018) use A^* algorithm which can set the safe distance around the USV to generate a safe path for navigation. Candeloro et al. (2017) use Voronoi diagram (VD) method to segment the navigation space. The path on the Voronoi edge is the safest path, but the path smoothed by Fermat’s spiral is closer to the obstacles. Niu et al. (2016) use VD algorithm and Dijkstra’s algorithm to search the path and get a path which is farthest from all the obstacles, but it is not smooth enough. Zhang et al. (2019b) mix GA with simulate anneal arithmetic and carry out experiments in the raster chart environment, which solves the problem of insufficient searching ability and time consumption of traditional GA. Mousazadeh (2018) use Kalman Filtering, search ball and APF to carry on the experiment. Finally, the global positioning system data are processed by Kalman Filtering, and a route which can avoid static obstacles is fitted. Singh et al. (2018) use Dijkstra’s algorithm that can set distance to generate a safe path. Junyi et al. (2019) used an improved rapid-exploration random tree (RRT) algorithm to calculate the nearest neighbor with diagonal distance instead of the traditional Euclidean distance, and completed the path searches process in the imitation environment. Xiong et al. (2019) uses the Voronoi-based ant colony optimization method for path planning and solved the adaptive sampling problem, but the generated path was too tortuous. Although the above studies consider the safety of the path, insufficient consideration is still given to the smoothness and economy of the path.

The current research methods of ship path planning include A^* algorithm, dynamic window algorithm, GA etc., and continue to develop in the direction of cross-integration of intelligent algorithms and multidisciplinary methods and have achieved good results in solving the collision avoidance decision-making and autonomous navigation of unmanned ships. However, some studies do not take into account the economy of planned path when ensuring the safety of navigation to the greatest extent. In summary, most of the current research is unilaterally considering the shortest path and the farthest distance, and there is no suitable route for the specific ship type. This method aims at the common USV with a length of 3–11 meters in the “The Navy Unmanned Surface Vehicle (USV) Master Plan” announced by the US Navy and evaluates the path feasibility of the Fujii and Tanaka (1971) safety ellipse field with a length of 7 L and a width of 3 L (L stands for the length of ship) and selects a path for different captains to consider safety and economy. Fujii ship domain model shown in Figure 1.

To solve the above problems, this paper proposes a new global path planning method. The method consists of three parts: first, use satellite images and Voronoi field algorithm (VFA) to establish a navigation environment; then, based on the improved A^* algorithm for path planning, generate a path that takes both safety and economy into consideration; finally, optimize the path nodes and according to the paper (Xiong et al., 2019) on the requirements of path smoothness, the path is smoothed to improve the continuity of the path.

The main contributions of this article are as follows:

• Establish a navigation area boundary for the environment based on the VFA and use the improved A^* algorithm to generate a navigation path that takes into account both safety and economy.

• Propose a method to solve the redundancy of grid environment path nodes and large-angle steering and smooth the path to improve the applicability of the global path planning method proposed in this paper.

• The proposed global path planning method solves the requirements of path safety and smoothness.

The organization structure of this paper is as follows. Section 2 introduces the construction of the environmental model. Section 3 introduces the global path planning based on the improved A^* algorithm with controllable distance from obstacles. The path nodes optimization and path smoothing algorithm is described in Section 4. In Section 5, the simulation and results of USV global path planning will be presented. The conclusions are given in Section 6.

2. Maritime environment model construction based on satellite image and Voronoi field algorithm

2.1 Generalized Voronoi diagram

Generalized VD (GVD) is a space segmentation algorithm, which is widely used in path planning (Wang et al., 2013; Özcan and Yaman, 2019; Niu et al., 2020; Wu et al., 2013). It divides the space into many sub-regions through a series of seed points, and each sub-region is called a cell and the cells boundary is called Voronoi edge. If d(p_i, p_j) represents the distance between point p_i = (x_i, y_i) and point p_j = (x_j, y_j), the mathematical definition of the GVD is as follows (Seda and Pich, 2008):

Suppose that P = {p₁, p₂,…,p_n|p_i, ∈R^d, i = 1,2,…,n} is a set of seed points, and R^d represents that all seed points are coordinating points in a d-dimensional space. These n seed nodes divide the d-dimensional space into n cells, and the definition of each cell is as follows:

(1) V(pi)={x∈Rd|∀i≠j,d(x,pi)≤d(x,pj)}

where V(p_i) is a subset of V = {V(p_i),…,V(p_n)}; p_i is the i-th seed point of the VD.

From the definition, it can be known that the distance from all the points in each cell to the seed point is less than the distance to all other seed points, and the cell boundary is the set of points farthest from all the seed points. Since P = {p₁, p₂,…,p_n} is the seed sets of the VD. We can get the following:

(2) V(P)=∪pi∈PV(pi) =∪pi∈P{x∈Rd|∀q∈(P−{pi}),   d(x,pi)≤d(x,q)} =∪pi∈P[∩q∈(P−{pi}){x∈Rd|   d(x,pi)≤d(x,q)}] 

where V(P) is the collection of the cell of the VD.

It can be seen base on the definition that the GVD can be obtained by dividing the space of the navigation environment with the obstacle area as p_i. Taking the cells boundary of the VD as the navigation path, the farthest path from all obstacles can be obtained.

2.2 Voronoi field algorithm

The Voronoi field (Dolgov et al., 2008) is a dangerous potential field between the generalized Voronoi edge and obstacles. The field value is between [0, 1], according to the distance between the obstacle and the navigable water area, it is distributed proportionally between the Voronoi edge and the obstacles. The closer the area to the Voronoi edge, the closer the Voronoi field value is to 0, the safer it is. The closer the area to the obstacle, the closer the Voronoi field value is to 1, the more dangerous it is. The formula is as follows:

(3) ρV(x,y)=(αα+do(x,y))(dv(x,y)do(x,y)+dv(x,y)) ((do−domax⁡)2(domax⁡)2)

where d_o is the distance from the current node to the obstacle; d_v is the distance from the current node to the Voronoi edge; α > 0 is a constant that controls the falloff rate of the potential field; domax⁡>0 is a constant that controls the maximum effective range of the potential field.

The formula has three characteristics:

1. The expression in (3) is for do≤domax⁡; when do>domax⁡, the potential field value is 0.

2. ρV(x, y) ∈ [0,1] is continuous on (x, y), because there is no d_o = d_v = 0.

3. It can reach the maximum value of 1 in the obstacle area and the minimum value of 0 at the Voronoi edge of the VD.

Applying the VFA to the GVD, not only can see the navigable path farthest from the obstacle more clearly and intuitively, but also the Voronoi field value in the interval of [0,1] can be used to control the distance between the navigation path and the obstacle.

2.3 Environment modeling process

When preforming an experiment for a global path, firstly, the experimental environment is modeled based on the known information. Then, according to the modeling results, a searching space containing obstacle information is obtained, and a specific path searching algorithm is used to conduct path planning experiments. The navigation environment is the embodiment of the characteristics of the USV. The construction of the experimental environment is a crucial part of the global path planning process. The quality of the construction directly affects the accuracy of the path planning results. According to the relevant standards of the International Maritime Organization, commonly using navigation charts, which includes electronic charts, paper charts and satellite images. In this paper, satellite images are used to construct a rasterized environment model, and the grid method is commonly used to establish an environment model (Singh et al., 2018). Its modeling process is simple, the amount of calculation is small and it can intuitively represent the environment map traversal situation, which is convenient for the application in the USV actual sailing process.

First, the binary image is obtained by processing satellite images, where the value 0 (white) represents the navigable water area, and the value 1 (black) represents the obstacle, which is the non-navigable area. Then, the GVD algorithm is used to obtain the space segmentation map of the environment. Finally, the potential field value is added to each grid in the environment by using the VFA to obtain the rasterized environment model that stores the field value information. The environmental processing flow chart is shown in Figure 2.

3. Global path planning based on improved A^* algorithm

In the current global path planning research, the result of pursuing the shortest path is the planned path often closer to obstacles. When the USV follows the planned path, there is a risk of collision. However, in the research of path planning based on safety, the increase of path length poses certain challenges to the endurance of USV. Therefore, it is very necessary to propose a path planning method that takes into account both safety and path length. In this paper, based on the improved A^* algorithm, a global path planning method with a controllable distance from obstacles is proposed. In the planning process, the distance between the path and the obstacle is controlled by adding the boundary of the navigation area, and the path generated under different boundaries can be selected. The path takes into account both safety and economy.

3.1 A^* algorithm

A^* algorithm is a heuristic path search algorithm, which is widely used in the field of path planning. The A^* algorithm includes a four-connected area search method and an eight-connected area search method. Taking into account the kinematic characteristics of USV in the ocean, this paper uses the search method of eight-connected areas to plan the path in navigable waters. The eight-connected area search method is shown in Figure 3.

The definition of the A^* algorithm is as follows:

(4) f(n)=g(n)+h(n)

Where g(n) is the distance from the starting point to the current node; h(n) is the distance from the current node to the target node, using Euclidean distance for calculation, namely:

(5) h(n)=(xm−xn)2+(ym−yn)2

Where (x_m, y_m) is the coordinate of the target point; (x_n, y_n) is the coordinate of the current node.

3.2 Improved A^* algorithm

The A^* algorithm only uses the path length as a heuristic function. The planned path is often close to obstacles and cannot effectively guide the safe and smooth movement of the USV. In response to this problem, this paper uses the Voronoi field value to establish the concept of navigation area boundary to improve the evaluation function f(n) of the A^* algorithm, The improved A^* algorithm is used as the search algorithm in the path planning process.

3.2.1 Navigation area boundary

According to the introduction in Section 1, the environmental model is a grid map that stores field value information, and the navigation area boundary is established for the navigation area based on the field value. In this paper, when searching for a path, the Voronoi field value interval [0,1] is set as the navigation area boundary and set to 0–5 levels. Level 0 is the safest and Level 5 is the most dangerous. The boundary level of the navigation area and its corresponding Voronoi field value are shown in Table 1. Among them, because 0 is the collection of the space points farthest from all obstacles, the Voronoi field value is set as the navigation area boundary alone.

3.2.2 Improved evaluation function

The A^* algorithm takes the shortest path as the search target, and the planned path is closer to the obstacle. As sailing close to obstacles has a certain risk of collision, this paper takes the risk function D(n) as a part of the evaluation function, and the evaluation function is as follows:

(6) f(n)=g(n)+h(n)+D(n)

where g(n) and h(n) are same as those in Formula (4); D(n) is the risk function, and the risk is added to the grid by using the Voronoi field value. The definition of D(n) is as follows:

(7) D(n)={∞,ρv(n)>ρv*0,ρv(n)≤ρv*

where ρ_v(n) is the value of the Voronoi field at the point n; ρv* is the maximum Voronoi value corresponding to the level of the navigation area boundary.

With the addition of the risk function, the USV is only allowed to sail in areas not greater than the navigation area boundary level. That is, when the Voronoi field value of the path extension point is not greater than the maximum Voronoi value corresponding to the navigation area boundary level, D(n) is equal to 0; when the Voronoi field value of the path extension point is greater than the maximum Voronoi value corresponding to the navigation area limit level, D(n) is equal to the hazard degree at the obstacle, and the hazard degree of the obstacle area is set to infinity.

According to Formula (7), the evaluation function of each grid after adding the degree of risk can be defined as:

(8) f(n)={g(n)+h(n),ρv(n)≤ρv*∞                                      , ρv(n)>ρv*

By improving f(n) and choosing different sailing boundaries, different paths can be planned. By evaluating the path length and the shortest distance between the path and the obstacle, the optimal path can be selected.

4. Path node optimization and smoothing

4.1 Path node optimization

As this paper uses a rasterized environment, the generated path has the problems of large turning angles and many redundant points, which will cause difficulties in the redirection of the USV navigation process. Excessive steering angle does not conform to the navigation characteristics of USV, so the generated path nodes need to be optimized. The schematic of path node optimization is shown in Figure 4. First, delete the collinear node, as shown in Figure 3, for p₃, p₄ and p₅ are collinear, p₄ is the middle point of the collinear, delete p₄. Then, at the waypoint with a larger turning angle, connect the interval nodes of the waypoint to determine whether the connection crosses the obstacle. If the two interval nodes are connected with a straight line and clear of the obstacle, delete unnecessary nodes in the middle. As shown in Figure 3, for p₁, p₂ and p₃, the turning angle at the p₂ is relatively large. After judging that p₁ and p₃ are connected in a straight line, the obstacle is not crossed, then the intermediate point p₂ is deleted. Before optimization, the path node is N = {p₁, p₂,…,p₈} and maximum steering angle is 90^°; after the node optimization, the path node is N = {p₁, p₃, p₅, p₇, p₈} and maximum steering angle is 45^°. After the path is optimized, the steering angle of the path decreases and the number of nodes reduces.

4.2 Path smoothing

For the USV to pass the turning point smoothly during navigation, it is essential to smooth the generated path. Path smoothing is achieved by minimizing the following two goals (Fedorenko and Gurenko, 2016):

(9) norm(Pi−Si)→min⁡

(10) norm(Si−Si+1)→min⁡

where P-represents the original path, S-represents the smoothed path.

To minimize the two expressions, define the following smoothing cost function:

(11) Cost=α‖Pi−Si‖+β‖Si−Si+1‖

where α is the weight coefficient of the original path; β is the smooth weight coefficient.

The first term of the cost is used to measure how much the smoothed points deviate from the original point, and the second term is used to measure the distance between the smoothed points. The smoothing process is the process of minimizing the cost, because these two checks and balances each other. Among them, α and β are the parameters of the degree of smoothness of the target route. The larger α is relative to β, the closer the smoothed point is to the original point; in contrast, the smoother the path. The method of finding the optimal solution to cost adopts the gradient descent method (GMD), through multiple iterative adjustments, the function obtains the minimum value. Processing as follows:

• Starting point: S_i is equal to P_i, where i = [1,…,n];

• Iteration: traverse all points except the start point and the end point and update S_i.

  (12) Si=Si+α(Pi−Si)+β(Si−1+Si+1−2Si)

• Iterate until the upper limit of the number of iterations or the gradient of the cost function drops to the specified threshold.

The schematic of path smoothing is shown in Figure 5. In Figure 4, the blue solid line represents the original path, the red dashed line represents the smooth path and the yellow dashed line (p2p2′) denotes the offset of the turning point before and after smoothing. The smoothing algorithm is used to solve the problem of unsmooth path at the steering angle.

5. Simulation experiment

The rationality and effectiveness of the proposed global path planning method are verified in this section. This section is divided into two parts. The first part introduces the experimental environment and its construction. The second part conducts the path planning experiment and discusses the experimental results. First, select the satellite image in the range of Latitude: 0°58′N ~ 1°2′N, Longitude:104°6′E ~ 104°10′E and process it into a 485 × 485 grid map as the global path planning scene (every grid is equal to 15.27 m), and then the path planning experiment is carried out through the proposed algorithm. Experiments have proved that the proposed algorithm can select a path that takes into account the safety and economy of navigation for the USV with a length of 3–11 meters and provide navigation guidance for the USV mission process.

5.1 Experimental environment

Before the start of the experiment, to set the navigation area boundary, the satellite image was processed according to the algorithm flow in Section 2.3, and the rasterized image with Voronoi field values was obtained after processing. The environmental processing process is shown in Figure 6. To control the distance between the path and the obstacle, set the navigation area boundary for the environment, the USV can only navigate within the designated area boundary. Figure 7 shows a schematic diagram of the navigational area boundary levels.

To clearly reflect the experimental results, this paper generates the planned path on a binary image. The red solid circle in the environment is the grid where the pixel coordinates of the ship is located, as the starting point; the green star is the grid where the pixel coordinates of the goal is located, as the end point. The experimental scene is shown in Figure 8.

5.2 Results and discussion

To prove the rationality and effectiveness of this method in USV path planning, experiments were carried out under different navigation boundaries, and the path lengths of the six groups of experiments and the closest distances between the path nodes and obstacles were obtained as the evaluation criteria of the experimental results. The comparison of the result data under different navigation boundaries is shown in Table 2. The comparison of the number of nodes before and after path optimization in Table 2 proves the effectiveness of the node optimization algorithm proposed in this paper. Analyzing the length of the smooth path shows that the path length fluctuates from 0% to 8.39% compared with the shortest path, which also conforms the fact that the generated path is more economical in the same conditions. Among them, the Navigation boundary level 2 to level 4 fluctuates from 0% to 1.56%, which can ensure economy and safety at the same time, and the optimal path can be obtained according to the distance requirements when sailing in USV. Taking the requirements of Fujii safety domain model as the distance standard, it can be seen that the USVs of different lengths of 3–11 meters can match the paths that meet the safety and economy in the experimental results, which proves the feasibility of the proposed algorithm in practice.

In this paper, the comparison results of the original paths and the smoothed paths of the six groups of experiments are shown in Figure 9. When the navigation area boundary is 0, the navigation path is generated near the Voronoi edge, which is the path farthest from the obstacle. When the navigation area boundary is 5, the experimentally generated navigation path is the shortest but close to the obstacle. The results of global path planning under different navigation area boundaries are shown in Figure 9. The blue solid line in the figure is the original planned path, and the red solid line is the path after node optimizing and smoothing.

In Figure 9, it can be seen that the proposed algorithm can generate paths with different distances from obstacles according to the navigation limits. The lower the navigation area limit level, the farther away the obstacles are. From the comparison of the effects of the original path and the smoothed path in Figure 9, it can be seen that the smoothed path better guarantees the continuity of the path and the smoothing effect at the corner conforms to the motion characteristics of the USV.

As can be seen from Figure 10, the processed resulting path is significantly smoother than the original path. In summary, by setting the boundaries of different navigation areas, this method can choose the most appropriate route according to the different magnitudes of ships. This can not only meet the navigation requirements of the distance between the ship and the obstacles, so as to control the distance between the path and the obstacle but also select a shorter path from multiple paths to consider its economy and safety.

Table 3 shows the statistical result of path planning under RRT algorithm and Dijkstra Algorithm. Figure 11 shows the path planning results under different methods. Blue represents the planning results of RRT, and magenta represents the planning results of Dijkstra algorithm. It can be seen from the figure that the paths planned by the two methods are close to obstacles, which is not conducive to actual navigation. The data of the method in this paper are shown in Table 2. Combining Table 3 with Figure 11, it can be seen that the algorithm proposed in this paper is superior to all indicators of Dijkstra algorithm under the same safety distance. Although the RRT algorithm is superior to the algorithm presented in this paper in terms of node number, it is inferior to the proposed algorithm in terms of economy and safety.

In the open scene, the method proposed in this paper is not only suitable for USV but also suitable for global path planning of UAV and UGV.

6. Conclusions

Aiming at the problem that cannot be balanced between safety and economy in the current USV global path planning research. In this paper, the VFA is used to establish the boundary of the navigation area in the environment to ensure the safety of USV. Using the hazard function to improve the evaluation function of the A^* algorithm, the improved A^* algorithm can generate safety and economic paths under different navigation area boundaries. In the USV mission process, the planned path can be selected according to specific requirements. For the problem of node redundancy and lack of smoothness in the planned path, a hybrid path smoothing algorithm is proposed. The global path planning system is evaluated through experiments in a satellite image environment. From the experimental results, it can be seen that the USV global path planning method that can control the distance from obstacles proposed in this paper has a better effect. The path smoothing effect of using node optimization and GDM can ensure the continuity of the path, which is in line with the kinematics characteristics of USV in the marine environment. The experimental results prove that the algorithm proposed in this paper has certain reference value in USV global path planning. In future work, consider putting dynamic obstacles into the experimental environment. At the same time, we will try to optimize the A^* algorithm and deeply integrate the A^* algorithm and the VFA to improve the search efficiency of path planning.

Figures

Figure 1

Fujii ship domain model

Figure 2

Flow chart of environment processing

Figure 3

8-directional search pattern of A^* algorithm

Figure 4

Schematic of node optimization

Figure 5

Path smoothing diagram

Figure 6

The process of environmental potential field

Figure 7

Navigation boundary level map

Figure 8

Experimental environment of path planning

Figure 9

Path planning results under different navigation boundaries

Figure 10

Smoothing effect displayed under improved A^* algorithm

Figure 11

Path planning results under different algorithms

Table 1

Navigation area boundary and its corresponding Voronoi field value

Navigation boundary level	The Voronoi value corresponding to the boundary level
0	0
1	(0, 0.2)
2	[0.2, 0.4)
3	[0.4, 0.6)
4	[0.6, 0.8)
5	[0.8, 1)

Table 2

Comparison of optimization results under different navigation boundaries

Navigation boundary level	Original nodes/Optimization nodes	Original path length/km	Smoothed path length/km	The shortest distance between the original path and the obstacle/m	The shortest distance between the smoothed path and the obstacle/m
0	537/357	9.53	9.04	112.16	126.74
1	490/273	9.00	8.66	106.89	108.42
2	464/234	8.76	8.47	61.08	51.92
3	448/213	8.62	8.40	45.81	42.32
4	439/183	8.53	8.35	42.76	40.59
5	432/116	8.47	8.34	15.27	16.80

Table 3

Path planning results under different methods

Methods	The total number of nodes	Path length/km	The shortest distance between the path and the obstacle/m
Dijkstra	431	8.46	15.27
RRT	40	9.02	30.54