基于多尺度A*与优化DWA算法融合的移动机器人路径规划

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

摘要/Abstract

摘要：

为解决传统A*算法与动态窗口法面对大规模复杂环境路径规划时，计算和时间成本的急剧上升以及灵活性较差的问题，提出了一种基于多尺度地图法的A*算法和改进DWA算法的融合算法。建立多尺度地图集并在A*算法的启发函数中增加障碍物占比因子，在粗尺度地图利用A*算法计算最优路径，将其映射到细尺度地图上进行二次A*算法并通过Floyd算法进行节点优化，删除冗余节点、提高路径的平滑度。增加了航向角自适应调整策略和停车等待状态来优化动态窗口法，提高灵活性。将A*算法的关键点作为动态窗口法的局部目标点，并在轨迹上有障碍物时再次规划，实现两种算法的融合。ROS仿真和实车实验结果表明改进的A*算法计算时间显著减少，在20 m×40 m的地图中减少98%，改进的融合算法大幅提高了机器人在动态环境下的平滑性和灵活性，可以有效解决传统融合算法存在的问题。

关键词: 移动机器人, 路径规划, A*算法, 动态窗口法, ROS

Abstract:

In order to solve the problems of sharply increasing computational and time costs, as well as poor flexibility of the traditional A* algorithm and dynamic window approach (DWA) in the face of large-scale complex environmental path planning, a fusion algorithm based on the A* algorithm of the multi-scale map approach(MMA) and the improved DWA algorithm is proposed. A multi-scale map set is established and an obstacle proportion factor is added to the heuristic function of the A* algorithm. The A* algorithm is used to calculate the optimal path on the coarse-scale map, and the optimal path is mapped onto the fine-scale map for quadratic A* algorithm planning. The Floyd algorithm is used to optimize the nodes, remove redundant nodes, and improve the smoothness of the path. In addition, the heading angle adaptive adjustment strategy and parking wait state are added to optimize the dynamic window method to improve flexibility. The key points of the A* algorithm are used as local target points of the dynamic window method and replanned when there are obstacles on the path to realize the integration of the two algorithms. The results of ROS simulation and actual vehicle experiments show that the computation time of the improved A* algorithm is significantly reduced by 98% in 20×40 maps and the improved fusion algorithm dramatically improves the smoothing and flexibility of the robot in dynamic environments, and can effectively solve the problems existing in the traditional fusion algorithm

Key words: mobile robots, path planning, A* algorithm, dynamic window approach, ROS

中图分类号:

TP242.6

许建民,宋雷,邓冬冬等 . 基于多尺度A*与优化DWA算法融合的移动机器人路径规划[J]. 系统仿真学报, 2025, 37(1): 257-270.

Xu Jianmin,Song Lei,Deng Dongdong,et al . Path Planning of Mobile Robot Based on the Integration of Multi-scale A* and Optimized DWA Algorithm[J]. Journal of System Simulation, 2025, 37(1): 257-270.

图/表 26

图1

图2

图3

表1

图4

图5

表2

图6

图7

图8

图9

图10

表3

图11

图12

图13

图14

图15

图16

图17

图18

图19

图20

图21

图22

图23

参考文献 20

1	Liu Jianhua, Yang Jianguo, Liu Huaping, et al. An Improved Ant Colony Algorithm for Robot Path Planning[J]. Soft Computing, 2017, 21(19): 5829-5839.
2	陈娇, 徐菱, 陈佳, 等. 改进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.
3	鲍惠芳, 方杰, 张进思, 等. 基于改进蚁群算法的低碳冷链配送路径优化[J]. 系统仿真学报, 2024, 36(1): 183-194.
	Bao Huifang, Fang Jie, Zhang Jinsi, et al. Optimization on Cold Chain Distribution Routes Considering Carbon Emissions Based on Improved Ant Colony Algorithm[J]. Journal of System Simulation, 2024, 36(1): 183-194.
