Robot Path Planning Optimization Based on Fusion of Improved Ant Colony Algorithm and A* Algorithm

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

Abstract

Abstract:

To improve slow search efficiency and achieve real-time obstacle avoidance in traditional ant colony algorithms, an adaptive ant colony algorithm was proposed. A guidance direction mechanism was introduced to shorten the time of node selection. The A* algorithm's path-finding mechanism was introduced into the heuristic function to reduce the length and number of circles of the optimal path solution. The route planned by the traditional A* algorithm was used as the initial iteration data of the ant colony algorithm in global path planning, so as to solve the problem of slow initial convergence of the ant colony algorithm. The breadth first search mechanism of the traditional A* algorithm was introduced into the ant colony algorithm to address the issue of multiple iterations in the algorithm. In order to verify the superiority of this algorithm, two representative environmental models were adopted and compared with two traditional ant colony algorithms and genetic algorithms through comprehensive experiments. Comparative experiments demonstrate that the adaptive path-finding ant colony algorithm exhibits significant advantages over AS, ACS, and EAS algorithms in path planning, featuring faster convergence and superior path generation.

Key words: mobile robot, path planning, ant colony algorithm, A* algorithm, guidance direction mechanism

CLC Number:

TP391.9

Yang Lanying, Li Chao, Zou Haifeng, Wan Jiangtao, Zhang Renqiang, Liu Hui, Lu Hong. Robot Path Planning Optimization Based on Fusion of Improved Ant Colony Algorithm and A* Algorithm[J]. Journal of System Simulation, 2025, 37(11): 2956-2965.

Figures/Tables 20

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Fig. 8

Table 1

Table 2

Fig. 9

Table 3

Fig. 10

Table 4

Fig. 11

Fig. 12

Table 5

Fig. 13

Fig. 14

Table 6

References 18

