Fusion of Improved A* and Dynamic Window Approach for Mobile Robot Path Planning

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

Abstract

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

CLC Number:

TP242

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

Figures/Tables 14

Fig. 1

Table 1

Node direction selection table

角度值	保留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₈

Table 1

Fig. 2

Fig. 3

Fig. 4

Table 2

Mobile robot properties and initial properties of the dynamic window method

参数	数值	参数	数值
最大线速度 $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

Table 2

Fig. 5

Table 3

Fig. 6

Table 4

Fig. 7

Table 5

Table 6

Table 7

References 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