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

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

CLC Number:

TP399

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.

Figures/Tables 9

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Table 1

Fig.7

Fig.8

References 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.

Related Articles 15

[1]	Jin ZHU,Qi HUANG. Automated terminal horizontal transportation scheduling and route planning under network resource allocation [J]. Journal of Jilin University(Engineering and Technology Edition), 2024, 54(8): 2245-2255.
[2]	Shuai-shuai SUN,Chun-xiao FENG,Liang ZHANG. Path planning for multimodal quadruped robots based on discrete sampling [J]. Journal of Jilin University(Engineering and Technology Edition), 2024, 54(4): 1120-1128.
[3]	Hao ZHENG,Li-jun YU,Peng-peng ZHI,Zhong-lai WANG. Dynamic obstacle avoidance strategy for flapping⁃wing micro air vehicles [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(9): 2732-2740.
[4]	Zhen-yu WU,Xiao-fei LIU,Yi-pu WANG. Trajectory planning of unmanned system based on DKRRT^*⁃APF algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(3): 781-791.
[5]	Fan YANG,Zhi-qiang ZHAI,Yuan-yuan WANG,Zhong-xiang ZHU,Yue-feng DU,En-rong MAO. Design of assembly system for tractor transmission based on virtual reality [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(10): 3038-3044.
[6]	Hang ZHU,Han-bo YU,Jia-hui LIANG,Hong-ze LI. Improved algorithm of UAV search based on electric field model and simulation analysis [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(12): 3029-3038.
[7]	Jia-xu ZHANG,Chen WANG,Jian ZHAO,Chun-yan BU. Path planning and tracking control for narrow parallel parking space [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(5): 1879-1886.
[8]	Jia-xu ZHANG,Xin-zhi WANG,Jian ZHAO,Zheng-tang SHI. Path planning and discrete sliding mode tracking control for high⁃speed lane changing collision avoidance of vehicle [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(3): 1081-1090.
[9]	Xiao-jian HAN,Wei-qiang ZHAO,Li-jun CHEN,Hong-yu ZHENG,Yang LIU,Chang-fu ZONG. Local path planning of bus based on RS-RRT algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2019, 49(5): 1428-1440.
[10]	CHE Xiang-jiu, ZHANG Sun-min. Edge extraction method based on ant colony asynchronous update strategy [J]. 吉林大学学报(工学版), 2017, 47(5): 1577-1582.
[11]	QIAN Li-jun, HU Wei-long, LIU Qing, WU Bing. Multiple segment method for automatic parking path planning and its key technology [J]. 吉林大学学报(工学版), 2016, 46(3): 785-791.
[12]	ZHOU Bing-hai, ZHOU Qi. Impending deadlock-free scheduling method for unified AMHS in semiconductor FABs [J]. 吉林大学学报(工学版), 2016, 46(2): 595-601.
[13]	TENG Zhi-jun, ZHANG Fan, SONG Ming-hui. Wireless sensor network energy balance ant colony routing algorithm [J]. 吉林大学学报(工学版), 2016, 46(1): 327-332.
[14]	KANG Bing, WANG Xi-hui, LIU Fu. Path planning of searching robot based on improved ant colony algorithm [J]. 吉林大学学报(工学版), 2014, 44(4): 1062-1068.
[15]	LIU Hou-de, LIANG Bin, XU Wen-fu, MU Qing-tao, YU Jiang-hua. Motion prediction and autonomous path planning for spinning target capturing [J]. 吉林大学学报(工学版), 2014, 44(3): 757-764.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

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

Robot path planning method based on double-origin ant colony algorithm

RICH HTML

PDF (PC)