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]	Liu Jialun, Yang Fan, Xie Lingli, Li Shijie, Wang Tengfei. Research on Virtual Simulation Testing Technology for Intelligent Navigation Collision Avoidance Decision-making and Planning [J]. Journal of System Simulation, 2024, 36(8): 1780-1789.
[2]	Huang Zhifeng, Liu Yuanhua. UAV Path Planning Based on Improved Harris Hawk Algorithm and B-spline Curve [J]. Journal of System Simulation, 2024, 36(7): 1509-1524.
[3]	Wang Yaru, Yao Dexin, Liu Zengli, Peng Yi. Path Planning for Mobile Robot Based on Angle Search [J]. Journal of System Simulation, 2024, 36(7): 1643-1654.
[4]	Wang Tao, Ji Xiaodong. Optimal Trajectory of Full-duplex UAV Relaying over Hybrid Probability Channels [J]. Journal of System Simulation, 2024, 36(6): 1369-1377.
[5]	Zhu Jingyu, Zhang Hongli, Kuang Minchi, Shi Heng, Zhu Jihong, Qiao zhi, Zhou Wenqing. Curriculum Learning-based Simulation of UAV Air Combat Under Sparse Rewards [J]. Journal of System Simulation, 2024, 36(6): 1452-1467.
[6]	Lei Xu, Chen Jingyi, Chen Xiaoyang. Research on Path Planning of Warehouse Robot with Improved Harris Hawks Algorithm [J]. Journal of System Simulation, 2024, 36(5): 1081-1092.
[7]	Xiao Peng, Xie Feng, Ni Haihong, Zhang Min, Tang Zhili, Li Ni. Research on Collaborative Optimization Method of Multi-UAV Task Allocation and Path Planning [J]. Journal of System Simulation, 2024, 36(5): 1141-1151.
[8]	Liu Zesen, Bi Sheng, Guo Chuanhong, Wang Yankui, Dong Min. Deep Learning Based Local Path Planning Method for Moving Robots [J]. Journal of System Simulation, 2024, 36(5): 1199-1210.
[9]	Wang Xiaokang, Ji Jie, Liu Yang, He Qing. Path Planning of Unmanned Delivery Vehicle Based on Improved Q-learning Algorithm [J]. Journal of System Simulation, 2024, 36(5): 1211-1221.
[10]	Jiang Zhaozhen, Wang Wenlong, Sun Wenqi. Path Planning Rapid Algorithm Based on Modified RRT* for Unmanned Surface Vessel [J]. Journal of System Simulation, 2024, 36(4): 888-900.
[11]	Zhang Rui, Zhou Li, Liu Zhengyang. Dynamic Path Planning for Mobile Robot Based on RRT* and Dynamic Window Approach [J]. Journal of System Simulation, 2024, 36(4): 957-968.
[12]	Gao Chao, Huang Zheng, Zhao Xuan, Wang Hongxing, Long Tao. Collaborative Navigation Method for 5G Cluster UAV Based on Configuration Optimization [J]. Journal of System Simulation, 2024, 36(4): 981-990.
[13]	Yu Xiang, Deng Qianrui, Duan Sirui, Jiang Chen. A Multi-UAV Collaborative Priority Coverage Search Algorithm [J]. Journal of System Simulation, 2024, 36(4): 991-1000.
[14]	Gui Xueqi, Li Chuntao. UAV Swarm Obstacle Avoidance Algorithm Based on Visual Field and Velocity Guidance [J]. Journal of System Simulation, 2024, 36(3): 545-554.
[15]	Li Gaoyang, Li Xiangfeng, Zhao Kang, Jin Yuchao, Yi Zhidong, Zuo Dunwen. Three-Dimensional Path Planning of UAV Based on All Particles Driving Wild Horse Optimizer Algorithm [J]. Journal of System Simulation, 2024, 36(3): 595-607.