×

Self-organization and multiagent systems. I: Models of multiagent self-organization. (English. Russian original) Zbl 1307.93045

J. Comput. Syst. Sci. Int. 51, No. 2, 256-281 (2012); translation from Izv. Ross. Akad. Nauk, Teor. Sist. Upr. 2012, No. 2, 92-120 (2012).
Summary: Nowadays, there are many problems whose complexity is much higher than the capabilities of modern information technologies. Such problems arise in economics, ecology, managing state-level infrastructures and global computer and telecommunication systems, ensuring the safety of society, and in many other fields. Even though these problems seem to be quite different, they have many common features, which imply common difficulties in their solution. These features are as follows: they are large-scale problems, they are open, have unpredictable dynamics and complex structure, include mobile components, and some others. The management in such systems is a challenging task, which requires a revision of modern views, models, architectures, and development technologies. A response to this challenge is the increasing activity in the field of principles and mechanisms of self-organization and in the software tools for their development. Although the paradigm of self-organizing control systems is not new, it is now at a new step of development, which involves, in particular, its integration with the multiagent system paradigm. The purposes of this paper are to analyze the state-of-the art in the field of multiagent self-organizing systems, to provide a critical review of the available applications, analyze development techniques, and generalize the results obtained in this field. The paper consists of two parts. In the first part, we discuss the modern interpretation of the principles of self-organization is analyzed, and the reasons for which the integration of these principles with the achievements in the field of multiagent systems provides a new impetus to the development of information technologies in the context of most complex modern applications. A systematization and description of the self-organization models and mechanisms implemented in the framework of the multiagent architecture is given, and biological self-organization mechanisms are discussed. Applications of self-organizing multiagent systems in telecommunication, grid resource management, and routing in computer networks with dynamic topology, as well as applications in distributed learning and in detecting intrusions into computer networks are described.
For Part II see [Zbl 1307.93053].

MSC:

93A15 Large-scale systems
68T42 Agent technology and artificial intelligence
93A14 Decentralized systems

Citations:

Zbl 1307.93053

Software:

