research-article

Decentralized approaches for self-adaptation in agent organizations

Authors:

Ramachandra Kota,

Nicholas Gibbins,

Nicholas R. JenningsAuthors Info & Claims

ACM Transactions on Autonomous and Adaptive Systems (TAAS), Volume 7, Issue 1

Article No.: 1, Pages 1 - 28

https://doi.org/10.1145/2168260.2168261

Published: 04 May 2012 Publication History

Get Access

Abstract

Self-organizing multi-agent systems provide a suitable paradigm for developing autonomic computing systems that manage themselves. Towards this goal, we demonstrate a robust, decentralized approach for structural adaptation in explicitly modeled problem solving agent organizations. Based on self-organization principles, our method enables the autonomous agents to modify their structural relations to achieve a better allocation of tasks in a simulated task-solving environment. Specifically, the agents reason about when and how to adapt using only their history of interactions as guidance. We empirically show that, in a wide range of closed, open, static, and dynamic scenarios, the performance of organizations using our method is close (70–90%) to that of an idealized centralized allocation method and is considerably better (10–60%) than the current state-of-the-art decentralized approaches.

References

[1]

Abdallah, S. and Lesser, V. 2007. Multiagent reinforcement learning and self-organization in a network of agents. In Proceedings of the 6th International Joint Conference on Autonomous Agents and Multi-Agent Systems (Aamas'07). 172--179.

Digital Library

Google Scholar

[2]

Alexander, G., Raja, A., Durfee, E. H., and Musliner, D. J. 2007. Design paradigms for meta-control in multi-agent systems. In Proceedings of the Workshop on Metareasoning in Agent-based Systems at AAMAS'07. 92--103.

Google Scholar

[3]

Bernon, C., Chevrier, V., Hilaire, V., and Marrow, P. 2006. Applications of self-organising multi-agents systems: An initial framework of comparison. Informatica 30, 1, 73--82.

Google Scholar

[4]

Biskupski, B., Dowling, J., and Sacha, J. 2007. Properties and mechanisms of self-organizing manet and p2p systems. ACM Trans. Auton. Adapt. Syst. 2, 1, 1.

Digital Library

Google Scholar

[5]

Bongaerts, L. 1998. Integration of scheduling and control in holonic manufacturing systems. Ph.D. thesis, PMA/K.U. Leuven.

Google Scholar

[6]

Bou, E., Lopez-Sanchez, M., and Rodriguez-Aguilar, J. A. 2006. Self-Configuration in autonomic electronic institutions. In Coordination, Organization, Institutions and Norms in Agent Systems Workshop at ECAI'06. 1--9.

Google Scholar

[7]

Bowling, M. and Veloso, M. 2001. Rational and convergent learning in stochastic games. In Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI'01). 1021--1026.

Digital Library

Google Scholar

[8]

Capera, D., George, J.-P., Gleizes, M.-P., and Glize, P. 2003a. The AMAS theory for complex problem solving based on self-organizing cooperative agents. In Proceedings of the 12th International Workshop on Enabling Technologies (WETICE'03). IEEE Computer Society, Los Alamitos, CA, 383.

Digital Library

Google Scholar

[9]

Capera, D., Gleizes, M. P., and Glize, P. 2003b. Self-organizing agents for mechanical design. In Engineering Self-Organising Systems. Lecture Notes in Computer Science, vol. 2977, Springer, 169--185.

Digital Library

Google Scholar

[10]

Conitzer, V. 2008. Metareasoning as a formal computational problem. In Proceedings of the Workshop on Metareasoning: Thinking about Thinking at AAAI'08.

Google Scholar

[11]

De Wolf, T. and Holvoet, T. 2003. Towards autonomic computing: Agent-Based modelling, dynamical systems analysis, and decentralised control. In Proceedings of the 1st International Workshop on Autonomic Computing Principles and Architectures. 10--20.

Google Scholar

[12]

Deloach, S. A., Oyenan, W. H., and Matson, E. T. 2008. A capabilities-based model for adaptive organizations. Auton. Agents Multi-Agent Syst. 16, 1, 13--56.

Digital Library

Google Scholar

[13]

Di Marzo Serugendo, G., Gleizes, M.-P., and Karageorgos, A. 2005. Self-Organization in multi-agent systems. Knowl. Engin. Rev. 20, 2, 165--189.

Digital Library

Google Scholar

[14]

Di Marzo Serugendo, G., Gleizes, M.-P., and Karageorgos, A. 2006. Self-organisation and emergence in multi-agent systems: An overview. Informatica 30, 1, 45--54.

Google Scholar

[15]

Dignum, V. 2003. A model for organizational interaction: Based on agents, founded in logic. Ph.D. thesis, Proefschrift Universiteit Utrecht.

Google Scholar

[16]

Ferber, J. and Gutknecht, O. 1998. A meta-model for the analysis and design of organizations in multi-agent systems. In Proceedings of the 3rd International Conference on Multi Agent Systems (ICMAS'98). IEEE Computer Society, Los Alamitos, CA, 128--135.

Digital Library

Google Scholar

[17]

Fischer, K. 2005. Self-organisation in holonic multiagent systems. In Mechanizing Mathematical Reasoning, vol. 2605, Springer, 543--563.

Crossref

Google Scholar

[18]

Forestiero, A., Mastroianni, C., and Spezzano, G. 2008. A self-organizing grid featuring bio-inspired algorithms. ACM Trans. Auton. Adapt. Syst. 3, 2, 1--37.

Digital Library

Google Scholar

[19]

Gaston, M. E. and desJardins, M. 2005. Agent-Organized networks for dynamic team formation. In Proceedings of the 4th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS'05). ACM, New York. 230--237.

Digital Library

Google Scholar

[20]

Gershenson, C. 2007. Design and control of self-organizing systems. Ph.D. thesis, Vrije Universiteit Brussels.

Google Scholar

[21]

Glinton, R., Sycara, K. P., and Scerri, P. 2008. Agent organized networks redux. In Proceedings of the 23rd AAAI Conference on Artificial Intelligence. AAAI Press, 83--88.

Digital Library

Google Scholar

[22]

Hannoun, M., Boissier, O., Sichman, J. S., and Sayettat, C. 2000. Moise: An organizational model for multi-agent systems. In Proceedings of the International Joint Conference, 7th Ibero-American Conference on AI, 15th Brazilian Symposium on AI (IBERAMIA/SBIA '2000). Lecture Notes in Artifical Intelligence, vol. 1952, Springer, 152--161.

Digital Library

Google Scholar

[23]

Hilaire, V., Koukam, A., and Rodriguez, S. 2008. An adaptative agent architecture for holonic multi-agent systems. ACM Trans. Auton. Adapt. Syst. 3, 1, 1--24.

Digital Library

Google Scholar

[24]

Hogg, L. M. and Jennings, N. R. 2001. Socially intelligent reasoning for autonomous agents. IEEE Trans. Syst. Man Cybernet. 31, 5, 381--393.

Digital Library

Google Scholar

[25]

Hoogendoorn, M. 2007. Adaptation of organizational models for multi-agent systems based on max flow networks. In Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI'07). AAAI Press, 1321--1326.

Digital Library

Google Scholar

[26]

Horling, B., Benyo, B., and Lesser, V. 2001. Using self-diagnosis to adapt organizational structures. In Proceedings of the 5th International Conference on Autonomous Agents (AGENTS'01). ACM Press, New York. 529--536.

Digital Library

Google Scholar

[27]

Hubner, J. F., Sichman, J. S., and Boissier, O. 2004. Using the MOISE+ for a cooperative framework of MAS reorganisation. In Proceedings of the 17th Brazilian Symposium on Artificial Intelligence (SBIA'04). vol. 3171. Springer, 506--515.

Google Scholar

[28]

Ishida, T., Gasser, L., and Yokoo, M. 1992. Organization self-design of distributed production systems. IEEE Trans. Knowl. Data Engin. 4, 2, 123--134.

Digital Library

Google Scholar

[29]

Jackson, M. O. and Watts, A. 2002. The evolution of social and economic networks. J. Econ. Theory 106, 2, 265--295.

Crossref

Google Scholar

[30]

Jin, Y. and Levitt, R. E. 1996. The virtual design team: A computational model of project organizations. Comput. Math. Organ. Theory 2, 171--196(26).

Crossref

Google Scholar

[31]

Kamboj, S. and Decker, K. S. 2007. Organizational self-design in semi-dynamic environments. In Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS'07). 1220--1227.

Digital Library

Google Scholar

[32]

Kephart, J. O. and Chess, D. M. 2003. The vision of autonomic computing. IEEE Comput. 36, 1, 41--50.

Digital Library

Google Scholar

[33]

Kota, R. 2009. Self-Adapting agent organisations. http://eprints.soton.ac.uk/72019/.

Google Scholar

[34]

Kota, R., Gibbins, N., and Jennings, N. R. 2008. Decentralised structural adaptation in agent organisations. In Proceedings of the Workshop on Organised Adaptation in Multi-Agent Systems at AAMAS '08. 1--16.

Google Scholar

[35]

Mano, J.-P., Bourjot, C., Lopardo, G., and Glize, P. 2006. Bio-Inspired mechanisms for artificial self-organised systems. Informatica 30, 1, 55--62.

Google Scholar

[36]

Mathieu, P., Routier, J.-C., and Secq, Y. 2002. Principles for dynamic multi-agent organizations. In Proceedings of the 5th Pacific Rim International Workshop on Multi Agents. Springer, 109--122.

Digital Library

Google Scholar

[37]

Maximilien, E. M. and Singh, M. P. 2005. Multiagent system for dynamic Web services selection. In Proceedings of 1st Workshop on Service-Oriented Computing and Agent-Based Engineering (SOCABE) at AAMAS'05. 25--29.

Google Scholar

[38]

Motwani, R. and Raghavan, P. 1995. Randomized Algorithms. Cambridge University Press.

Digital Library

Google Scholar

[39]

Norman, T. J., Preece, A., Chalmers, S., Jennings, N. R., Luck, M., Dang, V. D., Nguyen, T. D., Deora, V., Shao, J., Gray, A., and Fiddian, N. 2004. Agent-Based formation of virtual organisations. Int. J. Knowl. Based Syst. 17, 2-4, 103--111.

Digital Library

Google Scholar

[40]

Raja, A. and Lesser, V. 2004. Meta-level reasoning in deliberative agents. In Proceedings of the Intelligent Agent Technology (IAT'04), IEEE/WIC/ACM International Conference. IEEE Computer Society, Los Alamitos, CA, 141--147.

Digital Library

Google Scholar

[41]

Schlegel, T. and Kowalczyk, R. 2007. Towards self-organising agent-based resource allocation in a multi-server environment. In Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS'07). ACM, 1--8.

Digital Library

Google Scholar

[42]

Sierra, C., Rodriguez-Aguilar, J. A., Noriega, P., Esteva, M., and Arcos, J. L. 2004. Engineering multi-agent systems as electronic institutions. Euro. J. Inf. Profess. V, 4, 33--39.

Google Scholar

[43]

Sims, M., Goldman, C., and Lesser, V. 2003. Self-Organization through bottom-up coalition formation. In Proceedings of 2nd International Joint Conference on Autonomous Agents and MultiAgent Systems (AAMAS'03). ACM Press, 867--874.

Digital Library

Google Scholar

[44]

Tesauro, G., Chess, D. M., Walsh, W. E., Das, R., Segal, A., Whalley, I., Kephart, J. O., and White, S. R. 2004. A multi-agent systems approach to autonomic computing. In Proceedings of the 3rd International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS'04). IEEE Computer Society, Los Alamitos, CA, 464--471.

Digital Library

Google Scholar

[45]

Vazquez-Salceda, J., Dignum, V., and Dignum, F. 2005. Organizing multiagent systems. Auton. Agents Multi-Agent Syst. 11, 3, 307--360.

Digital Library

Google Scholar

[46]

Wang, Z. and Liang, X. 2006. A graph based simulation of reorganization in multi-agent systems. In Proceedings of the IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT'06). IEEE Computer Society, Los Alamitos, CA, 129--132.

Digital Library

Google Scholar

[47]

Watts, A. 2001. A dynamic model of network formation. Games Econ. Behav. 34, 2, 331--341.

Crossref

Google Scholar

Cited By

View all

Li KWu SWang Y(2023)Social Network Evolution of Multiagent Groups in Task AllocationIEEE Transactions on Computational Social Systems10.1109/TCSS.2022.320483810:5(2773-2785)Online publication date: Oct-2023
https://doi.org/10.1109/TCSS.2022.3204838
Hashmi SDam HUzunov AChhetri MGhose AColman A(2023)Goal-Driven Adversarial Search for Distributed Self-Adaptive Systems2023 IEEE International Conference on Software Services Engineering (SSE)10.1109/SSE60056.2023.00034(198-209)Online publication date: Jul-2023
https://doi.org/10.1109/SSE60056.2023.00034
Amaral CHübner JCranefield S(2023)Generating and choosing organisations for multi-agent systemsAutonomous Agents and Multi-Agent Systems10.1007/s10458-023-09623-837:2Online publication date: 24-Sep-2023
https://dl.acm.org/doi/10.1007/s10458-023-09623-8
Show More Cited By

Index Terms

Decentralized approaches for self-adaptation in agent organizations
1. Computing methodologies
  1. Artificial intelligence
    1. Distributed artificial intelligence
      1. Multi-agent systems

Recommendations

Self-Adaptation for Robustness and Cooperation in Holonic Multi-Agent Systems
Transactions on Large-Scale Data- and Knowledge-Centered Systems I

This paper reflects a discussion at the SARC workshop, held in Venice, October 2008. This workshop addresses robustness and cooperation in holonic multi-agent systems within a context of self-organizing and self-adaptive systems. The paper first ...
Self-Organizing Agent Coalitions in Distributed Multi-agent Systems
CICN '10: Proceedings of the 2010 International Conference on Computational Intelligence and Communication Networks

Self-Organization refers to the process through which a system changes its internal organization to adapt to changes in its goals & the environment, without explicit external control. The self-organizing capability seen in many natural and artificial ...
Towards self-organization in multi-agent systems and Grid computing

This paper presents an overview on some of the exciting interdisciplinary research areas that have emerged in recent years in multi-agent systems and Grid computing, e.g., semantic Grids, agent-based Grid computing, service-oriented architectures, ...

Reviews

Reviewer: Liz Sonenberg

Self-adapting agent organizations have been promoted as a useful and suitable paradigm for open and dynamic agent systems. This paper argues for a flexible approach that provides a meta-reasoning component to agents using localized adaptation rather than a centralized mechanism. This novel approach is presented for meta-reasoning using social utility factors to help decide whether or not to adapt an agent organization. Organizational structure is defined in terms of agent relationships. Changing the organizational structure entails changing, dissolving, or adding localized individual agent relationships. In this paper, the organizational structure is implicitly represented in the individual relationships, not explicitly represented at an organizational level. Each agent may have superiors, subordinates, and peer agent relationships. Subordinates or peer agents provide services that can be allocated. There is no first-class agent organizational entity as such. To address the dynamic nature of organizations, the authors propose a weighted (decaying with time) factor to calculate the utility of the relationship. The authors present three algorithms to apply based on the type of organization. The fundamental algorithm, k-adapt, is extended for open organizations based on the WoLF principle: "Win or Learn Fast." In other words, if you are working well with spare capacity, don't change quickly; if not, restructure quickly. For dynamic organizations, the k-adapt algorithm is extended to include decay over time, so that more recent relationships have more importance. The paper includes a modest but useful review of related work. It will be of interest to both those who want a sense of why and how to study self-organization from a multiagent systems perspective, and those who are interested in the fine details of a carefully addressed approach in one particular setting. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Autonomous and Adaptive Systems

ACM Transactions on Autonomous and Adaptive Systems Volume 7, Issue 1

Special section on formal methods in pervasive computing, pervasive adaptation, and self-adaptive systems: Models and algorithms

April 2012

365 pages

ISSN:1556-4665

EISSN:1556-4703

DOI:10.1145/2168260

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 May 2012

Accepted: 01 August 2010

Revised: 01 April 2010

Received: 01 June 2009

Published in TAAS Volume 7, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

56
Total Citations
View Citations
982
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)2

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Li KWu SWang Y(2023)Social Network Evolution of Multiagent Groups in Task AllocationIEEE Transactions on Computational Social Systems10.1109/TCSS.2022.320483810:5(2773-2785)Online publication date: Oct-2023
https://doi.org/10.1109/TCSS.2022.3204838
Hashmi SDam HUzunov AChhetri MGhose AColman A(2023)Goal-Driven Adversarial Search for Distributed Self-Adaptive Systems2023 IEEE International Conference on Software Services Engineering (SSE)10.1109/SSE60056.2023.00034(198-209)Online publication date: Jul-2023
https://doi.org/10.1109/SSE60056.2023.00034
Amaral CHübner JCranefield S(2023)Generating and choosing organisations for multi-agent systemsAutonomous Agents and Multi-Agent Systems10.1007/s10458-023-09623-837:2Online publication date: 24-Sep-2023
https://dl.acm.org/doi/10.1007/s10458-023-09623-8
Li KWu SWang Y(2023)Relation Adaptation of the Grouped Multiagent Network in Task AllocationAdvances in Guidance, Navigation and Control10.1007/978-981-19-6613-2_592(6125-6136)Online publication date: 31-Jan-2023
https://doi.org/10.1007/978-981-19-6613-2_592
Jin RSu J(2022)Self-Organizing Coalition Formation Based on Non-Cooperative Games in Social Networks2022 International Conference on Information Technology, Communication Ecosystem and Management (ITCEM)10.1109/ITCEM57303.2022.00026(90-94)Online publication date: Dec-2022
https://doi.org/10.1109/ITCEM57303.2022.00026
Jiang JLi YJiang YBu ZCao J(2022)An intermediary utility-based service search and structure organization approach in service-oriented MASKnowledge-Based Systems10.1016/j.knosys.2022.108154241(108154)Online publication date: Apr-2022
https://doi.org/10.1016/j.knosys.2022.108154
Yang G(2022)Learning to Adapt for Agile OrganisationsProceedings of 2022 10th China Conference on Command and Control10.1007/978-981-19-6052-9_26(278-289)Online publication date: 30-Aug-2022
https://doi.org/10.1007/978-981-19-6052-9_26
Li WWang XJin BSheng JHua YZha HDignum FLomuscio AEndriss UNowé A(2021)Structured Diversification Emergence via Reinforced Organization Control and Hierachical Consensus LearningProceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3463952.3464045(773-781)Online publication date: 3-May-2021
https://dl.acm.org/doi/10.5555/3463952.3464045
Saadi AMaamri RSahnoun Z(2020)Behavioral flexibility in Belief-Desire- Intention (BDI) architecturesMultiagent and Grid Systems10.3233/MGS-20033516:4(343-377)Online publication date: 31-Dec-2020
https://doi.org/10.3233/MGS-200335
Langlois SAkoroda OCarrillo EHerrmann JAzarm SXu HOtte M(2020)Metareasoning Structures, Problems, and Modes for Multiagent Systems: A SurveyIEEE Access10.1109/ACCESS.2020.30287518(183080-183089)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.3028751
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Self-Adaptation for Robustness and Cooperation in Holonic Multi-Agent Systems

Self-Organizing Agent Coalitions in Distributed Multi-agent Systems

Towards self-organization in multi-agent systems and Grid computing

Reviews

Access critical reviews of Computing literature here