[1]裴振兵,陈雪波.改进蚁群算法及其在机器人避障中的应用[J].智能系统学报,2015,10(01):90-96.[doi:10.3969/j.issn.1673-4785.201311018]
 PEI Zhenbing,CHEN Xuebo.Improved ant colony algorithm and its application in obstacle avoidance for robot[J].CAAI Transactions on Intelligent Systems,2015,10(01):90-96.[doi:10.3969/j.issn.1673-4785.201311018]
点击复制

改进蚁群算法及其在机器人避障中的应用(/HTML)
分享到:

《智能系统学报》[ISSN:1673-4785/CN:23-1538/TP]

卷:
第10卷
期数:
2015年01期
页码:
90-96
栏目:
出版日期:
2015-03-25

文章信息/Info

Title:
Improved ant colony algorithm and its application in obstacle avoidance for robot
作者:
裴振兵1 陈雪波2
1. 辽宁科技大学 电子与信息工程学院, 辽宁 鞍山 114051;
2. 辽宁科技大学 研究生院, 辽宁 鞍山 114051
Author(s):
PEI Zhenbing1 CHEN Xuebo2
1. School of Electronics and Information Engineering, Liaoning University of Science and Technology, Anshan 114051, China;
2. Graduate school, Liaoning University of Science and Technology, Anshan 114051, China
关键词:
改进蚁群算法互锁机器人避障栅格法建模凹形障碍物死锁
Keywords:
improved ant colony optimizationinterlockrobotsobstacle avoidancegrid methodmodelingconcave obstacledeadlock
分类号:
TP242
DOI:
10.3969/j.issn.1673-4785.201311018
文献标志码:
A
摘要:
提出了一种改进蚁群算法. 首先针对蚁群算法在构造解过程中收敛速度慢且容易陷入局部最优,提出了在蚁群搜索路径过程中,通过建立α(信息素启发式因子)和β(期望启发式因子)的互锁关系,动态自适应调整αβ;其次针对蚁群算法在面对凹形障碍物易陷入死锁,降低搜索效率,提出了广义信息素更新规则;最后利用栅格法进行静态已知环境建模,通过不同规模TSP的仿真验证了该方法的可行性和有效性,同时将其应用到机器人避障并取得了较好实验效果。
Abstract:
An improved ant colony algorithm is proposed in this paper. Firstly, in order to overcome the demerits of the ant colony algorithm, such as low convergence speed and easy to get into the local optimum, α and β are dynamically adaptively adjusted by establishing an interlock between alpha (pheromone heuristic factor) and beta (expected heuristic factor) in the searching route process of ant colony. Secondly, in order to prevent the ant colony algorithm from falling into deadlock when facing concave obstacles, which decreases search efficiency, an update rule of the generalized pheromone is proposed. Finally, static modeling for a known environment is conducted by the grid method. The simulation experiments showed that with different scales of TSP, the improved ant colony algorithm is feasible and efficient. In addition, this algorithm is applied to the obstacle avoidance of robots and the results are effective.

参考文献/References:

