基于双起点蚁群算法的机器人路径规划方法

doi:10.13229/j.cnki.jdxbgxb.20230339

摘要/Abstract

摘要：

针对现实环境的全局路径规划中蚁群算法搜索精度不足且易陷入局部极值以及迭代次数过多、求解目标单一等问题，本文提出了一种双起点蚁群算法。通过模拟栅格地图，在蚁群算法的基础上将起始位置进行调整，改进了传统蚁群算法中只能固定单向移动搜索的方式，设置两个起点，并在此基础上优化了信息素的更新策略，使其能够指导下一次迭代的进程，缩短路径搜索的时间，降低蚁群算法在前期搜索中的盲目性，且随着迭代次数的增多算法在前期所能得到的解的多样性增加，提高了得到最优解的概率，还能避免算法易陷入局部最优的问题，加快算法后期的收敛速度。通过对双起点蚁群算法进行模拟实验，实验结果表明该算法具有较好的寻优性能和迭代收敛性。

关键词: 蚁群算法, 双起点, 路径规划, 信息素, 栅格地图

Abstract:

Due to the insufficient search accuracy of ant colony algorithm in global path planning in the real environment and its tendency to fall into local extremum， excessive iteration times， and single solving objective， this paper proposes a dual starting point ant colony algorithm. By simulating a grid map and adjusting the starting position based on the ant colony algorithm， we improved the traditional ant colony algorithm's fixed one-way moving search method by setting two starting points. On this basis， we also optimized the pheromone update strategy to guide the next iteration process， which can shorten the path search time and reduce the blindness of the ant colony algorithm in the early search， and as the number of iterations increases， the diversity of solutions that the algorithm can obtain in the early stage increases， increasing the probability of obtaining the optimal solution， and also avoiding the problem of the algorithm easily falling into local optima， accelerating the convergence speed of the algorithm in the later stage. Through simulation experiments on the dual starting point ant colony algorithm， it is shown that the algorithm has good optimization performance and iterative convergence.

Key words: ant colony algorithm, dual starting point, path planning, pheromone, raster map

中图分类号:

TP399

李健,孙晓海,廖昌义,杨建平. 基于双起点蚁群算法的机器人路径规划方法[J]. 吉林大学学报(工学版), 2025, 55(1): 325-332.

