Three-dimensional path planning algorithm for UAV based on obstacle envelopes

doi:10.23919/JSEE.2026.000126

Abstract

Abstract:

In this paper, a three-dimension envelope-based path planning algorithm (3DE-PP) is proposed to automatically generate a collision-free trajectory for unmanned aerial vehicle (UAV). Firstly, focusing on the defects of low efficiency of obstacle modelling representation and large search space, an elliptical envelope-based obstacle modelling method is proposed to facilitate the generation of obstacle avoidance waypoints and improve the search efficiency. Then, considering safety and aiming at minimum energy consumption, waypoint generation strategies based on tangent guidance and minimum deviation are designed. Meanwhile, aiming at the UAV motion constraint, a three-dimension (3D) path construction method based on improved Dubins is proposed. Finally, combined with the main path generation algorithm based on saving algorithm, a safe and feasible 3D flight path is constructed by considering the power constraint of UAV and the access of charging stations comprehensively. The proposed 3DE-PP is compared with four algorithms (SAS, Dubins-RRT*, APF, 3D-TG) by 15 examples generated from five typical environments, and the computational results confirm its advantages. Furthermore, a real-world case is introduced, and the key factors influencing path planning are analyzed.

Key words: ellipsoidal envelope, unmanned aerial vehicle (UAV), path planning, obstacle avoidance

Yuzhen ZHOU, Yao LIU, Jincai HUANG, Jianmai SHI. Three-dimensional path planning algorithm for UAV based on obstacle envelopes[J]. Journal of Systems Engineering and Electronics, 2026, 37(3): 1042-1058.

Figures/Tables 21

Fig 1

Table 1

Fig 2

Table 2

Fig 3

Fig 4

Fig 5

Fig 6

Fig 7

Fig 8

Table 3

Table 4

Fig 9

Fig 10

Fig 11

Fig 12

Fig 13

Table 5

Fig 14

Table 6

Fig 15

References 58