[1]	Liu Lixing, Wang Xu, Yang Xin, et al. Path Planning Techniques for Mobile Robots: Review and Prospect[J]. Expert Systems with Applications, 2023, 227: 120254.
[2]	Shen Zhipeng, Ding Wenna, Liu Yuchen, et al. Path Planning Optimization for Unmanned Sailboat in Complex Marine Environment[J]. Ocean Engineering, 2023, 269: 113475.
[3]	Yonetani Ryo, Taniai Tatsunori, Barekatain Mohammadamin, et al. Path Planning Using Neural A^* Search[C]//Proceedings of the 38th International Conference on Machine Learning. Chia Laguna Resort: PMLR, 2021: 12029-12039.
[4]	Luo Min, Hou Xiaorong, Yang Jing. Surface Optimal Path Planning Using an Extended Dijkstra Algorithm[J]. IEEE Access, 2020, 8: 147827-147838.
[5]	Zhang Yi, Pang Dashuai. Research on Path Planning of Mobile Robot Based on Improved Ant Colony Algorithm[C]//2022 IEEE 6th Information Technology and Mechatronics Engineering Conference (ITOEC). Piscataway: IEEE, 2022: 558-563.
[6]	Dorigo M, Maniezzo V, Colorni A. Ant System: Optimization by a Colony of Cooperating Agents[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 1996, 26(1): 29-41.
[7]	Yang Bing, Wu Lunwen, Xiong Jian, et al. Location and Path Planning for Urban Emergency Rescue by a Hybrid Clustering and Ant Colony Algorithm Approach[J]. Applied Soft Computing, 2023, 147: 110783.
[8]	Liu Chao, Wu Lei, Xiao Wensheng, et al. An Improved Heuristic Mechanism Ant Colony Optimization Algorithm for Solving Path Planning[J]. Knowledge-Based Systems, 2023, 271: 110540.
[9]	Li Mingze, Li Bing, Qi Zhigang, et al. Optimized APF-ACO Algorithm for Ship Collision Avoidance and Path Planning[J]. Journal of Marine Science and Engineering, 2023, 11(6): 1177.
[10]	Fatemidokht Hamideh, Marjan Kuchaki Rafsanjani. F-ant: An Effective Routing Protocol for Ant Colony Optimization Based on Fuzzy Logic in Vehicular Ad Hoc Networks[J]. Neural Computing and Applications, 2018, 29(11): 1127-1137.
[11]	王晓燕, 杨乐, 张宇, 等. 基于改进势场蚁群算法的机器人路径规划[J]. 控制与决策, 2018, 33(10): 1775-1781.
	Wang Xiaoyan, Yang Le, Zhang Yu, et al. Robot Path Planning Based on Improved Ant Colony Algorithm with Potential Field Heuristic[J]. Control and Decision, 2018, 33(10): 1775-1781.
[12]	Miao Changwei, Chen Guangzhu, Yan Chengliang, et al. Path Planning Optimization of Indoor Mobile Robot Based on Adaptive Ant Colony Algorithm[J]. Computers & Industrial Engineering, 2021, 156: 107230.
[13]	李祥祥, 胡甫才, 刘畅, 等. 基于改进精英势场蚁群算法的机器人三维路径规划算法研究[J]. 计算机科学与应用, 2021, 11(4): 849-858
	Li Xiangxiang, Hu Fuchai, Liu Chang, et al. Robot 3D Path Planning Algorithm Based on Improved Elitist Potential Field Ant Colony Algorithm[J]. Computer Science and Application, 2021, 11(4): 849-858.
[14]	Tao Yong, Gao He, Ren Fan, et al. A Mobile Service Robot Global Path Planning Method Based on Ant Colony Optimization and Fuzzy Control[J]. Applied Sciences, 2021, 11(8): 3605.
[15]	Wei Z Q, Xu F, Jin Y Q. Phase Unwrapping for SAR Interferometry Based on an Ant Colony Optimization Algorithm[J]. International Journal of Remote Sensing, 2008, 29(3): 711-725.
[16]	万晓凤, 胡伟, 方武义, 等. 基于改进蚁群算法的机器人路径规划研究[J]. 计算机工程与应用, 2014, 50(18): 63-66.
	Wan Xiaofeng, Hu Wei, Fang Wuyi, et al. Research on Path Planning of Robot Based on Improved Ant Colony Algorithm[J]. Computer Engineering and Applications, 2014, 50(18): 63-66.
[17]	Xiong Ni, Zhou Xinzhi, Yang Xiuqing, et al. Mobile Robot Path Planning Based on Time Taboo Ant Colony Optimization in Dynamic Environment[J]. Frontiers in Neurorobotics, 2021, 15: 642733.
[18]	Pei Zuan, Wei Yufeng. Prediction of the Bond Strength of FRP-to-concrete Under Direct Tension by ACO-based ANFIS Approach[J]. Composite Structures, 2022, 282: 115070.

启发式因子	路径长度最优值
3	33.970 5
4	34.142 1
5	34.456 2
6	34.556 3
7	34.556 3
8	33.970 5
9	34.556 3
10	34.556 3

信息素因子	路径长度最优值
2	34.556 3
3	34.556 3
4	34.556 3
5	33.970 6
6	33.970 5
7	34.556 3
8	34.556 3
9	34.556 3

信息素蒸发因子	路径长度最优值
0.1	33.970 6
0.2	33.970 5
0.3	34.556 3
0.4	34.556 3
0.5	34.556 3
0.6	34.556 3

因子		环境模型II		环境模型III
因子		路径长度最优值	10次路径平均值	路径长度最优值	10次路径平均值
启发式	3	29.799 0	31.716 16	75.639 6	75.639 60
	4	29.799 0	31.609 06	73.982 8	75.469 78
	5	29.799 0	31.964 68	74.811 2	75.283 98
	6	29.799 0	31.136 28	73.982 8	74.755 58
	7	29.799 0	31.219 12	73.982 8	74.986 94
	8	29.799 0	30.970 60	73.982 8	74.621 26
	9	29.799 0	31.633 32	73.982 8	74.621 26
	10	29.799 0	31.467 64	73.982 8	74.562 68
信息素	2	29.799 0	30.970 60	73.982 8	74.065 64
	3	29.799 0	31.750 48	73.982 8	74.397 00
	4	29.799 0	31.219 12	73.982 8	74.314 16
	5	29.799 0	31.219 12	73.982 8	74.821 26
	6	29.799 0	31.219 12	73.982 8	74.065 64
	7	29.799 0	32.296 04	73.982 8	74.621 26
	8	29.799 0	32.520 30	73.982 8	74.231 32
信息素蒸发	0.1	29.799 0	31.219 12	73.982 8	74.065 64
	0.2	29.799 0	31.053 44	73.982 8	74.065 64
	0.3	29.799 0	31.550 48	73.982 8	74.645 52
	0.4	29.799 0	32.851 67	73.982 8	74.597 00

性能指标	AACA	AS	ACS	EAS
最优值	30.971 0	32.971 0	34.870 0	31.799 0
最优值次数	4	1	3	1
平均值	32.602 2	33.427 6	35.435 6	33.799 2
最大值	32.627 4	34.042 0	36.284 0	35.799 0
转弯次数	11	12	13	13
运行时间/s	20	38	49	46