Improved A-Star Algorithm for Long-Distance Off-Road Path Planning Using Terrain Data Map

Abstract

To overcome the limitation of poor processing times for long-distance off-road path planning, an improved A-Star algorithm based on terrain data is proposed in this study. The improved A-Star algorithm for long-distance off-road path planning tasks was developed to identify a feasible path between the start and destination based on a terrain data map generated using a digital elevation model. This study optimised the algorithm in two aspects: data structure, retrieval strategy. First, a hybrid data structure of the minimum heap and 2D array greatly reduces the time complexity of the algorithm. Second, an optimised search strategy was designed that does not check whether the destination is reached in the initial stage of searching for the global optimal path, thus improving execution efficiency. To evaluate the efficiency of the proposed algorithm, three different off-road path planning tasks were examined for short-, medium-, and long-distance path planning tasks. Each group of tasks corresponded to three different off-road vehicles, and nine groups of experiments were conducted. The experimental results show that the processing efficiency of the proposed algorithm is significantly better than that of the conventional A-Star algorithm. Compared with the conventional A-Star algorithm, the path planning efficiency of the improved A-Star algorithm was accelerated by at least 4.6 times, and the maximum acceleration reached was 550 times for long-distance off-road path planning. The simulation results show that the efficiency of long-distance off-road path planning was greatly improved by using the improved algorithm.

1. Introduction

Optimising planning paths is crucial for identifying safe and efficient driving paths for off-road path-planning tasks. Especially, long-distance off-road path planning is highly challenging in a 3D environment [1]. The key problem of long-distance off-road path planning is slow and inefficient, different from 2D path planning [2]. Therefore, the quick completion of long-distance off-road path planning in a 3D environment has always been a hot and difficult problem for researchers.

The purpose of path planning is to plan the optimal path between the starting and end points when there are obstacles [3]. This technology is widely used for autonomous vehicles [4], mobile robots [5], indoor path finding [6], and planetary and space missions [7]. The path-planning problem can be viewed as the problem of mapping which grid elements are part of the path being sought [8]. Digital Elevation Models (DEM) yield a type of grid data that can be obtained by remote sensing satellites. Each grid unit represents the corresponding position and height, which is a commonly used technique for describing off-road terrain. For path planning problems, most constraints can be derived from DEM [9]. To obtain 3D paths that meet the needs of field path planning tasks, it is appropriate to adopt terrain data maps based on DEM datasets for path planning.

Path planning is generally divided into global and local path planning [10]. Global path planning is based on static map data, whereas local path planning is based on real-time traffic environment data. In the global path planning method [11], there are evolutionary algorithms, such as ant colony [12], genetic [13], and grid-based algorithms, including the Dijkstra algorithm [14] and A-Star algorithm [15]. Evolutionary algorithms are often considered optimal for local use, and their computational costs are high. The Dijkstra algorithm is inefficient owing to over-searching of non-optimal path nodes. The A-Star algorithm uses a heuristic function to calculate the value of the heuristic function of path nodes and obtain the optimal solution, which is highly efficient [16]. Moreover, the A-Star algorithm is more suitable for global path searching of static grid data.

Scholars have designed several variants of the A-Star algorithm for path planning. Duchon et al. [17] dealt with path planning of a mobile robot based on a grid map. Panov et al. [8] used a neural network for path planning on grid data. Zhang et al. [18] adopted the key point selection strategy for secondary planning to reduce the planning time of path-redundant nodes. Shang et al. [19] improved the efficiency and obstacle avoidance ability of the A-Star algorithm by using guidelines and key points. Wang et al. [20] settled problems of shortest path planning and collision by introducing turning factors to solve multiple shortest path problems. However, the calculation amount of the A-Star algorithm increases sharply with the increase in spatial dimension, which makes it unsuitable for long-distance off-road path planning tasks in 3D environments. Hierarchical Path-Finding uses a hierarchical system to reduce the complexity of path planning. It is more efficient that the path planning process on the low level. However, it fails to achieve the optimal solution in most cases [21]. The existing A-Star algorithm is suitable for path-planning tasks in a small range of datasets. There are few studies on the A-Star algorithm for path-planning tasks with a range of more than 20 × 20 km².

