UAV Path Planning Model Based on R5DOS Model Improved A-Star Algorithm

Abstract

In order to solve the problems of large amounts of calculation and long calculation times of the A-star algorithm in three-dimensional space, based on the R5DOS model, this paper proposes a three-dimensional space UAV path planning model. The improved R5DOS intersection model is combined with the improved A-star algorithm. Together, they construct a local search process, and the R5DOS path planning model is established by reducing the number of search nodes. The path planning model is simulated through MATLAB software and the model can greatly reduce the number of nodes and computational complexity of the A-star algorithm in three-dimensional spaces, while also reducing the calculation time of the UAV. Finally, we compare the improved A-star algorithm with the original A-star algorithm and the geometric A-star algorithm. The final fitting result proves that the improved A-star algorithm has a shorter computation time and fewer node visits. Overall, the simulation results confirm the effectiveness of the improved A-star algorithm and they can be used as a reference for future research on path planning algorithms.

1. Introduction

With the progress of science and technology, the development and application of various types of robots and remote sensing [1] have become more advanced and they are increasingly entering all aspects of modern life. Within this trend, UAVs are now widely used in agriculture [2,3], forestry, smart healthcare [4,5], geological exploration [6], disaster relief [7] and for military purposes. Gupta et al. conducted a comprehensive investigation and discussion on green technology and application, current challenges and the future direction of UAV-Fog [8]. Banerjee et al. designed a multi-UAV and multi-IoT network, saving energy and time of the model [9]. El Haber et al. optimized the position, unloading decision and resource allocation of UAVs [10]. Khan et al. proposed a layered architecture to improve the capacity and coverage of UAV-mounted BS [11].

In Chinese agriculture and forestry, UAVs [12,13] are extremely important; however, they face many obstacles during operation. In agricultural work, common obstacles are trees, utility poles, flocks of birds and houses. In forestry work, obstacles are mainly trees and flocks of birds. Thus, the core problem of UAVs is how to effectively avoid obstacles during operation. In response to this problem, many researchers have developed a number of path planning and obstacle avoidance algorithms [14,15,16]. Examples of these algorithms include: the Dijkstra algorithm, the ant colony algorithm, the A-star algorithm and the artificial potential field method. Among them, the artificial potential field method has the advantages of a simple principle and a smooth pathway, but it also has disadvantages such as easily falling into local optimization and being unable to avoid large obstacles. To optimize these problems, scholars locally and internationally have conducted significant research. Zhang et al. proposed a three-dimensional artificial potential field method based on the pilot method, which solves the problem of the UAV falling into a limit value in the process of obstacle avoidance [17]. Fan et al. proposed an improved artificial potential field method using the regular hexagon guidance process to improve the local minimum value problem [18]. Zhang et al. combined and improved the artificial potential field method and the A-star algorithm, so that the path smoothing of the UAV during obstacle avoidance is more in line with the actual situation of the UAV [19]. Rostami added a regulator between the repulsive functions, which further improved the artificial potential field method [20]. Additionally, Yan et al., through combining virtual structures with the artificial potential field method, reduced the amount of computation and increased the flexibility of unmanned ships [21].

Many of the above researchers have made a lot of improvements to the artificial potential field method. However, when operating unmanned aerial vehicles, it is possible that large obstacles will be encountered where the artificial potential field method struggles to work effectively. This can be significantly improved by using the traditional A-star algorithm in the three-dimensional space. To solve this problem, this paper proposes an artificial potential field method based on the R5DOS model and an improved A-star combined algorithm in three-dimensional space. The model combines an artificial potential field method and an A-star algorithm in three-dimensional space, which improves the search efficiency of the A-star algorithm and avoids the problem of the artificial potential field method falling into the local minimum value.

Our work scope is mainly around the improvement of A-star in three-dimensional space, and the effectiveness and progressiveness of the improved A-star algorithm are studied through simulation experiments. The main contributions and innovations of this paper are as follows:

• (1). Aiming at the problem of path planning in three-dimensional space, an improved A-star algorithm is proposed that modifies the hop search algorithm and the A-star algorithm based on the R5DOS model.

• (2). A preprocessing process is added to filter the access nodes, which improves the computing speed and saves computing time and resources.

• (3). When an obstacle is detected, the algorithm will generate grids to find safe nodes and re-plan feasible routes to avoid obstacles.

