移动机器人路径规划中A*算法的改进研究

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

系统仿真学报 ›› 2024, Vol. 36 ›› Issue (11): 2684-2698.doi: 10.16182/j.issn1004731x.joss.23-0968

• 研究论文 • 上一篇

移动机器人路径规划中A*算法的改进研究

姚得鑫¹^,², 伞红军¹^,², 王雅如³, 孙海杰¹^,², 陈久朋¹^,², 杨晓园¹^,²

^1.昆明理工大学机电工程学院，云南昆明 650500
^2.云南省先进装备智能制造技术重点实验室，云南昆明 650500
^3.昆明理工大学信息工程与自动化学院，云南昆明 650500

收稿日期:2023-07-31 修回日期:2023-10-11 出版日期:2024-11-13 发布日期:2024-11-19
通讯作者: 伞红军
第一作者简介:姚得鑫(1998-)，男，硕士生，研究方向为机器人路径规划。
基金资助:
云南省科技厅重大专项(02002AC080001);云南省基础研究计划(202301AU070059)

Improvement of A* Algorithm in Path Planning of Mobile Robot

Yao Dexin¹^,², San Hongjun¹^,², Wang Yaru³, Sun Haijie¹^,², Chen Jiupeng¹^,², Yang Xiaoyuan¹^,²

^1.Faculty of Mechanical and Electrical Engineering, Kunming University of Science and Technology, Kunming 650500, China
^2.Key Laboratory of Advanced Equipment Intelligent Manufacturing Technology of Yunnan Province, Kunming 650500, China
^3.Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China

Received:2023-07-31 Revised:2023-10-11 Online:2024-11-13 Published:2024-11-19
Contact: San Hongjun

摘要/Abstract

摘要：

为解决传统A*算法在路径搜索过程中存在冗余节点过多、搜索效率不高、路径转折角度过大的问题，提出一种改进的A*算法来规划最优路径。将A*算法的搜索邻域增加到24个，以获得更加精确和宽阔的搜索视野；引入角度搜索算法，剔除了路径搜索过程中的不必要节点，使搜索过程更具有目标导向性；通过当前点与目标点的相对位置对启发函数进行指数衰减的加权，用于处理搜索速度与路径长度之间的关系；平滑所得路径，减少了路径折弯数和折弯角度，使得机器人运动更加平稳。结果表明：改进的A*算法相较于A*算法，在复杂与简单环境中搜索速度分别提升29.16%~65.82%和41.87%~64.71%，路径折弯数分别减少27.27%~63.64%和59.09%~62.12%，相较于D*算法在寻路速度、遍历节点及路径折弯数量方面都有较大提升，将改进A*算法在真实环境中进行实验，验证了其具有较好性能及路径规划能力。

关键词: A*算法, 移动机器人, 路径规划, 角度搜索, ROS

Abstract:

To solve the problems of excessively redundant nodes, low search efficiency, and excessive path turning angle in the path search of the traditional A* algorithm, an improved A* algorithm is proposed to plan the optimal path. First, the amount of search neighborhood of the A* algorithm is increased to 24 to obtain a more accurate and comprehensive search field. Second, the angle search algorithm is introduced, eliminating the unnecessary nodes in the path search and making the search more target-oriented. Third, the heuristic function is weighted by the exponential attenuation through the relative position of the current point and the target point, to deal with the relationship between the search speed and the path length. Finally, the obtained path is smoothed to reduce the number of path bends and the bending angle, making the robot move more smoothly. The results show that, compared with the search speed of the original A* algorithm, that of the improved one is increased by 29.16% ~ 65.82% in a complex environment and by 41.87% ~ 64.71% in a simple environment, and the number of path bends is reduced by 27.27% ~ 63.64% and 59.09% ~ 62.12%. Compared to the D* algorithm, there are significant improvements in pathfinding speed, traversing nodes, and the number of path bends. Furthermore, experiments on the improved A* algorithm are conducted in the real environment to verify its better performance and path planning ability.

