UAV Dynamic Path Planning Algorithm Combined with Dynamic Window Approach

doi:10.16182/j.issn1004731x.joss.23-0993

Abstract

Abstract:

To solve the problem of the poor search for optimal performance and obstacle avoidance ability of path planning algorithms in complex dynamic environments, a UAV dynamic path planning algorithm combined with dynamic window approach (UAV-DPPA-DWA) is proposed. In the UAV-DPPA-DWA algorithm, a novel elliptic tangent graph algorithm based on the evaluation of offset degree and obstacle distance is proposed to obtain the optimal guidance path for the UAV in static environments. If the UAV detects moving obstacles, a localized obstacle avoidance trajectory will be generated using the dynamic window method with adaptive parameters. Otherwise, the UAV will continue to fly along the guidance path obtained in the static environment. Various types of complex dynamic obstacle avoidance scenarios are presented to verify the performance of the proposed algorithm in terms of both path length and flight time. The experimental results show that, compared with the DWA, A*-DWA, RRT-DWA and PRM-DWA algorithms, the UAV-DPPA-DWA not only has a stronger obstacle avoidance capability to achieve a feasible flight trajectory, but also can complete the task along the optimal path in shorter time.

Key words: UAV, path planning, elliptical tangent graph method, dynamic window approach, obstacle avoidance

CLC Number:

TP242

Liu Bin, Lan Ying, Huang Wentao, Fan Qinqin. UAV Dynamic Path Planning Algorithm Combined with Dynamic Window Approach[J]. Journal of System Simulation, 2024, 36(8): 1843-1853.

Figures/Tables 10

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Table 1

Table 2

Table 3

Fig. 5

Table 4

Fig. 6

References 32

1	Xu Cheng, Xu Ming, Yin Chanjuan. Optimized Multi-UAV Cooperative Path Planning Under the Complex Confrontation Environment[J]. Computer Communications, 2020, 162: 196-203.
2	Xia Zhaoyue, Du Jun, Wang Jingjing, et al. Multi-agent Reinforcement Learning Aided Intelligent UAV Swarm for Target Tracking[J]. IEEE Transactions on Vehicular Technology, 2022, 71(1): 931-945.
3	Choi Y, Choi Y, Briceno S, et al. Energy-constrained Multi-UAV Coverage Path Planning for an Aerial Imagery Mission Using Column Generation[J]. Journal of Intelligent & Robotic Systems, 2020, 97(1): 125-139.
4	Duchoň František, Babinec Andrej, Kajan Martin, et al. Path Planning with Modified a Star Algorithm for a Mobile Robot[J]. Procedia Engineering, 2014, 96: 59-69.
5	Yuan Chengren, Liu Guifeng, Zhang Wenqun, et al. An Efficient RRT Cache Method in Dynamic Environments for Path Planning[J]. Robotics and Autonomous Systems, 2020, 131: 103595.
6	李兆强, 张时雨. 基于快速RRT算法的三维路径规划算法研究[J]. 系统仿真学报, 2022, 34(3): 503-511.
	Li Zhaoqiang, Zhang Shiyu. Research on 3D Path Planning Algorithm Based on Fast RRT Algorithm[J]. Journal of System Simulation, 2022, 34(3): 503-511.
7	Ravankar Ankit A, Ravankar Abhijeet, Emaru Takanori, et al. HPPRM: Hybrid Potential Based Probabilistic Roadmap Algorithm for Improved Dynamic Path Planning of Mobile Robots[J]. IEEE Access, 2020, 8: 221743-221766.
8	邓向阳, 张立民, 方伟, 等. 基于双向汇聚引导蚁群算法的机器人路径规划[J]. 系统仿真学报, 2022, 34(5): 1101-1108.
	Deng Xiangyang, Zhang Limin, Fang Wei, et al. Robot Path Planning Based on Bidirectional Aggregation Ant Colony Optimization[J]. Journal of System Simulation, 2022, 34(5): 1101-1108.
