融合改进A*算法和动态窗口法的移动机器人路径规划

doi:10.16182/j.issn1004731x.joss.24-0233

摘要/Abstract

摘要：

针对传统A*算法存在拐点冗余、搜索效率低和规划路径曲折等问题，提出一种改进A*算法与改进动态窗口法相结合的融合算法，用于移动机器人的路径规划。针对拐点冗余问题，通过提取关键节点有效去除无用拐点；针对搜索效率低问题，在评价函数的启发函数中引入动态加权因子，改变搜索邻域，减少搜索节点，提高算法运行效率；针对规划路径曲折问题，对规划后的路径使用改进动态窗口法进行优化，提高路径平滑度。通过MATLAB仿真对比实验，证明融合算法在全局路径优化方面的优势，有效减少路径冗余节点数量、缩短路径长度。此外，所提融合算法能够增加机器人路径平滑度和运动稳定性。

关键词: A*算法, 动态窗口法, 融合算法, 路径规划, 路径平滑

Abstract:

The traditional A* algorithm is computationally simple and has short planning paths, but it still suffers from redundancy of inflection points, low search efficiency and zigzagging planning paths. Aiming at the above problems, a fusion algorithm combining the improved A* algorithm and the improved dynamic window approach is proposed for the path planning of mobile robots. For the problem of redundant inflection points, the key nodes are extracted to effectively remove the useless inflection points; for the problem of low search efficiency, a dynamic weighting factor is introduced into the heuristic function of the evaluation function, which changes the search neighborhood and reduces the search nodes to improve the operation efficiency of the algorithm; for the problem of zigzagging of the planning paths, the paths are optimized using the improved dynamic window approach, which improves the smoothness of the paths. Through Matlab simulation and comparison experiments, the fusion algorithm is proved to be advantageous in global path optimization, effectively reducing the number of redundant nodes in the path and shortening the path length. In addition, the proposed fusion algorithm can increase the robot path smoothness and motion stability.

Key words: A* algorithm, dynamic window approach, fusion algorithm, path planning, path smoothing

中图分类号:

TP242

赖荣燊,窦磊,巫志勇等 . 融合改进A*算法和动态窗口法的移动机器人路径规划[J]. 系统仿真学报, 2024, 36(8): 1884-1894.

Lai Rongshen,Dou Lei,Wu Zhiyong,et al . Fusion of Improved A* and Dynamic Window Approach for Mobile Robot Path Planning[J]. Journal of System Simulation, 2024, 36(8): 1884-1894.

图/表 14

图1

表1

节点方向选择表

角度值	保留5方向	舍去3方向
$[22.5 °, 67.5 °)$	p₁、p₂、p₃、p₅、p₈	p₄、p₆、p₇
$[67.5 °, 112.5 °)$	p₂、p₃、p₅、p₇、p₈	p₁、p₄、p₆
$[112.5 °, 155.5 °)$	p₃、p₅、p₆、p₇、p₈	p₁、p₂、p₄
$[155.5 °, 202.5 °)$	p₄、p₅、p₆、p₇、p₈	p₁、p₂、p₃
$[202.5 °, 247.5 °)$	p₁、p₄、p₆、p₇、p₈	p₂、p₃、p₅
$[247.5 °, 292.5 °)$	p₁、p₂、p₄、p₆、p₇	p₃、p₅、p₈
$[292.5 °, 337.5 °)$	p₁、p₂、p₃、p₄、p₆	p₅、p₇、p₈
$[337.5 °, 360 °) ⋃ [0 °, 22.5 °)$	p₁、p₂、p₃、p₄、p₅	p₆、p₇、p₈

表1

图2

图3

图4

表2

移动机器人属性以及动态窗口法初始属性

参数	数值	参数	数值
最大线速度 $v m a x / (m / s)$	1.0	方位角评价系数	0.2
最大角速度 $ω m a x / ((∘) / s)$	20	障碍物距离评价系数	0.1
线加速度 $v ˙ / (m / s 2)$	0.2	速度评价系数	0.3
角加速度 $ω ˙ / ((∘) / s 2)$	50	偏移距离评价系数	0.4
线速度分辨率 $d v / (m / s)$	0.01	采样时间/s	3
角速度分辨率 $d ω / ((∘) / s)$	1	距离阈值/m	0.5