The organization of this paper is as follows: In the next Section 2, we introduce the improvement and algorithm architecture of the A-star algorithm. In Section 3, simulation is carried out to verify the effectiveness of the improved A-star algorithm. Finally, we give a conclusion in Section 4.

2. Materials and Methods

2.1. UAV Representation Based on R5DOS-Intersection Model

In 2021, Li et al. [22] proposed a multi-UAV formation based on the R5DOS intersection model. Improvements were made to the R5DOS intersection model. Comparing the R5DOS model formation with the rectangular model and the grid model, it can be seen that the R5DOS model formation can effectively reduce communication, time and energy costs, while enhancing the robustness of the UAV formation and ensuring the integrity of the UAV’s formation communication. Simulation experiments were carried out on the model and the results showed that the model formation was stable. Additionally, when the leader failed, the follower could quickly replace the leader and improve the robustness of the formation.

The R5DOS model divides the space into 16 regions and combines topological relationships:

(1)$R5DOS=\left(\begin{array}{cccc}\epsilon (A^{\mathrm{o}}\cap B^{\mathrm{o}}\cap C^{\mathrm{o}})& \epsilon (A^{\mathrm{o}}\cap B^{\mathrm{o}}\cap {(C^c)}^{\mathrm{o}})& \epsilon (A^{\mathrm{o}}\cap {(B^c)}^{\mathrm{o}}\cap C^{\mathrm{o}})& \epsilon (A^{\mathrm{o}}\cap {(B^c)}^{\mathrm{o}}\cap {(C^c)}^{\mathrm{o}})\\ \epsilon ({(A^c)}^{\mathrm{o}}\cap B^{\mathrm{o}}\cap C^{\mathrm{o}})& \epsilon ({(A^c)}^{\mathrm{o}}\cap B^{\mathrm{o}}\cap {(C^c)}^{\mathrm{o}})& \epsilon ({(A^c)}^{\mathrm{o}}\cap {(B^c)}^{\mathrm{o}}\cap C^{\mathrm{o}})& \epsilon ({(A^c)}^{\mathrm{o}}\cap {(B^c)}^{\mathrm{o}}\cap {(C^c)}^{\mathrm{o}})\\ \epsilon (s1NE)& \epsilon (s2NE)& \epsilon (s3NW)& \epsilon (s4NW)\\ \epsilon (s1EN)& \epsilon (s2EN)& \epsilon (s3NW)& \epsilon (s4NW)\\ \epsilon (s5ES)& \epsilon (s6ES)& \epsilon (s7WS)& \epsilon (s8WS)\\ \epsilon (s5SE)& \epsilon (s6SE)& \epsilon (s7SW)& \epsilon (s8SW)\end{array}\right)$

Here,