9	Ajeil Fatin H, Ibraheem Kasim Ibraheem, Sahib Mouayad A, et al. Multi-objective Path Planning of an Autonomous Mobile Robot Using Hybrid PSO-MFB Optimization Algorithm[J]. Applied Soft Computing, 2020, 89: 106076.
10	Song Baoye, Wang Zidong, Zou Lei. An Improved PSO Algorithm for Smooth Path Planning of Mobile Robots Using Continuous High-degree Bezier Curve[J]. Applied Soft Computing, 2021, 100: 106960.
11	Liu Yiyang, Yan Shuaihua, Zhao Yang, et al. Improved Dyna-Q: A Reinforcement Learning Method Focused via Heuristic Graph for AGV Path Planning in Dynamic Environments[J]. Drones, 2022, 6(11): 365.
12	Chen Pengzhan, Pei Jiean, Lu Weiqing, et al. A Deep Reinforcement Learning Based Method for Real-time Path Planning and Dynamic Obstacle Avoidance[J]. Neurocomputing, 2022, 497: 64-75.
13	Chu Zhenzhong, Wang Fulun, Lei Tingjun, et al. Path Planning Based on Deep Reinforcement Learning for Autonomous Underwater Vehicles Under Ocean Current Disturbance[J]. IEEE Transactions on Intelligent Vehicles, 2023, 8(1): 108-120.
14	Fu Bing, Chen Lin, Zhou Yuntao, et al. An Improved A^* Algorithm for the Industrial Robot Path Planning with High Success Rate and Short Length[J]. Robotics and Autonomous Systems, 2018, 106: 26-37.
15	Zhang Zhen, Wu Defeng, Gu Jiadong, et al. A Path-planning Strategy for Unmanned Surface Vehicles Based on an Adaptive Hybrid Dynamic Stepsize and Target Attractive Force-RRT Algorithm[J]. Journal of Marine Science and Engineering, 2019, 7(5): 132.
16	Cao Kai, Cheng Qian, Gao Song, et al. Improved PRM for Path Planning in Narrow Passages[C]//2019 IEEE International Conference on Mechatronics and Automation (ICMA). Piscataway: IEEE, 2019: 45-50.
17	Liu Huan, Li Xiamiao, Fan Mingfeng, et al. An Autonomous Path Planning Method for Unmanned Aerial Vehicle Based on a Tangent Intersection and Target Guidance Strategy[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(4): 3061-3073.
18	Fox D, Burgard W, Thrun S. The Dynamic Window Approach to Collision Avoidance[J]. IEEE Robotics & Automation Magazine, 1997, 4(1): 23-33.
19	Chang Lu, Shan Liang, Jiang Chao, et al. Reinforcement Based Mobile Robot Path Planning with Improved Dynamic Window Approach in Unknown Environment[J]. Autonomous Robots, 2021, 45(1): 51-76.
20	Zhong Xunyu, Tian Jun, Hu Huosheng, et al. Hybrid Path Planning Based on Safe A^* Algorithm and Adaptive Window Approach for Mobile Robot in Large-scale Dynamic Environment[J]. Journal of Intelligent & Robotic Systems, 2020, 99(1): 65-77.
21	Han Sen, Wang Lei, Wang Yiting, et al. A Dynamically Hybrid Path Planning for Unmanned Surface Vehicles Based on Non-uniform Theta^* and Improved Dynamic Windows Approach[J]. Ocean Engineering, 2022, 257: 111655.
22	魏立新, 张钰锟, 孙浩, 等. 基于改进蚁群和DWA算法的机器人动态路径规划[J]. 控制与决策, 2022, 37(9): 2211-2216.
	Wei Lixin, Zhang Yukun, Sun Hao, et al. Robot Dynamic Path Planning Based on Improved Ant Colony and DWA Algorithm[J]. Control and Decision, 2022, 37(9): 2211-2216.
23	Li Yonggang, Jin Rencai, Xu Xiangrong, et al. A Mobile Robot Path Planning Algorithm Based on Improved A^* Algorithm and Dynamic Window Approach[J]. IEEE Access, 2022, 10: 57736-57747.
24	Dai Jun, Li Dongfang, Zhao Junwei, et al. Autonomous Navigation of Robots Based on the Improved Informed-RRT^∗ Algorithm and DWA[J]. Journal of Robotics, 2022, 2022(1): 3477265.
25	Fu Jinyu, Sun Guanghui, Yao Weiran, et al. On Trajectory Homotopy to Explore and Penetrate Dynamically of Multi-UAV[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(12): 24008-24019.
26	Yu Xiaobing, Li Chenliang, Yen G G. A Knee-guided Differential Evolution Algorithm for Unmanned Aerial Vehicle Path Planning in Disaster Management[J]. Applied Soft Computing, 2021, 98: 106857.
27	王洪斌, 尹鹏衡, 郑维, 等. 基于改进的A^*算法与动态窗口法的移动机器人路径规划[J]. 机器人, 2020, 42(3): 346-353.
	Wang Hongbin, Yin Pengheng, Zheng Wei, et al. Mobile Robot Path Planning Based on Improved A^*Algorithm and Dynamic Window Method[J]. Robot, 2020, 42(3): 346-353.
28	Yang Dian, Su Chen, Wu Hang, et al. Construction of Novel Self-adaptive Dynamic Window Approach Combined with Fuzzy Neural Network in Complex Dynamic Environments[J]. IEEE Access, 2022, 10: 104375-104383.
29	张伟龙, 单梁, 常路, 等. 基于改进DWA的多无人水面艇分布式避碰算法[J]. 控制与决策, 2023, 38(4): 951-962.
	Zhang Weilong, Shan Liang, Chang Lu, et al. Distributed Collision Avoidance Algorithm for Multiple Unmanned Surface Vessels Based on Improved DWA[J]. Control and Decision, 2023, 38(4): 951-962.
30	王永雄, 田永永, 李璇, 等. 穿越稠密障碍物的自适应动态窗口法[J]. 控制与决策, 2019, 34(5): 927-936.
	Wang Yongxiong, Tian Yongyong, Li Xuan, et al. Self-adaptive Dynamic Window Approach in Dense Obstacles[J]. Control and Decision, 2019, 34(5): 927-936.
31	常路, 单梁, 戴跃伟, 等. 未知环境下基于改进DWA的多机器人编队控制[J]. 控制与决策, 2022, 37(10): 2524-2534.
	Chang Lu, Shan Liang, Dai Yuewei, et al. Multi-robot Formation Control in Unknown Environment Based on Improved DWA[J]. Control and Decision, 2022, 37(10): 2524-2534.
32	Xu Ce, Xu Zhenbang, Xia Mingyi. Obstacle Avoidance in a Three-dimensional Dynamic Environment Based on Fuzzy Dynamic Windows[J]. Applied Sciences, 2021, 11(2): 504.

环境	布局	障碍物数量	起点S	终点E
E1	L1	11	(1,1)	(100,100)
E2	L2	11	(1,1)	(100,100)
E3	L3	41	(1,1)	(100,100)
E4	L4	41	(1,1)	(100,100)
E5	L3	61	(1,1)	(100,100)
E6	L4	61	(1,1)	(100,100)
E7	L3	81	(1,1)	(100,100)
E8	L4	81	(1,1)	(100,100)
E9	L5	39	(1,1)	(100,100)
E10	L5	59	(1,1)	(100,100)

参数	取值
最大线速度/(m/s)	2
最小线速度/(m/s)	0
最大角速度/((°)/s)	60
最小角速度/((°)/s)	0
线加速度/(m/s²)	0.5
角加速度/((°)/s²)	90
线速度分辨率/(m/s)	0.1
旋转角速度分辨率/((°)/s)	2
安全距离/m	0.5
模拟预测时间/s	1
单位时间Δt/s	0.5
窗口探测范围/m	5

环境		路径长度/m					航行时间/s
环境		DWA	A*-DWA	RRT-DWA	PRM-DWA	UAV-DDPA-DWA	DWA	A*-DWA	RRT-DWA	PRM-DWA	UAV-DDPA-DWA
E1	Mean	—	156.30	175.02	183.68	146.62	—	34.22	38.85	42.49	15.07
E1	SD	—	0	9.48	5.27	0	—	0.85	2.49	2.90	0.62
E2	Mean	164.84	150.22	159.36	155.69	147.81	36.67	31.63	34.95	34.44	32.47
E2	SD	0	0	3.84	2.96	0	1.32	0.26	2.54	1.82	0.73
E3	Mean	178.86	153.40	158.64	154.77	140.88	116.56	89.93	94.28	95.10	24.66
E3	SD	0	0	5.03	1.88	0	8.45	1.41	3.76	4.41	0.24
E4	Mean	158.98	162.85	156.02	164.05	141.12	112.79	97.22	94.06	98.18	52.31
E4	SD	0	0	5.79	4.89	0	1.97	0.90	5.55	2.75	0.85
E5	Mean	176.43	162.06	155.04	158.44	141.66	157.96	147.23	140.16	147.42	78.58
E5	SD	0	0	1.85	2.90	0	2.96	2.67	3.37	2.15	0.54
E6	Mean	187.72	152.26	163.70	157.20	144.42	167.95	132.63	140.98	141.80	90.94
E6	SD	0	0	4.44	2.48	0	1.70	1.49	5.84	2.51	0.40
E7	Mean	182.63	157.84	162.41	160.61	141.35	207.19	182.36	183.05	199.24	43.66
E7	SD	0	0	3.65	2.68	0	4.49	0.57	4.54	5.32	1.52
E8	Mean	171.39	157.71	161.92	172.86	143.38	321.19	255.00	221.54	203.68	113.33
E8	SD	0	0	2.22	2.85	0	9.18	1.57	3.72	5.41	0.76
E9	Mean	—	222.47	209.05	—	170.34	—	156.28	121.52	—	23.95
E9	SD	—	0	3.75	—	0	—	2.46	5.35	—	0.12
E10	Mean	—	—	214.33	—	171.29	—	—	208.09	—	86.54
E10	SD	—	—	3.37	—	0	—	—	3.30	—	0.62

环境	SETG-TG	IETG
E2	152.833	142.770
E3	145.890	140.940
E4	142.012	140.150
E5	148.580	141.69
E6	141.966	140.95

[1]	Yu Yiran, Lai Huicheng, Gao Guxue, Zhang Guo, Peng Wangyinan, Yang Longfei, Huang Junhao. Optimization Method for Multi Agricultural Machinery Collaborative Operation Based on Genetic Algorithm and A * Algorithm [J]. Journal of System Simulation, 2025, 37(9): 2397-2408.
[2]	Ni Peilong, Mao Pengjun, Wang Ning, Yang Mengjie. Robot Path Planning Based on Improved A-DDQN Algorithm [J]. Journal of System Simulation, 2025, 37(9): 2420-2430.
[3]	Zhang Kaixiang, Mao Jianlin, Wang Niya, Xu Zhihao. Multi-robot Hierarchical Collaborative k-robust Path Planning for Path Interference [J]. Journal of System Simulation, 2025, 37(8): 2074-2088.
[4]	Wan Yuhang, Zhu Zilu, Zhong Chunfu, Liu Yongkui, Lin Tingyu, Zhang Lin. Dynamic Path Planning for Robotic Arms Based on an Improved PPO Algorithm [J]. Journal of System Simulation, 2025, 37(6): 1462-1473.
[5]	Ye Chen, Shao Peng, Zhang Shaoping, Li Wenting, Zhou Tengming. Enhanced Artificial Gorilla Algorithm for Mobile Robot Path Planning [J]. Journal of System Simulation, 2025, 37(6): 1474-1485.
[6]	Zhang Yan, Li Binghua, Huo Tao, Liu Rong. Research on Robot Dynamic Obstacle Avoidance Method Based on Improved A* and Dynamic Window Algorithm [J]. Journal of System Simulation, 2025, 37(6): 1555-1564.
[7]	Qu Changhong, Wang Junjie, Wang Kun, Cui Qingyong, Chen Jiangyang, Wang Xinpeng. A Modeling and Simulation Method for Firepower Intelligent Decision-making of Directed Energy System Based on Joint DQN [J]. Journal of System Simulation, 2025, 37(5): 1256-1265.
[8]	Zhou Xiaohui, Li Yanqiang, Wang Yong, Zhao Decai, Yang Xiaoyao. Robot Path Planning Based on Ant Colony Algorithm with Dual Heuristic Information [J]. Journal of System Simulation, 2025, 37(5): 1280-1289.
[9]	Yu Die, Bao Baizhong, Si Yan, Duan Jian, Zhan Xiaobin, Shi Tielin. Mobile Robot Path Planning Based on Search-step Optimized A* Algorithm [J]. Journal of System Simulation, 2025, 37(4): 1041-1050.
[10]	Zhang Sen, Dai Qiangqiang. UAV Path Planning Based on Improved Deep Deterministic Policy Gradients [J]. Journal of System Simulation, 2025, 37(4): 875-881.
[11]	He Zhigang, Li Dayan, Wang Niya, Mao Jianlin, Wang Ning. A Multi-robot Collaborative Path Planning Algorithm with Chain Working Mode [J]. Journal of System Simulation, 2025, 37(4): 953-967.
[12]	Wang He, Xu Jianing, Yan Guangyu. Research on Pedestrian Avoidance Strategy for AGV Based on Deep Reinforcement Learning [J]. Journal of System Simulation, 2025, 37(3): 595-606.
[13]	Yang Chao, Zheng Ruiqun, Li Zhen, Zhang Hongwei, Tang Yanqun, Li Dongze. Parallel Task Transmission and Processing Optimization Scheme for UAV-assisted Internet of Vehicles [J]. Journal of System Simulation, 2025, 37(3): 635-645.
[14]	Lin Guijuan, Li Zihan, Wang Yu. Research on Improved A* Algorithm Path Planning Based on Global Key Point Extraction [J]. Journal of System Simulation, 2025, 37(3): 667-678.
[15]	Bai Yuxin, Chen Zhenya, Shi Ruitao, Su Weitao, Ma Zhuoqiang, Yang Shangjin. Research on Robot Path Planning Based on Improved Harris Hawks Algorithm [J]. Journal of System Simulation, 2025, 37(3): 742-752.