Key words: A* algorithm, mobile robot, path planning, angle search, ROS (robot operating system)

中图分类号:

TP391.9

姚得鑫,伞红军,王雅如等 . 移动机器人路径规划中A*算法的改进研究[J]. 系统仿真学报, 2024, 36(11): 2684-2698.

Yao Dexin,San Hongjun,Wang Yaru,et al . Improvement of A* Algorithm in Path Planning of Mobile Robot[J]. Journal of System Simulation, 2024, 36(11): 2684-2698.

图/表 26

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

图13

图14

图15

图16

表1

图17

表2

图18

图19

图20

图21

图22

图23

图24

参考文献 21

1	Wu Lei, Huang Xiaodong, Cui Junguo, et al. Modified Adaptive Ant Colony Optimization Algorithm and Its Application for Solving Path Planning of Mobile Robot[J]. Expert Systems with Applications, 2023, 215: 119410.
2	Fragapane Giuseppe, René de Koster, Sgarbossa Fabio, et al. Planning and Control of Autonomous Mobile Robots for Intralogistics: Literature Review and Research Agenda[J]. European Journal of Operational Research, 2021, 294(2): 405-426.
3	张瑞, 周丽, 刘正洋. 融合RRT^*与DWA算法的移动机器人动态路径规划[J]. 系统仿真学报, 2024, 36(4): 957-968.
	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.
4	Jeddisaravi Kossar, Reza Javanmard Alitappeh, C A Pimenta Luciano, et al. Multi-objective Approach for Robot Motion Planning in Search Tasks[J]. Applied Intelligence, 2016, 45(2): 305-321.
5	Luo Qiang, Wang Haibao, Zheng Yan, et al. Research on Path Planning of Mobile Robot Based on Improved Ant Colony Algorithm[J]. Neural Computing and Applications, 2020, 32(6): 1555-1566.
6	Wang Qi, Tang Chunlei. Deep Reinforcement Learning for Transportation Network Combinatorial Optimization: A Survey[J]. Knowledge-Based Systems, 2021, 233: 107526.
7	Qu Rong, Xu Ying, Castro J P, et al. Particle Swarm Optimization for the Steiner Tree in Graph and Delay-constrained Multicast Routing Problems[J]. Journal of Heuristics, 2013, 19(2): 317-342.
8	Huynh Thi Thanh Binh, Pham Dinh Thanh, Ta Bao Thang. New Approach to Solving the Clustered Shortest-path Tree Problem Based on Reducing the Search Space of Evolutionary Algorithm[J]. Knowledge-Based Systems, 2019, 180: 12-25.
9	Tang Gang, Tang Congqiang, Claramunt Christophe, et al. Geometric A-star Algorithm: An Improved A-star Algorithm for AGV Path Planning in a Port Environment[J]. IEEE Access, 2021, 9: 59196-59210.
10	Zhao Tao, Li Haodong, Songyi Dian. Multi-robot Path Planning Based on Improved Artificial Potential Field and Fuzzy Inference System[J]. Journal of Intelligent & Fuzzy Systems, 2020, 39(5): 7621-7637.
11	Li Changgeng, Huang Xia, Ding Jun, et al. Global Path Planning Based on a Bidirectional Alternating Search A^*Algorithm for Mobile Robots[J]. Computers & Industrial Engineering, 2022, 168: 108123.
12	赵晓, 王铮, 黄程侃, 等. 基于改进A^*算法的移动机器人路径规划[J]. 机器人, 2018, 40(6): 903-910.
	Zhao Xiao, Wang Zheng, Huang Chengkan, et al. Mobile Robot Path Planning Based on an Improved A^* Algorithm[J]. Robot, 2018, 40(6): 903-910.