4	Orozco-Rosas Ulises, Montiel Oscar, Sepúlveda Roberto. Mobile Robot Path Planning Using Membrane Evolutionary Artificial Potential Field[J]. Applied Soft Computing, 2019, 77: 236-251.
5	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.
6	Ogata Kazuhiro. A Generic Approach on How to Formally Specify and Model Check Path Finding Algorithms: Dijkstra, A^and LPA^ [J]. International Journal of Software Engineering and Knowledge Engineering, 2020, 30(10): 1481-1523.
7	魏立新, 张钰锟, 孙浩, 等. 基于改进蚁群和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.
8	Cao Yan, Wei Wanyu, Bai Yu, et al. Multi-base Multi-UAV Cooperative Reconnaissance Path Planning with Genetic Algorithm[J]. Cluster Computing, 2019, 22(S3): 5175-5184.
9	Sun Changyin, He Wei, Hong Jie. Neural Network Control of a Flexible Robotic Manipulator Using the Lumped Spring-mass Model[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2017, 47(8): 1863-1874.
10	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.
11	张丹红, 陈文文, 张华军, 等. A^*算法与蚁群算法相结合的无人艇巡逻路径规划[J]. 华中科技大学学报(自然科学版), 2020, 48(6): 13-18.
	Zhang Danhong, Chen Wenwen, Zhang Huajun, et al. Patrol Path Planning of Unmanned Surface Vehicle Based on A^* Algorithm and Ant Colony Algorithm[J]. Journal of Huazhong University of Science and Technology(Natural Science Edition), 2020, 48(6): 13-18.
12	Hong Zhonghua, Sun Pengfei, Tong Xiaohua, et al. Improved A-star Algorithm for Long-distance Off-road Path Planning Using Terrain Data Map[J]. ISPRS International Journal of Geo-Information, 2021, 10(11): 785.
13	迟旭, 李花, 费继友. 基于改进A^*算法与动态窗口法融合的机器人随机避障方法研究[J]. 仪器仪表学报, 2021, 42(3): 132-140.
	Chi Xu, Li Hua, Fei Jiyou. Research on Robot Random Obstacle Avoidance Method Based on Fusion of Improved A^* Algorithm and Dynamic Window Method[J]. Chinese Journal of Scientific Instrument, 2021, 42(3): 132-140.
14	Kyu Kang Nam, Ho Joon Son, Hong Lee Soo. Modified A-star Algorithm for Modular Plant Land Transportation[J]. Journal of Mechanical Science and Technology, 2018, 32(12): 5563-5571.
15	Wang Xingdong, Zhang Haowei, Liu Shuo, et al. Path Planning of Scenic Spots Based on Improved A^*Algorithm[J]. Scientific Reports, 2022, 12(1): 1320.
16	王洪斌, 尹鹏衡, 郑维, 等. 基于改进的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.
17	Li Xiuyun, Liu Fei, Liu Juan, et al. Obstacle Avoidance for Mobile Robot Based on Improved Dynamic Window Approach[J]. Turkish Journal of Electrical Engineering and Computer Sciences, 2017, 25(2): 666-676.
18	王彬, 聂建军, 李海洋, 等. 优化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.
19	康文雄, 许耀钊. 节点约束型最短路径的分层Dijkstra算法[J]. 华南理工大学学报(自然科学版), 2017, 45(1): 66-73.
	Kang Wenxiong, Xu Yaozhao. A Hierarchical Dijkstra Algorithm for Solving Shortest Path from Constrained Nodes[J]. Journal of South China University of Technology(Natural Science Edition), 2017, 45(1): 66-73.
20	柴红杰, 李建军, 姚明. 改进的A^*算法移动机器人路径规划[J]. 电子器件, 2021, 44(2): 362-367.
	Chai Hongjie, Li Jianjun, Yao Ming. Improved A^* Algorithm for Path Planning of Mobile Robot[J]. Chinese Journal of Electron Devices, 2021, 44(2): 362-367.

算法1：多尺度子图法和粗尺度最佳规划算法
输入：	粗-细尺度地图数据集O={x, y}；起点位置和终点位置Sp, Tp
输出：	选出的粗尺度M_C；粗尺度最优路径cop
步骤1：	由输入数据集O={x, y}绘制多尺度图，多尺度图集为M={M₁,M₂,…,M_n }
步骤2：	从多尺度图集M={M₁,M₂,…,M_n }中选择合适的粗尺度图M_k，以反映细尺度地图地形的基本起伏特征，并包含尽可能少的节点
步骤3：	应用改进A算法计算在步骤2中选取的粗尺度地图M_k 的最优路径cop*

算法2：多尺度子图法和细尺度最佳规划算法
输入：	粗比例尺度子图和细比例母图M_C, M_F；粗比例尺度子图最优路径cop
输出：	细比例尺度母图最优路径fop
步骤1：	将cop映射到细尺度母图中，从cop1开始依次与下一个节点cop2相连并判断连线是否经过障碍物，否则将路径点加U中，是则判节点cop2是否为障碍物，如果不为障碍物就将cop1，cop2作为新的起点和终点放入集合A中，如果为障碍物则判断cop2的下一个节点是否为障碍物，直到下一个节点copn不为障碍物为止，将cop1，copn做为新的起点和终点放入集合A中，从节点copn继续重复上面的步骤直到到达cop中的最后一个节点
步骤2：	在细尺度母图中使用改进A*算法计算步骤1中得到的新的起点和终点A的最优路径，并将最优路径加入对应的路径点集U中

栅格地图大小	算法类型	遍历节点个数	耗费时间	路径长度/m	折点数	节点减少率/%	时间减少率/%	路径长减少率/%	折点数减少率/%
地图1 20×20	传统A*	124	0.003 9	24.556 3	7	47	35.9	1.8
地图1 20×20	改进A*	66	0.002 5	24.110 6	7	47	35.9	1.8
地图2 40×40	传统A*	395	0.012	55.941	11	72.9	62.5	2.1	81.8
地图2 40×40	改进A*	107	0.004 5	54.783	2	72.9	62.5	2.1	81.8
地图3 80×80 (23%)	传统A*	2 705	0.113	120.812	15	88.5	82.5	1.5	33.3
地图3 80×80 (23%)	改进A*	311	0.019 75	119.034	10	88.5	82.5	1.5	33.3
地图4 80×80 (15%)	传统A*	3 953	0.133 6	177.681 2	39	96.7	94.4	2.2	84.6
地图4 80×80 (15%)	改进A*	123	0.007 4	173.822 5	6	96.7	94.4	2.2	84.6
地图5 80×80 (33%)	传统A*	2 800	0.097 3	151.840 6	23	82.1	72.6	3.3	73.9
地图5 80×80 (33%)	改进A*	500	0.026 7	146.881 3	9	82.1	72.6	3.3	73.9

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