1	BURNS L D A vision of our transport future. Nature, 2013, 497 (7448): 181- 182. doi: 10.1038/497181a
2	LE V S, ZOLFAGHARI A, POLAK J Autonomous cars: the tension between occupant experience and intersection capacity. Transportation Research Part C: Emerging Technologies, 2015, 52, 1- 14.
3	JARAŠŪNIENĖ A, IŠORAITĖ M, PETRAŠKA A Developing small-cargo flows in cities using unmanned aerial vehicles. Future Transportation, 2024, 4 (2): 450- 474. doi: 10.3390/futuretransp4020022
4	FANG Z, SAVKIN A V Strategies for optimized UAV surveillance in various tasks and scenarios: a review. Drones, 2024, 8 (5): 193- 233. doi: 10.3390/drones8050193
5	AGRAWAL J, ARAFAT M Y Transforming farming: a review of AI-powered UAV technologies in precision agriculture. Drones, 2024, 8 (11): 664- 688. doi: 10.3390/drones8110664
6	SUN C, FONTANESI G, CANBERK B, et al Advancing UAV communications: a comprehensive survey of cutting-edge machine learning techniques. IEEE Open Journal of Vehicular Technology, 2024, 5, 825- 854. doi: 10.1109/OJVT.2024.3401024
7	PAN Y, LI L F, QIN J J, et al Unmanned aerial vehicle-human collaboration route planning for intelligent infrastructure inspection. Computer-Aided Civil and Infrastructure Engineering, 2024, 39 (14): 2074- 2104.
8	ZHANG J, DU X, DONG Q C, et al Distributed collaborative complete coverage path planning based on hybrid strategy. Journal of Systems Engineering and Electronics, 2023, 35 (2): 463- 472.
9	YANG L M, ZHANG X Y, LI Z P, et al A LODBO algorithm for multi-UAV search and rescue path planning in disaster areas. Chinese Journal of Aeronautics, 2025, 38 (2): 1000- 9361.
10	JUNG S, KIM H Analysis of amazon prime air UAV delivery service. Journal of Knowledge Information Technology and Systems, 2017, 12 (2): 253- 266. doi: 10.34163/jkits.2017.12.2.005
11	LEVIN A. Alphabet and chipotle are bringing burrito delivery drones to campus. https://www.bloomberg.com/news/articles/2016-09-08/burrito-by-drone-coming-to-campus-in-test-of-alphabet-s-delivery.
12	FAN F F. JD. com opens first unmanned sorting center. https://www.chinadaily.com.cn/specials/0803huawei.pdf.
13	MOHANTY S N, RAVINDRA J V R, NARAYANA G S, et al. Drone technology: future trends and practical applications. Hoboken: John Wiley & Sons, 2023.
14	WALKER R, JIWANI R. Reinventing e-commerce: Amazon’s bet on unmanned vehicle delivery. London: Kellogg School of Management, 2015.
15	KELLEHER K. UPS, matternet delivering medical samples in North Carolina using drones. https://www.auvsi.org/industry-news/ups-matternet-deliveringmedical-samples-north-carolina-using-drones.
16	LEE Y M A study on the current status and case of the logistics industry using drone. Journal of Korea Culture Industry, 2020, 20 (4): 75- 85. doi: 10.35174/jkci.2020.12.20.4.75
17	YANG L, QI J, XIAO J, et al. A literature review of UAV 3D path planning. Proc. of the 11th World Congress on Intelligent Control and Automation, 2014: 2376−2381.
18	MAZAHERI H, GOLI S, NOUROLLAH A A survey of 3D space path-planning methods and algorithms. ACM Computing Surveys, 2024, 57 (1): 1- 32.
19	KHAN M T R, MUHAMMAD S M, RU Y, et al Aspects of unmanned aerial vehicles path planning: overview and applications. International Journal of Communication Systems, 2021, 34 (10): 1074- 5351.
20	CHEN Q, WANG Y J, SUN Y F An improved dung beetle optimizer for UAV 3D path planning. The Journal of Supercomputing, 2024, 80 (18): 26537- 26567. doi: 10.1007/s11227-024-06414-0
21	LUO J H, TIAN Y X, WANG Z Y Research on unmanned aerial vehicle path planning. Drones, 2024, 8 (2): 51. doi: 10.3390/drones8020051
22	PHALAPANYAKOON K, SIRIPONGWUTIKORN P Route planning of heterogeneous unmanned aerial vehicles under recharging and mission time with carrying payload constraints. Journal of Industrial Engineering and Management, 2023, 16 (2): 215- 235. doi: 10.3926/jiem.4381
23	CHEN F, ZHENG Y, WANG Z, et al. RBI-RRT*: efficient sampling-based path planning for high-dimensional state space. Proc. of the IEEE International Conference on Robotics and Automation. 2024: 8721−8727.
24	LIU M J, ZHANG H X, YANG J, et al A path planning algorithm for three-dimensional collision avoidance based on potential field and B-spline boundary curve. Aerospace Science and Technology, 2024, 144, 1270- 9638. doi: 10.1016/j.ast.2023.108763
25	JIANG Y, XU X X, ZHENG M Y, et al Evolutionary computation for unmanned aerial vehicle path planning: a survey. Artificial Intelligence Review, 2024, 57, 267.
26	ZHANG J D, GUO Y K, ZHENG L H, et al Real-time UAV path planning based on LSTM network. Journal of Systems Engineering and Electronics, 2024, 35 (2): 374- 385. doi: 10.23919/JSEE.2023.000157
27	SZCZERBA R J, GALKOWSKI P, GLICKTEIN I S, et al Robust algorithm for real-time route planning. IEEE Trans. on Aerospace and Electronic Systems, 2000, 36 (3): 869- 878. doi: 10.1109/7.869506
28	LIU S, WATTERSON M, MOHTA K, et al Planning dynamically feasible trajectories for quadrotors using safe flight corridors in 3-d complex environments. IEEE Robotics and Automation Letters, 2017, 2 (3): 1688- 1695. doi: 10.1109/LRA.2017.2663526
29	ZHANG N, ZHANG M, LOW K H 3D path planning and real-time collision resolution of multirotor drone operations in complex urban low-altitude airspace. Transportation Research Part C: Emerging Technologies, 2021, 129, 103123. doi: 10.1016/j.trc.2021.103123
30	ROHNERT H Shortest paths in the plane with convex polygonal obstacles. Information Processing Letters, 1986, 23 (2): 71- 76. doi: 10.1016/0020-0190(86)90045-1
31	LIU Y H, ARIMOTO S Path planning using a tangent graph for mobile robots among polygonal and curved obstacles: communication. The International Journal of Robotics Research, 1992, 11 (4): 376- 382. doi: 10.1177/027836499201100409
32	LIU H, WU G H, ZHOU L, et al Tangent-based path planning for uav in a 3-D low altitude urban environment. IEEE Trans. on Intelligent Transportation Systems, 2023, 24 (11): 12062- 12077. doi: 10.1109/TITS.2023.3285568
33	CHEN H, CHANG K, AGATE C S UAV path planning with tangent-plus-Lyapunov vector field guidance and obstacle avoidance. IEEE Trans. on Aerospace and Electronic Systems, 2013, 49 (2): 840- 856. doi: 10.1109/TAES.2013.6494384
34	LIU Y S, WANG Q X, HU H S, et al A novel real-time moving target tracking and path planning system for a quadrotor UAV in unknown unstructured outdoor scenes. IEEE Trans. on Systems, Man, and Cybernetics: Systems, 2018, 49 (11): 2362- 2372. doi: 10.1109/tsmc.2018.2808471
35	LIU H, LI X M, FAN M F, et al An autonomous path planning method for unmanned aerial vehicle based on a tangent intersection and target guidance strategy. IEEE Trans. on Intelligent Transportation Systems, 2020, 23 (4): 3061- 3073. doi: 10.1109/tits.2020.3030444
36	YANG F, LEE D H, KELLER J, et al. Graph-based topological exploration planning in large-scale 3D environments. Proc. of the IEEE International Conference on Robotics and Automation, 2021: 12730−12736.
37	LIANG X, MENG G L, XU Y M, et al A geometrical path planning method for unmanned aerial vehicle in 2D/3D complex environment. Intelligent Service Robotics, 2018, 11 (3): 301- 312. doi: 10.1007/s11370-018-0254-0
38	KARAMAN S, WALTER M R, PEREZ A, et al. Anytime motion planning using the RRT. Proc. of the IEEE International Conference on Robotics and Automation. 2011: 1478−1483.
39	LIU J, XU T, YANG S X, et al Navigation and visual feedback control for magnetically driven helical miniature swimmers. IEEE Trans. on Industrial Informatics, 2019, 16 (1): 477- 487. doi: 10.1109/tii.2019.2913762
40	GAMMELL J D, SRINIVASA S S, BARFOOT T D. Informed RRT*: optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic. Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems, 2014: 2997−3004.
41	WARREN C W. Global path planning using artificial potential fields. Proc. of the IEEE International Conference on Robotics and Automation, 1989: 316−321.
42	ROBERGE V, TARBOUCHI M, LABONTÉ G Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning. IEEE Trans. on Industrial Informatics, 2012, 9 (1): 132- 141. doi: 10.1109/tii.2012.2198665
43	WU Y, LOW K H, PANG B, et al Swarm-based 4D path planning for drone operations in urban environments. IEEE Trans. on Vehicular Technology, 2021, 70 (8): 7464- 7479. doi: 10.1109/TVT.2021.3093318
44	VENTURINI F, MASON F, PASE F, et al. Distributed reinforcement learning for flexible UAV swarm control with transfer learning capabilities. Proc. of the 6th ACM Workshop on Micro Aerial Vehicle Networks, Systems, and Applications, 2020. DOI: 10.1145/3396864.3399701.
45	ZHANG C Q, ZHOU W J, QIN W D, et al A novel UAV path planning approach: heuristic crossing search and rescue optimization algorithm. Expert Systems with Applications, 2023, 215, 119- 243.
46	XU J Y, SHI M J, TANG F, et al. Dubins-A*: a new global path planning scheme for fixed-wing UAV with irregular obstacles avoidance. Proc. of the 7th International Conference on Electronics Technology, 2024: 636−641.
47	KUMAR D P, DARBHA S, MANYAM S G, et al. A new approach to motion planning in 3D for a dubins vehicle: special case on a sphere. https://arxiv.org/abs/2504.01215.
48	FIGLIOZZI M A Lifecycle modeling and assessment of unmanned aerial vehicles (drones) CO2e emissions. Transportation Research Part D: Transport and Environment, 2017, 57, 251- 261. doi: 10.1016/j.trd.2017.09.011
49	REKLEITIS I M, DUDEK G, MILIOS E E. Graph-based exploration using multiple robots. Proc. of the International Symposium on Distributed Autonomous Robotic Systems, 2000: 241−250.
50	CLARKE G, WRIGHT J W Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 1964, 12 (4): 568- 581. doi: 10.1007/978-3-642-27922-5_18
51	CHITSAZ H, LAVALLE S M. Time-optimal paths for a Dubins airplane. Proc. of the IEEE 46th Conference on Decision and Control, 2007: 2379−2384.
52	MCLAIN T, BEARD R W, OWEN M. Implementing Dubins airplane paths on fixed-wing UAVs. Dordrecht: Springer Netherlands, 2014.
53	HOTA S, GHOSE D. Optimal geometrical path in 3D with curvature constraint. Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems, 2010: 113−118.
54	FREITAS E J R, COHEN M W, NETO A A, et al DE3D-NURBS: a differential evolution-based 3D path-planner integrating kinematic constraints and obstacle avoidance. Knowledge-Based Systems, 2024, 300, 112084.
55	TSARDOULIAS E G, ILIAKOPOULOU A, KARGAKOS A, et al A review of global path planning methods for occupancy grid maps regardless of obstacle density. Journal of Intelligent & Robotic Systems, 2016, 84 (1): 829- 858. doi: 10.1007/s10846-016-0362-z
56	BI C Y, LIU J H, WANG J A, et al. Motion planning for fixed-wing UAV using modified Dubins-RRT* algorithm. Proc. of the International Conference on Guidance, Navigation and Control, 2024: 128−138.
57	LAU D, EDEN J, OETOMO D Fluid motion planner for nonholonomic 3-D mobile robots with kinematic constraints. IEEE Trans. on Robotics, 2015, 31 (6): 1537- 1547. doi: 10.1109/TRO.2015.2482078
58	COHEN I, EPSTEIN C, SHIMA T On the discretized dubins traveling salesman problem. IISE Transactions, 2017, 49 (2): 238- 254. doi: 10.1080/0740817X.2016.1217101