To address the problems associated with off-road long-distance path planning tasks, an improved A-Star algorithm based on a terrain data map is proposed herein. The proposed A-Star algorithm reduces the execution time and improves the efficiency of the algorithm without changing the path node search process of the conventional A-Star algorithm. Data structure and retrieval strategy are the two aspects of this algorithm improvement. To test the validity of the proposed algorithm, short-, medium-, and long-distance path planning tasks with distinct terrain characteristics were designed. Compared with the conventional A-Star algorithm, the maximum acceleration of the off-road long-distance path planning reached was 550 times by using the improved A-Star algorithm.

The remainder of this paper is organised as follows. Section 2 describes the study area and the dataset used in the study. Section 3 introduces the conventional A-Star algorithm and the proposed improved A-Star algorithm. In Section 4, the effectiveness of the algorithm is verified through several groups of comparative experiments and the research results are presented. Finally, Section 5 presents the conclusions.

2. Related Work

Path planning has aroused interest in the research community. Zambrano et al. [22] realised the balance of traffic flow, and effectively reduced traffic congestion, through the proposed urban traffic route server. Xu et al. [23] proposed a complete coverage neural network algorithm and an improved A-Star algorithm for path planning of unmanned surface vehicles, which made the generated complete coverage path have fewer path turns and deadlocks. Borkowski et al. [24] interpolated the ship state vector with the proposed interpolation function on the basis of the improved Dijkstra algorithm, so as to determine the anti-collision manoeuvre trajectory of the ship in open waters.

The off-road path planning task is carried out on static grid data in the off-road environment. Due to different task requirements, the path planning task is faced with long distance and more complex terrain. Wang et al. [25] used a hierarchical system based on the conventional A-Star algorithm to save memory and CPU resources. However, the hierarchical system was not suitable for the off-road path planning task that does not consider road network and other environmental information. The efficiency of grid-based path planning depends largely on the number of retrieval nodes and retrieval speed. To improve the efficiency of path planning tasks, especially path planning tasks for long distance and complex terrain, data structure or search method can be used for fast retrieval. A-Star is the baseline of the prototype and changes the grid-based planning method [26], so improvement based on A-Star algorithm was adopted.

In this section, we review the bidirectional A-Star search which is a variation of A-Star path planning method.

The bidirectional A-Star search introduced a two direction heuristic search algorithm, based on the conventional A-Star search algorithm. The bidirectional A-Star algorithm with the advantage of the small search volume, helps to speed up the path search in both search directions and terminate the search process earlier [27]. Bidirectional search is divided into forward search and backward search, in which forward search is from the current point to the end point, and backward search is from the current point to the start point. Additionally, the forward search and backward search are performed alternately. The bidirectional A-Star search is terminated in advance to improve the efficiency of path planning, by determining the intersection point of forward search and backward searches.

Most of the existing path planning optimisation methods may lead to a disaster in terms of search time due to the large depth of recursion or the enormous number of retrieval nodes. Moreover, previous methods had rarely been tested on large-scale data maps. Hence, we compared the bidirectional A-Star search and the conventional A-Star algorithm with the proposed improved A-Star algorithm. The result verified that the improved A-Star algorithm improves the efficiency to solve the time requirements in the long-distance off-road path planning task.

3. Study Area and Data Set

3.1. Study Area

Considering the representativeness of the experiment, a terrain area with obvious topographical characteristics was selected as the study area. The selected area spans 260 × 260 km² in Jiangxi Province and surrounding provinces in China and extends approximately 3° × 3° from 111°30 N latitude and 25°00′ E longitude. The Region of Interest (ROI) is shown in Figure 1.

The elevation of the ROI in the study area is used as the slope constraint basis for off-road path planning. The feasible region was mapped according to different off-road vehicle feasible gradient threshold value divisions based on different corresponding feasible slope thresholds of off-road vehicles. The area on the left side of the map has a lower elevation than that on the right side. The terrain on the right side of the map changes significantly while that on the left side of the map changes minimally.

3.2. Data Set