AntHocNet; AntNet
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Interdisciplinary Program on Application Software towards Exascale Computing for Global Scale Issues // http:www.dfg.de/g8-initiative . Accessed November 11, 2010.
[2] W. R. Ashby, ”Principles of the Self-Organizing Dynamic System,” J. General Psychology, No. 37, 125–128 (1947).
[3] P. P. Grassé, ”La reconstruction du nid et les coordinations interindividuelles chez Bellicositermes natalensis et Cubitermes sp., la théorie de la stigmergie: Essais d’interpretation du comportement des termites constructeurs,” J. Insectes Sociaux 6, 41–84 (1959). · doi:10.1007/BF02223791
[4] Self-Organizing Systems, Ed. by T. N. Sokolov (Mir, Moscow, 1964) [in Russian].
[5] G. Nicolis and I. Prigogine, Self-Organization in Nonequilibrium Systems: From Dissipative Structures to Order through Fluctuations (Wiley, New York, 1977; Mir, Moscow, 1979). · Zbl 0363.93005
[6] A. B. Kazanskii, ”Formalization of Being-with: Bootstrap Systems in Physics, Earth System Science, Cybernetics, and Biology.” http://akazansky.by.ru/Kazansky-alm-2007tab.htm . Accessed November 11, 2010.
[7] C. Bernon, V. Chevrier, V. Hilaire, et al., ”Applications of Self-Organising Multi-Agent Systems: An Initial Framework for Comparison,” Informatica, No. 30, 73–82 (2006).
[8] C. Bernon, V. Camps, M.-P. Gleizes, et al., ”Tools for Self-Organizing Applications Engineering,” in Ser. Lecture Notes in Artificial Intelligence, Ed. by G. Di Marzo Serugendo (Springer, 2004), Vol. 2977, pp. 283–298. · Zbl 1082.68542
[9] T. De Wolf and T. Holvoet, ”Design Patterns for Decentralized Coordination in Self-Organizing Emergent Systems,” in Ser. Lecture Notes in Artificial Intelligence, Ed. by S. Brueckner, G. Di Marzo Serugendo, A. Karageorgos, et al. (Springer, 2005), Vol. 3464, pp. 28–49.
[10] L. Gardelli, M. Viroli, and A. Omicini, ”Design Patterns for Self-Organising Systems,” in Ser. Lecture Notes in Computer Science, Ed. By H.-D. Burkhard, G. Lindemann, R. Verbrugge, et al. (Springer, 2007) Vol. 4696, pp. 123–132.
[11] L. Gardelli, M. Viroli, M. Casade, et al., ”Designing Self-Organising Environments with Agents and Artifacts: A Simulation-Driven Approach,” Int. J. Agent-Oriented Software Eng. 2(2), 254–271 (2007).
[12] L. Gardelli, M. Viroli, M. Casadei, et al., ”Designing Self-Organising MAS Environments: The Collective Sort Case,” in Ser. Lecture Notes in Artificial Intelligence: Environments for Multi-Agent Systems III, Ed. by D. Weyns, H. V. D. Parunak, and F. Michel (Springer, 2006), Vol. 4389, pp. 254–271.
[13] J.-P. Georgé, B. Edmonds, and P. Glizes, ”Making Self-Organizing Adaptive Multi-Agent Systems Work–Towards the Engineering of Emergent Multi-Agent Systems,” in Methodologies and Software Engineering for Agent Systems (Kluwer, Boston, 2004), Chap. 8, pp. 319–338.
[14] M.-P. Gleizes, V. Camps, J-P. Georgé, et al., ”Engineering Systems which Generate Emergent Functionalities,” in Proc. Int. Workshop on Engineering Environment-Mediated Multi-Agent Systems (EEMMAS 2007), Dresden, Germany, 2007, pp. 58–75.
[15] J. Lind, ”Patterns in Agent-Oriented Software Engineering,” in Ser. Lecture Notes in Computer Science, Ed. by F. Giunchiglia, J. Ordell, and G. Weiß (Springer, 2003) Vol. 2585, pp. 47–58 (2003). · Zbl 1018.68737
[16] G. Di Marzo Serugendo, M.-P. Gleizes, and A. Karageorgos, ”Self-Organisation in Multi-Agent Systems,” Rapport de recherche IRIT, No. 2005-18 (Universite Paul Sabatier, Toulouse, 2010). http://www.irit.fr/TFGSO/DOCS/TFG2/TFGIISO-LongReport.pdf . Accessed November 11, 2010.
[17] M. Mamei, R. Menezes, R. Tolksdorf, et al., ”Case Studies for Self-Organization in Computer Science,” J. Syst. Architecture 52, 443–460 (2006). · Zbl 05431919 · doi:10.1016/j.sysarc.2006.02.002
[18] T. De Wolf and T. Holvoet, ”Emergence versus Self-Organisation: Different Concepts but Promising when Combined,” in Ser. Lecture Notes in Artificial Intelligence. Engineering Self-Organizing Systems: Methodologies and Applications, Ed. by S. Brueckner and G. Di Marzo Serugendo, A. Karageorgos, et al. (Springer, 2005), Vol. 3464, pp. 1–15.
[19] A. Omicini and L. Gardelli, Self-Organisation and MAS: An Introduction. http://unibo.lgardelli.com/teaching/2007-selforg-mas.pdf . Accessed November 11, 2010.
[20] G. Di Marzo Serugendo, M.-P. Gleizes, and A. Karageorgos, ”Self-Organization in Multi-Agent Systems,” J. Knowledge Eng. Review 20(2), 165–189 (2005).
[21] G. Di Marzo Serugendo, M.-P. Gleizes, and A. Karageorgos, ”Self-Organisation and Emergence in Multi-Agent Systems: An Overview,” Informatica 30(1), 45–54 (2006). · Zbl 1111.68310
[22] M. Mamei, M. Vasirani, and F. Zambonelli, ”Self-Organizing Spatial Shapes in Mobile Particles: The Tota Approach,” in Proc. Int. Conf. on Engineering Self-Organizing Systems, Methodologies and Applications (ESOA 04), New York, 2004, pp. 138–153.
[23] J.-P. Mano, C. Bourjot, G. Lopardo, et al., ”Bio-Inspired Mechanisms for Artificial Self-Organised Systems,” Informatica 30(1), 55–62 (2006).
[24] K. Tumer and D. Wolpert, ”A Survey of Collectives,” in Collectives and the Design of Complex Systems (Springer, 2004), pp. 1–42. · Zbl 1121.91415
[25] J.-P. Georgé, M.-P. Gleizes, P. Glize, et al., ”Real-Time Simulation for Flood Forecast: An Adaptive Multi-Agent System STAFF,” in Proc. Symp. on Adaptive Agents and Multi-Agent Systems, University of Wales, Aberystwyth, UK, 2003, pp. 7–11.
[26] M. Mamei and F. Zambonelli, ”Motion Coordination in the Quake 3 Area Environment: A Field-Based Approach,” in Ser. Lecture Notes in Computer Science, Ed. by D. Weyns, H. V. D. Parunak, and F. Michel (Springer, 2005) Vol. 3374, pp. 264–278.
[27] M. Mamei, F. Zambonelli, and L. Leonardi, ”Co-Fields: A Physically Inspired Approach to Motion Coordination,” Int. J. IEEE Pervasive Computing 3(2), 52–61 (2004). · Zbl 05099890 · doi:10.1109/MPRV.2004.1316820
[28] A. Chavez and P. Maes, ”Kasbah: An Agent Marketplace for Buying and Selling Goods,” in Proc. First Int. Conf. on the Practical Application of Intelligent Agents and Multi-Agent Technology, London, 1996, pp. 75–90.
[29] K. Fisher, J. P. Mueller, I. Heimig, et al., ”Intelligent Agents in Virtual Enterprises,” in Proc. First Int. Conf. on the Practical Application of Intelligent Agents and Multi-Agent Technology, London, 1996, pp. 205–224.
[30] N. Jennings, P. Paratin, and M. Jonson, ”Using Intelligent Agents to Manage Business Processes,” in Proc. First Int. Conf. on the Practical Application of Intelligent Agents and Multi-Agent Technology, London, 1996, pp. 345–376.
[31] T. Sandholm, ”Negotiation among Self-Interested Computationally Limited Agents,” Ph.D. Thesis (University of Massachusetts, Amherst, 1996). http://portal.acm.org/citation.cfm&id=924453 , http://www.cs.cmu.edu/ sandholm/dissertation.ps . Accessed November 11, 2010.
[32] G. Smith, ”Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver,” IEEE Trans. on Computers 29, 1104–1113 (1980). · doi:10.1109/TC.1980.1675516
[33] R. Smith and R. Davis, ”Framework for Cooperation in Distributed Problem Solving,” IEEE Trans. Syst., Man, Cybernetics 11, 61–70 (1981). · doi:10.1109/TSMC.1981.4308579
[34] P. Valckenaers, H. Van Brussel, and T. Holvoet, ”Fundamentals of Holonic Systems and Their Implications for Self-Adaptive and Self-Organizing Systems,” in Proc. 2nd IEEE Int. Conf. on Self-Adaptive and Self-Organizing Systems, Italy, 2008 (IEEE Computer Press, 2008), pp. 168–173.
[35] R. Nagpal, ”A Catalog of Biologically-Inspired Primitives for Engineering Self-Organization,” in Ser. Lecture Notes in Artificial Intelligence, Ed. by G. Di Marzo Serugendo, A. Karageorgos, et al. (Springer, 2004) Vol. 2977, pp. 53–62. · Zbl 1082.68552
[36] V. I. Gorodetskii and O. L. Bukhvalov, ”Managing Workload in a Grid Based on the Multi-Agent Self-Organization Model: Part 1. Multi-Agent Model and the Self-Organization Mechanism,” Mekhatronika, Avtomatizatsiya, Upravlenie, No. 3, 40–46 (2011).
[37] C. Bernon, M.-P. Gleizes, S. Peyruqueou, et al., ”ADELFE: A Methodology for Adaptive Multi-Agent Systems Engineering,” in Ser. Lecture Notes in Computer Science, Ed. by P. Petta, R. Tolksdorf, and F. Zambonelli, (Springer, 2002) Vol. 2577, pp. 156–169. · Zbl 1022.68632
[38] R. Schoon der Woerd, O. E. Holland, J. L. Bruten, et al., ”Ant-Based Load Balancing in Telecommunications Networks,” Int. J. Adaptive Behavior 5(2), 169–207 (1996).
[39] G. Di Caro and M. Dorigo, ”AntNet: Distributed Stigmergetic Control for Communications Networks,” J. Artif. Intell. Research, No. 9, 317–365 (1998). · Zbl 0910.68182
[40] G. Di Caro, F. Ducatelle, and L. Gambardella, ”AntHocNet: An Adaptive Nature-Inspired Algorithm for Routing in Mobile ad hoc Networks,” Europ. Trans. Telecommun., Special Issue on Self-Organization in Mobile Networking 16, 443–455 (2005).
[41] C. E. Perkins and E. M. Royer, ”Ad-Hoc on-Demand Distance Vector Routing,” in Proc. 2nd Workshop on Mobile Computer Systems and Applications, Los Alamitos, Calif. (IEEE Computer Society Press, 1999) pp. 90–100.
[42] M. Jelasity and O. Babaoglu, ”T-Man: Gossip-Based Overlay Topology Management,” in Ser. Lecture Notes in Artificial Intelligence, Ed. by S. Brueckner, G. Di Marzo Serugendo, D. Hales, et al. (Springer, 2006), Vol. 3910, pp. 1–15.
[43] M. Kwiatkowska, G. Norman, and D. Parker, ”Analysis of a Gossip Protocol in PRISM,” ACM SIGMETRICS, Performance Evaluation Review 36(3), 17–22 (2008). · doi:10.1145/1481506.1481511
[44] S. Lin, F. Taïani, and G. S. Blair, ”GossipKit: A Framework of Gossip Protocol Family,” in Proc. 5th Workshop on Middleware for Network Eccentric and Mobile Applications, Magdeburg, 2007, pp. 26–30.
[45] I. Clarke, O. Sandberg, B. Wiley, et al., ”Freenet: A Distributed Anonymous Information Storage and Retrieval System,” in Proc. Int. Workshop on Designing Privacy Enhancing Technologies (Springer, New York, 2000), pp. 46–66. · Zbl 0977.68665
[46] V. I. Gorodetskii, O. V. Karsaev, V. V. Samoilov, et al., ”Development Tools for Open Agent Networks,” J. Comput. Syst. Sci. Int. 47, 429–446 (2008). · Zbl 1178.93012 · doi:10.1134/S1064230708030131
[47] S. J. Russell and P. Norvig, Artificial Intelligence: A Modern Approach (Prentice Hall, Upper Saddle River, N.J., 2003). · Zbl 0835.68093
[48] FIPA Nomadic Agent Working Group (P2PNA WG6). http://www.fipa.org/subgroups/P2PNA-WG.html . Accessed November 11, 2010.
[49] V. Gorodetskiy, O. Karsaev, V. Samoilov, et al., ”P2P Agent Platform: Implementation and Testing,” Ser. Lecture Notes in Artificial Intelligence, Ed. by S. R. H. Joseph, Z. Despotovich, and G. Moro, (Springer, 2010), Vol. 5319, pp. 41–54.
[50] M. Weiser, ”The Computer for the 21st Century,” Scientific American Special Issue on Communications, Computers, and Networks (1991).
[51] M. Mamei, F. Zambonelli, and L. Leonardi, ”Distributed Motion Coordination with Co-Fields: A Case Study in Urban Traffic Management,” in Proc. 6th Int. Symp. on Autonomous Decentralized Systems (ISADS’03) (IEEE Computer Press, Washington, 2003), pp. 63–70.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.