(2)$$\begin{gathered} \{\begin{array}{c}s1NE;x_b\ge 0,y_b\ge 0,z_b\ge 0,{\theta }_{ob}\in \left[0,\frac{\pi }{4}\right)\\ s2NE;x_b<0,y_b\ge 0,z_b\ge 0,{\theta }_{ob}\in \left[0,\frac{\pi }{4}\right)\\ s1EN;x_b\ge 0,y_b\ge 0,z_b\ge 0,{\theta }_{ob}\in \left[\frac{\pi }{4},\frac{\pi }{2}\right)\\ s2EN;x_b<0,y_b\ge 0,z_b\ge 0,{\theta }_{ob}\in \left[\frac{\pi }{4},\frac{\pi }{2}\right)\end{array}\{\begin{array}{c}s5ES;x_b\ge 0,y_b\ge 0,z_b<0,{\theta }_{ob}\in \left[\frac{\pi }{2},\frac{3\pi }{4}\right)\\ s6ES;x_b<0,y_b\ge 0,z_b<0,{\theta }_{ob}\in \left[\frac{\pi }{2},\frac{3\pi }{4}\right)\\ s5SE;x_b\ge 0,y_b\ge 0,z_b<0,{\theta }_{ob}\in \left[\frac{3\pi }{4},\pi \right)\\ s6SE;x_b<0,y_b\ge 0,z_b<0,{\theta }_{ob}\in \left[\frac{3\pi }{4},\pi \right)\end{array} \\ \{\begin{array}{c}s8SW;x_b\ge 0,y_b\ge 0,z_b<0,{\theta }_{ob}\in \left[\pi ,\frac{5\pi }{4}\right)\\ s7SW;x_b\ge 0,y_b\ge 0,z_b\ge 0,{\theta }_{ob}\in \left[\pi ,\frac{5\pi }{4}\right)\\ s8WS;x_b\ge 0,y_b<0,z_b<0,{\theta }_{ob}\in \left[\frac{5\pi }{4},\frac{3\pi }{2}\right)\\ s7WS;x_b<0,y_b<0,z_b<0,{\theta }_{ob}\in \left[\frac{5\pi }{4},\frac{3\pi }{2}\right)\end{array}\{\begin{array}{c}s4WN;x_b\ge 0,y_b<0,z_b\ge 0,{\theta }_{ob}\in \left[\frac{3\pi }{2},\frac{7\pi }{4}\right)\\ s3WN;x_b<0,y_b<0,z_b\ge 0,{\theta }_{ob}\in \left[\frac{3\pi }{2},\frac{7\pi }{4}\right)\\ s4NW;x_b\ge 0,y_b<0,z_b\ge 0,{\theta }_{ob}\in \left[\frac{7\pi }{4},2\pi \right)\\ s3NW;x_b<0,y_b<0,z_b\ge 0,{\theta }_{ob}\in \left[\frac{7\pi }{4},2\pi \right)\end{array} \end{gathered}$$

${\theta }_{ob}$ is the two-sided angle of the plane.

We define UAVs according to R5DOS-intersection: According to the R5DOS model, we can divide the UAV formation into detection areas and UAV movement areas. The detection area is the area where the UAV detects the surrounding environment during flight, which we can regard as a buffer area, and the UAV movement area is the area where the UAV can fly in the air. Obviously, for probing UAVs, motion area C is contained in the detection zone B, satisfies B includes C, it is PP (B,C), according to the R5DOS- intersection model in Figure 1:

Then, we can get the following definition:

Definition 1. 

For the R5 layer, we define in Table 1 an operator “ ∨” about the set {0,1}.

Definition 2. 

For the DOS layer, we define in Formula (3).

(3) $\epsilon (DOS)=\{\begin{array}{c}0:Noobjectsinthisarea\\ 1:Obstaclesinthisarea\end{array}$

The improvements to the A-star algorithm in this paper are based on this model.

2.2. A-Star Algorithm

The traditional A-star algorithm has the advantages of a simple principle and fast calculation speed. However, its spatial growth is exponential and the larger the map the greater the amount of computation. In the three-dimensional space, the traditional A-star algorithm will have a very large amount of computation, serious memory occupation, long calculation time and low pathfinding efficiency. The A-star algorithm will search for many unnecessary nodes in the process of running, resulting in a great increase in the running time of the algorithm. To solve this problem, this paper improves the A-star algorithm based on the R5DOS model and combines it with the hop-point search algorithm.

The A-star algorithm mainly uses the evaluation function to guide and select the expansion nodes in the raster map, to traverse the nodes around the grid map each time and to calculate the evaluation function. Finally, it selects the smallest path of the evaluation function to move, as shown in Figure 2.

We construct a cost function in the A-star algorithm to search for path nodes. The cost function $f(n)$ can be expressed as $f\left(n\right)=G\left(n\right)+H\left(n\right)$, where $H(n)$ is the estimated cost function expression for the shortest path from the nth node to the target node and $G(n)$ represents the move cost function expression for the shortest path from the start point to the nth node. So, according to the expression, it is a function expression $f(n)$ for the shortest path between the nth node of the UAV from the starting point to the midpoint. This calculation generally uses Manhattan distance, Chebyshev distance and Origid distance. For this article, we will use the Origid distance to calculate the cost of movement. For the first three-dimensional space represented by the raster method, the cost d is shown in Equation (4).

(4)$d=\sqrt{{\left(x_2-x_1\right)}^2+{\left(y_2-y_1\right)}^2+{\left(z_2-z_1\right)}^2}$

(x₁, y₁, z₁) and (x₂, y₂, z₂) represent the coordinates of nodes, respectively. $f(n)$, $G(n)$ and $H(n)$ can be calculated by Equation (4).

We redefine the nodes of UAV searches. In three-dimensional spaces, there are many nodes that can be moved by UAVs, far more than a few atomic directions in two-dimensional spaces. According to the R5DOS model, we divide the space into 16 regions, but this division is not conducive to the judgment of the A-star algorithm for nodes. We have improved the spatial relationship division of the R5DOS model, focusing on the eight limits in space and establishing eight cube regions. Assuming that the orange dot is a UAV, and all the vertices of its adjacent limits, the yellow dot can be used as neighbors of the current node, that is, the next search node. Then, according to the concept, there can be a total of 26 search nodes, as shown in Figure 3.

2.3. Improved A-Star Algorithm

The A-star algorithm is a global planning algorithm that requires all the information on maps and obstacles to perform a good job. However, for UAVs, because of the limitation of detection range, the full information of the map cannot be obtained while working, causing the A-star algorithm to work poorly. The map information of the three-dimensional space is too complex and the larger the map the greater the amount of computation. We improved the A-star algorithm based on the R5DOS model.

The hop-point search algorithm is a special search strategy that ignores unnecessary search nodes during the search process; the points that the algorithm searches for after ignoring processing are called hop points. As shown in Figure 4, the three paths from the P node can be selected to reach the Q node:

• P→B₁→C₁→Q

• P→B₂→C₂→Q

• P→B₃→C₃→Q

During the search process, the A-star algorithm compares the estimates of each node and calculates the B₂ lowest cost of the nodes through comparison. The algorithm will then traverse each adjacent node B₁, B₂, B₃. The operation of searching for B₁, B₃ is unnecessary because the moving cost of path 2 is always the lowest in this case. To further improve the search efficiency and speed, you can search directly according to the location and direction of the target node; this is the search method of a jump-point search. A hop-point search improves the search efficiency by searching for specific nodes and ignoring unnecessary nodes in the process of expanding nodes; these specific nodes are called hop points. The Q node in the figure is a hop point. The other nodes between the two hop paths will be ignored, which will greatly reduce the amount of computation and storage. This effectively solves the problem of large amounts of computation and memory consumption caused by the A-star algorithm in larger map sizes.

In this article, a search requires access to 26 nodes, which will greatly increase the computational difficulty and time required, so we have improved the A-star algorithm based on the hop-point search algorithm. In this paper, preprocessing for nodes is added to the A-star algorithm to filter out a batch of jump points in advance, which can greatly reduce the access and computation of the A-star algorithm to a large number of intermediate unnecessary nodes. The improved A-star algorithm does not traverse each node but calculates special nodes over long distances and jumps.

Preprocessing is essentially the process of filtering the jump points in a raster map, which is defined in this article according to the situation. The UAV cannot obtain the information of the full map while working, but the UAV has a detection area and can obtain local information. For UAVs, the UAV does not set up nodes when it does not detect obstacle A $R\left(A,B,C\right)=\left(\begin{array}{cccc}0& 0& 0& 1\\ 1& 1& 0& 1\end{array}\right)$. When the UAV detection area detects obstacle A $R\left(A,B,C\right)=\left(\begin{array}{cccc}0& 1& 0& 1\\ 1& 1& 0& 1\end{array}\right)$, the local map is rasterized and all 26 nodes around it are removed, as shown in Figure 5.

Set the node coordinates to $\left(x_i,y_i,z_i\right)i=1,2\cdots 26$. The coordinates of the UAV are $\left(x_u,y_u,z_u\right)$, the distance from the node to the UAV is $d_{ui}=\sqrt{{\left(x_i-x_u\right)}^2+{\left(y_i-y_u\right)}^2+{\left(z_i-z_u\right)}^2}$ and the direction unit vector from the node to the UAV is ${\overrightarrow{V}}_{ui}\left(x_{vi},y_{vi},z_{vi}\right)=\left(\frac{\left(x_i-x_u\right)}{d_{ui}},\frac{\left(y_i-y_u\right)}{d_{ui}},\frac{\left(z_i-z_u\right)}{d_{ui}}\right)$. Target point coordinates are $\left(x_t,y_t,z_t\right)$. Define the connection line between the current position of the UAV and the target point $V_{ut}$, the distance and the direction unit vector ${\overrightarrow{V}}_{ut}\left(x_{vt},y_{vt},z_{vt}\right)=\left(\frac{\left(x_t-x_u\right)}{d_{ut}},\frac{\left(y_t-y_u\right)}{d_{ut}},\frac{\left(z_t-z_u\right)}{d_{ut}}\right)$. To better screen the nodes, we calculate ${\overrightarrow{V}}_{ui}$, the inner product N of the ${\overrightarrow{V}}_{ui}$ unit vector, then we get Equation (5).

(5)$$\begin{gathered} N={\overrightarrow{V}}_{ui}•{\overrightarrow{V}}_{ut}=x_{vi}{x}_{vt}+y_{vi}{y}_{vt}+z_{vi}{z}_{vt} \\ \{\begin{array}{c}N>0 \mathrm{keep}\mathrm{the}\mathrm{corresponding}\mathrm{node}\\ N\le 0 \mathrm{remove}\mathrm{the}\mathrm{corresponding}\mathrm{node}\end{array} \end{gathered}$$

If $N>0$, the corresponding node of the inner product is retained. If $N\le 0$, the corresponding node is removed. In this way, we further screened a batch of jump points, as shown in Figure 6. The direction of the arrow is the vector from the target point to the UAV, bound by the plane. The yellow node is the reserved node and the gray node is the removed node.

This article removes unnecessary nodes.

Because the movement path of the A-star algorithm is not smooth enough and there are many inflection points, it is not conducive to the rotation and displacement of the UAV. Then, after filtering the hop point and determining the best movement path, we use the nearest neighbor interpolation method to smooth the path, which is more in line with the movement mode of the UAV, such as Equation (6). This reduces the difficulty of moving the UAV and improves the obstacle avoidance efficiency of the UAV.

(6)$\{\begin{array}{l}{y}_s\left(i\right)=\frac{1}{2N+1}\left[y\left(i+N\right)+y\left(i+N-1\right)+\cdots +y\left(i-N\right)\right]\\ y_s\left(1\right)=y\left(1\right) \\ y_s\left(2\right)=\frac{\left[y\left(1\right)+y\left(2\right)+y\left(3\right)\right]}{3} \\ y_s\left(3\right)=\frac{\left[y\left(1\right)+y\left(2\right)+y\left(3\right)+y\left(4\right)+y\left(5\right)\right]}{5} \\ y_s\left(4\right)=\frac{\left[y\left(2\right)+y\left(3\right)+y\left(4\right)+y\left(5\right)+y\left(6\right)\right]}{5} \end{array}$

2.4. Improved A-Star Algorithm

According to the definition of the previous sections, we give the final path planning algorithm based on the R5DOS model. The pseudo code is shown in Algorithm 1.

Algorithm 1: A-start plus

1  algorithm A-start plus (start, n, goal)

2  if reachAroundGoal(start) ≠ goal then return makePath(start)

3  open ← closestPoint(start)

4  closed ← 0

5  finale ← 0

6  while open ≠ 0 do

7  sort(open)

8  n ← open.pop( )

9  if reachAroundGoal(n) ≠ goal then return makePath(n)

10   Jump bodys ← expendFlexibleUnits(n)

11  end if

12  for all the Jump bodys do

13:    if $R\left(A,B,C\right)=\left(\begin{array}{cccc}0& 0& 0& 1\\ 1& 1& 0& 1\end{array}\right)$

14:      neighbor.f  ← Ø

15        if $R\left(A,B,C\right)=\left(\begin{array}{cccc}0& 1& 0& 1\\ 1& 1& 0& 1\end{array}\right)$ then open ← neighbor

16        else closed ← neighbor

17      end if

18      closed ← n

19      if crossPath(n) and smoothPath(n) then

20        final ← closed

21      end if

22     end if

23   end for

24  end

25  return 0

The flowchart of the improved algorithm is shown in Figure 7.

3. Results and Discussion

Based on the above path planning algorithm, we created different simulation environments in Matlab. We set the starting point as the coordinate origin and the location of the target point varies with the size of the map, usually the point farthest from the starting point in the map. In order to simulate the real situation, the number, position and size of obstacles are generated randomly.

Due to the complexity of the improved A-star path planning algorithms, we need to use the computing time to evaluate the efficiency of the improved A-star algorithm in the process of path planning and obstacle avoidance for maps of different specifications.

The CPU of our computer is Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz 2.21 GHz and the GPU is NVIDIA GTX 1060 Max-Q 6 GB. We have carried out eighty simulation experiments in MATLAB 2022A and taken the average value. To determine the potential advantages of the improved path planning algorithm in a random map, we fixed the altitude at 15 m.

To determine the potential advantages of the improved path planning algorithm in random maps, we fixed the height to 15 m and simulated the improved A-star algorithm in maps with two options for length and width, 30 m × 90 m and 50 m × 150 m, respectively. The results are shown in Figure 8 and Figure 9.

After eighty simulations, we can see that, compared with the A-star algorithm, the improved A-star algorithm has fewer turning angles, a smoother flight path and a good effect on obstacle avoidance. To further calculate the advantages of the improved A-star algorithm in three-dimensional space, we compare the improved A-star algorithm with the traditional A-star algorithm, as shown in Figure 10.

Simulation Using Eight Specification Diagrams

After multiple fittings, we compared the traditional A-star algorithm and the improved A-star algorithm under different map sizes with the number of obstacles using an aspect ratio of 2:1.

Starting with a map length of 30 m in size, with a 10-m step, the A-star algorithm and the improved A-star algorithm were compared to determine the advantages of the improved route planning algorithm. The starting point and the target point are set at corresponding locations in eight maps, as shown in Table 2.

We can: obtain the A-star algorithm and the improved A-star algorithm in the eight specification graphs corresponding to the path lengths, as shown in Figure 11; explore nodes and their logarithmic scale graphs, as shown in Figure 12; calculate the time of its logarithmic scale graph, as shown in Figure 13.

It is clear that the A-star algorithm grows exponentially as the map grows larger, while the improved A-star algorithm explores very small nodes and computation times. In 2021, Tang et al. [23] proposed an improved geometric A-star algorithm. Compared with the traditional A-star algorithm, the number of nodes is reduced by more than 19%, the total distance is reduced by more than 13% and the running time is reduced by 41.1%. As can be seen from Table 3, using a map size of 50 m × 100 m as an example, the improved A-star algorithm reduces the number of nodes by approximately 99.18%, the total distance by about 5.30% and the calculation time by about 99.72%. In addition, the number of nodes is reduced by approximately 99.18%, the total distance decreases by about 5.30% and the calculation time decreases by about 99.72%.

The larger the specifications of the map, the better the effect of the obstacle-improved A-star algorithm.

Overall, the improved A-star algorithm clearly performs better in all examples, with better parameters, calculation times and probe nodes.

4. Conclusions

Experimental results show that the algorithm generates feasible paths and the screening speed is faster. First, a batch of nodes is filtered out, then the nodes are calculated by the evaluation function and finally we simplify the entire path. Overall, our method can effectively reduce the computational time of a UAV in motion and the number of nodes and can make the UAV complete turns quickly and fluently.

However, our algorithm has many limitations, as shown below.

• (1). Our algorithm cannot be applied to complex dynamic scenes.

• (2). The path selection of our algorithm in obstacle avoidance can be further studied.

There are several directions for future work, as shown below.

• (1). We want to consider the application of UAVs in dynamic complex scenes, such as moving birds and agricultural machinery.

• (2). It is considered to enhance the response and obstacle avoidance ability of the algorithm to sudden situations, so that it can effectively avoid obstacles while the UAV is working and flying.

We will consider these factors in future work and further optimize our model.

Author Contributions

Conceptualization, J.L. and C.L.; methodology, J.L. and H.F.; software, S.F. and W.Z.; validation, S.F. and W.Z.; data curation, W.Z.; writing—original draft preparation, C.L.; writing—review and editing, C.L.; funding acquisition, J.L. All authors have read and agreed to the published version of the manuscript.

Data Availability Statement

Not applicable.

Conflicts of Interest

The authors declare no conflict of interest.

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Figures and Tables

Figure 1. Abstract expression of UAV area.

Figure 2. Pathfinding method of the A-star algorithm.

Figure 3. Motion directions of the UAV.

Figure 4. Path selection during search.

Figure 5. When the UAV detects an obstacle.

Figure 6. Node filtering conditions.

Figure 7. Improved algorithm flow based on A-star algorithm and APFM.

Figure 8. The fitting result of the improved algorithm on a 30 m × 90 m size map.

Figure 9. The fitting result of the improved algorithm on a 50 × 150 size map.

Figure 10. Comparison of A-star Plus algorithm and A-star algorithm.

Figure 11. Comparison of moving paths between A-star algorithm and A-star Plus algorithm.

Figure 12. Comparison of explore node between A-star algorithm and A-star Plus algorithm.

Figure 13. Comparison of calculation time between A-star algorithm and A-star Plus algorithm.

Table 1

Operator “v”.

v	0	1
0	0	1
1	1	1

Table 2

Coordinates of start and end points in maps of different sizes.

Map Size	Start Point	End Point	Map Size	Start Point	End Point
15 × 30	(0, 0, 15)	(8, 32, 15)	35 × 70	(0, 0, 15)	(18, 72, 15)
20 × 40	(0, 0, 15)	(10, 42, 15)	40 × 80	(0, 0, 15)	(20, 82, 15)
25 × 50	(0, 0, 15)	(13, 52, 15)	45 × 90	(0, 0, 15)	(23, 92, 15)
30 × 60	(0, 0, 15)	(15, 62, 15)	50 × 100	(0, 0, 15)	(25, 102, 15)

Table 3

Comparison of A-star Plus algorithm with geometric A-star algorithm and traditional A-star data.

Path Parameters	Traditional A-Star	A-Star Plus	Geometric A-Star Reduced Proportion	A-Star PlusReduced Proportion
Running time/s	1184.188	0.26625	41.1%	99.98%
Number of nodes	157,550	514	24.2%	99.7%
Total distance/s	112.177	106.075	15%	5.4%

References

1. Li, H.P.; Zhang, C.; Zhang, S.Q.; Ding, X.H.; Atkinson, P.M. Iterative Deep Learning (IDL) for agricultural landscape classification using fine spatial resolution remotely sensed imagery. Int. J. Appl. Earth Obs. Geoinf.; 2021; 102, 102437. [DOI: https://dx.doi.org/10.1016/j.jag.2021.102437]

2. Bera, B.; Vangala, A.; Das, A.K.; Lorenz, P.; Khan, M.K. Private blockchain-envisioned drones-assisted authentication scheme in IoT-enabled agricultural environment. Comput. Stand. Interfaces; 2022; 80, 103567. [DOI: https://dx.doi.org/10.1016/j.csi.2021.103567]

3. Hovhannisyan, T.; Efendyan, P.; Vardanyan, M. Creation of a digital model of fields with application of DJI phantom 3 drone and the opportunities of its utilization in agriculture. Ann. Agrar. Sci.; 2018; 16, pp. 177-180. [DOI: https://dx.doi.org/10.1016/j.aasci.2018.03.006]

4. Aggarwal, S.; Kumar, N.; Alhussein, M.; Muhammad, G. Blockchain-based UAV path planning for healthcare 4.0: Current challenges and the way ahead. IEEE Netw.; 2021; 35, pp. 20-29. [DOI: https://dx.doi.org/10.1109/MNET.011.2000069]

5. Verma, A.; Bhattacharya, P.; Zuhair, M.; Tanwar, S.; Kumar, N. Vacochain: Blockchain-based 5g-assisted uav vaccine distribution scheme for future pandemics. IEEE J. Biomed. Health Inform.; 2021; 26, pp. 1997-2007. [DOI: https://dx.doi.org/10.1109/JBHI.2021.3103404] [PubMed: https://www.ncbi.nlm.nih.gov/pubmed/34388100]

6. Park, S.; Choi, Y. Applications of Unmanned Aerial Vehicles in Mining from Exploration to Reclamation: A Review. Minerals; 2020; 10, 663. [DOI: https://dx.doi.org/10.3390/min10080663]

7. Al-Naji, A.; Perera, A.G.; Mohammed, S.L.; Chahl, J. Life Signs Detector Using a Drone in Disaster Zones. Remote Sens.; 2019; 11, 2441. [DOI: https://dx.doi.org/10.3390/rs11202441]

8. Gupta, A.; Gupta, S.K. A survey on green unmanned aerial vehicles-based fog computing: Challenges and future perspective. Trans. Emerg. Telecommun. Technol.; 2022; 33, e4603. [DOI: https://dx.doi.org/10.1002/ett.4603]

9. Banerjee, A.; Sufian, A.; Paul, K.K.; Gupta, S.K. EDTP: Energy and Delay Optimized Trajectory Planning for UAV-IoT Environment. Comput. Netw.; 2022; 202, 108623. [DOI: https://dx.doi.org/10.1016/j.comnet.2021.108623]

10. El Haber, E.; Alameddine, H.A.; Assi, C.; Sharafeddine, S. UAV-aided ultra-reliable low-latency computation offloading in future IoT networks. IEEE Trans. Commun.; 2021; 69, pp. 6838-6851. [DOI: https://dx.doi.org/10.1109/TCOMM.2021.3096559]

11. Khan, A.; Gupta, S.; Gupta, S.K. Unmanned aerial vehicle-enabled layered architecture based solution for disaster management. Trans. Emerg. Telecommun. Technol.; 2021; 32, e4370. [DOI: https://dx.doi.org/10.1002/ett.4370]

12. Szczepanski, C.J.; Purushothaman, R. Sensors for UAVs dedicated to agriculture: Current scenarios and challenges. Aircr. Eng. Aerosp. Technol.; 2022; 94, pp. 31-44. [DOI: https://dx.doi.org/10.1108/AEAT-11-2020-0257]

13. Allred, B.; Martinez, L.; Fessehazion, M.K.; Rouse, G.; Koganti, T.; Freeland, R.; Eash, N.; Wishart, D.; Featheringill, R. Time of day impact on mapping agricultural subsurface drainage systems with UAV thermal infrared imagery. Agric. Water Manag.; 2021; 256, 107071. [DOI: https://dx.doi.org/10.1016/j.agwat.2021.107071]

14. Bagherian, M.; Alos, A. 3D UAV trajectory planning using evolutionary algorithms: A comparison study. Aeronaut. J.; 2015; 119, pp. 1271-1285. [DOI: https://dx.doi.org/10.1017/S0001924000011246]

15. Niu, X.; Yuan, X.; Zhou, Y.; Fan, H. UAV Track Planning Based on Evolution Algorithm in Embedded System. Microprocess. Microsyst.; 2020; 75, 103068. [DOI: https://dx.doi.org/10.1016/j.micpro.2020.103068]

16. Hosseinpoor, H.R.; Samadzadegan, F.; DadrasJavan, F. Pricise target geolocation and tracking based on uav video imagery. ISPRS Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci.; 2016; 41, pp. 243-249. [DOI: https://dx.doi.org/10.5194/isprs-archives-XLI-B6-243-2016]

17. Zhang, J.; Yan, J.; Zhang, P. Fixed-Wing UAV Formation Control Design with Collision Avoidance Based on an Improved Artificial Potential Field. IEEE Access; 2018; 6, pp. 78342-78351. [DOI: https://dx.doi.org/10.1109/ACCESS.2018.2885003]

18. Fan, X.; Guo, Y.; Liu, H.; Wei, B.; Liu, W. Improved Artificial Potential Field Method Applied for AUV Path Planning. Math. Probl. Eng.; 2020; 2020, 6523158. [DOI: https://dx.doi.org/10.1155/2020/6523158]

19. Zhang, J.; Wu, J.; Shen, X.; Li, Y. Autonomous land vehicle path planning algorithm based on improved heuristic function of A-Star. Int. J. Adv. Robot. Syst.; 2021; 18, 17298814211042730. [DOI: https://dx.doi.org/10.1177/17298814211042730]

20. Rostami, S.M.H.; Sangaiah, A.K.; Wang, J.; Liu, X. Obstacle avoidance of mobile robots using modified artificial potential field algorithm. J. Wirel. Commun. Netw.; 2019; 1, pp. 70-89. [DOI: https://dx.doi.org/10.1186/s13638-019-1396-2]

21. Yan, X.; Jiang, D.; Miao, R.; Li, Y. Formation Control and Obstacle Avoidance Algorithm of a Multi-USV System Based on Virtual Structure and Artificial Potential Field. J. Mar. Sci. Eng.; 2021; 9, 161. [DOI: https://dx.doi.org/10.3390/jmse9020161]

22. Li, J.; Zhang, W.; Hu, Y.; Li, X.; Wang, Z. Leader-follower uav formation model based on r5dos-intersection model. Comput. Mater. Contin.; 2021; 69, pp. 2493-2511. [DOI: https://dx.doi.org/10.32604/cmc.2021.018743]

23. Tang, G.; Tang, C.; Claramunt, C.; Hu, X.; Zhou, P. Geometric A-Star Algorithm: An Improved A-Star Algorithm for AGV Path Planning in a Port Environment. IEEE Access; 2021; 9, pp. 59196-59210. [DOI: https://dx.doi.org/10.1109/ACCESS.2021.3070054]