Collective Self-assembly Model on Three Dimensional Grid Space
-
摘要: 对三维网格空间上的自组装模型进行了较为深入的研究,提出了仅依赖局部信息的两个约束条件, 从理论上严格证明了这两条约束是确保组装结构侧面连通性的充分必要条件. 并进一步指出,对于任意侧面连通结构,均可通过满足上述约束的组装规则组装而成. 对Agent的状态及行动进行了规定,采用冲突等待的策略有效地解决了并行组装时 "死锁"现象的产生, 同时,制定了组装点选择策略,以减少中间结构中"孔道"产生,一定程度上提高了组装效率. 通过实验对本文提出的组装模型及组装过程中Agent状态变化特征进行了验证.Abstract: We deeply studied the self-assembly model on 3D grid space and proposed two constraints which only depend on local information. These two constraints were strictly proved in theory to be the sufficient and necessary condition for the connectivity of the assembly structure side. Furthermore, any side-connective structure can be assembled by the assembling rules which satisfy the above constraints. We defined the state and behavior of the agent, and the "deadlock" during parallel assembly was effectively avoided by taking the collision delay strategy. Meanwhile, the assembly point selecting strategy was formulated so as to reduce the generation of "pore canal" in the intermediate structure, which improves the assembly efficiency to a certain extent. The assembly model proposed in this paper and the variation features of the agent state during the assembly process were verified by experiment.
-
Key words:
- Self-organization /
- swarm intelligence /
- multi-agent system /
- parallel
-
[1] Mason Z. Programming with stigmergy: using swarms for construction. In: Proceedings of the 8th international conference on Artificial Life VIII. Cambridge, MA: MIT Press, 2002. 371-374[2] Parker C A C, Zhang H, Kube C R. Blind bulldozing: multiple robot nest construction. In: Proceedings of the 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems. Las Vegas, USA: IEEE, 2003. 2010-2015[3] Guo Y, Poulton G, Valencia P, James G. Designing self-assembly for 2-dimensional building blocks.Guo Y, Poulton G, Valencia P, James G. Designing self-assembly for 2-dimensional building blocks. 14-18 July 2003, Melbourne, Australia; In: Proceedings of the 2th International Joint Conference on Autonomous Agents and Multi-Agent Systems. Berlin: Springer, 2003. 75-89[4] Werfel J, Nagpal R. Three-dimensional construction with mobile robots and modular blocks. International Journal of Robotics Research, 2008, 27(3-4): 463-479[5] Petersen K, Nagpal R, Werfel J. TERMES: an autonomous robotic system for three-dimensional collective construction. Robotics: Science and Systems Conference, 2011, VII: 249-251[6] Bowyer A. Automated Construction Using Co-operating Biomimetic Robots. Technical Report 11/00, University of Bath Department of Mechanical Engineering, Bath, UK, 2000, 89-116[7] Gardelli L, Viroli M, Omicini A. Design patterns for self-organizing multiagent systems. In: Proceedings of the 2nd International Workshop on Engineering Emergence in Decentralised Autonomic Systems (EEDAS 2007). University of Greenwich: CMS Press, 2007, 61-70[8] Serugendo G D M, Gleizes M P, Karageorgos A. Self-organisation and emergence in MAS: an overview. Informatica, 2006, 30(1): 45-54[9] Prokopenko M, Rajah P M, Wang P. On convergence of dynamic cluster formation in multi-agent networks. In: Proceedings of the 8th European Conference on Advances in Artificial Life. Berlin: Springer-Verlag, 2005. 884-894[10] Yamins D, Nagpal R. Automated global-to-local programming in 1-D spatial multi-agent systems. In: Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems, 2008. 615-622[11] Yu C H, Nagpal R. A self-adaptive framework for modular robots in a dynamic environment: theory and applications. International Journal of Robotics Research, 2010, 30(8): 1015-1036[12] Lacko P, Kvasnicka V, Pospíchal J. An emergence of game strategy in multiagent systems. International Journal of Computational Intelligence and Applications, 2004, 4(3): 283-298[13] Karuna H, Valckenaers P, Saint-Germain B, Verstraete P, Zamfrescu C B, Van Brussels H. Emergent forecasting using a stigmergy approach in manufacturing coordination and control. In: Proceedings of the 3rd International Joint Conference on Autonomous Agents and Multi-Agent Systems. Berlin: Springer, 2005. 210-226[14] Werfel J. Building blocks for multi-agent construction. In: Proceedings of Distributed Autonomous Robotic Systems (DARS2004). Toulouse, France, 2004. 275-281[15] Werfel J, Bar-Yam Y, Nagpal R. Building patterned structures with robot swarms. In: Proceedings of the 19th International Joint Conference on Artificial Intelligence. San Francisco, CA: Morgan Kaufmann Publishers Inc., 2005. 1495-1502[16] Werfel J, Nagpal R. Extended stigmergy in collective construction. IEEE Intelligent Systems, 2006, 21(2): 20-28[17] Werfel J, Bar-Yam Y, Rus D, Nagpal R. Distributed construction by mobile robots with enhanced building blocks. In: Proceedings of the 2006 IEEE International Conference on Robotics and Automation. Orlando, USA: IEEE, 2006. 2787-2794[18] Werfel J, Ingber D, Nagpal R. Collective construction of environmentally-adaptive structures. In: Proceedings of the 2007 IEEE/RSJ International Conference on Intelligent Robots and Systems. San Diego, CA: IEEE, 2007. 2345- 2352
点击查看大图
计量
- 文章访问数: 1836
- HTML全文浏览量: 76
- PDF下载量: 830
- 被引次数: 0