Notation	Description
$ {Y}_{{\mathrm{max}}} $	Maximum UAV power
$ {P}_{i} $	The waypoint
$ E\left({P}_{i},{P}_{j}\right) $	The energy consumption between $ {P}_{i} $ and $ {P}_{j} $
$ {m}_{t} $	The net weight of the drone
$ {m}_{d} $	The weight of the battery
$ {m}_{1} $	The weight of the cargo
$ {\theta }_{\nu } $	The lift-to-drag ratio, related to speed
$ \eta $	The energy transfer efficiency
g	The gravitational acceleration
$ v $	The flight speed
$ {R}_{\min} $	The minimum turning radius
$ {R}_{\max} $	The limb rate
$ r $	The minimum safety distance
$ {H}_{\max} $	The maximum altitude
$ {L}_{i} $	The obstacles ($ i=1,2,\cdots , $N)
$ {x}_{i},{y}_{i},{z}_{i} $	The coordinates of the centre point of the obstacle
$ {l}_{i},{w}_{i},{h}_{i} $	The length, width and height of the obstacle

Notation	Description
$ S $	Points set
$ L $	Obstacle list
$ T $	Generated path points
$ O,D $	Origin and destination points, i.e., two vertices of each sub-path
$ {\mathrm{Pa}} $	Set of determined waypoints used to generate collision-free edges in order
$ {\mathrm{Ca}} $	Set of candidate waypoints
$ {\mathrm{Ba}} $	Set that records the obstacles avoided
$ H $	The cruising altitude

