Emergent behaviors in social networks of adaptive agents. (English) Zbl 1264.91106

Leon, Florin

Math. Probl. Eng. 2012, Article ID 857512, 19 p. (2012).

Summary: Designing multiagent systems that can exhibit coherent group behavior based on a small number of simple rules is a very challenging problem. The evolution of mobile computing environments has created a need for adaptive, robust systems, whose components should be able to cooperate in order to solve the tasks continuously received from users or other software agents. In this paper, an interaction protocol for a task allocation system is proposed, which can reveal the formation of social networks as an emergent property. The agents can improve their solving ability by learning and can collaborate with their peers to deal with more difficult tasks. The experiments show that the evolution of the social networks is similar under a great variety of settings and depends only on the dynamism of the environment. The average number of connections and resources of the agents follows a power law distribution. Different configurations are studied in order to find the optimal set of parameters that leads to the maximum overall efficiency of the multiagent system.

MSC:

91D30	Social networks; opinion dynamics
68T42	Agent technology and artificial intelligence
68M10	Network design and communication in computer systems

References:

[1]	C. Lucas, “Self-organizing systems: frequently asked questions,” Version 3, September 2008, http://www.calresco.org/sos/sosfaq.htm.
[2]	J. M. E. Gabbai, H. Yin, W. A. Wright, and N. M. Allinson, “Self-organization, emergence and multi-agent systems,” in Proceedings of the IEEE International Conference on Neural Networks and Brain Proceedings (ICNN&B ’05), pp. 1858-1863, Beijing, China, October 2005.
[3]	F. Heylighen, “Knowledge Management, Organizational Intelligence and Learning, and Complexity,” in The Encyclopedia of Life Support Systems, L. D. Kiel, Ed., Eolss Publishers, Oxford, 2001. · Zbl 0990.68137
[4]	P. Glansdorff and I. Prigogine, Thermodynamic Study of Structure, Stability and Fluctuations, Wiley, 1971. · Zbl 0246.73005
[5]	N. S. Contractor and D. R. Seibold, “Theoretical frameworks for the study of structuring processes in group decision support system-adaptive structuration theory and self-organising systems theory,” Human Communication Research, vol. 19, no. 4, pp. 528-563, 1993.
[6]	C. Bernon, V. Chevrier, V. Hilaire, and P. Marrow, “Applications of self-organising multi-agent systems: an initial framework for comparison,” Informatica, vol. 30, no. 1, pp. 73-82, 2006.
[7]	F. Wang, “Self-organising communities formed by middle agents,” in Proceedings of the 1st International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS ’02), pp. 1333-1339, Bologna, Italy, July 2002.
[8]	G. Picard, C. Bernon, and M. P. Gleizes, “ETTO: emergent timetabling by cooperative self-organisation,” in Proceedings of the 3rd International Workshop on Engineering Self-Organising Applications (ESOA ’05), pp. 31-45, Utrecht, The Netherlands, 2005.
[9]	J. P. Georgé, M. P. Gleizes, P. Glize, and C. Régis, “Real-time simulation for flood forecast: an adaptive multi-agent system STAFF,” in Proceedings of the Symposium on Adaptive Agents and Multi-Agent Systems (AISB ’03), pp. 7-11, University of Wales, Aberystwyth, UK, 2003.
[10]	A. Dury, F. Le Ber, and V. Chevrier, “A reactive approach for solving constraint satisfaction problems: assigning land use to farming territories,” in Intelligent Agents V Agents Theories, Architectures and Languages, J. P. Muller, M. P. Singh, and A. S. Rao, Eds., vol. 1555 of Lecture Notes in Artificial Intelligence, pp. 397-412, Springer, 1998.
[11]	S. Rodriguez, V. Hilaire, and A. Koukam, “Holonic modeling of environments for situated multi-agent systems,” in Proceedings of the 2nd International Workshop on Environments for Multi-Agent Systems (E4MAS ’05), Selected Revised and Invited Papers, pp. 18-31, Utrecht, The Netherlands, 2006.
[12]	M. Gardner, On Cellular Automata, Self-Reproduction, and the Game “Life”, Scientific American, 1971.
[13]	P. Rendell, Turing Universality of the Game of Life, Collision-Based Computing, Springer, London, UK, 2002. · Zbl 1238.68091
[14]	S. Stepney, F. A. C. Polack, and H. R. Turner, “Engineering emergence,” in Proceedings of the 11th IEEE International Conference on Engineering of Complex Computer Systems (ICECCS ’06), pp. 89-97, Stanford, Calif, USA, August 2006.
[15]	E. M. A. Ronald, M. Sipper, and M. S. Capcarrère, “Testing for emergence in artificial life,” in Advances in Artificial Life: 5th European Conference, D. Floreano, J. D. Nicoud, and F. Mondada, Eds., vol. 1674 of Lecture Notes in Artificial Intelligence, pp. 13-20, Springer, Heidelberg, Germany, 1999.
[16]	J. P. Crutchfield, “The calculi of emergence: computation, dynamics, and induction,” Physica D, vol. 75, no. 1-3, pp. 11-54, 1994. · Zbl 0860.68046
[17]	J. Deguet, L. Magnin, and Y. Demazeau, “Emergence and software development based on a survey of emergence definitions,” in Emergent Intelligence of Networked Agents, A. Namatame, S. Kurihara, and H. Nakashima, Eds., vol. 56 of Studies in Computational Intelligence, pp. 13-21, Springer, 2007.
[18]	L. Guo and X. Cai, “The fractal dimensions of complex networks,” Chinese Physics Letters, vol. 26, no. 8, Article ID 088901, 2009.
[19]	E. G. Bakhoum and C. Toma, “Specific mathematical aspects of dynamics generated by coherence functions,” Mathematical Problems in Engineering, vol. 2011, Article ID 436198, 10 pages, 2011. · Zbl 1248.37075
[20]	E. G. Bakhoum and C. Toma, “Dynamical aspects of macroscopic and quantum transitions due to coherence function and time series events,” Mathematical Problems in Engineering, vol. 2010, Article ID 428903, 13 pages, 2010. · Zbl 1191.35219
[21]	F. Leon, S. Curteanu, C. Lisa, and N. Hurduc, “Machine learning methods used to predict the liquid-cristalline behavior of some copolyethers,” Molecular Crystals & Liquid Crystals, vol. 469, pp. 1-22, 2007.
[22]	D. J. Watts and S. H. Strogatz, “Collective dynamics of “small-world” networks,” Nature, vol. 393, no. 6684, pp. 440-442, 1998. · Zbl 1368.05139
[23]	P. Erd\Hos and A. Rényi, “On random graphs: I,” Publicationes Mathematicae Debrecen, vol. 6, pp. 290-297, 1959. · Zbl 0092.15705
[24]	S. Milgram, “The small world problem,” Psychology Today, vol. 2, pp. 60-67, 1967.
[25]	R. Albert, H. Jeong, and A. L. Barabási, “Diameter of the world-wide web,” Nature, vol. 401, no. 6749, pp. 130-131, 1999.
[26]	R. Albert and A. L. Barabási, “Statistical mechanics of complex networks,” Reviews of Modern Physics, vol. 99, no. 3, pp. 7314-7316, 2002.
[27]	M. E. Gaston and M. desJardins, “Social networks and multi-agent organizational performance,” in Proceedings of the 18th International Florida Artificial Intelligence Research Society Conference (FLAIRS ’05), Special Track on AI for Social Networks, Social Networks for AI, Clearwater, Fla, USA, May 2005.
[28]	C. Song, S. Havlin, and H. A. Makse, “Self-similarity of complex networks,” Nature, vol. 433, no. 7024, pp. 392-395, 2005.
[29]	F. Leon, Intelligent Agents with Cognitive Capabilities, Tehnopress, Iasi, Romania, 2006.
[30]	G. Di Marzo Serugendo, M. P. Gleizes, and A. Karageorgos, “Self-organisation and emergence in MAS: an overview,” Informatica, vol. 30, no. 1, pp. 45-54, 2006. · Zbl 1111.68310
[31]	X. Zheng and S. Koenig, “Reaction functions for task allocation to cooperative agents,” in Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems, pp. 559-566, Estoril, Portugal, 2008.
[32]	K. Lerman and O. Shehory, “Coalition formation for large-scale electronic markets,” in Proceedings of the 4th International Conference on Multi-Agent Systems, pp. 167-174, Boston, Mass, USA, 2000.
[33]	M. D. Weerdt, Y. Zhang, and T. Klos, “Distributed task allocation in social networks,” in Proceedings of the 6th Automous Agents and Multiagent Systems, pp. 500-507, Honolulu, Hawaii, USA, 2007.
[34]	D. Ye, Q. Bai, M. Zhang, K. T. Win, and Z. Shen, “An efficient task allocation protocol for P2P multi-agent systems,” in Proceedings of the IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA ’09), pp. 11-18, Chengdu, China, August 2009.
[35]	X. Zheng and S. Koenig, “Greedy approaches for solving task-allocation problems with coalitions,” in Proceedings of the Workshop on Formal Models and Methods for Multi-Robot Systems (AAMAS ’08), pp. 35-40, Estoril, Portugal, 2008.
[36]	A. Campbell and A. S. Wu, “Multi-agent role allocation: issues, approaches, and multiple perspectives,” Autonomous Agents and Multi-Agent Systems, vol. 22, no. 2, pp. 317-355, 2010.
[37]	R. G. Smith, “The contract net protocol: high-level communication and control in a distributed problem solver,” IEEE Transactions on Computers, vol. 29, no. 12, pp. 1104-1113, 1980.