13	Shang Erke, Dai Bin, Nie Yiming, et al. An Improved A-star Based Path Planning Algorithm for Autonomous Land Vehicles[J]. International Journal of Advanced Robotic Systems, 2020, 17(5): 1729881420962263.
14	Liu Haoxin, Zhang Yonghui. ASL-DWA: An Improved A-star Algorithm for Indoor Cleaning Robots[J]. IEEE Access, 2022, 10: 99498-99515.
15	辛煜, 梁华为, 杜明博, 等. 一种可搜索无限个邻域的改进A^*算法[J]. 机器人, 2014, 36(5): 627-633.
	Xin Yu, Liang Huawei, Du Mingbo, et al. An Improved A^*Algorithm for Searching Infinite Neighbourhoods[J]. Robot, 2014, 36(5): 627-633.
16	Xie Lei, Xue Shuangfei, Zhang Jinfen, et al. A Path Planning Approach Based on Multi-direction A^* Algorithm for Ships Navigating Within Wind Farm Waters[J]. Ocean Engineering, 2019, 184: 311-322.
17	陈娇, 徐菱, 陈佳, 等. 改进A^*和动态窗口法的移动机器人路径规划[J]. 计算机集成制造系统, 2022, 28(6): 1650-1658.
	Chen Jiao, Xu Ling, Chen Jia, et al. Path Planning Based on Improved A^* and Dynamic Window Approach for Mobile Robot[J]. Computer Integrated Manufacturing Systems, 2022, 28(6): 1650-1658.
18	封声飞, 雷琦, 吴文烈, 等. 自适应蚁群算法的移动机器人路径规划[J]. 计算机工程与应用, 2019, 55(17): 35-43.
	Feng Shengfei, Lei Qi, Wu Wenlie, et al. Mobile Robot Path Planning Based on Adaptive Ant Colony Algorithm[J]. Computer Engineering and Applications, 2019, 55(17): 35-43.
19	徐菱, 付文浩, 江文辉, 等. 基于16方向24邻域改进蚁群算法的移动机器人路径规划[J]. 控制与决策, 2021, 36(5): 1137-1146.
	Xu Ling, Fu Wenhao, Jiang Wenhui, et al. Mobile Robots Path Planning Based on 16-directions 24-neighborhoods Improved Ant Colony Algorithm[J]. Robot, 2021, 36(5): 1137-1146.
20	王中玉, 曾国辉, 黄勃, 等. 改进A^*算法的机器人全局最优路径规划[J]. 计算机应用, 2019, 39(9): 2517-2522.
	Wang Zhongyu, Zeng Guohui, Huang Bo, et al. Global Optimal Path Planning for Robots with Improved A^* Algorithm[J]. journal of Computer Applications, 2019, 39(9): 2517-2522.
21	王雅如, 姚得鑫, 刘增力, 等. 基于角度搜索的移动机器人路径规划方法[J]. 系统仿真学报, 2024, 36(7): 1643-1654.
	Wang Yaru, Yao Dexin, Liu Zengli, et al. Path Planning for Mobile Robot Based on Angle Search[J]. Journal of System Simulation, 2024, 36(7): 1643-1654.

地图尺寸	算法	平均计算时间/s	路径长度	搜索节点数	路径折弯数
20×20	A*	0.004 58	31.556	69	10
	改进A*	0.003 24	30.603	30	6
	D*	0.041 41	28.627	313	6
50×50	A*	0.022 83	79.255	236	11
	改进A*	0.008 85	77.378	100	8
	D*	0.280 05	77.359	1 830	8
80×80	A*	0.045 14	130.468	388	11
	改进A*	0.015 43	124.936	169	4
	D*	1.239 53	129.882	4 609	12
100×100	A*	0.055 85	154.651	448	13
	改进A*	0.021 82	142.086	222	8
	D*	3.252 59	146.451	7 859	13

地图尺寸	算法	平均计算时间/s	路径长度	搜索节点数	路径折弯数
20×20	A*	0.004 32	30.384	66	11
	改进A*	0.002 55	29.973	25	5
	D*	0.037 04	29.213	267	12
