基于生物启发的群机器人系统群体搭建机制研究
|
摘要
群机器人系统是一类特殊的多机器人系统,由许多相对简单的个体组成,主要研究如何设计个体,使得通过个体之间或者个体与环境之间的局部交互涌现出期望的系统行为。群机器人系统研究的兴起源于生物学,尤其是社会性昆虫的启发,因此具有典型的分布式系统特征。相比于传统的个体机器人系统,群机器人系统在灵活性、鲁棒性、分散性以及自组织性等方面表现出特有的优势,潜在应用领域非常广阔。
群机器入学的研究注重个体机器人的物理实现以及个体交互、个体与环境交互的物理实现,目前已成为研究的热点,但是该方向是一门崭新的学科,尚未形成系统的理论,仍有很多问题亟待研究与解决。例如对于给定的系统行为,该如何设计底层的交互机器人,使得系统行为在底层个体的交互中涌现出来,是群机器人学研究中一个尚未解决的问题。群机器人学是一门应用性的学科,对该学科的研究往往通过结合具体任务深入探究其内在机理。本文通过结合群体搭建任务,研究一群相对简单的机器人如何以分散控制的方式并行搭建出具有几何形状的结构。该任务特别要求搭建过程时空的协调,本文针对群体搭建过程中若干协调机制问题进行了相关探讨与研究,内容如下：
(1)针对现有模板机制在群体搭建任务中存在的不足,受蜜蜂视觉导航机制的启发,提出了群体搭建机器人以环境中自然存在的一些显著特征为模板,实现了机器人搭建过程的视觉导航与定位,完成了砖块指定地点的搁放,并实现了群体搭建过程的协调,建立起视觉模板机制。直线墙搭建实验结果表明视觉模板机制是可行的。该机制的优点是无需事先对环境进行布置,无需机器人之问通讯,并对多机器人的控制有很好的扩展性,适应于未知环境中的群体搭建工作。
(2)在视觉模板机制的基础上,提出了基于自身的时空可变模板机制,使模板从环境的固定地标中解脱出来,为群机器人搭建更为复杂的结构提供了可能。同时作为模板的机器人并不是固定不变的,所有机器人都可以充当模板,这就降低了系统中因为个体失效导致整个系统失效的风险,提高了系统的鲁棒性,使之成为更为一般化的搭建方法。
(3)针对现有的基于Stigmergy的机制在群体搭建任务中存在的不足,提出了基于机器人评估能力的群体搭建时空协调机制。该机制可通过赋予机器人感知环境、评估系统当前状态的能力,简化对搭建规则的依赖,即机器人利用简单的搭建规则即可完成群体搭建任务,实现群体搭建过程时空的协调。
(4)针对基于信息素的群体搭建机制,探讨了群体搭建过程中出现的涌现行为。通过研究白蚁王族巢室的搭建过程,抽象并建立了基于智能体的环境动力学模型以及个体行为模型,针对不同的目标结构,设计出机器人不同的行为模型,分析并探讨了简单规则产生复杂全局模式的原因等问题。
A swarm robotic system is a special type of multiple robot system, which focuses on the study of how a large number of relatively simple physically embodiment agents can be designed such that the global pattern of the system emerges from the local interactions among agents and between agents and the environment. Swarm robotics takes its inspiration from biology, in particular social insects, therefore, it exhibits many functional properties including flexibility, robustness, decentralization, self-organization, etc., which are desirable properties required in many wide-ranging potential applications.
Swarm robotics is a novel approach to the coordination of large number of robots. Researchers typically focus on one problem domain to study the underlying properties of system. This dissertation focuses on the problem of collective construction which is concerned with the building of a geometric structure with a collection of robots working in parallel, without centralized control. Robots in the swarm have to coordinate their building activities both in space and time such that a consistent structure can be achieved. For a given structure, how the robot can be designed such that the given structure can be built is still an open question in swarm robotics. Although it has drawn increasing attention over the last decade and many achievements have been made, swarm robotics is still a brand new research field and no systematic theoretical methodology has been established. This dissertation focuses on the coordination mechanisms involved in collective construction. The main works and contributions are summarized as follows:
(1) Inspired by honeybee visual navigation behavior, a visual template mechanism is proposed in which a natural landmark serves as a visual reference or template for distance determination as well as for navigation during collective construction. This mechanism can make use of an interesting landmark, reference point or salient object in the construction environment which allows for robots manipulating homogeneous bricks in a non-communicative way. Therefore, such a mechanism has an obvious appeal to those researching collective construction for applications in unknown environments.
(2) The visual template mechanism allows the robots to finish simple construction tasks. But when it comes to a more complicated task, robots would become complex. Complexity refers to the hardware and software complexity of the robots. Aiming at the drawbacks of the visual template mechanism, a spatio-temporal varying template mechanism is proposed which uses the robot itself as a template without referring to the outside world. This self-generated template varies spatially and temporally when the robot varies in position. This means the various moving pattern of the robot makes a variety of template patterns. This mechanism is a more general mechanism because it is possible for robots to build complex structures. Furthermore, the robot serving as a template is not fixed, and all the other robots could possibly become a template. This role-changing mechanism makes the system less prone to system failure when the individual malfunctions such that the robustness of the system can be increased.
(3) A new spatio-temporal coordination mechanism is proposed in the case of stigmergy-based collective construction. The originality of the work lies in the increase in the capabilities of the construction robot. Endowed with the system state assessment capability, construction robots can collective build the desired structure using only a simple rule set.
(4) A preliminary study of the emergence behavior in collective construction is given in a pheromone-based collective construction system. First the termite's royal chamber construction is studied and then agent-based collective construction model is abstracted and established. This model consists of two parts:one is a dynamic model of the environment and the other is an individual behavior model. Based on this model, several different objective structures are studied and how simple rules give rise to a complex global pattern is also discussed.
群机器入学的研究注重个体机器人的物理实现以及个体交互、个体与环境交互的物理实现,目前已成为研究的热点,但是该方向是一门崭新的学科,尚未形成系统的理论,仍有很多问题亟待研究与解决。例如对于给定的系统行为,该如何设计底层的交互机器人,使得系统行为在底层个体的交互中涌现出来,是群机器人学研究中一个尚未解决的问题。群机器人学是一门应用性的学科,对该学科的研究往往通过结合具体任务深入探究其内在机理。本文通过结合群体搭建任务,研究一群相对简单的机器人如何以分散控制的方式并行搭建出具有几何形状的结构。该任务特别要求搭建过程时空的协调,本文针对群体搭建过程中若干协调机制问题进行了相关探讨与研究,内容如下：
(1)针对现有模板机制在群体搭建任务中存在的不足,受蜜蜂视觉导航机制的启发,提出了群体搭建机器人以环境中自然存在的一些显著特征为模板,实现了机器人搭建过程的视觉导航与定位,完成了砖块指定地点的搁放,并实现了群体搭建过程的协调,建立起视觉模板机制。直线墙搭建实验结果表明视觉模板机制是可行的。该机制的优点是无需事先对环境进行布置,无需机器人之问通讯,并对多机器人的控制有很好的扩展性,适应于未知环境中的群体搭建工作。
(2)在视觉模板机制的基础上,提出了基于自身的时空可变模板机制,使模板从环境的固定地标中解脱出来,为群机器人搭建更为复杂的结构提供了可能。同时作为模板的机器人并不是固定不变的,所有机器人都可以充当模板,这就降低了系统中因为个体失效导致整个系统失效的风险,提高了系统的鲁棒性,使之成为更为一般化的搭建方法。
(3)针对现有的基于Stigmergy的机制在群体搭建任务中存在的不足,提出了基于机器人评估能力的群体搭建时空协调机制。该机制可通过赋予机器人感知环境、评估系统当前状态的能力,简化对搭建规则的依赖,即机器人利用简单的搭建规则即可完成群体搭建任务,实现群体搭建过程时空的协调。
(4)针对基于信息素的群体搭建机制,探讨了群体搭建过程中出现的涌现行为。通过研究白蚁王族巢室的搭建过程,抽象并建立了基于智能体的环境动力学模型以及个体行为模型,针对不同的目标结构,设计出机器人不同的行为模型,分析并探讨了简单规则产生复杂全局模式的原因等问题。
A swarm robotic system is a special type of multiple robot system, which focuses on the study of how a large number of relatively simple physically embodiment agents can be designed such that the global pattern of the system emerges from the local interactions among agents and between agents and the environment. Swarm robotics takes its inspiration from biology, in particular social insects, therefore, it exhibits many functional properties including flexibility, robustness, decentralization, self-organization, etc., which are desirable properties required in many wide-ranging potential applications.
Swarm robotics is a novel approach to the coordination of large number of robots. Researchers typically focus on one problem domain to study the underlying properties of system. This dissertation focuses on the problem of collective construction which is concerned with the building of a geometric structure with a collection of robots working in parallel, without centralized control. Robots in the swarm have to coordinate their building activities both in space and time such that a consistent structure can be achieved. For a given structure, how the robot can be designed such that the given structure can be built is still an open question in swarm robotics. Although it has drawn increasing attention over the last decade and many achievements have been made, swarm robotics is still a brand new research field and no systematic theoretical methodology has been established. This dissertation focuses on the coordination mechanisms involved in collective construction. The main works and contributions are summarized as follows:
(1) Inspired by honeybee visual navigation behavior, a visual template mechanism is proposed in which a natural landmark serves as a visual reference or template for distance determination as well as for navigation during collective construction. This mechanism can make use of an interesting landmark, reference point or salient object in the construction environment which allows for robots manipulating homogeneous bricks in a non-communicative way. Therefore, such a mechanism has an obvious appeal to those researching collective construction for applications in unknown environments.
(2) The visual template mechanism allows the robots to finish simple construction tasks. But when it comes to a more complicated task, robots would become complex. Complexity refers to the hardware and software complexity of the robots. Aiming at the drawbacks of the visual template mechanism, a spatio-temporal varying template mechanism is proposed which uses the robot itself as a template without referring to the outside world. This self-generated template varies spatially and temporally when the robot varies in position. This means the various moving pattern of the robot makes a variety of template patterns. This mechanism is a more general mechanism because it is possible for robots to build complex structures. Furthermore, the robot serving as a template is not fixed, and all the other robots could possibly become a template. This role-changing mechanism makes the system less prone to system failure when the individual malfunctions such that the robustness of the system can be increased.
(3) A new spatio-temporal coordination mechanism is proposed in the case of stigmergy-based collective construction. The originality of the work lies in the increase in the capabilities of the construction robot. Endowed with the system state assessment capability, construction robots can collective build the desired structure using only a simple rule set.
(4) A preliminary study of the emergence behavior in collective construction is given in a pheromone-based collective construction system. First the termite's royal chamber construction is studied and then agent-based collective construction model is abstracted and established. This model consists of two parts:one is a dynamic model of the environment and the other is an individual behavior model. Based on this model, several different objective structures are studied and how simple rules give rise to a complex global pattern is also discussed.
引文
[1]C. Fountas. Swarm intelligence:The ant paradigm[M], in Multimedia Services in Intelligent Environments:Software Development Challenges and Solutions, L. C. J. George A. Tsihrintzis, Maria Virvou, Ed. Springer, ch.9,2010:137-157.
[2]G. Beni and J. Wang. Swarm intelligence in cellular robotic systems[C], in NATO Advanced Workshop on Robotics and Biological Systems, Jun.1989.
[3]M. Dorigo and L. M. Gambardella. Ant colony system:a cooperative learning approach to the traveling salesman problem[J], Evolutionary Computation, IEEE Transactions on,1997, 1(1):53-66.
[4]X. Hu, J. Zhang, and Y. Li. Orthogonal methods based ant colony search for solving continuous optimization problems[J], Journal of Computer Science and Technology,2008, 23(1):2-18.
[5]M. Zlochin, M. Birattari, N. Meuleau, and M. Dorigo. Model-based search for combinatorial optimization:A critical survey[J], Annals of Operations Research,2004,131(1-4).
[6]T. Krink and M. Lovbjerg. The lifecycle model:Combining particle swarm optimisation, genetic algorithms and hillclimbers[J], Parallel Problem Solving from Nature VII (PPSN), 2002:621-630.
[7]Z. Xinchao. A perturbed particle swarm algorithm for numerical optimization[J], Appl. Soft Comput.,2010,10(1):119-124.
[8]Z. hui Zhan, J. Zhang, Y. Li, and H. S.-H. Chung. Adaptive particle swarm optimization[J], IEEE Transactions on Systems, Man, and Cybernetics, Part B,2009,39(6):1362-1381.
[9]R. C. Eberhart, Y. Shi, and J. Kennedy. Swarm Intelligence (The Morgan Kaufmann Series in Evolutionary Computation) [M],1st ed. Morgan Kaufmann, Apr.2001.
[10]D. Payton, R. Estkowski, M. Howard. Pheromone Robotics and the Logic of Virtual Pheromones[M], in Swarm Robotics, ser. Lecture Notes in Computer Science, E. Sahin, and W. Spears, Eds. Springer Berlin/Heidelberg,2005,3342:45-57.
[11]S. Berman, Q. Lindsey, M. Sakar, V. Kumar, and S. Pratt. Experimental study and modeling of group retrieval in ants as an approach to collective transport in swarm robotic systems[C], Proceedings of the IEEE,2011,99(9):1470-1481.
[12]L. Bayindir and E. Sahin. Modeling self-organized aggregation in swarm robotic systems[C], in Swarm Intelligence Symposium,2009. SIS'09. IEEE,2009:88-95.
[13]A. H. Purnamadjaja and R. A. Russell. Bi-directional pheromone communication between robots[J], Robotica,2010,28(1):69-79.
[14]C. A. C. Parker and H. Zhang. Biologically inspired collective comparisons by robotic swarms[J], Int. J. Rob. Res.,2011,30:524-535.
[15]E. Sahin, S. Girgin, L. Bayindir, and A. E. Turgut. Swarm robotics[M], in Swarm Intelligence:Introduction and Applications, ser. Natural Computing Series, C. Blum and D. Merkle, Eds. Springer,2008:87-100.
[16]Y. U. Cao, A. S. Fukunaga, and A. Kahng. Cooperative mobile robotics:Antecedents and directions[J], Auton. Robots,1997,4(1):7-27.
[17]E. Bonabeau, M. Dorigo, and G. Theraulaz. Swarm intelligence:from natural to artificial systems[M]. New York, NY, USA:Oxford University Press, Inc.,1999.
[18]E. Bonabeau, G. Theraulza, J.-L. Deneubourg, S. Aron, and S. Camazine. Self-organization in social insects[C], Santa Fe Institute, Working Papers 97-04-032, Apr.1997.
[19]C. R. Kube, C. A. Parker, T. Wang, and H. Zhang. Biologically inspired collective robotics[M], in Recent Developments in Biologically Inspired Computing, L. N. de Castro and F. J. Von Zuben, Eds. New York:Idea Group Publishing, ch. XV,2005:369-397.
[20]E. Bonabeau. From classical models of morphogenesis to agent-based models of pattern formation[J], Artificial Life,1997,3(3):191-211.
[21]C. Parker. Distributed Robotic Construction Without Communication[D], Dept. of Computing Science, University of Alberta,2002.
[22]J. L. Jones and A. M. Flynn. Mobile robots:inspiration to implementation[M], Natick, MA, USA:A. K. Peters, Ltd.,1993.
[23]K. Lerman and A. Galstyan. A general methodology for mathematical analysis of multi-agent systems[C], USC Information Sciences, Tech. Rep.,2001.
[24]K. Lerman. Design and mathematical analysis of agent-based systems[C], in Proceedings of the First International Workshop on Formal Approaches to Agent-Based Systems-Revised Papers, ser.FAABS'00. London, UK:Springer-Verlag,2001:222-234.
[25]R. Brooks. A robust layered control system for a mobile robot[J], IEEE Journal on Robotics and Automation,1986,2(1):14-23.
[26]C. Melhuish, O. Holland, and S. Hoddell. Collective sorting and segregation in robots with minimal sensing[C], in Proceedings of the fifth international conference on simulation of adaptive behavior on From animals to animats 5. Cambridge, MA, USA:MIT Press, 1998:465-470.
[27]R. Beckers, O. E. Holl, J. L. Deneubourg, Z. universitat Bielefeld, and D-Bielefeld. From local actions to global tasks:Stigmergy and collective robotics[M]. MIT Press, 1994:181-189.
[28]J. L. Deneubourg, S. Goss, N. Franks, A. S. Franks, C. Detrain, and L. Chr'etien. The dynamics of collective sorting robot-like ants and ant-like robots[C], in Proceedings of the first international conference on simulation of adaptive behavior on From animals to animats. Cambridge, MA, USA:MIT Press,1991:356-363.
[29]M. Wilson, C. Melhuish, A. B. Sendova-Franks, and S. Scholes. Algorithms for building annular structures with minimalist robots inspired by brood sorting in ant colonies[J], Auton. Robots,2004,17(2-3):115-136.
[30]A. J. Ijspeert, A. Martinoli, A. Billard, and L. M. Gambardella. Collaboration through the exploitation of local interactions in autonomous collective robotics:The stick pulling experiment[J], Auton. Robots,2001,11:149-171.
[31]K. Lerman and A. Galstyan. Mathematical model of foraging in a group of robots:Effect of interference[J], Auton. Robots,2002,13:127-141.
[32]T. H. Labella, M. Dorigo, and J. louis Deneubourg. Efficiency and task allocation in prey retrieval[C], in Proceedings of the First International Workshop on Biologically Inspired Approaches to Advanced Information Technology (Bio-ADIT2004), Lecture Notes in Computer Science. Springer Verlag,2004:32-47.
[33]M. J. Matari'c, Designing and understanding adaptive group behavior[J], Adaptive Behavior, 1995,4(1):51-80.
[34]J. McLurkin and J. Smith. Distributed algorithms for dispersion in indoor environments using a swarm of autonomous mobile robots[C], in Distributed Autonomous Robotic Systems Conference,2004.
[35]D. Payton, M. Daily, R. Estowski, M. Howard, and C. Lee. Pheromone robotics[J], Auton. Robots,2001,11(3):319-324.
[36]N. Franks and J. Deneubourg. Self-organizing nest construction in ants:individual worker behaviour and the nest's dynamics[J], Animal Behaviour,1997,54(4):779-796.
[37]G. Theraulaz and E. Bonabeau. Coordination in distributed building[J], Science,1995, 269(5224):686-688.
[38]C. A. C. Parker, H. Zhang, and C. R. Kube. Blind bulldozing:Multiple robot nest construction[C], in Proc. IEEE/RSJ Int'l Conf. Intelligent Robots and Systems (IROS'03), 2003,2:2010-2015.
[39]G. Theraulaz and E. Bonabeau. Modelling the collective building of complex architectures in social insects with lattice swarms[J], Journal of Theoretical Biology,1995,177(4):381-400.
[40]C. R. Kube and H. Zhang. Collective robotics:from social insects to robots[J], Adapt. Behav.,1993,2(2):189-218.
[41]O. H. Bruinsma. An analysis of building behaviour of the termite macrotermes subhyalinus[D], Landbouwhogeschool te Wageningenbuhl, The Netherlands,1979.
[42]W.-M. Shen, C.-M. Chuong, and P. Will. Simulating self-organization for multi-robot systems[C], Switzerland,2002:2776-2781.
[43]R. Mayet, J. Roberz, T. Schmickl, and K. Crailsheim. Antbots:A Feasible Visual Emulation of Pheromone Trails for Swarm Robots[M], in Swarm Intelligence, Springer,2010, 6234:84-94.
[44]R. Russell. Heat trails as short-lived navigational markers for mobile robots[C], in Proc. IEEE Int'l Conf. Robotics and Automation,1997,4:3534-3539.
[45]K. Sugawara, T. Kazama, and T. Watanabe. Foraging behavior of interacting robots with virtual pheromone[C], in Proceedings of 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems, Los Alamitos, CA:IEEE Press,2004:3074-3079.
[46]J. L. Pearce, P. E. Rybski, S. A. Stoeter, and N. Papanikolopoulos. Dispersion behaviors for a team of multiple miniature robots[C], in Proc of the IEEE Intl Conf on Robotics and Automation ICRA Taipei Taiwan,2003,1:1158-1163.
[47]G. Theraulaz, J. Gautrais, S. Camazine, and J. L. Deneubourg. The formation of spatial patterns in social insects:from simple behaviours to complex structures[J], Phil. Trans. R. Soc. Lond. A,2003,361 (1807):1263-1282.
[48]C. Melhuish, J. Welsby, and C. Edwards. Using templates for defensive wall building with autonomous mobile ant-like robots[C], in Proc. Towards Intelligent Mobile Robots (TIMR), U. Nehmzow and C. Melhuish, Eds., Mar.1999.
[49]R. L. Stewart and R. A. Russell. Building a loose wall structure with a robotic swarm using a spatio-temporal varying template[C], in Proc. IEEE/RSJ Int'l Conf. Intelligent Robots and Systems (IROS'04),2004:712-716.
[50]R. L. Stewart and R. A. Russell. A distributed feedback mechanism to regulate wall construction by a robotic swarm[J], Adapt. Behav.,2006,14(1):21-51.
[51]G. Theraulaz and E. Bonabeau. A brief history of stigmergy[J], Artificial Life,1999, 5(2):97-116.
[52]Z. Mason. Programming with stigmergy:Using swarms for construction[C], In Artificial Life Ⅵ:Proc. of the Eighth International Conference on Artificial Life. MIT Press, 2002:371-374.
[53]E. Bonabeau, G. Theraulaz, E. Arpin, and E. Sardet. The building behavior of lattice swarms[M], in Artificial Life IV, R. A. Brooks and P. Maes, Eds. MIT Press, Cambridge, MA,1994:307-312.
[54]C. V. Jones and M. J. Matari'c. From local to global behavior in intelligent self-assembly[C], in Proc. IEEE/RSJ Int'l Conf. Intelligent Robots and Systems (IROS'03), Taipei, Taiwan, 2003:721-726.
[55]G. Li and Z. H.. A rectangular partition algorithm for planar selfassembly[C], in Proc. IEEE/RSJ Int'l Conf. Intelligent Robots and Systems (IROS'05), Edmonton, Canada, 2005:2324-2329.
[56]J. Kelly and H. Zhang. Combinatorial optimization of sensing for rule-based planar distributed assembly[C], in Proc. IEEE/RSJ Int'l Conf. Intelligent Robots and Systems (IROS'06), Beijing, China,2006:3728-3734.
[57]J. Wawerla, G. Sukhatme, and M. Matari'c. Collective construction with multiple robots[C], in Proc. IEEE/RSJ Int. Conf. on Intel. Robots and Systems (IROS),2002,3:2696-2701.
[58]J. Werfel, Y. B. Yam, and R. Nagpal. Building patterned structures with robot swarms[C], in IJCAI'05:Proceedings of the 19th international joint conference on Artificial intelligence. San Francisco, CA, USA:Morgan Kaufmann Publishers Inc.,2005:1495-1502.
[59]J. Werfel and R. Nagpal. Three-dimensional construction with mobile robots and modular blocks[J], Int. J. Rob. Res.,2008,27:463-479.
[60]J. Werfel, Y. Bar-Yam, D. Rus, and R. Nagpal. Distributed construction by mobile robots with enhanced building blocks[C], in Proc. IEEE Int. Conf. Robot. Autom. (ICRA), 2006:2787-2794.
[61]J. Werfel, D. E. Ingber, and R. Nagpal. Collective construction of environmentally-adaptive structures[C], in Proc. IEEE/RSJ Int'l Conf. Intelligent Robots and Systems (IROS'06), 2007:2345-2352.
[62]T. S. Collett and M. Collett. Memory use in insect visual navigation[J], Nat. Rev. Neurosci., 2002,3(7):542-552.
[63]T. S. Collett, P. Graham, and V. Durier. Route learning by insects[J], Curr. Opin. Neurobiol., 2003,13(6):718-725.
[64]S. N. Fry and R. Wehner. Look and turn:landmark-based goal navigation in honey bees[J], J. Exp. Biol.,2005,208(20):3945-3955.
[65]R. I. Hartley and A. Zisserman. Multiple View Geometry in Computer Vision[M],2nd ed. Cambridge Univ. Press, Apr.2004.
[66]S. Camazine, N. R. Franks, J. Sneyd, E. Bonabeau, J.-L. Deneubourg and G. Theraulaz. Self-Organization in Biological Systems[M]. Princeton, NJ, USA:Princeton Univ. Press, 2001.
[67]T.G. Howsman, D. O'Neil and M.A.K. L. Craft. A stigmergic cooperative multi-robot control architecture[M], In Artificial life Ⅸ:Proceedings of the 9th International Conference on the Simulation and Synthesis of Living Systems, J. Pollack, M. Bedau, P. Husbands, T. Ikegami,& R. A. Watson (Eds.), Massachusetts:MIT Press, Cambridge, MA, USA, 2004:88-93.
[68]R. L. Stewart. A stigmergy rule set compiler for collective construction using the distance transform[C], in Proceedings of the 22nd IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) Workshop on Biologically-Inspired Robotics, St. Louis, MO, USA, Oct 2009.
[69]M. Dorigo. Ant colony optimization:A new meta-heuristic[C], in Proceedings of the Congress on Evolutionary Computation. IEEE Press,1999:1470-1477.
[70]T. Stutzle and H. H. Hoos. Max-min ant system and local search for combinatorial optimization problems[M], in Meta-Heuristics:Advances and trends in local search paradigms for optimization. Hrsg.:S. Voss (u.a.)-Boston (u.a.):Kluwer,1998. S.137-154.
[71]W. Gutjahr. S-ACO:An Ant-Based Approach to Combinatorial Optimization under Uncertainty[C], in Proceedings of ANTS 2004-Fourth International Workshop on Ant Colony Optimization and Swarm Intelligence, ser. Lecture Notes in Computer Science, M. Dorigo, M Birattari, C. Blum, L. Gambardella, F. Mondada, and T. Stutzle, Eds., Brussels, Belgium:Springer Verlag,2004,3172:238-249.
[72]T. N. Bui, T. H. Nguyen, C. M. Patel, and K.-A. T. Phan. An antbased algorithm for coloring graphs[J], Discrete Applied Mathematics,2008,156(2):190-200.
[73]C. D. and A. Hertz. Ants can colour graphs[J], Journal of the Operational Research Society, 1997,48:295-305.
[74]C. Coello Coello and A. Hern'andez Aguirre. Automated design of combinational logic circuits using the ant system[J], Engineering Optimization,2002,34(2):109-127.
[75]R. Schoonderwoerd, J. L. Bruten, O. E. Holland, and L. J. M. Rothkrantz. Ant-based load balancing in telecommunications networks[J], Adapt. Behav.,1996,5(2):169-207.
[76]G. D. Caro and M. Dorigo. Antnet:Distributed stigmergetic control for communications networks[J], Journal of Artificial Intelligence Research,1998.
[77]G. A. Di Caro and M. Dorigo. Two ant colony algorithms for best effort routing in datagram networks[C], in Proceedings of the Tenth IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS'98). IASTED/ACTA Press,1998:541-546.
[78]K. M. Sim and W. H. Sun. Ant colony optimization for routing and load-balancing:survey and new directions[J], IEEE Transactions on Systems, Man, and Cybernetics, Part A,2003, 33(5):560-572.
[79]K. M. Sim and W. H. Sun. Multiple ant colony optimization for load balancing[C], in Intelligent Data Engineering and Automated Learning,4th International Conference, IDEAL 2003, Hong Kong, China, Revised Papers, ser. Lecture Notes in Computer Science, J. Liu, Y.-m. Cheung, and H. Yin, Eds.,2003,2690:467-471.
[80]I. Ellabib, O. A. Basir and P. Calamai. An experimental study of a simple ant colony system for the vehicle routing problem with time windows[C], in Proceedings of the Third International Workshop on Ant Algorithms, ser. ANTS '02. London, UK, UK: Springer-Verlag,2002:53-64.
[81]L. M. Gambardella, E. Taillard, and G. Agazzi. New ideas in optimization[M], D. Corne, M. Dorigo, F. Glover, D. Dasgupta, P. Moscato, R. Poli, and K. V. Price, Eds. Maidenhead, UK, England:McGraw-Hill Ltd., UK, ch. MACSVRPTW:a multiple ant colony system for vehicle routing problems with time windows,1999:63-76.
[82]L. Panait and S. Luke. A pheromone-based utility model for collaborative foraging[C], in Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, ser. AAMAS '04. Washington, DC, USA:IEEE Computer Society, 2004,1:36-43.
[83]W. min Shen, B. Salemi, and P. Will. Hormone-inspired adaptive communication and distributed control for conro self-reconfigurable robots[J], IEEE Transactions on Robotics and Automation,2002,18:700-712.
[84]E. Bonabeau, G. Theraulaz, J. L. Deneubourg, N. R. Franks, O. Rafelsberger, J. L. Joly, and S. Blanco. A model for the emergence of pillars, walls and royal chambers in termite nests[J], Phil. Trans. R. Soc. Lond. B,1998,353(1375):1561-1576.
[85]D. Ladley and S. Bullock. The role of logistic constraints in termite construction of chambers and tunnels[J], Journal of Theoretical Biology,2005,234(4):551-564.
[86]C. Hirsch.E. Numerical computation of internal and external flows, Vol.1:Fundamentals of numerical discretization[M], ser. Wiley series in numerical methods in engineering, Wiley, 1988.
[2]G. Beni and J. Wang. Swarm intelligence in cellular robotic systems[C], in NATO Advanced Workshop on Robotics and Biological Systems, Jun.1989.
[3]M. Dorigo and L. M. Gambardella. Ant colony system:a cooperative learning approach to the traveling salesman problem[J], Evolutionary Computation, IEEE Transactions on,1997, 1(1):53-66.
[4]X. Hu, J. Zhang, and Y. Li. Orthogonal methods based ant colony search for solving continuous optimization problems[J], Journal of Computer Science and Technology,2008, 23(1):2-18.
[5]M. Zlochin, M. Birattari, N. Meuleau, and M. Dorigo. Model-based search for combinatorial optimization:A critical survey[J], Annals of Operations Research,2004,131(1-4).
[6]T. Krink and M. Lovbjerg. The lifecycle model:Combining particle swarm optimisation, genetic algorithms and hillclimbers[J], Parallel Problem Solving from Nature VII (PPSN), 2002:621-630.
[7]Z. Xinchao. A perturbed particle swarm algorithm for numerical optimization[J], Appl. Soft Comput.,2010,10(1):119-124.
[8]Z. hui Zhan, J. Zhang, Y. Li, and H. S.-H. Chung. Adaptive particle swarm optimization[J], IEEE Transactions on Systems, Man, and Cybernetics, Part B,2009,39(6):1362-1381.
[9]R. C. Eberhart, Y. Shi, and J. Kennedy. Swarm Intelligence (The Morgan Kaufmann Series in Evolutionary Computation) [M],1st ed. Morgan Kaufmann, Apr.2001.
[10]D. Payton, R. Estkowski, M. Howard. Pheromone Robotics and the Logic of Virtual Pheromones[M], in Swarm Robotics, ser. Lecture Notes in Computer Science, E. Sahin, and W. Spears, Eds. Springer Berlin/Heidelberg,2005,3342:45-57.
[11]S. Berman, Q. Lindsey, M. Sakar, V. Kumar, and S. Pratt. Experimental study and modeling of group retrieval in ants as an approach to collective transport in swarm robotic systems[C], Proceedings of the IEEE,2011,99(9):1470-1481.
[12]L. Bayindir and E. Sahin. Modeling self-organized aggregation in swarm robotic systems[C], in Swarm Intelligence Symposium,2009. SIS'09. IEEE,2009:88-95.
[13]A. H. Purnamadjaja and R. A. Russell. Bi-directional pheromone communication between robots[J], Robotica,2010,28(1):69-79.
[14]C. A. C. Parker and H. Zhang. Biologically inspired collective comparisons by robotic swarms[J], Int. J. Rob. Res.,2011,30:524-535.
[15]E. Sahin, S. Girgin, L. Bayindir, and A. E. Turgut. Swarm robotics[M], in Swarm Intelligence:Introduction and Applications, ser. Natural Computing Series, C. Blum and D. Merkle, Eds. Springer,2008:87-100.
[16]Y. U. Cao, A. S. Fukunaga, and A. Kahng. Cooperative mobile robotics:Antecedents and directions[J], Auton. Robots,1997,4(1):7-27.
[17]E. Bonabeau, M. Dorigo, and G. Theraulaz. Swarm intelligence:from natural to artificial systems[M]. New York, NY, USA:Oxford University Press, Inc.,1999.
[18]E. Bonabeau, G. Theraulza, J.-L. Deneubourg, S. Aron, and S. Camazine. Self-organization in social insects[C], Santa Fe Institute, Working Papers 97-04-032, Apr.1997.
[19]C. R. Kube, C. A. Parker, T. Wang, and H. Zhang. Biologically inspired collective robotics[M], in Recent Developments in Biologically Inspired Computing, L. N. de Castro and F. J. Von Zuben, Eds. New York:Idea Group Publishing, ch. XV,2005:369-397.
[20]E. Bonabeau. From classical models of morphogenesis to agent-based models of pattern formation[J], Artificial Life,1997,3(3):191-211.
[21]C. Parker. Distributed Robotic Construction Without Communication[D], Dept. of Computing Science, University of Alberta,2002.
[22]J. L. Jones and A. M. Flynn. Mobile robots:inspiration to implementation[M], Natick, MA, USA:A. K. Peters, Ltd.,1993.
[23]K. Lerman and A. Galstyan. A general methodology for mathematical analysis of multi-agent systems[C], USC Information Sciences, Tech. Rep.,2001.
[24]K. Lerman. Design and mathematical analysis of agent-based systems[C], in Proceedings of the First International Workshop on Formal Approaches to Agent-Based Systems-Revised Papers, ser.FAABS'00. London, UK:Springer-Verlag,2001:222-234.
[25]R. Brooks. A robust layered control system for a mobile robot[J], IEEE Journal on Robotics and Automation,1986,2(1):14-23.
[26]C. Melhuish, O. Holland, and S. Hoddell. Collective sorting and segregation in robots with minimal sensing[C], in Proceedings of the fifth international conference on simulation of adaptive behavior on From animals to animats 5. Cambridge, MA, USA:MIT Press, 1998:465-470.
[27]R. Beckers, O. E. Holl, J. L. Deneubourg, Z. universitat Bielefeld, and D-Bielefeld. From local actions to global tasks:Stigmergy and collective robotics[M]. MIT Press, 1994:181-189.
[28]J. L. Deneubourg, S. Goss, N. Franks, A. S. Franks, C. Detrain, and L. Chr'etien. The dynamics of collective sorting robot-like ants and ant-like robots[C], in Proceedings of the first international conference on simulation of adaptive behavior on From animals to animats. Cambridge, MA, USA:MIT Press,1991:356-363.
[29]M. Wilson, C. Melhuish, A. B. Sendova-Franks, and S. Scholes. Algorithms for building annular structures with minimalist robots inspired by brood sorting in ant colonies[J], Auton. Robots,2004,17(2-3):115-136.
[30]A. J. Ijspeert, A. Martinoli, A. Billard, and L. M. Gambardella. Collaboration through the exploitation of local interactions in autonomous collective robotics:The stick pulling experiment[J], Auton. Robots,2001,11:149-171.
[31]K. Lerman and A. Galstyan. Mathematical model of foraging in a group of robots:Effect of interference[J], Auton. Robots,2002,13:127-141.
[32]T. H. Labella, M. Dorigo, and J. louis Deneubourg. Efficiency and task allocation in prey retrieval[C], in Proceedings of the First International Workshop on Biologically Inspired Approaches to Advanced Information Technology (Bio-ADIT2004), Lecture Notes in Computer Science. Springer Verlag,2004:32-47.
[33]M. J. Matari'c, Designing and understanding adaptive group behavior[J], Adaptive Behavior, 1995,4(1):51-80.
[34]J. McLurkin and J. Smith. Distributed algorithms for dispersion in indoor environments using a swarm of autonomous mobile robots[C], in Distributed Autonomous Robotic Systems Conference,2004.
[35]D. Payton, M. Daily, R. Estowski, M. Howard, and C. Lee. Pheromone robotics[J], Auton. Robots,2001,11(3):319-324.
[36]N. Franks and J. Deneubourg. Self-organizing nest construction in ants:individual worker behaviour and the nest's dynamics[J], Animal Behaviour,1997,54(4):779-796.
[37]G. Theraulaz and E. Bonabeau. Coordination in distributed building[J], Science,1995, 269(5224):686-688.
[38]C. A. C. Parker, H. Zhang, and C. R. Kube. Blind bulldozing:Multiple robot nest construction[C], in Proc. IEEE/RSJ Int'l Conf. Intelligent Robots and Systems (IROS'03), 2003,2:2010-2015.
[39]G. Theraulaz and E. Bonabeau. Modelling the collective building of complex architectures in social insects with lattice swarms[J], Journal of Theoretical Biology,1995,177(4):381-400.
[40]C. R. Kube and H. Zhang. Collective robotics:from social insects to robots[J], Adapt. Behav.,1993,2(2):189-218.
[41]O. H. Bruinsma. An analysis of building behaviour of the termite macrotermes subhyalinus[D], Landbouwhogeschool te Wageningenbuhl, The Netherlands,1979.
[42]W.-M. Shen, C.-M. Chuong, and P. Will. Simulating self-organization for multi-robot systems[C], Switzerland,2002:2776-2781.
[43]R. Mayet, J. Roberz, T. Schmickl, and K. Crailsheim. Antbots:A Feasible Visual Emulation of Pheromone Trails for Swarm Robots[M], in Swarm Intelligence, Springer,2010, 6234:84-94.
[44]R. Russell. Heat trails as short-lived navigational markers for mobile robots[C], in Proc. IEEE Int'l Conf. Robotics and Automation,1997,4:3534-3539.
[45]K. Sugawara, T. Kazama, and T. Watanabe. Foraging behavior of interacting robots with virtual pheromone[C], in Proceedings of 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems, Los Alamitos, CA:IEEE Press,2004:3074-3079.
[46]J. L. Pearce, P. E. Rybski, S. A. Stoeter, and N. Papanikolopoulos. Dispersion behaviors for a team of multiple miniature robots[C], in Proc of the IEEE Intl Conf on Robotics and Automation ICRA Taipei Taiwan,2003,1:1158-1163.
[47]G. Theraulaz, J. Gautrais, S. Camazine, and J. L. Deneubourg. The formation of spatial patterns in social insects:from simple behaviours to complex structures[J], Phil. Trans. R. Soc. Lond. A,2003,361 (1807):1263-1282.
[48]C. Melhuish, J. Welsby, and C. Edwards. Using templates for defensive wall building with autonomous mobile ant-like robots[C], in Proc. Towards Intelligent Mobile Robots (TIMR), U. Nehmzow and C. Melhuish, Eds., Mar.1999.
[49]R. L. Stewart and R. A. Russell. Building a loose wall structure with a robotic swarm using a spatio-temporal varying template[C], in Proc. IEEE/RSJ Int'l Conf. Intelligent Robots and Systems (IROS'04),2004:712-716.
[50]R. L. Stewart and R. A. Russell. A distributed feedback mechanism to regulate wall construction by a robotic swarm[J], Adapt. Behav.,2006,14(1):21-51.
[51]G. Theraulaz and E. Bonabeau. A brief history of stigmergy[J], Artificial Life,1999, 5(2):97-116.
[52]Z. Mason. Programming with stigmergy:Using swarms for construction[C], In Artificial Life Ⅵ:Proc. of the Eighth International Conference on Artificial Life. MIT Press, 2002:371-374.
[53]E. Bonabeau, G. Theraulaz, E. Arpin, and E. Sardet. The building behavior of lattice swarms[M], in Artificial Life IV, R. A. Brooks and P. Maes, Eds. MIT Press, Cambridge, MA,1994:307-312.
[54]C. V. Jones and M. J. Matari'c. From local to global behavior in intelligent self-assembly[C], in Proc. IEEE/RSJ Int'l Conf. Intelligent Robots and Systems (IROS'03), Taipei, Taiwan, 2003:721-726.
[55]G. Li and Z. H.. A rectangular partition algorithm for planar selfassembly[C], in Proc. IEEE/RSJ Int'l Conf. Intelligent Robots and Systems (IROS'05), Edmonton, Canada, 2005:2324-2329.
[56]J. Kelly and H. Zhang. Combinatorial optimization of sensing for rule-based planar distributed assembly[C], in Proc. IEEE/RSJ Int'l Conf. Intelligent Robots and Systems (IROS'06), Beijing, China,2006:3728-3734.
[57]J. Wawerla, G. Sukhatme, and M. Matari'c. Collective construction with multiple robots[C], in Proc. IEEE/RSJ Int. Conf. on Intel. Robots and Systems (IROS),2002,3:2696-2701.
[58]J. Werfel, Y. B. Yam, and R. Nagpal. Building patterned structures with robot swarms[C], in IJCAI'05:Proceedings of the 19th international joint conference on Artificial intelligence. San Francisco, CA, USA:Morgan Kaufmann Publishers Inc.,2005:1495-1502.
[59]J. Werfel and R. Nagpal. Three-dimensional construction with mobile robots and modular blocks[J], Int. J. Rob. Res.,2008,27:463-479.
[60]J. Werfel, Y. Bar-Yam, D. Rus, and R. Nagpal. Distributed construction by mobile robots with enhanced building blocks[C], in Proc. IEEE Int. Conf. Robot. Autom. (ICRA), 2006:2787-2794.
[61]J. Werfel, D. E. Ingber, and R. Nagpal. Collective construction of environmentally-adaptive structures[C], in Proc. IEEE/RSJ Int'l Conf. Intelligent Robots and Systems (IROS'06), 2007:2345-2352.
[62]T. S. Collett and M. Collett. Memory use in insect visual navigation[J], Nat. Rev. Neurosci., 2002,3(7):542-552.
[63]T. S. Collett, P. Graham, and V. Durier. Route learning by insects[J], Curr. Opin. Neurobiol., 2003,13(6):718-725.
[64]S. N. Fry and R. Wehner. Look and turn:landmark-based goal navigation in honey bees[J], J. Exp. Biol.,2005,208(20):3945-3955.
[65]R. I. Hartley and A. Zisserman. Multiple View Geometry in Computer Vision[M],2nd ed. Cambridge Univ. Press, Apr.2004.
[66]S. Camazine, N. R. Franks, J. Sneyd, E. Bonabeau, J.-L. Deneubourg and G. Theraulaz. Self-Organization in Biological Systems[M]. Princeton, NJ, USA:Princeton Univ. Press, 2001.
[67]T.G. Howsman, D. O'Neil and M.A.K. L. Craft. A stigmergic cooperative multi-robot control architecture[M], In Artificial life Ⅸ:Proceedings of the 9th International Conference on the Simulation and Synthesis of Living Systems, J. Pollack, M. Bedau, P. Husbands, T. Ikegami,& R. A. Watson (Eds.), Massachusetts:MIT Press, Cambridge, MA, USA, 2004:88-93.
[68]R. L. Stewart. A stigmergy rule set compiler for collective construction using the distance transform[C], in Proceedings of the 22nd IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) Workshop on Biologically-Inspired Robotics, St. Louis, MO, USA, Oct 2009.
[69]M. Dorigo. Ant colony optimization:A new meta-heuristic[C], in Proceedings of the Congress on Evolutionary Computation. IEEE Press,1999:1470-1477.
[70]T. Stutzle and H. H. Hoos. Max-min ant system and local search for combinatorial optimization problems[M], in Meta-Heuristics:Advances and trends in local search paradigms for optimization. Hrsg.:S. Voss (u.a.)-Boston (u.a.):Kluwer,1998. S.137-154.
[71]W. Gutjahr. S-ACO:An Ant-Based Approach to Combinatorial Optimization under Uncertainty[C], in Proceedings of ANTS 2004-Fourth International Workshop on Ant Colony Optimization and Swarm Intelligence, ser. Lecture Notes in Computer Science, M. Dorigo, M Birattari, C. Blum, L. Gambardella, F. Mondada, and T. Stutzle, Eds., Brussels, Belgium:Springer Verlag,2004,3172:238-249.
[72]T. N. Bui, T. H. Nguyen, C. M. Patel, and K.-A. T. Phan. An antbased algorithm for coloring graphs[J], Discrete Applied Mathematics,2008,156(2):190-200.
[73]C. D. and A. Hertz. Ants can colour graphs[J], Journal of the Operational Research Society, 1997,48:295-305.
[74]C. Coello Coello and A. Hern'andez Aguirre. Automated design of combinational logic circuits using the ant system[J], Engineering Optimization,2002,34(2):109-127.
[75]R. Schoonderwoerd, J. L. Bruten, O. E. Holland, and L. J. M. Rothkrantz. Ant-based load balancing in telecommunications networks[J], Adapt. Behav.,1996,5(2):169-207.
[76]G. D. Caro and M. Dorigo. Antnet:Distributed stigmergetic control for communications networks[J], Journal of Artificial Intelligence Research,1998.
[77]G. A. Di Caro and M. Dorigo. Two ant colony algorithms for best effort routing in datagram networks[C], in Proceedings of the Tenth IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS'98). IASTED/ACTA Press,1998:541-546.
[78]K. M. Sim and W. H. Sun. Ant colony optimization for routing and load-balancing:survey and new directions[J], IEEE Transactions on Systems, Man, and Cybernetics, Part A,2003, 33(5):560-572.
[79]K. M. Sim and W. H. Sun. Multiple ant colony optimization for load balancing[C], in Intelligent Data Engineering and Automated Learning,4th International Conference, IDEAL 2003, Hong Kong, China, Revised Papers, ser. Lecture Notes in Computer Science, J. Liu, Y.-m. Cheung, and H. Yin, Eds.,2003,2690:467-471.
[80]I. Ellabib, O. A. Basir and P. Calamai. An experimental study of a simple ant colony system for the vehicle routing problem with time windows[C], in Proceedings of the Third International Workshop on Ant Algorithms, ser. ANTS '02. London, UK, UK: Springer-Verlag,2002:53-64.
[81]L. M. Gambardella, E. Taillard, and G. Agazzi. New ideas in optimization[M], D. Corne, M. Dorigo, F. Glover, D. Dasgupta, P. Moscato, R. Poli, and K. V. Price, Eds. Maidenhead, UK, England:McGraw-Hill Ltd., UK, ch. MACSVRPTW:a multiple ant colony system for vehicle routing problems with time windows,1999:63-76.
[82]L. Panait and S. Luke. A pheromone-based utility model for collaborative foraging[C], in Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, ser. AAMAS '04. Washington, DC, USA:IEEE Computer Society, 2004,1:36-43.
[83]W. min Shen, B. Salemi, and P. Will. Hormone-inspired adaptive communication and distributed control for conro self-reconfigurable robots[J], IEEE Transactions on Robotics and Automation,2002,18:700-712.
[84]E. Bonabeau, G. Theraulaz, J. L. Deneubourg, N. R. Franks, O. Rafelsberger, J. L. Joly, and S. Blanco. A model for the emergence of pillars, walls and royal chambers in termite nests[J], Phil. Trans. R. Soc. Lond. B,1998,353(1375):1561-1576.
[85]D. Ladley and S. Bullock. The role of logistic constraints in termite construction of chambers and tunnels[J], Journal of Theoretical Biology,2005,234(4):551-564.
[86]C. Hirsch.E. Numerical computation of internal and external flows, Vol.1:Fundamentals of numerical discretization[M], ser. Wiley series in numerical methods in engineering, Wiley, 1988.