Frontiers in Computing and Intelligent Systems ISSN: 2832-6024 | Vol. 3, No. 2, 2023 74 Three-dimensional path planning of UAV in complex urban environment Fankai Chen*, Qinyu Liu, Xiaohan Cong, Xiuhuan Dong, Yuanyuan Zhang College of Electronic Engineering, Tianjin University of Technology and Education, Tianjin 300222, China * Corresponding author: Fankai Chen (Email: 1642426596@qq.com) Abstract: Aiming at the three-dimensional path planning problem of UAV in complex urban environment, the improved grid method is used to simulate the flight environment, and the safety of path planning is improved by building a safe flight area and introducing a navigation safety cost function. In order to solve the problems of A* (A_Star) algorithm in path planning, such as large number of nodes, large amount of computation and low planning efficiency, we can reduce the redundant checking process in the path search process by expanding the line of sight strategy, improve the algorithm search efficiency and smooth the planned lines. Analyze the characteristics of each stage of path planning, adaptively adjust the weight factor, design the flight cost function, shorten the length of path planning, and improve the speed of path planning. As a result of the experiment, the improved A* algorithm clearly decreased over the time of the path planning, the number of nodes and the total cost of the flight, and it was clarified that the planned route was smoother and more feasible than the traditional algorithm. The performance of the improved algorithm has been fully verified under the complexity of different cities, which provides a reference for the research of UAV path planning in urban environment. Keywords: UAV; Path planning; Improved A* algorithm. 1. Introduction With the continuous development of intelligent manufacturing technology, UAV have gained widespread attention and are used in all areas of life [1]. The city is the most frequent site of people's activities, dense buildings, and complex transportation networks, so some smart devices can't be effectively demonstrated, and in recent years the influence of the plague has faced a major pressure on urban logistics. It is necessary to seek an efficient and safe contactless delivery system instead of artificial transportation. The use of land intelligence facilities such as unmanned vehicles can alleviate the pressure of logistics transportation, but it is likely to cause traffic congestion, traffic accidents, and it is difficult to provide a visit delivery service. The urban airspace environment is relatively open. As an aerial vehicle, UAV is favored by people with its advantages of flexibility and maneuverability [2]. UAV will be widely applied to various areas of the city as a main force of new age smart equipment. In this paper, the technology of three-dimensional path planning for UAV is studied in complex urban environment, so that UAV can be better used in cities and provide more convenient and comfortable services for cities. The UAV path planning technology should explore the best path to reduce costs on the premise of ensuring the safety of flight missions. The core of UAV path planning technology is path planning algorithm. In terms of 3D path search algorithms, there are traditional algorithms such as artificial potential field method [3] and fuzzy logic algorithm [4], heuristic path optimization algorithms such as A* algorithm [5] and Dijkstra algorithm [6], and swarm intelligence simulation optimization algorithms [7] such as genetic algorithm and ant colony algorithm [8]. Based on the A* algorithm, this paper improves and optimizes the existing algorithm for complex urban environments, adapts the comprehensive flight cost function by adaptive modification of algorithm parameters, and introduces the optimization algorithm model of the line of sight expansion mode to ensure a safe, to achieve efficient and fast three-dimensional light rail planning. 2. Environment construction The urban environment is mainly composed of closely connected high-rise buildings, so the grid method can be used to simulate the urban environment. The urban space is divided into a discrete grid, the protruding part represents the obstacle, the obstacle height simulates the height of the building, and the other area represents the free region. A three-dimensional digital map can be formed. As shown in Figure 1. Figure 1. Urban building map Considering the safety of UAV flight, the standard map is converted to the drone flight safety map, and the standard height map of the height and width of the building is increased. The external extension area is the drone and building buffers. Set the failure area to 1, buffer area to 0.5, and free space to 0. In the trajectory planning stage, if the obstacle is 1, it means that the path will not be flown strictly. And the buffer allocated to the building of 0.5 is an evolved trajectory after the constant safety cost is increased, and the safety flying buffer can be formed to increase the safety of the flight trajectory. The improved grid assignment method is shown in Figure 2. 75 Figure 2. Grid assignment method 3. Algorithm analysis 3.1. Traditional A* algorithm A* algorithm is one of the most common algorithms in path planning for better performance and accuracy, and determines the optimal route by constantly evaluating the cost of search nodes in space [9]. Algorithm expression is shown in equation (1). F(n)=G(n)+H(n) (1) The expression represents the actual cost of the trip from the start node to the current node, representing the estimated cost of trip from the current node to the target node. Selecting a path node is globally evaluated that the minimum node is the next routing point to find the optimal path. 3.2. Algorithm of this paper 3.2.1. Cost function weight optimization There are several drawbacks in the cost function of the traditional A* algorithm, and the grid diagram always has a relatively small F(n) value and has a relatively small H(n) ratio, and these types of nodes depend primarily on the actual cost of the trip, which is blurred by the algorithm's direction and too many searches for invalid nodes Operation load is large. Therefore, this paper optimizes the weight of the cost function of A* algorithm. As shown in Formula (2) F(n)=Ξ±*G(n)+Ξ²*H(n) (2) The definition of G(n) and H(n) determined the effect of the path search, and analyzed whether the relatively large algorithm had a better late search effect and that the relatively large algorithm had better early search effects. The minimum value of the weight H(n) is set, and the direction is blurred while the algorithm is too low and the direction is blurred while searching the algorithm, and the search node is too numerous and the search time is too long. Adjust the weight of G(n) and H(n), As shown in Formula (3) { 𝛼(𝑛) = 𝛼0 (1βˆ’ 𝐻(𝑛) 𝐷 ) 𝛼(𝑛) < π›Όπ‘šπ‘Žπ‘₯ 𝛽(𝑛) = 𝛽0 ( 𝐻(𝑛) 𝐷 ) 𝛽(𝑛) > π›½π‘šπ‘–π‘› (3) Indicates that the initial value of the expression is greater than 1, indicating the weight of the current node's cost function. The algorithm gradually increases and decreases gradually during search. D represents the Euclidean distance between the start point and the target node. The rationality of the algorithm execution and the route search efficiency are improved by changing the weight. 3.2.2. Introducing the Cost Function of Navigation Safety There is a flight area near the obstacle in planning a trajectory, but there is a certain risk in the flight of the area, and the safety cost evaluation of different areas is combined with the above described mesh allocation method, and the trajectory safety cost function is designed as the expression (4). S(n)=mD (4) Here, m represents the safety of the region in which the node is present, the free area, the buffer area and the fault area, and m takes 0, 0.5 and infinity values, so that the safety cost of each position is 0, S(n), infinity, and the path planning option is enhanced. 3.2.3. Improvement of comprehensive evaluation function Since the safety cost of each point is calculated at the total orbital cost, the global evaluation function is improved to balance the impact of the actual navigation cost function, the estimated navigation cost function and the safety cost function on the orbit search, and the drone specific elements and environmental conditions are taken into consideration as shown in equation (5). F(n)=Ξ±*G(n)+Ξ²*H(n)+Ξ³*S(n) (5) There is the weight coefficient of safety cost. 3.2.4. Line of sight search strategy optimization Figure 3. Schematic diagram of line of sight expansion For path node search, the existing A* algorithm uses the path search between the current node and adjacent nodes [10]. This search method easily leads to a large number of calculations, multi-path nodes, frequent direction changes, 76 high UAV flight costs and high risks[11].The algorithm in this paper not only limits the flight line of sight around the current node, but also adopts the line of sight expansion strategy considering the visibility of the previous node, which can reduce the trajectory navigation nodes, greatly reduce the frequency of flight direction changes of UAVs, and make the flight trajectory more smooth and safe. Its principle is shown in Figure 3. Here, the blue area is the obstacle area, the white area is the free area, the path search from the start node, the search direction as shown in Figure 3(a); find the nearest point B2 at the end of the path as an extension node, with this node to reachability search as shown in Figure 3(b); so as to find the next extension point B3, as shown in Figure 3(c); as the next extension point C4 and the start node between the possible route obstacle region, so the path is adjusted to route A1-B3- C4 from the free area, while the C4 node as a new realization of the expandable node as shown in Figure 3(d); and so on, until the search to the end, avoiding the obstacle area encountered, the planned path is A1-B2-B3-C4-D5, as shown in Figure 3(e); at this point is not the shortest path, on the basis of which the line of sight between the nodes is judged permeability, the route is optimized, and the optimal path is A1-B3-D5, as in Figure 3(f). By using the line-of-sight expansion strategy, the path planning route nodes are reduced, and the problem of too many flight direction shifts is improved. 3.2.5. Algorithm implementation steps Step 1: initialize the algorithm, the starting point and the end point are set, the parameter weight is set, the open and close tables are established, and the start node is put in the open table. Step 2: determine whether the open table is empty and determine if the search fails, and the program is terminated. Step 3: update the close table by removing the lowest node cost from the open table (n) to the close table. Step 4: whether or not the current section is the target node, and if it is a return path, go to step 7, and if not, perform a line of sight inspection and proceed to step 5. Step 5: the line of sight detection determines whether there is an executable space (if any), closes the table directly, otherwise searches for all nodes around that point, the adjacent node n closes the table, ignores the visibility, and opens the table. Step 6: the table is updated, the cost function is calculated, sorted and advanced to step 3. Step 7: merge the path and examine the path information and output the result. 4. Simulation Analysis In order to analyze the feasibility and effectiveness of the algorithm, the controlled comparison method was used to verify the experiment, and the experimental simulation was carried out using a three-dimensional grid map with 100*100*20 experimental area and different obstacle densities. In this experiment, MATLAB R2019a simulation algorithm is used. The relevant weights are 𝛼 = 1.5, 𝛽 = 1.5, 𝛾 = 1, and the density of obstacles on the map is set to 5%, 10%, 15%, 20%, 25%, etc. To avoid the contingency of experimental data, for different maps, the traditional algorithm and the improved algorithm are simulated 10 times each, and the data with the best effect are taken as the analysis data of the experiment. The experimental results are recorded in Table 1, and 25% of the experimental guidance tracks are planned as shown in Figure 4 (a) and Figure 4 (b). The altitude and flight distance are shown in Figure 4 (c). Table 1. Test record of two algorithms under different urban building densities Type of algorithm Building density Number of path nodes Path length/m Planning time/s A* 5% 85 118.9477 5.4797 10% 85 118.9477 5.0338 15% 85 119.5834 8.9334 20% 85 120.2191 8.4649 25% 85 120.8548 14.5524 Improve A* 5% 7 115.8948 0.2404 10% 8 116.0125 0.5037 15% 7 116.0844 1.1005 20% 11 116.6239 1.4091 25% 11 116.6689 0.4349 (a) (b) (c) Figure 4. Route planning when the urban building density is 25%: Figure(a) UAV path planning diagram; Figure(b) Top view of path planning; Figure(c) Variation of flight altitude and distance 77 As a result of the experiment, the improved A* algorithm can complete the path plan from the beginning to the end, and proved the feasibility of the improved a * algorithm. As shown in Table 1, with the increase in urban building density, the algorithm is improved compared with the conventional algorithm, the trajectory search node is less, the flight distance is shorter, the required planning time is remarkably reduced, the performance is remarkably improved, and the drone locus plan is more advantageous. As shown in Figure 4 (a), the improved A* algorithm is more reasonable for the drone flight trajectory in a complex environment with a 25% urban building density, as seen from above, the improved algorithm planning line is almost the shortest distance and greatly conserved costs. Figure 4 (c) clearly shows the correspondence between the flight distance and the altitude during the trajectory planning, and the transition between the nodes to improve the algorithm is relatively smooth, and the change in the angle is not so frequent, and the frequent direction change is avoided during the drone flight period, and the flight safety of the drone is enhanced. Based on the simulation results, the improved algorithm greatly improves the performance of traditional algorithms in the urban unmanned vehicle trajectory planning, satisfies the demand for unmanned vehicle trajectory planning, saving flight costs, and increasing safety. 5. Conclusion Based on the traditional A* algorithm, optimize it by combining drone's flight requirements and the urban environment features. Path planning integrates the cost of navigation by improving navigation cost function, increasing route planning, reducing path planning, increasing route security constraints, and adjusting the weight of adaptive cost functions. By extending the line of sight strategy, the width and frequency of the direction change in the drone flight are reduced, and the algorithm makes the route more smoothly. The optimization algorithm has the advantage that the path length is short, the number of nodes is small, and the planning time is fast in the complicated urban environment. If the flight requirements for drones are met, the planned trajectory becomes safer and more convenient. References [1] Muchiri G N, Kimathi S. A review of applications and potential applications of UAV[C]//Proceedings of the Sustainable Research and Innovation Conference. 2022: 280-283. [2] Kandrot S, Hayes S, Holloway P. Applications of Uncrewed Aerial Vehicles (UAV) Technology to Support Integrated Coastal Zone Management and the UN Sustainable Development Goals at the Coast[J]. Estuaries and Coasts, 2022, 45(5): 1230-1249. [3] Chen Y, Luo G, Mei Y, et al. UAV path planning using artificial potential field method updated by optimal control theory[J]. International Journal of Systems Science, 2016, 47(6): 1407-1420. [4] Pandey A, Sonkar R K, Pandey K K, et al. Path planning navigation of mobile robot with obstacles avoidance using fuzzy logic controller[C]//2014 IEEE 8th international conference on intelligent systems and control (ISCO). IEEE, 2014: 39-41. [5] Mandloi D, Arya R, Verma A K. Unmanned aerial vehicle path planning based on A* algorithm and its variants in 3d environment[J]. International Journal of System Assurance Engineering and Management, 2021, 12(5): 990-1000. [6] He Z F, Zhao L. The comparison of four UAV path planning algorithms based on geometry search algorithm[C]//2017 9th International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC). IEEE, 2017, 2: 33-36. [7] Silva Arantes J, Silva Arantes M, Motta Toledo C F, et al. Heuristic and genetic algorithm approaches for UAV path planning under critical situation[J]. International Journal on Artificial Intelligence Tools, 2017, 26(01): 1760008. [8] Xiang A, Wang L. Research on Path Planning of UAV Forest Fire Fighting Based on Improved Ant Colony Algorithm[C] // 2021 7th International Conference on Computing and Artificial Intelligence. 2021: 289-295. [9] SΓ‘nchez-IbÑñez J R, PΓ©rez-del-Pulgar C J, GarcΓ­a-Cerezo A. Path Planning for Autonomous Mobile Robots: A Review[J]. Sensors, 2021, 21(23): 7898. [10] Zhang L, Li Y. Mobile Robot Path Planning Algorithm Based on Improved A Star[C] //Journal of Physics: Conference Series. IOP Publishing, 2021, 1848(1): 012013. [11] Zhang Z, Wu J, Dai J, et al. Optimal path planning with modified A-Star algorithm for stealth unmanned aerial vehicles in 3D network radar environment[J]. Proceedings of the Institution of Mechanical Engineers, Part G: Journal of Aerospace Engineering, 2022, 236(1): 72-81.