融合动态窗口法的无人机动态路径规划算法

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

摘要/Abstract

摘要：

为解决路径规划算法在复杂动态环境下寻优性能和避障能力差的问题，提出一种融合动态窗口法的无人机动态路径规划算法(UAV dynamic path planning algorithm combined with DWA，UAV-DPPA-DWA)。为获取无人机在静态环境下的最佳引导路径，提出了一种基于偏移程度和障碍物距离评估的改进椭圆切线图算法；如果无人机检测到有移动障碍物，那么通过自适应参数的动态窗口法生成局部避障轨迹；否则，无人机仍沿静态环境下所获得的引导路径飞行。提出多种类型的复杂动态避障场景，并从路径长度和飞行时间两方面来验证所提算法的性能。实验结果表明：相比DWA、A*-DWA、RRT-DWA和PRM-DWA算法，UAV-DPPA-DWA不仅有较强的避障能力得到可行飞行轨迹，还能以短时间沿最佳路径完成任务。

关键词: 无人机, 路径规划, 椭圆切线图法, 动态窗口法, 动态避障

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

中图分类号:

TP242

刘斌,兰莹,黄文焘等 . 融合动态窗口法的无人机动态路径规划算法[J]. 系统仿真学报, 2024, 36(8): 1843-1853.

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

图/表 10

图 1

图 2

图 3

图 4

表 1

表 2

表 3

图 5

表 4

图 6

参考文献 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]	刘佳仑, 杨帆, 谢玲利, 李诗杰, 王腾飞. 面向智能航行避碰决策与规划的虚拟仿真测试技术研究[J]. 系统仿真学报, 2024, 36(8): 1780-1789.
[2]	黄志锋, 刘媛华. 基于改进哈里斯鹰和B-spline曲线的无人机路径规划研究[J]. 系统仿真学报, 2024, 36(7): 1509-1524.
[3]	王雅如, 姚得鑫, 刘增力, 彭艺. 基于角度搜索的移动机器人路径规划方法[J]. 系统仿真学报, 2024, 36(7): 1643-1654.
[4]	王涛, 吉晓东. 混合概率信道下的全双工无人机中继轨迹优化[J]. 系统仿真学报, 2024, 36(6): 1369-1377.
[5]	雷旭, 陈静夷, 陈潇阳. 改进哈里斯鹰算法的仓储机器人路径规划研究[J]. 系统仿真学报, 2024, 36(5): 1081-1092.
[6]	刘泽森, 毕盛, 郭传鈜, 王延葵, 董敏. 基于深度学习的机器人局部路径规划方法[J]. 系统仿真学报, 2024, 36(5): 1199-1210.
[7]	王小康, 冀杰, 刘洋, 贺庆. 基于改进Q学习算法的无人物流配送车路径规划[J]. 系统仿真学报, 2024, 36(5): 1211-1221.
[8]	姜兆祯, 王文龙, 孙文祺. 基于改进RRT^*算法的无人艇路径规划快速求解算法[J]. 系统仿真学报, 2024, 36(4): 888-900.
[9]	张瑞, 周丽, 刘正洋. 融合RRT*与DWA算法的移动机器人动态路径规划[J]. 系统仿真学报, 2024, 36(4): 957-968.
[10]	高超, 黄郑, 赵轩, 王红星, 龙涛. 基于构型优选的5G集群无人机协同导航方法[J]. 系统仿真学报, 2024, 36(4): 981-990.
[11]	余翔, 邓千锐, 段思睿, 姜陈. 一种多无人机协同优先覆盖搜索算法[J]. 系统仿真学报, 2024, 36(4): 991-1000.
[12]	桂雪琪, 李春涛. 基于视野和速度引导的无人机集群避障算法[J]. 系统仿真学报, 2024, 36(3): 545-554.
[13]	李高扬, 黎向锋, 赵康, 金玉超, 易志东, 左敦稳. 全粒子推动野马优化算法的无人机三维路径规划[J]. 系统仿真学报, 2024, 36(3): 595-607.
[14]	闫星宇, 李大焱, 王妮娅, 张凯翔, 毛剑琳. 带障碍物惩罚因子的多机器人路径规划[J]. 系统仿真学报, 2024, 36(3): 673-685.
[15]	卢元杰, 龙珊珊, 赵航, 冯国旭, 赵晓葭. 基于混合模型的异构无人机蜂群效能评估[J]. 系统仿真学报, 2024, 36(3): 700-712.