表2

图5

表3

图6

表4

图7

表5

表6

表7

参考文献 17

1	Tang Meiqin, Sheng Jiawen, Sun Shaoyan. A Coverage Optimization Algorithm for Underwater Acoustic Sensor Networks Based on Dijkstra Method[J]. IEEE/CAA Journal of Automatica Sinica, 2023, 10(8): 1769-1771.
2	许建民, 宋雷, 邓冬冬, 等. 基于多尺度A*与优化DWA算法融合的移动机器人路径规划[J/OL]. 系统仿真学报. (2023-11-22) [2024-04-24]. .
	Xu Jianmin, Song Lei, Deng Dongdong, et al. Path Planning of Mobile Robot Based on the Integration of Multi-scale A^*and Optimized Dynamic-window Approach Algorithm[J/OL]. Journal of System Simulation. (2023-11-22) [2024-04-24]. .
3	黄鲁, 周非同. 基于路径优化D^*Lite算法的移动机器人路径规划[J]. 控制与决策, 2020, 35(4): 877-884.
	Huang Lu, Zhou Feitong. Path Planning of Moving Robot Based on Path Optimization of D^* Lite Algorithm[J]. Control and Decision, 2020, 35(4): 877-884.
4	常路, 单梁, 戴跃伟, 等. 未知环境下基于改进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.
5	鲜斌, 宋宁. 基于模型预测控制与改进人工势场法的多无人机路径规划[J/OL]. 控制与决策. (2024-01-02) [2024-02-01]. .
	Xian Bin, Song Ning. A Multiple UAVs Path Planning Method Based on Model Predictive Control and Improved Artificial Potential Field[J/OL]. Control and Decision. (2024-01-02) [2024-02-01]. .
6	崔宝侠, 王淼弛, 段勇. 基于可搜索24邻域的A^*算法路径规划[J]. 沈阳工业大学学报, 2018, 40(2): 180-184.
	Cui Baoxia, Wang Miaochi, Duan Yong. Path Planning for A^* Algorithm Based on Searching 24 Neighborhoods[J]. Journal of Shenyang University of Technology, 2018, 40(2): 180-184.
7	槐创锋, 郭龙, 贾雪艳, 等. 改进A^*算法与动态窗口法的机器人动态路径规划[J]. 计算机工程与应用, 2021, 57(8): 244-248.
	Huai Chuangfeng, Guo Long, Jia Xueyan, et al. Improved A^*Algorithm and Dynamic Window Method for Robot Dynamic Path Planning[J]. Computer Engineering and Applications, 2021, 57(8): 244-248.
8	Min Haitao, Xiong Xiaoyong, Wang Pengyu, et al. Autonomous Driving Path Planning Algorithm Based on Improved A^* Algorithm in Unstructured Environment[J]. Proceedings of the Institution of Mechanical Engineers, Part D: Journal of Automobile Engineering, 2021, 235(2/3): 513-526.
9	姬鹏, 张新元, 高帅轩, 等. 融合改进A^*算法与动态窗口法的路径规划研究[J/OL]. 系统仿真学报. (2023-09-07) [2024-03-13]. .
	Ji Peng, Zhang Xinyuan, Gao Shuaixuan, et al. Path Planning Based on Improved A^* and Dynamic Window Approach[J/OL]. Journal of System Simulation. (2023-09-07) [2024-03-13]. .
10	Lai Rongshen, Wu Zhiyong, Liu Xiangui, et al. Fusion Algorithm of the Improved A^* Algorithm and Segmented Bézier Curves for the Path Planning of Mobile Robots[J]. Sustainability, 2023, 15(3): 2483.
11	王彬, 聂建军, 李海洋, 等. 优化A^*与动态窗口法的移动机器人路径规划[J]. 计算机集成制造系统, 2024, 30(4): 1353-1363.
	Wang Bin, Nie Jianjun, Li Haiyang, et al. Mobile Robot Path Planning Based on Optimized A^* and Dynamic Window Approach[J]. Computer Integrated Manufacturing Systems, 2024, 30(4): 1353-1363.