Many public datasets, such as the SRTM1, GSDEM-30, and AW3D30 DEM datasets, have resolutions of 30 m. However, the vehicle is regarded as a particle for path planning in the off-road path planning task, and high resolution DEM yield the best datasets for path planning tasks. In this study, Sentinel-1 SAR image interferometry was used to produce a DEM with a resolution of 20 m. Sentinel-1 data were obtained from Copeernicus Open Access Hub (https://scihub.copernicus.eu/, accessed on 17 November 2021). Sentinel-1 DEM was generated using the Sarscape plugin processing in the ENVI software. The DEM data used in this study was 20 m resolution. It had 13,139 × 13,245 cell data, equivalent to the actual area of about 69,610.4 km².

In 3D environments, terrain gradient information is an important parameter that affects path planning tasks. Based on an analysis of the terrain gradient characteristics of the DEM, the feasible and infeasible areas were designated to evaluate whether the path is suitable for different off-road vehicles and determine which obstacles can be passed.

In this study, only the slope values of DEM were calculated without considering the slope aspect. It was assumed that the projected area of the vehicle is a grid unit. According to the grid unit (i,j) (corresponding elevation is $Z_{i,j}$) and eight surrounding grid units, a 3 × 3 window is formed, as shown in Figure 2. Using this information, the slope in the X direction $Slop{e}_{we}$ and the slope in the Y direction $Slop{e}_{sn}$ were calculated using Equations (1) and (2), respectively:

$$Slop{e}_{we}=\frac{\left(Z_{i+1,j-1}+2\times Z_{i,j-1}+Z_{i-1,j-1}\right)-\left(Z_{i+1,j+1}+2\times Z_{i,j+1}+Z_{i-1,j+1}\right)}{8\times CellSize}$$

(1)

$$Slop{e}_{sn}=\frac{\left(Z_{i+1,j+1}+2\times Z_{i+1,j}+Z_{i+1,j-1}\right)-\left(Z_{i-1,j+1}+2\times Z_{i-1,j}+Z_{i-1,j-1}\right)}{8\times CellSize}$$

(2)

where $CellSize$ is the interval length of grid DEM.

The slope of the grid unit $\left(i, j\right)$ can be described using Equation (3).

$$Slop{e}_{i,j}=arctan\sqrt{Slop{e}_{we}^2+Slop{e}_{sn}^2}$$

(3)

The DEM in the study area was transformed into a slope map using the method described above. The terrain data map was generated by combining the feasible slope thresholds of off-road vehicles. Any pixel whose slope is greater than the threshold value is infeasible, and vehicles with a high feasible slope threshold can pass through the low feasible slope threshold area. The application of the feasible slope threshold is illustrated in Figure 3.

4. Global Path Planning

4.1. A-Star Path Planning Algorithm

The conventional A-Star algorithm is a popular heuristic search algorithm for off-road path planning. It calculates the feasible finite-sequence shortest path from the starting point to the end point. The key factors of the A-Star algorithm are the path node structure (S), OpenList, and CloseList. The node structure contains the coordinate S(i, j) of the path node, the coordinate of the parent node S′(i′,j′), and the heuristic distance cost $F\left(S\right)$ of the path node. OpenList stores the path node to be selected, CloseList stores the path node that has been searched, and the local heuristic distance cost function is expressed as Equation (4).

$$F\left(S\right)=G\left(S\right)+H\left(S\right)$$

(4)

where $G\left(S\right)$ is the distance cost of node(S) from the start point, and $H\left(S\right)$ is the distance cost of node(S) to the end point. In this study, the Euclidean distance is used to calculate $G\left(S\right)$, and the Manhattan distance is used to calculate $H\left(S\right)$.

The main steps of the A-Star algorithm are as follows:

• Initialisation generates an OpenList, CloseList, and PathList, inserting the Start node into OpenList.
• When OpenList is not empty, the point traverses are determined in the OpenList with the smallest F value, removed from the OpenList, added to CloseList, and taken as the current point.
• Traverse the neighbouring feasible node corresponding to the current point to determine whether the neighbouring feasible node is in OpenList. If not, add it to the OpenList, add the current point to PathList, and calculate the heuristic distance cost. If it is in the OpenList, calculate its G value; continue traversing other nearby feasible nodes; otherwise, add the current point to PathList and update the heuristic distance cost of the node.
• The iteration moves to subsequent nodes until the current node becomes the end node.

The A-Star algorithm is finished when the end point is in the openList, which indicates that the feasible shortest path has been found. The A-Star algorithm is terminated, when the OpenList is empty or the current point is in the ClosedList. It indicates that there is no way to go and the feasible shortest path cannot be found.

4.2. Improved A-Star Path Planning Algorithm

Conventional algorithms in terms of access to all nodes and calculating the heuristic function value to spend a lot of time, especially in the long-distance off-road path planning tasks, OpenList and CloseList have a huge amount of retrieval nodes, meaning that with the growth of the search path searching time will also increase a lot. This is not conducive to the completion of off-road path planning tasks. Based on the conventional algorithm, the hybrid data structure greatly reduces the time complexity of the improved algorithm, so that the long-distance off-road path planning task can be completed quickly. The corresponding pseudocode was described in Algorithm 1.

The improved A-Star algorithm is shown in Figure 4 to better express the proposed improved parts. The green, yellow, and blue boxes correspond to the operations of OpenList, CloseList, and the traversal strategy, respectively. The two major improvements are as follows:

Algorithm 1: Improved A-Star Algorithm.

Input: start node SStart, end node Send, slope map Smap, feasible slope Fslope

Outout: PathList

1  initialise: vector PathList

2  path node P = FINDPATH (SStart, Send)

3  while(P)

4  add P into PathList and set P is the parent node of P

Function FINDPATH (SStart, Send)

5 initialise: priority_queue OpenList, **CloseList

6   add SStart into OpenList

7 while OpenList is not empty do

8   current node S is node with lowest F value in OpenList

9   if   S is in CloseList return S

10  else delete S from OpenList and set S is in CloseList

11  for  each neighboring node N of S  do

12    if  ISFEASILE(N)! = ture  continue

13    if  N is in OpenList

14       set the parent node of N is S and  calculate F(N),G(N),H(N) and  add N into OpenList

15    else  calculate new G’(N)

16       if  G’(N) < G(N)

17        set the parent node of N is S and calculate F(N),G(N),H(N) and update N

18    if  H(S) < 100    //optimisation  ①

19       if  Send is in OpenList

20        return Send

Function ISFEASILE(N)

21  if  slope of N in Smap is greater than Fslope

22    return ture

23  else return false

• In terms of search strategy optimisation, since the actual point retrieved will not be the end point at the beginning of the path planning, checking whether the endpoint is reached is not necessary. The intermediate detection retrieving the end point in the OpenList runs at the end of the path planning. If the end point is found in the OpenList, the execution of path planning ends. When the distance between the leading and end point is less than 100, the intermediate detection is started. It will reduce the retrieval time. Additionally, the threshold for the distance is not a fixed value. Additionally, 100 is an appropriate threshold for distances, obtained through experiments. This improvement is illustrated in ① of Figure 4.
• In terms of data structure optimisation, the improved A-Star algorithm uses the hybrid data structure of minimum heap and 2D array to reduce the time cost of data processing. OpenList has frequent insert, delete, update, and retrieve operations, especially the process of finding the node with the least heuristic value in OpenList is time-consuming; therefore, the priority queue (minimum heap) is used as the container of OpenList, and the time complexity of finding the minimum heuristic value node and deleting process is reduced from O(n) to O(1). Although the time complexity is increased from O(1) to O(log(n)) in the process of constructing the binary tree, the overall time complexity is reduced. This improvement is located in ② of Figure 4. CloseList has frequent insert and retrieve operations, which have time complexities of O(1) and O(n), respectively. There is no delete operation in CloseList, so the retrieval time will continue to increase as the number of nodes increases. The 2D state array stores the retrieval state of each point in the map. Thus, the time complexity in the CloseList retrieval process is reduced from the original O(n) to O(1), which greatly improves retrieval speed. This improvement is located in ③ of Figure 4.

5. Experiment and Results

To evaluate the performance of the improved A-Star algorithm, nine scenarios of experiments were designed, including three kinds of path planning tasks with distinct terrain characteristics. Each path planning tasks corresponds to the three different vehicles with different feasible slope thresholds. The applicability of the proposed algorithm was verified by comparing the path planning tasks under different terrain characteristics. By comparing the planned paths of vehicles with different feasible slope thresholds, the execution efficiency of the proposed algorithm was tested.

The conventional A-Star, the bidirectional search algorithm, and the proposed A-Star algorithm were implemented and tested on nine experimental scenarios to compare the execution efficiency. The short path is located in mountainous areas. The median path began in a relatively flat region and ended in a mountainous area with significant elevation changes. The long path is similar to that of the second path. However, most paths are located in mountainous areas. In addition, three different vehicles, namely, a tracked vehicle, wheeled vehicle, and tracked lunar rover.

The experiment was conducted using C++ 11 compiled on VS2013. OpenCV V3.1.0 was used to process the map on a laptop computer. The slope threshold, starting point, and end point position were input from the C++ program, and the complete code was tested on an Intel Core [email protected]. This shows that the improved algorithm can also complete the off-road path planning task quickly on slow processors.

5.1. Slope Threshold for Off-Road Vehicles

Based on the experimental data of off-road vehicles and expert experience, the off-road performance of tracked vehicles is better than that of wheeled vehicles. For off-road vehicles, especially military vehicles, the feasible slope threshold of wheeled vehicles is considered to be 31° [28], and the feasible slope threshold of the tracked vehicle is set at an appropriate 35° [29]. Considering the strict conditions, the feasible slope threshold of the third type of vehicle was set at 20°, referring to the tracked lunar rover. The proposed improved A-Star algorithm is also applicable to the path planning of the rover. In this study, the feasible slope threshold of the third type of vehicle was set at 20°, referring to the tracked lunar rover [30]. It was applied to the experiment of a path-planning task on a ground terrain data map.

Therefore, according to the three types of off-road vehicles, the feasible slope thresholds of off-road vehicles were set into the following three categories, as shown in

Table 1. Feasible slope thresholds corresponding to different vehicles.

level	Vehicle Type	Feasible Slope (Degree)
1	Tracked vehicle	35
2	Wheeled vehicle	31
3	Tracked lunar rover	20

.

5.2. Improved A-Star Algorithm for Path Planning of Different Off-Road Vehicles

Owing to the different feasible slope thresholds corresponding to different vehicles, the routes planned on the map are also different. Therefore, this study compared the routes planned by different vehicles at the same starting and ending points. As the length of the path between the starting point and the end point has an important impact on the processing time of the algorithm, the planned routes with different path lengths were compared.

To verify the reliability and consistency of the improved algorithm, three experiments with different starting and finishing points were conducted, as shown in

Table 2. Detailed information of the three path planning tasks.

Path	Start Point (px, px)	End Point (px, px)	Distance (km)	Characteristics
Short	(8031, 9183)	(10,709, 10,551)	60.144	Mountainous
Median	(3881, 3134)	(7580, 11,302)	179.33	Mostly flat, partly mountainous
Long	(741, 5121)	(12,053, 6931)	229.118	Partially flat, mostly mountainous

, corresponding to the short-, medium-, and long-distance path planning tasks.

The vehicle begins at the starting point listed in Table 2, and the path to the end point is determined based on the terrain data map combined with the feasible slope threshold of the off-road vehicle. The red path represents the final output path. In Figure 5, the path planning outputs of the three off-road vehicles all adhere to the corresponding threshold region in the short-, medium-, and long-distance path planning tasks. The start and end points and the path are in areas where the terrain changes significantly in the short-distance path planning task. The vehicle starts from the top of the map and ends at the bottom of the map in the median distance path planning task. Most paths pass through areas with gentle terrain changes on the map. The vehicle starts on the left of the map and ends on the right side of the map in the long-distance path planning task. The first half of the path falls in areas with gentle terrain changes, while the second half of the path falls in areas with great terrain changes. The results show that even if start and end points are the same, the planned paths are not the same, as the corresponding feasible slope thresholds are different. Moreover, the lower the feasible slope threshold, the more tortuous the path.

The improved A-Star algorithm was compared with the conventional algorithm and the bidirectional search algorithm. The efficiency performance of the improved A-Star algorithm was evaluated in nine different scenarios. The comparison was from three aspects: retrieval length, path length, and processing time. The results of the different path planning tasks corresponding to the three groups of different off-road vehicles are listed in

Table 3. Comparison of the path planning of different off-road vehicles with different path lengths.

Vehicle Type	Distance Set	Conventional A-Star			Improved A-Star			Bidirectional Search
		Retrieve Length (px)	Path Length (px)	Process Time (s)	Retrieve Length (px)	Path Length (px)	Process Time (s)	Retrieve Length (px)	Path Length (px)	Process Time (s)
Tracked vehicle	Short	2697	2691	1.573	2697	2691	0.801	2685	2679	1.022
	Medium	8293	8267	18.992	8293	8267	5.63	8273	8239	12.556
	Long	11,547	11,444	39.526	11,547	11,444	8.512	11,406	11,323	23.716
Wheeled vehicle	Short	2789	2737	1.489	2789	2737	0.745	2751	2721	1.156
	Medium	8562	8343	18.394	8562	8343	6.553	8413	8298	12.667
	Long	12,942	11,623	45.267	12,942	11,623	9.244	12,325	11,507	29.135
Tracked lunar rover	Short	113,315	5432	2502.35	113,315	5432	24.575	110,032	5432	1626.527
	Medium	24,419	10,046	99.333	24,419	10,046	14.487	23,206	9993	62.58
	Long	567,091	21,453	182,753.8	567,091	21,453	331.468	554,127	21,313	113,307.3

. Compared with the conventional algorithm and the bidirectional search algorithm, the improved A-Star increases the efficiency for all path planning tasks of various lengths, and the efficiency improvement is the most obvious in the long-distance path planning task.

6. Discussion

The execution time of the algorithm is greatly affected by the complexity of the terrain in the process of path planning tasks. The terrain changes lead to the frequent change of path search direction and the expansion of search scope. This problem exists in the other path planning algorithm and is even more serious. Therefore, the improved algorithm reduces the algorithm execution time from the perspective of reducing the algorithm time complexity to overcome the limitation of processing times. The improved A-Star algorithm in this study mainly improves the efficiency of the algorithm. The experimental results show that the planned paths and accuracy were the same as the conventional A-Star algorithm.

In Figure 6, the horizontal axis represents nine experimental scenes, and the vertical axis represents the multiple of efficiency improvement relative to the conventional A-Star algorithm. The bidirectional search algorithm was accelerated by at least 1.2 times, and the maximum acceleration reached was 1.6 times, comparing to the conventional A-Star algorithm. Meanwhile, the improvement efficiency of nine scenarios by the bidirectional search algorithm was not obvious, comparing to the proposed improved A-Star algorithm. The bidirectional search can be divided into forward search and backward search alternates. Therefore, the planning path of the bidirectional search was different from the conventional A-Star algorithm.

By comparing the experimental results of different path planning tasks for the same vehicle, the optimisation efficiency of the improved algorithm is significant, and the longer the retrieval length, the higher the percentage increase in efficiency improvement. The improvement efficiency of tracked vehicles and wheeled vehicles increases with the lengthening of the path and the increase of retrieval nodes. In the most severe case, the Lunar Orbiter has the lowest feasible slope threshold. The medium-distance task planning path nodes mostly fall in flat areas, while the short-distance task planning path nodes mostly fall in areas with large terrain changes. The retrieval length of short-distance plan planning task is longer than that of medium-distance tasks. Therefore, the improvement efficiency of short-distance planning tasks is higher than that of medium-distance planning tasks. Compared with the other different vehicles, the improved A-Star algorithm is significantly improved for path planning tasks of tracked lunar rovers. The improved A-Star algorithm was accelerated by at least 6.8 times, and the maximum acceleration reached was 550 times for path planning tasks of tracked lunar rovers in Figure 6.

In the same path-planning task, the number of nodes retrieved and the path length of the improved algorithm are the same as those of the conventional algorithm. This indicates that the improved algorithm was consistent and robust. The feasible slope threshold of tracked off-road vehicles is slightly higher than that of wheeled off-road vehicles, the corresponding processing times of tracked off-road vehicles are also slightly lower than those of wheeled off-road vehicles in Table 3. Owing to the relatively short processing time and the instability of the CPU, it is reasonable that the processing time of individual path planning tasks corresponding to wheeled off-road vehicles is slightly shorter than that of the tracked vehicle.

7. Conclusions

In this study, an improved A-Star algorithm was proposed and the results of global path planning for the off-road long-distance path planning task were presented with the aim of addressing low efficiency and long retrieval time limitations of the conventional A-Star algorithm. The improved algorithm uses a hybrid data structure and improved retrieval strategies to promote efficiency. The comparison between the conventional and improved algorithms was made in short-, medium-, and long-distance path planning tasks with three different vehicles. The percentage increase in the efficiency improvement between the two algorithms was calculated and compared. In this study, the path planning efficiency of the improved A-Star algorithm was improved, compared with the conventional A-Star algorithm. The improved A-Star algorithm was shown to increase efficiency improvement minimally by at least 4.6 times, and the maximum acceleration reached was 550 times for long-distance off-road path planning. The results show that the improved A-Star algorithm is far superior to the conventional A-Star algorithm in terms of execution efficiency, allowing the proposed algorithm to quickly complete off-road long-distance path planning tasks. Future work will apply the proposed algorithm to different situations for the wider applications of the proposed algorithm, such as path planning on the moon or Mars.