基于双向汇聚引导蚁群算法的机器人路径规划

doi:10.16182/j.issn1004731x.joss.20-1000

摘要/Abstract

摘要：

路径规划是自主移动机器人技术的核心理论问题之一，论文采用网格法建立路径规划问题的环境模型，提出了基于先验知识的优势方位角，建立了主优势网格和次优网格的改进网格模型，并采用基于子路径认知方法的信息素释放策略，提出了起始点与目标点互换的交替双向引导策略，实现了一种汇聚融合的信息素结构，实现了基于改进网格模型的双向汇聚斑迹信息素蚁群算法。实验表明，该方法在求解具有复杂障碍物分布的大规模地图规划问题时，具有空间复杂度小和效率高的优点，大大提升了构建初始解及收敛的速度，具有很好的求解性能。

关键词: 斑迹蚁群算法, 双向汇聚引导, 机器人路径规划, 节点信息素

Abstract:

Path planning is a key theoretical issue of the autonomous mobile robot technology. This paper utilizes an improved grid method to establish environment model, which involves a new priori advantage azimuth structure that includes two parts of the primary dominant grid cell and the subprime grid cell. It improves the pheromone mark ant colony optimization algorithm by putting forward a novel pheromone update strategy based on secondary path cognitive method, which is called bidirectional guidance strategies. It repeats an alternation of the starting point and the target point in each new round of iteration. The experimental results show that the improved algorithm has the advantages of low spatial complexity and high efficiency in solving large-scale planning problems especially with complex obstacles, and greatly improves the speed of initial solution construction and convergence, and has good solving performance.

Key words: pheromone mark ant colony optimization (PM-ACO), bidirectional aggregation, robot path planning, node-based pheromone

中图分类号:

邓向阳, 张立民, 方伟, 汤淼. 基于双向汇聚引导蚁群算法的机器人路径规划[J]. 系统仿真学报, 2022, 34(5): 1101-1108.

Xiangyang Deng, Limin Zhang, Wei Fang, Miao Tang. Robot Path Planning Based on Bidirectional Aggregation Ant Colony Optimization[J]. Journal of System Simulation, 2022, 34(5): 1101-1108.

图/表 7

图1

图2

图3

图4

图5

图6

表1

参考文献 17

[1]	Alajlan M, Koubaa A, Chaari I, et al. Global Path Planning Formobile Robots in Large-Scale Grid Environment Using Genetic Algorithms[C]//International Conference on Individual and Collective Behaviors in Robotics. Piscataway. USA: IEEE, 2013: 1-8.
[2]	王辉, 朱龙彪, 王景良, 等. 基于Dijkstra-蚁群算法的泊车系统路径规划研究[J]. 工程设计学报, 2016, 23(5): 489-496.
	Wang Hui, Zhu Longbiao, Wang Jingliang, et al. Research on Path Planning of Parking System Based on Dijkstra-Ant Colony Hybrid Algorithm[J]. Chinese Journal of Engineering Design, 2016, 23(5): 489-496.
[3]	Deng X Y, Zhang L M, Luo L. An Improved Ant Colony Optimization Applied in Robot Path Planning Problem[J]. Journal of Computers (S1796-203X), 2013, 8(3): 585-593.
[4]	王醒策, 张汝波, 顾国昌. 基于势场栅格法的机器人全局路径规划[J]. 哈尔滨工程大学学报, 2003, 24(2): 170-174.
	Wang Xingce, Zhang Rubo, Gu Guochang. Potential Grid based Global Path Planning for Robots[J]. Journal of Harbin Engineering University, 2003, 24(2): 170-174.
[5]	曾辰, 许瑛. 一种蜂巢栅格下机器人路径规划的蚁群算法[J]. 机械科学与技术, 2016, 35(8): 1308-1312.
	Zeng Chen, Xu Ying. An Ant Colony Algorithm for robot Path Planning in a Honeycomb Grid[J]. Mechanical Science and Technology for Aerospace Engineering, 2016, 35(8): 1308-1312.
[6]	卜新苹, 苏虎, 邹伟, 等. 基于复杂环境非均匀建模的蚁群路径规划[J]. 机器人, 2016, 38(3): 276-284.
	Bu Xinping, Su Hu, Zou Wei, et al. Ant Colony Path Planning Based on Non-Uniform Modeling of Complex Environment[J]. Robot, 2016, 38(3): 276-284.
[7]	林彬, 韩光辉, 宋晨晨, 等. 基于辐射扫描算法的机器人路径规划与仿真[J]. 系统仿真学报, 2021, 33(1): 84-90.
	Lin Bin, Han Guanghui, Song Chenchen, et al. Traversal Path Planning and Simulation of Robot Based on Radiation Scanning[J]. Journal of System Simulation. 2021, 33(1): 84-90.
