General Ant Colony Algorithm and Its Applications in Robot Formation
ZHANG Ying1,2, CHEN XueBo2
1.School of Electronics and Information Engineering, Dalian University of Technology, Dalian 116024 2.School of Electronics and Information Engineering, Liaoning University of Science and Technology, Anshan 114044
Abstract A general ant colony algorithm is proposed. In this algorithm, ants are supposed to be divided into several swarms and each swarm possesses its own nest and food at different places. During a preset period, ants from the same swarm increase the strength of pheromone on the shortest path which they have found between a food source and the nest. In the meanwhile, they adjust the strength of pheromone on other paths to zero. Each swarm moves on its own path and collision never occurs. When environment changes, the swarms crawl to their food along the increased pheromone. The general ant algorithm combined with the affine transformation is applied to the robot formation, and the results are effective.
[1] Colorni A, Dorigo M, Maniezzo V. Distributed Optimization by Ant Colonies // Proc of the 1st European Conference on Artificial Life. Paris, France, 1991: 134142 [2] Dorigo M, Maniezzo V, Colorni A. Ant System: Optimization by a Colony of Cooperating Agents. IEEE Trans on Systems, Man, and Cybernetics, 1996, 26(1): 2941 [3] Dorigo M, Caro G D, Gambardella L M. Ant Algorithms for Discrete Optimization. Artificial Life, 1999, 5(3): 137172 [4] Colorni A, Dorigo M. Ant System for JobShop Scheduling. Belgian Journal of Operations Research, Statistics and Computer Science, 1994, 34(1): 3953 [5] Bullnheimer B, Hartl R F, Strauss C. Applying the Ant System to the Vehicle Routine Problem // Vo S, Martello S, Osman I H, et al, eds. Meta Heuristics: Advances and Trends in Local Search Paradigms for Optimization. Boston, USA: Kluwer Academics, 1998: 109120 [6] Costa D, Hertz A. Ant Can Colour Graphs. Journal of the Operational Research Society, 1997, 48(3): 295305 [7] Gambardella L M, Dorigo M. HOSSOP: A Hybrid Ant System for the Sequential Ordering Problem. Technical Report, IDSIA1197, Lugano, Switzerland: Dalle Molle Institute for Artificial Intelligence, 1997 [8] Zhang Xuliang, Zhang Jinbin. Ant Colony Cable Laying System Based on Cooperative Learning. Computer Engineering and Applications, 2000, 36(5): 181182 (in Chinese) (张徐亮,张晋斌.基于协同学习的蚁群电缆敷设系统.计算机工程与应用, 2000, 36(5): 181182) [9] Casllas J, Cordón O, Herrera F. Learning Cooperative Fuzzy Rules Using Ant Colony Optimization Algorithms. Technical Report, 00119, Granada, Spain: University of Granada. Department of Computer Science and Artificial Intelligence, 2000 [10] Gao Shang, Yang Jingyu. Convergence Analysis of Ant Colony Algorithm for Solving Shortest Path Problem. Science Technology and Engineering, 2006, 6(3): 273277 (in Chinese) (高 尚,杨静宇.最短路的蚁群算法收敛性分析.科学技术与工程, 2006, 6(3): 273277) [11] Han Xuedong, Hong Bingrong, Meng Wei. Distributed Control for Generating Arbitrary Formation of Multiple Robots. Robot, 2003, 25(1): 6672 (in Chinese) (韩学东,洪炳熔,孟 伟.多机器人任意队形分布式控制研究. 机器人, 2003, 25(1): 6672) [12] Hong Bingrong, Wang Yuehai. A Formation Vector Based Robot Troop Formation Control Algorithm. Robot, 2001, 23(7): 580583 (in Chinese) (洪炳熔,王月海.基于队形向量的机器人部队队形控制.机器人, 2001, 23(7): 580583) [13] Han Fengqing, Li Hongmei, Li Gang, et al. An Improved Control Algorithm for Arbitrary Formation of Multiple Robots. Robot, 2003, 25(6): 521525 (in Chinese) (韩逢庆,李红梅,李 刚,等. 一种改进的多机器人任意队形控制算法.机器人, 2003, 25(6): 521525) [14] Zhan Shichang, Xu Jie, Wu Jun. The Optimal Selection on the Parameters of the Ant Colony Algorithm. Bulletin of Science and Technology, 2003, 19(5): 381386 (in Chinese) (詹士昌,徐 婕,吴 俊.蚁群算法中有关算法参数的最优选择.科技通报, 2003, 19(5): 381386)
2007, Vol. 20 
