Complex Environment Path Planning Based on an Improved Ant Colony Algorithm
YANG Junqi, LIU Feiyang, ZHANG Hongwei
School of Electrical Engineering and Automation, Henan Key Laboratory of Intelligent Detection and Control of Coal Mine Equipment, Henan Polytechnic University, Jiaozuo 454003, China
Abstract：This paper proposes an improved ant colony algorithm to solve the problem of slow and poor convergence. First, a correction strategy is introduced, which includes two local correction methods to reduce invalid paths. Second, an adaptive pheromone updating mechanism is developed to distinguish and volatilize the initial pheromone from the pheromone released. For the pheromone released in each iteration, a change law of time-varying volatilization factor is designed to volatilize independently and obtain pheromone volatilization mechanism with adaptive volatilization intensity. Finally, the proposed algorithm is applied to mobile robot path planning. Compared with the existing improved ant colony algorithms, the results show that the improved algorithm is excellent in terms of effective time, average distance and shortest distance.
杨俊起, 刘飞洋, 张宏伟. 基于改进蚁群算法的复杂环境路径规划[J]. 复杂系统与复杂性科学, 2024, 21(3): 93-99.
YANG Junqi, LIU Feiyang, ZHANG Hongwei. Complex Environment Path Planning Based on an Improved Ant Colony Algorithm[J]. Complex Systems and Complexity Science, 2024, 21(3): 93-99.
[1] DORIGO M, MANIEZZO V, COLORNI A. Positive feedback as a search strategy[J]. Technical Report, 1991, 1(1):91-016. [2] WANG Y H, GAO D M, WANG X D. Shortest path planning based on improved ant colony algorithm[J]. ASP Transactions on Computes, 2021, 1(3):6-11. [3] AKKA K, KHABER F. Mobile robot path planning using an improved ant colony optimization[J]. International Journal of Advanced Robotic Systems, 2018, 15(3):1-7. [4] BULLNHEIMER B, HARTL R F, STRAUSS C. An improved ant system algorithm for the vehicle routing problem[J], Annals of Operations Research, 1999, 89:319-328. [5] CARO D. Antnet: distributed stigmergetic control for communications networks[J]. Journal of Artificial Intelligent Research, 1999, 9(1): 317-365. [6] HOU W B, XIONG Z H, WANG C S, et al. Enhanced ant colony algorithm with communication mechanism for mobile robot path planning[J]. Robotics and Autonomous Systems, 2022,148: 103949. [7] LU L C, YUE T W. Mission-oriented ant-team ACO for min-max MTSP[J]. Applied Soft Computing, 2018, 76:436-444. [8] MIAO C W, CHEN G Z, YAN C L, et al. Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm[J]. Computers & Industrial Engineering, 2021,156:107230. [9] XUE T, LIU L, LIU S, et al. Path planning of mobile robot based on improved ant colony algorithm for logistics[J]. Mathematical Biosciences and Engineering, 2021, 18(4): 3034-3045. [10] 孔珊,仲昭林,张纪会.多路径选择变速双目标物流配送路径规划[J].复杂系统与复杂性科学, 2022, 19(1):74-80. KONG S, ZHONG Z L, ZHANG J H. Bi-objective vehicle routing problems with path choice and variable speed[J]. Complex System and Complexity Science, 2022, 19(1):74-80. [11] 江明,王飞,葛愿,等.基于改进蚁群算法的移动机器人路径规划研究[J].仪器仪表学报, 2019, 40(2): 113-121. JIANG M, WANG F, GE Y, et al. Research on path planning of mobile robot based on improved ant colony algorithm[J]. Chinese Journal of Scientific Instrument, 2019, 40(2): 113-121. [12] 王晓燕,杨乐,张宇,等. 基于改进势场蚁群算法的机器人路径规划[J].控制与决策, 2018, 33(10): 1775-1781. WANG X Y, YANG L, ZHANG Y, et al, et al. Robot path planning based on improved ant colony algorithm with potential field heuristic[J]. Control and Decision, 2018, 33(10): 1775-1781. [13] 徐兴,钱誉钦,赵芸,等.基于改进蚁群算法的立体仓库三维空间路径优化[J].计算机集成制造系统, 2021, 27(1): 207-214. XU X, QIAN Y Q, ZHAO Y, et al.3D spatial path optimization of stereo warehouse based on improved ant colony algorithm[J].Computer Integrated Manufacturing Systems, 2021, 27(1): 207-214. [14] 徐小斐,陈婧,饶运清,等.迁移蚁群强化学习算法及其在矩形排样中的应用[J].计算机集成制造系统, 2020, 26(12): 3236-3247. XU X F, CHEN J, RAO Y Q, et al. Transfer ants reinforcement learning algorithm and its application on rectangular packing problem[J]. Computer Integrated Manufacturing Systems, 2021, 36(7): 1581-1591. [15] 徐菱,付文浩,江文辉,等.基于16方向24邻域改进蚁群算法的移动机器人路径规划[J].控制与决策, 2021, 36(5): 1137-1146. XU L, FU W H, JIANG W H, et al. Mobile robots path planning based on 16-directions 24-neighborhoods improved ant colony algorithm[J]. Control and Decision, 2021, 36(5): 1137-1146. [16] DEBORA D C, ALI E, HAMIDREZA A, et al. A novel ant colony algorithm for solving shortest path problems with fuzzy arc weights[J]. Alexandria Engineering Journal, 2022, 61: 3403-3415. [17] 张恒,何丽,袁亮,等.基于改进双层蚁群算法的移动机器人路径规划[J].控制与决策, 2022, 37(2): 303-313. ZHANG H, HE L, YUAN L, et al. Mobile robot path planning using improved double-layer ant colony algorithm[J]. Control and Decision, 2022, 37(2): 303-313. [18] 张玮,马焱,赵捍东,等.基于改进烟花-蚁群混合算法的智能移动体避障路径规划[J].控制与决策, 2019, 34(2): 335-343. ZHANG W, MA Y, ZHAO H D, et al. Obstacle avoidance path planning of intelligent mobile based on improved fireworks-ant colony hybrid algorithm[J]. Control and Decision, 2019, 34(2): 335-343. [19] 邓丽娟,张纪会.混合蚁群算法求解双目标时间窗VRP[J].复杂系统与复杂性科学,2020,17(4):73-84. DENG L J, ZHANG J H. A hybrid ant colony optimization for bi-objective VRP with time windows[J]. Complex System and Complexity Science, 2020, 17(4): 73-84. [20] HOU W B, XIONG Z H, WANG C S, et al. Enhanced ant colony algorithm with communication mechanism for mobile robot path planning[J]. Robotics and Autonomous Systems, 2022, 148:103949.