[8]	罗德林, 吴顺祥. 基于势场蚁群算法的机器人路径规划[J]. 系统工程与电子技术, 2010, 32(6): 1277-1280.
	Luo Delin, Wu Shunxiang. Ant Colony Optimization with Potential Field Heuristic for Robot Path Planning[J]. Journal of Systems Engineering and Electronics, 2010, 32(6): 1277-1280.
[9]	柳长安, 鄢小虎, 刘春阳, 等. 基于改进蚁群算法的移动机器人动态路径规划方法[J]. 电子学报, 2011, 39(5): 1220-1224.
	Liu Changan, Yan Xiaohu, Liu Chunyang, et al. Dynamic Path Planning for Mobile Robot Based on Improved ant Colony Optimization Algorithm[J]. Chinese Journal of Electronics, 2011, 39(5): 1220-1224.
[10]	白建龙, 陈瀚宁, 胡亚宝, 等. 基于负反馈机制的蚁群算法及其在机器人路径规划中的应用[J]. 计算机集成制造系统, 2019, 25(7): 1767-1774.
	Bai Jianlong, Chen Hanning, Hu Yabao, et al. Ant Colonyalgoritm Based on Negative Feedback and Its Application on Robot Path Planning[J]. Computer Integrated Manufacturing System, 2019, 25(7): 1767-1774.
[11]	王雷, 石鑫. 改进蚁群算法在移动机器人避障中的应用[J]. 南京航空航天大学学报, 2019, 51(5): 728-734.
	Wang Lei, Shi Xin. Improved Ant Colony Algorithm of Obstacle Avoidance for Mobile Robot[J]. Journal of Nanjing University of Aeronautics & Astronautics, 2019, 51(5): 728-734.
[12]	游晓明, 刘升, 吕金秋. 一种动态搜索策略的蚁群算法及其在机器人路径规划中的应用[J]. 控制与决策, 2017, 32(3): 552-556.
	You Xiaoming, Liu Sheng, Lü Jinqiu. Ant Colony Algorithm based on Dynamic Search Strategy and Its Application on Path Planning of Robot[J]. Control and Decision, 2017, 32(3): 552-556.
[13]	李理, 李鸿, 单宁波. 多启发因素改进蚁群算法的路径规划[J]. 计算机工程与应用, 2019, 55(5): 225-231.
	Li Li, Li Hong, Shan Ningbo. Path Planning Based on Improved Ant Colony Algorithm with Multiple Inspired Factor[J]. Computer Engineering and Applications, 2019, 55(5): 225-231.
[14]	孙功武, 苏义鑫, 顾轶超, 等. 基于改进蚁群算法的水面无人艇路径规划[J]. 控制与决策, 2021, 36(4): 847-856.
	Sun Gongwu, Su Yixin, Gu Yichao, et al. Path Planning for Unmanned Surface Vehicle Based on Improved Ant Colony Algorithm[J]. Control and Decision, 2021, 36(4): 847-856.
[15]	张玮, 马焱, 赵捍东, 等. 基于改进烟花-蚁群混合算法的智能移动体避障路径规划[J]. 控制与决策, 2019, 34(2): 114-122.
	Zhang Wei, Ma Yan, Zhao Handong, et al. Obstacle Avoidance Path Planning of Intelligent Mobile Based on Improved Fireworks-Ant Colony Hybrid Algorithm[J]. Control and Decision, 2019, 34(2): 114-122.
[16]	Deng X Y, Zhang L M, Lin H W, et al. Pheromone Mark Ant Colony Optimization with a Hybrid Node-based Pheromone Update Strategy[J]. Neurocomputing (S0925-2312), 2015, 148: 46-53.
[17]	Blum C, Dorigo M. The Hyper-Cube Framework for Ant Colony Optimization[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (S1083-4419), 2004, 34(2): 1161-1172.

序号	最优值50×50		最优值首达轮次50×50		最优值80×80		最优值首达轮次80×80
序号	本文	文献[3]	本文	文献[3]	本文	文献[3]	本文	文献[3]
1	64	65	147	260	93	139	39	233
2	63	68	104	283	93	118	78	311
3	63	65	105	371	95	105	122	298
4	63	63	138	329	101	152	318	237
5	64	63	125	297	93	148	432	443
6	63	65	104	307	95	125	204	427
7	65	70	121	335	104	100	101	201
8	63	64	131	244	97	–	111	–
9	63	67	120	281	93	117	200	323
10	63	65	158	248	96	135	325	219
平均	63.4	65.5	125.3	295.5	96	126.6	193	299.1
最小	63	63	104	244	93	100	39	201
最大	65	70	158	377	104	152	432	443