[1] COLORNI A, DORIGO M, MANIEZZO V. Distributed optimization by ant colonies[C]//Processings of the 1st European Conference on Artificial Life.Paris, France, 1991: 134-142.
[2] 徐利超, 张世武. 基于改进蚁群算法的障碍环境下路径规划研究[J].机械与电子, 2013 (7): 61-64.XU Lichao, ZHANG Shiwu. Study of path planning in obstacle environment based on an improved ant algorithm[J]. Machinery & Electronics, 2013,(7): 61-64.
[3] 朱绍伟,徐夫田,腾兆明.一种改进蚁群算法求解最短路径的应用[J].计算机技术与发展, 2011(7): 202-205.ZHU Shaowei, XU Futian, TENG Zhaoming. Application of improvement ants algorithm in solving shortest path[J]. Computer Technology and Development,2011, 21(7): 202-205.
[4] 柳长安, 鄢小虎, 刘春阳,等. 基于改进蚁群算法的移动机器人动态路径规划方法[J]. 电子学报, 2011, 39(5):1220-1224. LIU Changan, YAN Xiaohu, LIU Chunyang, et al. Dynamic path planning for mobile robot based on improoved ant colony optimization algorithm[J]. Acta Electronica Sinica, 2011, 39(5): 1220-1224.
[5] 段海滨. 蚁群算法原理及其应用[M]. 北京: 科学出版社, 2005: 176-181.
[6] GUTJAHR W J. A graph-based ant system and its convergence [J]. Future Generation Computer Systems, 2000, 16(8): 873-888.
[7] 周明秀, 程科, 王正霞.动态路径规划中的改进蚁群算法[J]. 计算机科学, 2012, 40(1): 314-316. ZHOU Mingxiu, CHENG Ke, WANG Zhengxia. Improved ant colony algorithm with planning of dynamic path[J]. Computer Science, 2012, 40(1): 314-316.
[8] 王越, 叶秋冬. 蚁群算法在求解最短路径问题上的改进策略[J]. 计算机工程与应用, 2012, 48(13): 35-38.WANG Yue, YE Qiudong. Improved strategies of ant colony algorithm for solving shortest path problem[J].Computer Engineering and Applications, 2012, 48(13):35-38.
[9] 赵凯, 李声晋, 孙娟, 等.改进蚁群算法在移动机器人路径规划中的研究[J]. 微型机与应用, 2013, 32(4): 67-70.ZHAO Kai, LI Shengjin, SUN Juan, et al. Research of improved ant colony algorithm in mobile robot path planning[J]. Microcomputer & its Applications, 2013, 32(4): 67-70.
[10] 温如春, 汤青波, 杨国亮. 基于改进蚁群算法的移动机器人路径规划[J]. 兵工自动化, 2010, 29(8): 69-70. WEN Ruchun, TANG Qingbo, YANG Guoliang. Mobile robot’s path planning based on improved ant colony algorithm[J]. Ordance Industry Automation, 2010, 29(8): 69-70.
[11] 张颖, 陈雪波. 广义蚁群算法及其在机器人队形变换中的应用[J]. 模式识别与人工智能, 2007, 19, 20(3): 3-8.ZHANG Ying, CHEN Xuebo. General ant colony algorithm and its applications in robot formation[J]. Pattern Recognition and Aitificial Intelligence, 2007, 19, 20(3): 3-8.
[12] JACKSON D E, HOLCOMBE M, RATNIEKS F L W. Trail geometry gives polarity to ant foraging networks [J].Nature, 2004, 432(7019):907-909.
[13] 贾振华, 斯庆巴拉, 王慧娟. 基于启发式机器人路径规划仿真研究[J]. 计算机仿真, 2012, 29(1): 135-138.JIA Zhenhua, SIQING Bala, WANG Huijuan. Path planning based on heuristic algorithm[J]. Computer Simulation, 2012, 29(1): 135-138.
[14] AI-TAHARWA I, SHETA A, AI-WESHAN M. A mobile robot path planning using genetic algorithm in static environment [J]. Journal of Computer Sciences, 2008, 4(4): 341-344.
[15] YAO L M, DUAN H B, SHAO S. Adaptive template matching based on improved ant colony optimization[C]//Proceedings of International Workshop on Intelligence Systems and Applications. [s.l.], 2009:1-4.
[16] BROOKS R A. Solving the find-path problem by good representation of free space [J]. IEEE Trans on System Man and Cybernetics, 1983, 13(3): 190-197.
[17] JANET J A. The essential visibility graph: an approach to global motion planning for autonomous mobile robots[C]//IEEE International Conference on Robotics and Automation. [s.l.], 1995: 1958-1963.
[18] EMILIO F. Real-time motion planning for agile autonomous vehicles [J]. Journal of Guidance, Control and Dynamics, 2002, 25(1):116-129.
[19] BONABEAU E, DORIGO M, Theraulaz G. Inspiration for optimization from social insect behavior [J]. Nature, 2000, 406(6): 39-42.
[20] DORIGO M, DI CARO G, GAMBARDELLA L M. Ant algorithms for discrete optimization [J]. Artificial Life, 1999, 5(2): 137-172.

备注/Memo

备注/Memo:
收稿日期:2013-11-7;改回日期:。
基金项目:国家自然科学基金资助项目(60874017).
作者简介:裴振兵,男,1989年生,硕士研究生,主要研究方向为智能优化及机器人路径规划;陈雪波,男,1960年生,教授,博士生导师,中国自动化学会过程控制专业委员会委员。主要研究方向为复杂系统、群集智能等。主持多项国家及省部级科研基金项目,出版专著1部。
通讯作者:陈雪波.E-mail:xuebochen@126.com.
更新日期/Last Update: 2015-06-16