Path Planning of Mobile Robot Based on the Integration of Multi-scale A* and Optimized DWA Algorithm

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

Abstract

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

CLC Number:

TP242.6

Xu Jianmin, Song Lei, Deng Dongdong, Chen Yaoruo, Yang Wei. 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.

Figures/Tables 26

Fig. 1

Fig. 2

Fig. 3

Table 1

Fig. 4

Fig. 5

Table 2

Fig. 6

Fig. 7

Fig. 8

Fig. 9

Fig. 10

Table 3

Fig. 11

Fig. 12

Fig. 13

Fig. 14

Fig. 15

Fig. 16

Fig. 17

Fig. 18

Fig. 19

Fig. 20

Fig. 21

Fig. 22

Fig. 23

References 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]	Qi Bensheng, Li Yan, Miao Hongxia, Chen Jialin, Li Chenglin. Research on Path Planning Method for Autonomous Underwater Vehicles Based on Improved Informed RRT [J]. Journal of System Simulation, 2025, 37(1): 245-256.
[2]	Xu Lixia, Zhong Jilong, Wu Shaoshi, Ding Yishan, Zhai Xiaoyu, Chen Shizhao, Wang Yizhe, Wen Xue, Zeng Juanfang, Hou Xinwen. Indicator Transfer Learning Based on Cloud Model and Maximum Mean Discrepancy [J]. Journal of System Simulation, 2024, 36(9): 2004-2015.
[3]	Zhu Qiankun, Li Jiwu, Du Yongfeng. Simulation Study of Personnel Evacuation in Fire Scenarios of Old School Buildings [J]. Journal of System Simulation, 2024, 36(9): 2043-2053.
[4]	Wang Yuelong, Wang Songyan, Chao Tao. Multi-step Information Aided Q-learning Path Planning Algorithm [J]. Journal of System Simulation, 2024, 36(9): 2137-2148.
[5]	Huo Hanlin, Zou Xiangjun, Chen Yan, Zhou Xinzhao, Chen Mingyou, Li Chengen, Pan Yaoqiang, Tang Yunchao. Visual Robot Obstacle Avoidance Planning and Simulation Using Mapped Point Clouds [J]. Journal of System Simulation, 2024, 36(9): 2149-2158.
[6]	Ji Peng, Zhang Xinyuan, Gao Shuaixuan, Wei Shuorang. Path Planning Based on Improved A* and Dynamic Window Approach [J]. Journal of System Simulation, 2024, 36(9): 2171-2180.
[7]	Sun Haijie, San Hongjun, Xiao Le, Yao Dexin, Chen Jiupeng, Yang Xiaoyuan. An Improved Path Planning Algorithm for Mobile Robots [J]. Journal of System Simulation, 2024, 36(9): 2193-2207.
[8]	Liu Jialun, Yang Fan, Xie Lingli, Li Shijie, Wang Tengfei. Research on Virtual Simulation Testing Technology for Intelligent Navigation Collision Avoidance Decision-making and Planning [J]. Journal of System Simulation, 2024, 36(8): 1780-1789.
[9]	Liu Bin, Lan Ying, Huang Wentao, Fan Qinqin. UAV Dynamic Path Planning Algorithm Combined with Dynamic Window Approach [J]. Journal of System Simulation, 2024, 36(8): 1843-1853.
[10]	Liu Peijin, Fu Xuefeng, Sun Haofeng, He Lin, Liu Shujie. A Highly Robust Target Tracking Algorithm Merging CNN and Transformer [J]. Journal of System Simulation, 2024, 36(8): 1854-1868.
[11]	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.
[12]	Kang Liang, Du Yi, Yin Lihua. An Improved Cat Swarm Optimization for Heterogeneous Multiple Mobile Robots [J]. Journal of System Simulation, 2024, 36(8): 1958-1968.
[13]	Huang Zhifeng, Liu Yuanhua. UAV Path Planning Based on Improved Harris Hawk Algorithm and B-spline Curve [J]. Journal of System Simulation, 2024, 36(7): 1509-1524.
[14]	Wang Yaru, Yao Dexin, Liu Zengli, Peng Yi. Path Planning for Mobile Robot Based on Angle Search [J]. Journal of System Simulation, 2024, 36(7): 1643-1654.
[15]	Bao Weimin, Qi Zhenqiang. Thinking of Aerospace Equipment Systematization Simulation Technology Development [J]. Journal of System Simulation, 2024, 36(6): 1257-1272.