[1]PEI Zhenbing,CHEN Xuebo.Improved ant colony algorithm and its application in obstacle avoidance for robot[J].CAAI Transactions on Intelligent Systems,2015,10(1):90-96.[doi:10.3969/j.issn.1673-4785.201311018]
Copy

Improved ant colony algorithm and its application in obstacle avoidance for robot

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 10 Number of periods: 2015 1 Page number: 90-96 Column: 学术论文—智能系统 Public date: 2015-03-25
Title:
Improved ant colony algorithm and its application in obstacle avoidance for robot
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 optimization; interlock; robots; obstacle avoidance; grid method; modeling; concave obstacle; deadlock
CLC:
TP242
DOI:
10.3969/j.issn.1673-4785.201311018
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.
Similar References:

Memo

-

Last Update: 2015-06-16

Copyright © CAAI Transactions on Intelligent Systems