Jian LI,Xiao-hai SUN,Chang-yi LIAO,Jian-ping YANG. Robot path planning method based on double-origin ant colony algorithm[J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(1): 325-332.

图/表 9

图1

图2

图3

图4

图5

图6

表1

图7

图8

参考文献 28

1	Li J, Liao C Y, Zhang W J, et al.UAV path planning model based on R5DOS model improved a-star algorithm[J].Applied Sciences,2022,12(22):No.11338.
2	杨庆芳, 梅朵, 韩振波, 等.基于云计算的蚁群算法求解城市路网最短路径[J].吉林大学学报: 工学版,2013, 43(5): 1210-1214.
	Yang Qing-fang, Mei Duo, Han Zhen-bo, et al. Ant colony algorithm based on cloud computing to solve the shortest path of urban road network [J].Journal of Jilin University (Engineering and Technology Edition), 2013, 43(5): 1210-1214.
3	陈谋, 肖健, 姜长生.基于改进蚁群算法的无人机三维航路规划[J].吉林大学学报: 工学版, 2008, 38(4):991-995.
	Chen Mou, Xiao Jian, Jiang Chang-sheng. Three-dimensional route planning of UAV based on improved ant colony algorithm [J].Journal of Jilin University(Engineering and Technology Edition), 2008,38(4): 991-995.
4	段海滨, 王道波, 于秀芬.基于云模型的小生境MAX-MIN相遇蚁群算法[J].吉林大学学报: 工学版, 2006, 36(5): 803-808.
	Duan Hai-bin, Wang Dao-bo, Yu Xiu-fen. Cloud model based niche MAX-MIN encounter ant colony algorithm[J].Journal of Jilin University (Engineering and Technology Edition), 2006, 36(5): 803-808.
5	Li J, Zhang W J, Hu Y T, et al. Leader-follower UAV formation model based on R5DOS-intersection model[J]. Computers, Materials and Continua, 2021, 69(2): 2493-2511.
6	申铉京, 刘阳阳, 黄永平, 等.求解TSP问题的快速蚁群算法[J].吉林大学学报: 工学版,2013, 43(1):147-151.
	Shen Xuan-jing, Liu Yang-yang, Huang Yong-ping, et al. Fast ant colony algorithm for solving TSP problem[J].Journal of Jilin University (Engineering and Technology Edition), 2013, 43 (1): 147-151.
7	焦斌, 熊友平, 顾幸生.改进的蚁群优化算法在无线传感器网络中的应用[J].吉林大学学报: 工学版,2011, 41(): 215-219.
	Jiao Bin, Xiong You-ping, Gu Xing-sheng. Application of improved ant colony optimization algorithm in wireless sensor networks[J].Journal of Jilin University(Engineering and Technology Edition), 2011,41(Sup.1): 215-219.
8	Tian Y, Zhang J, Wang Q, et al.Application of hybrid algorithm based on ant colony optimization and sparrow search in UAV path planning[J].International Journal of Computational Intelligence Systems, 2024,17(1): 286.
9	吴帅, 魏文红, 张宇辉, 等.基于改进蚁群算法的移动机器人路径规划[J].东莞理工学院学报, 2023, 30(1):24-34.
	Wu Shuai, Wei Wen-hong, Zhang Yu-hui, et al. Mobile robot path planning based on improved ant colony algorithm[J].Journal of Dongguan University of Technology, 2023, 30(1): 24-34.
10	张俊豪.模拟退火蚁群算法在最优路径选择中的应用[J].怀化学院学报, 2022, 41(5): 68-75.
	Zhang Jun-hao. Application of simulated annealing ant colony algorithm in optimal path selection[J]. Journal of Huaihua University, 2022, 41(5): 68-75.
11	周敬东, 高伟周, 杨文广, 等.基于改进蚁群算法的移动机器人路径规划[J].科学技术与工程, 2022,22(28): 12484-12490.
	Zhou Jing-dong, Gao Wei-zhou, Yang Wen-guang, et al. Mobile robot path planning based on improved ant colony algorithm[J]. Science, Technology and Engineering, 2022, 22(28): 12484-12490.
12	张志军, 董学平, 甘敏.基于优化蚁群算法的AGV路径规划研究[J].合肥工业大学学报: 自然科学版,2022, 45(7): 914-919, 924.
	Zhang Zhi-jun, Dong Xue-ping, Gan Min. Research on AGV path planning based on optimized ant colony algorithm[J].Journal of Hefei University of Technology (Natural Science Edition), 2022,45(7): 914-919, 924.
13	Morteza K, García E, Villar J R, et al. A*-based co-evolutionary approach for multi-robot path planning with collision avoidance[J]. Cybernetics and Systems, 2023, 54(1/4): 339-354.
14	Ding J, Zhou Y, Huang X, et al. An improved RRT* algorithm for robot path planning based on path expansion heuristic sampling[J]. Journal of Computational Science, 2023, 67: No.101937.
15	Niu Y B, Yan X F, Wang Y Z,et al. Three-dimensional UCAV path planning using a novel modified artificial ecosystem optimizer[J]. Expert Systems with Applications, 2023, 217: No.119499.
16	兰国辉, 张玉遇. 改进蚁群算法对多配送中心物流配送路径优化[J].长春工程学院学报: 自然科学版,2024, 25(2): 119-124.
	Lan Guo-hui, Zhang Yu-yu. Improved ant colony algorithm for multi-distribution center logistics distribution path optimization[J].Journal of Changchun University of Engineering (Natural Science Edition), 2024, 25(2): 119-124.
17	Chen Y, Dong Q, Shang X Z, et al. Multi-UAV autonomous path planning in reconnaissance missions considering incomplete information: a reinforcement learning method[J]. Drones, 2022, 7(1): 10.
18	Cheng L H, Xiao Y P, Ma C S. Research on the path planning of transportation UAV in rasterization scene based on ant colony algorithm[J]. Journal of Physics: Conference Series, 2022, 2365(1): No. 012051.
19	Wang Y, Deng Q R. Optimization of maintenance scheme for offshore wind turbines considering time windows based on hybrid ant colony algorithm[J]. Ocean Engineering, 2022, 263: No.122357.
20	Yang Y X, Chen Z X. Optimization of dynamic obstacle avoidance path of multirotor UAV based on ant colony algorithm[J]. Wireless Communications and Mobile Computing, 2022, 2022: No.122434.
21	李二超, 齐款款. 基于栅格图特征点提取下的蚁群算法路径规划[J]. 上海交通大学学报: 自然科学版, 2023, 28(1): 86-99.
	Li Er-Chao, Qi Kuan-kuan. Ant colony algorithm for path planning based on grid feature point extraction[J]. Journal of Shanghai Jiaotong University (Science Edition), 2023, 28(1): 86-99.
22	Li X W, Li Q, Zhang J H. Research on global path planning of unmanned vehicles based on improved ant colony algorithm in the complex road environment[J]. Measurement and Control, 2022, 55(9-10): 945-959.
23	Musa R, Arnaout J, Jung H.Ant colony optimization algorithm to solve for the transportation problem of cross-docking network[J].Computers & Industrial Engineering, 2010, 59(1): 85-92.
24	Soroush V, Abbas D. Optimal path planning for unmanned surface vehicle using new modified local search ant colony optimization[J]. Journal of Marine Science and Technology, 2022, 27(4): 1207-1219..
25	Hussain S F, Butt I A, Hanif M,et al. Clustering uncertain graphs using ant colony optimization (ACO)[J]. Neural Computing and Applications,2022,34:11721-11738.
26	Petr S, Pavel O, Kamila H. Adaptive ant colony optimization with node clustering applied to the travelling salesman problem[J]. Swarm and Evolutionary Computation, 2022, 70: No.101056.
27	Gilberto R, Coello Carlos A, Laura C R, et al. Preference incorporation into many-objective optimization: an ant colony algorithm based on interval outranking[J]. Swarm and Evolutionary Computation,2022, 69: No.101024.
28	Pu Y F, Siarry P, Zhu W Y, et al. Fractional-order ant colony algorithm: a fractional long term memory based cooperative learning approach[J]. Swarm and Evolutionary Computation, 2022, 69: No.101014.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

算法	最佳路径长度	平均长度	平均迭代次数
传统蚁群算法	35.86	36.52	136
双起点蚁群算法	33.29	33.85	61
多步长蚁群算法	34.85	34.49	115

[1]	朱瑾,黄琦. 路网资源分配下自动化码头水平运输调度与路径规划[J]. 吉林大学学报(工学版), 2024, 54(8): 2245-2255.
[2]	孙帅帅,冯春晓,张良. 基于离散采样的多模态四足机器人路径规划[J]. 吉林大学学报(工学版), 2024, 54(4): 1120-1128.
[3]	杨娇寰,王鹏. 基于自适应莱维多样性的改进蚁群算法[J]. 吉林大学学报(工学版), 2024, 54(10): 2978-2983.
[4]	孙宝凤,刘娇娇,姚天姿,任欣欣. 考虑能量消耗的纯电动物流车柔性时间窗路径规划问题[J]. 吉林大学学报(工学版), 2023, 53(4): 1047-1059.
[5]	吴振宇,刘小飞,王义普. 基于DKRRT^*-APF算法的无人系统轨迹规划[J]. 吉林大学学报(工学版), 2023, 53(3): 781-791.
[6]	孙宝凤,姚天姿,陈雨琦. 考虑时变交通拥堵的纯电动物流车路径规划模型[J]. 吉林大学学报(工学版), 2023, 53(2): 468-479.
[7]	杨帆,翟志强,汪圆圆,朱忠祥,杜岳峰,毛恩荣. 基于虚拟现实的拖拉机变速箱装配系统设计[J]. 吉林大学学报(工学版), 2023, 53(10): 3038-3044.
[8]	朱航,于瀚博,梁佳辉,李宏泽. 基于电场模型的无人机搜寻改进算法及仿真分析[J]. 吉林大学学报(工学版), 2022, 52(12): 3029-3038.
[9]	张必达,闫强,张琳,张海瑞. 基于实时交通信息的电动汽车充换电路径规划方法[J]. 吉林大学学报(工学版), 2022, 52(10): 2333-2342.
[10]	张家旭,王晨,赵健,卜纯研. 面向狭小平行泊车位的路径规划与跟踪控制[J]. 吉林大学学报(工学版), 2021, 51(5): 1879-1886.
[11]	张家旭,王欣志,赵健,施正堂. 汽车高速换道避让路径规划及离散滑模跟踪控制[J]. 吉林大学学报(工学版), 2021, 51(3): 1081-1090.
[12]	韩小健,赵伟强,陈立军,郑宏宇,刘阳,宗长富. 基于区域采样随机树的客车局部路径规划算法[J]. 吉林大学学报(工学版), 2019, 49(5): 1428-1440.
[13]	车翔玖, 张孙旻. 基于异步更新策略的蚁群边缘提取算法[J]. 吉林大学学报(工学版), 2017, 47(5): 1577-1582.
[14]	钱立军, 胡伟龙, 刘庆, 吴冰. 多段式自动泊车路径规划及其关键技术[J]. 吉林大学学报(工学版), 2016, 46(3): 785-791.
[15]	周炳海, 周琪. 防潜在死锁的整体式自动物料搬运系统调度方法[J]. 吉林大学学报(工学版), 2016, 46(2): 595-601.