12	王永雄, 田永永, 李璇, 等. 穿越稠密障碍物的自适应动态窗口法[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.
13	张伟龙, 单梁, 常路, 等. 基于改进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.
14	邹文, 韩丙辰, 李鹏飞, 等. 融合改进A^*算法和优化动态窗口法的路径规划[J]. 计算机集成制造系统, 2024, 30(1): 184-195.
	Zou Wen, Han Bingchen, Li Pengfei, et al. Path Planning by Integrating Improved A^* Algorithm and Optimized Dynamic Window Approach[J]. Computer Integrated Manufacturing Systems, 2024, 30(1): 184-195.
15	程传奇, 郝向阳, 李建胜, 等. 融合改进A^*算法和动态窗口法的全局动态路径规划[J]. 西安交通大学学报, 2017, 51(11): 137-143.
	Cheng Chuanqi, Hao Xiangyang, Li Jiansheng, et al. Global Dynamic Path Planning Based on Fusion of Improved A^* Algorithm and Dynamic Window Approach[J]. Journal of Xi'an Jiaotong University, 2017, 51(11): 137-143.
16	张涛, 陈璋, 李玉梅, 等. 融合改进A^∗算法与动态窗口法的机器人避障研究[J]. 仪表技术与传感器, 2023(4): 102-106.
	Zhang Tao, Chen Zhang, Li Yumei, et al. Research on Robot Obstacle Avoidance Based on Improved A^* Algorithm and Dynamic Window Method[J]. Instrument Technique and Sensor, 2023(4): 102-106.
17	郭园园, 袁杰, 赵克刚. 基于改进A^*算法和动态窗口法的机器人路径规划[J]. 计算机工程与科学, 2022, 44(7): 1273-1281.
	Guo Yuanyuan, Yuan Jie, Zhao Kegang. Robot Path Planning Based on an Improved A^* Algorithm and an Improved Dynamic Window Method[J]. Computer Engineering & Science, 2022, 44(7): 1273-1281.

地图规格	算法名称	路径长度/m	运算时间/s
20×20	传统A*算法	23.799	0.025
	文献[16]改进A*算法	23.748	0.021
	本文改进A*算法	23.545	0.016
30×30	传统A*算法	39.527	0.085
	文献[16]改进A*算法	39.476	0.056
	本文改进A*算法	39.253	0.028

地图规格	算法名称	路径长度/m	运算时间/s
20×20	融合传统DWA算法	24.529	143.04
	融合文献[17]改进 DWA算法	24.497	144.99
	融合本文改进 DWA算法	24.197	152.82
30×30	融合传统DWA算法	40.247	527.12
	融合文献[17]改进 DWA算法	40.226	521.69
	融合本文改进DWA算法	39.449	552.09

地图规格	算法名称	角度方差	角度标准差
20×20	融合传统DWA算法	0.341 8	0.116 8
	融合文献[17]改进DWA算法	0.339 3	0.115 1
	融合本文改进DWA算法	0.292 0	0.085 3
30×30	融合传统DWA算法	0.442 2	0.195 5
	融合文献[17]改进DWA算法	0.443 1	0.196 3
	融合本文改进DWA算法	0.392 3	0.153 9

地图规格	算法名称	线速度方差	线速度标准差
20×20	融合传统DWA算法	0.179 5	0.032 2
	融合文献[17]改进DWA算法	0.180 1	0.032 5
	融合本文改进DWA算法	0.168 0	0.028 2
30×30	融合传统DWA算法	0.153 3	0.023 5
	融合文献[17]改进DWA算法	0.152 7	0.023 3
	融合本文改进DWA算法	0.111 8	0.012 5

地图规格	算法名称	角速度方差	角速度标准差
20×20	融合传统DWA算法	0.114 9	0.013 2
	融合文献[17]改进DWA算法	0.112 1	0.012 6
	融合本文改进DWA算法	0.090 3	0.008 2
30×30	融合传统DWA算法	0.140 6	0.019 8
	融合文献[17]改进DWA算法	0.141 2	0.019 9
	融合本文改进DWA算法	0.110 5	0.012 2