Example	Environment	Number of obstacles	Size/km	Height of obstacles/m
E1	Fig. 8(a)	8	1*1	30−100
E2	Fig. 8(b)	8	1*1	30−100
E3	Fig. 8(c)	20	1*1	30−100
E4	Fig. 8(d)	40	1*1	30−100
E5	Fig. 8(e)	30	1*1	30−100
E6	Fig. 8(a)	8	2*2	30−100
E7	Fig. 8(b)	8	2*2	30−100
E8	Fig. 8(c)	20	2*2	30−100
E9	Fig. 8(d)	40	2*2	30−100
E10	Fig. 8(e)	30	2*2	30−100
E11	Fig. 8(a)	32	2*2	30−100
E12	Fig. 8(b)	32	2*2	30−100
E13	Fig. 8(c)	80	2*2	30−100
E14	Fig. 8(d)	160	2*2	30−100
E15	Fig. 8(e)	120	2*2	30−100

Example	Energy consumption/kWh					Gap/%					Time/s
Example	Dubins-RRT*	SAS	APF	3D-TG	3DE-PP	Dubins-RRT*	SAS	APF	3D-TG	3DE-PP	Dubins-RRT*	SAS	APF	3D-TG	3DE-PP
E1	1.73	1.58	1.60	1.60	1.55	11.54	2.26	3.59	3.12	0.00	343.23	0.33	0.01	0.02	1.03
E2	1.60	1.57	1.57	1.59	1.53	4.75	2.90	2.99	4.02	0.00	539.25	0.56	0.01	0.00	0.91
E3	1.67	1.59	1.76	1.61	1.57	6.95	1.35	12.76	2.86	0.00	525.46	0.60	0.02	0.01	1.26
E4	1.85	1.57	1.87	1.56	1.61	18.76	1.11	20.47	0.00	3.48	556.02	0.02	0.02	0.01	1.11
E5	1.89	1.56	2.46	1.58	1.54	22.47	1.02	59.56	2.71	0.00	491.28	0.01	0.03	0.01	1.24
E6	3.10	3.09	2.35	2.82	2.72	31.52	31.18	0.00	19.87	15.56	693.71	0.09	0.01	0.44	0.96
E7	3.18	2.89	2.77	2.83	2.74	16.19	5.83	1.13	3.54	0.00	490.25	0.96	0.04	0.01	0.92
E8	3.33	2.88	3.02	2.84	2.74	21.64	5.21	10.33	3.72	0.00	509.06	1.09	0.03	0.02	1.17
E9	3.56	3.22	3.15	2.92	2.90	22.72	11.19	8.67	0.89	0.00	305.78	1.26	0.02	0.03	1.54
E10	2.84	2.92	3.30	2.84	2.81	1.16	3.95	17.65	1.27	0.00	775.14	1.84	0.07	0.01	1.71
E11	3.79	2.96	2.92	2.78	2.77	36.97	6.89	5.63	0.56	0.00	402.80	0.07	0.05	0.01	1.31
E12	3.33	2.92	3.05	2.88	2.81	18.37	3.76	8.23	2.33	0.00	661.65	0.05	0.02	0.01	0.88
E13	3.59	2.92	3.50	2.83	2.89	27.01	3.20	23.73	0.00	2.14	920.22	0.53	0.04	0.03	1.76
E14	3.94	2.81	3.72	2.91	2.87	40.21	0.00	32.28	3.40	2.12	1017.64	0.24	0.10	0.03	1.74
E15	3.53	2.81	3.27	2.82	2.80	26.26	0.25	16.83	0.76	0.00	727.30	0.91	0.07	0.02	1.63

Example	Energy consumption/Wh
Example	3DE-PP without fly-over	3DE-PP
1	1807.586	1807.586
2	1812.672	1812.672
3	1843.703	1844.772
4	1848.161	1849.374
5	1765.162	1766.437
6	1829.947	1871.858
7	1820.236	1844.217
8	1788.739	1857.109
9	1830.160	1849.126
10	1818.768	1837.652
11	1825.433	1873.088
12	1873.707	1922.271
13	1877.794	1942.789
14	1879.739	1942.802
15	1872.559	1965.317