50×50	A*	0.019 83	75.740	220	19
	改进A*	0.007 62	74.501	90	10
	D*	0.260 48	75.154	1735	15
80×80	A*	0.040 67	125.711	346	21
	改进A*	0.014 35	119.089	155	11
	D*	1.245 51	119.338	4 716	17
100×100	A*	0.057 49	149.380	470	19
	改进A*	0.020 77	151.063	207	13
	D*	3.010 94	149.380	7 330	21

[1]	姚万业, 庞泽伟, 孙沛杰, 王祝. 基于窗口化匹配估计的ORB-SLAM算法研究[J]. 系统仿真学报, 2024, 36(9): 2032-2042.
[2]	朱前坤, 李继武, 杜永峰. 老旧教学楼火灾场景人员疏散仿真研究[J]. 系统仿真学报, 2024, 36(9): 2043-2053.
[3]	王越龙, 王松艳, 晁涛. 基于多步信息辅助的Q-learning路径规划算法[J]. 系统仿真学报, 2024, 36(9): 2137-2148.
[4]	霍韩淋, 邹湘军, 陈燕, 周馨曌, 陈明猷, 李承恩, 潘耀强, 唐昀超. 基于视觉机器人障碍点云映射避障规划及仿真[J]. 系统仿真学报, 2024, 36(9): 2149-2158.
[5]	姬鹏, 张新元, 高帅轩, 魏铄让. 融合改进A*算法与动态窗口法的路径规划研究[J]. 系统仿真学报, 2024, 36(9): 2171-2180.
[6]	孙海杰, 伞红军, 肖乐, 姚得鑫, 陈久朋, 杨晓园. 一种改进的移动机器人路径规划算法[J]. 系统仿真学报, 2024, 36(9): 2193-2207.
[7]	刘佳仑, 杨帆, 谢玲利, 李诗杰, 王腾飞. 面向智能航行避碰决策与规划的虚拟仿真测试技术研究[J]. 系统仿真学报, 2024, 36(8): 1780-1789.
[8]	刘斌, 兰莹, 黄文焘, 范勤勤. 融合动态窗口法的无人机动态路径规划算法[J]. 系统仿真学报, 2024, 36(8): 1843-1853.
[9]	赖荣燊, 窦磊, 巫志勇, 孙帅. 融合改进A*算法和动态窗口法的移动机器人路径规划[J]. 系统仿真学报, 2024, 36(8): 1884-1894.
[10]	康亮, 杜奕, 尹丽华. 一种面向异质多移动机器人的改进猫群算法[J]. 系统仿真学报, 2024, 36(8): 1958-1968.
[11]	黄志锋, 刘媛华. 基于改进哈里斯鹰和B-spline曲线的无人机路径规划研究[J]. 系统仿真学报, 2024, 36(7): 1509-1524.
[12]	王雅如, 姚得鑫, 刘增力, 彭艺. 基于角度搜索的移动机器人路径规划方法[J]. 系统仿真学报, 2024, 36(7): 1643-1654.
[13]	朱子璐, 刘永奎, 张霖, 王力翚, 林廷宇. 基于深度强化学习的机器人轴孔装配策略仿真研究[J]. 系统仿真学报, 2024, 36(6): 1414-1424.
[14]	刘金辉, 陈孟元, 韩朋朋, 陈何宝, 张玉坤. 面向移动机器人大视角运动的图神经网络视觉SLAM算法[J]. 系统仿真学报, 2024, 36(5): 1043-1060.
[15]	雷旭, 陈静夷, 陈潇阳. 改进哈里斯鹰算法的仓储机器人路径规划研究[J]. 系统仿真学报, 2024, 36(5): 1081-1092.

移动机器人路径规划中A*算法的改进研究

Improvement of A* Algorithm in Path Planning of Mobile Robot

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 26

参考文献 21

相关文章 15

编辑推荐

Metrics

本文评价