Self-Adaptation-Based Dynamic Coalition Formation in a Distributed Agent Network: A Mechanism and a Brief Survey
---
paper_title: Agent-Based Cloud Computing

paper_content:

Agent-based cloud computing is concerned with the design and development of software agents for bolstering cloud service discovery, service negotiation, and service composition. The significance of this work is introducing an agent-based paradigm for constructing software tools and testbeds for cloud resource management. The novel contributions of this work include: 1) developing Cloudle: an agent-based search engine for cloud service discovery, 2) showing that agent-based negotiation mechanisms can be effectively adopted for bolstering cloud service negotiation and cloud commerce, and 3) showing that agent-based cooperative problem-solving techniques can be effectively adopted for automating cloud service composition. Cloudle consists of 1) a service discovery agent that consults a cloud ontology for determining the similarities between providers' service specifications and consumers' service requirements, and 2) multiple cloud crawlers for building its database of services. Cloudle supports three types of reasoning: similarity reasoning, compatibility reasoning, and numerical reasoning. To support cloud commerce, this work devised a complex cloud negotiation mechanism that supports parallel negotiation activities in interrelated markets: a cloud service market between consumer agents and broker agents, and multiple cloud resource markets between broker agents and provider agents. Empirical results show that using the complex cloud negotiation mechanism, agents achieved high utilities and high success rates in negotiating for cloud resources. To automate cloud service composition, agents in this work adopt a focused selection contract net protocol (FSCNP) for dynamically selecting cloud services and use service capability tables (SCTs) to record the list of cloud agents and their services. Empirical results show that using FSCNP and SCTs, agents can successfully compose cloud services by autonomously selecting services.
---
paper_title: A Distributed Algorithm for Anytime Coalition Structure Generation

paper_content:

A major research challenge in multi-agent systems is the problem of partitioning a set of agents into mutually disjoint coalitions, such that the overall performance of the system is optimized. This problem is difficult because the search space is very large: the number of possible coalition structures increases exponentially with the number of agents. Although several algorithms have been proposed to tackle this Coalition Structure Generation (CSG) problem, all of them suffer from being inherently centralized, which leads to the existence of a performance bottleneck and a single point of failure. In this paper, we develop the first decentralized algorithm for solving the CSG problem optimally. In our algorithm, the necessary calculations are distributed among the agents, instead of being carried out centrally by a single agent (as is the case in all the available algorithms in the literature). In this way, the search can be carried out in a much faster and more robust way, and the agents can share the burden of the calculations. The algorithm combines, and improves upon, techniques from two existing algorithms in the literature, namely DCVC [5] and IP [9], and applies novel techniques for filtering the input and reducing the inter-agent communication load.
---
paper_title: Self-organization through bottom-up coalition formation

paper_content:

We present a distributed approach to self-organization in a distributed sensor network. The agents in the system use a series of negotiations incrementally to form appropriate coalitions of sensor and processing resources.Since the system is cooperative, we have developed a range of protocols that allow the agents to share meta-level information before they allocate resources. On one extreme the protocols are based on local utility computations, where each agent negotiates based on its local perspective. From there, a continuum of additional protocols exists in which agents base decisions on marginal social utility, the combination of an agent's marginal utility and that of others. We present a formal framework that allows us to quantify how social an agent can be in terms of the set of agents that are considered and how the choice of a certain level affects the decisions made by the agents and the global utility of the organization.Our results show that by implementing social agents, we obtain an organization with a high global utility both when agents negotiate over complex contracts and when they negotiate over simple ones. The main difference between the two cases is mainly the rate of convergence. Our algorithm is incremental, and therefore the organization that evolves can adapt and stabilize as agents enter and leave the system.
---
paper_title: Agent Organized Networks Redux

paper_content:

Individual robots or agents will often need to form coalitions to accomplish shared tasks, e.g., in sensor networks or markets. Furthermore, in most real systems it is infeasible for entities to interact with all peers. The presence of a social network can alleviate this problem by providing a neighborhood system within which entities interact with a reduced number of peers. Previous research has shown that the topology of the underlying social network has a dramatic effect on the quality of coalitions formed and consequently on system performance (Gaston & deslardins 2005a). It has also been shown that it is feasible to develop agents which dynamically alter connections to improve an organization's ability to form coalitions on the network. However those studies have not analysed the network topologies that result from connectivity adaptation strategies. In this paper the resulting network topologies were analysed and it was found that high performance and rapid convergence were attained because scale free networks were being formed. However it was observed that organizational performance is not impacted by limiting the number of links per agent to the total number of skills available within the population. implying that bandwidth was wasted by previous approaches. We used these observations to inform the design of a token based algorithm that attains higher performance using an order of magnitude less messages for both uniform and non-uniform distributions of skills.
---
paper_title: Task inference and distributed task management in the Centibots robotic system

paper_content:

We describe the Centibots system, a very large scale distributed robotic system, consisting of more than 100 robots, that has been successfully deployed in large, unknown indoor environments, over extended periods of time (i.e., durations corresponding to several power cycles). Unlike most multiagent systems, the set of tasks about which teams must collaborate is not given a priori. We first describe a task inference algorithm that identifies potential team commitments that collectively balance constraints such as reachability, sensor coverage, and communication access. We then describe a dispatch algorithm for task distribution and management that assigns resources depending on either task density or replacement requirements stemming from failures or power shortages. The targeted deployment environments are expected to lack a supporting communication infrastructure; robots manage their own network and reason about the concomitant localization constraints necessary to maintain team communication. Finally, we present quantitative results in terms of a "search and rescue problem" and discuss the team-oriented aspects of the system in the context of prevailing theories of multiagent collaboration.
---
paper_title: Distributed Sensor Networks: A Multiagent Perspective

paper_content:

1. Introduction to a Multiagent Perspective V. Lesser, C.L. Ortiz, Jr., M. Tambe. Part I: The Sensor Network Challenge Problem. 2. The Radsim Simulator J.H. Lawton. 3. Challenge Problem Testbed P. Zemany, M. Gaughan. 4. Visualization and Debugging Tools A. Egyed, B. Horling, R. Becker, R. Balzer. 5. Target Tracking with Bayesian Estimation J.E. Vargas, K. Tvalarparti, Zhaojun Wu. Part II: Distributed Resource Allocation: Architectures and Protocols. 6. Dynamic resource-bounded negotiation in non-additive domains C.L. Ortiz, Jr., T.W. Rauenbusch, E. Hsu, R. Vincent. 7. A satisficing, negotiated, and learning coalition formation architecture Leen-Kiat Soh, C. Tsatsoulis, H. Sevay. 8. Using Autonomy, Organizational Design and Negotiation in a DSN B. Horling, R. Mailler, Jiaying Shen, R. Vincent, V. Lesser. 9. Scaling-up Distributed Sensor Networks O. Yadgar, S. Kraus, C.L. Ortiz, Jr. 10. Distributed Resource Allocation P.J. Modi, P. Scerri, Wei-Min Shen, M. Tambe. 11. Distributed Coordination through Anarchic Optimization S. Fitzpatrick, L. Meertens. Part III: Insights into Distributed Resource Allocation Protocols based on Formal Analyses. 12. Communication and Computation in Distributed CSP Algorithms C. Fernandez, R. Bejar, B. Krishnamachari, C. Gomes, B. Selman. 13. A Comparative Study of Distributed Constraint Algorithms Weixiong Zhang, Guandong Wang, Zhao Xing, L. Wittenburg. 14. Analysis of Negotiation Protocols by Distributed Search Guandong Wang, Weixiong Zhang, R. Mailler, V. Lesser.
---
paper_title: Self-Organisation and Emergence in MAS: An Overview

paper_content:

The spread of the Internet and the evolution of mobile communication, have created new possibilities for software applications such as ubiquitous computing, dynamic supply chains and medical home care. Such systems need to operate in dynamic, heterogeneous environments and face the challenge of handling frequently changing requirements; therefore they must be flexible, robust and capable of adapting to the circumstances. It is widely believed that multi-agent systems coordinated by selforganisation and emergence mechanisms are an effective way to design these systems. This paper aims to define the concepts of self-organisation and emergence and to provide a state of the art survey about the different classes of self-organisation mechanisms applied in the multi-agent systems domain. Furthermore, the strengths and limits of these approaches are examined and research issues are provided. Povzetek: Clanek opisuje pregled samoorganizacije v MAS.
---
paper_title: Coalition Formation with Spatial and Temporal Constraints

paper_content:

The coordination of emergency responders and robots to undertake a number of tasks in disaster scenarios is a grand challenge for multi-agent systems. Central to this endeavour is the problem of forming the best teams (coalitions) of responders to perform the various tasks in the area where the disaster has struck. Moreover, these teams may have to form, disband, and reform in different areas of the disaster region. This is because in most cases there will be more tasks than agents. Hence, agents need to schedule themselves to attempt each task in turn. Second, the tasks themselves can be very complex: requiring the agents to work on them for different lengths of time and having deadlines by when they need to be completed. The problem is complicated still further when different coalitions perform tasks with different levels of efficiency. Given all these facets, we define this as The Coalition Formation with Spatial and Temporal constraints problem (CFSTP). We show that this problem is NP-hard---in particular, it contains the well-known complex combinatorial problem of Team Orienteering as a special case. Based on this, we design a Mixed Integer Program to optimally solve small-scale instances of the CFSTP and develop new anytime heuristics that can, on average, complete 97% of the tasks for large problems (20 agents and 300 tasks). In so doing, our solutions represent the first results for CFSTP.
---
paper_title: THE EFFECT OF NETWORK STRUCTURE ON DYNAMIC TEAM FORMATION IN MULTI‐AGENT SYSTEMS

paper_content:

Previous studies of team formation in multi-agent systems have typically assumed that the agent social network underlying the agent organization is either not explicitly described or the social network is assumed to take on some regular structure such as a fully connected network or a hierarchy. However, recent studies have shown that real-world networks have a rich and purposeful structure, with common properties being observed in many different types of networks. As multi-agent systems continue to grow in size and complexity, the network structure of such systems will become increasing important for designing efficient, effective agent communities. ::: ::: We present a simple agent-based computational model of team formation, and analyze the theoretical performance of team formation in two simple classes of networks (ring and star topologies). We then give empirical results for team formation in more complex networks under a variety of conditions. From these experiments, we conclude that a key factor in effective team formation is the underlying agent interaction topology that determines the direct interconnections among agents. Specifically, we identify the property of diversity support as a key factor in the effectiveness of network structures for team formation. Scale-free networks, which were developed as a way to model real-world networks, exhibit short average path lengths and hub-like structures. We show that these properties, in turn, result in higher diversity support; as a result, scale-free networks yield higher organizational efficiency than the other classes of networks we have studied.
---
paper_title: Methods for Task Allocation Via Agent Coalition Formation

paper_content:

Task execution in multi-agent environments may require cooperation among agents. Given a set of agents and a set of tasks which they have to satisfy, we consider situations where each task should be attached to a group of agents that will perform the task. Task allocation to groups of agents is necessary when tasks cannot be performed by a single agent. However it may also be beneficial when groups perform more efficiently with respect to the single agents' performance. In this paper we present several solutions to the problem of task allocation among autonomous agents, and suggest that the agents form coalitions in order to perform tasks or improve the efficiency of their performance. We present efficient distributed algorithms with low ratio bounds and with low computational complexities. These properties are proven theoretically and supported by simulations and an implementation in an agent system. Our methods are based on both the algorithmic aspects of combinatorics and approximation algorithms for NP-hard problems. We first present an approach to agent coalition formation where each agent must be a member of only one coalition. Next, we present the domain of overlapping coalitions. We proceed with a discussion of the domain where tasks may have a precedence order. Finally, we discuss the case of implementation in an open, dynamic agent system. For each case we provide an algorithm that will lead agents to the formation of coalitions, where each coalition is assigned a task. Our algorithms are any-time algorithms, they are simple, efficient and easy to implement.
---
paper_title: Agent-organized networks for dynamic team formation

paper_content:

Many multi-agent systems consist of a complex network of autonomous yet interdependent agents. Examples of such networked multi-agent systems include supply chains and sensor networks. In these systems, agents have a select set of other agents with whom they interact based on environmental knowledge, cognitive capabilities, resource limitations, and communications constraints. Previous findings have demonstrated that the structure of the artificial social network governing the agent interactions is strongly correlated with organizational performance. As multi-agent systems are typically embedded in dynamic environments, we wish to develop distributed, on-line network adaptation mechanisms for discovering effective network structures. Therefore, within the context of dynamic team formation, we propose several strategies for agent-organized networks (AONs) and evaluate their effectiveness for increasing organizational performance.
---
paper_title: An anytime algorithm for optimal coalition structure generation

paper_content:

In multi agent system, how to find a coalition structure making the greatest profits in cooperation in the shortest time is an issue which has been given much attention. When finding the optimal coalition structure, if we make no any restriction on the searching space, we must search all the coalition structures. An anytime algorithm—LVAA(Lateral and Vertical Anytime Algorithm), designed in this paper, used a branch and bound technique and pruning function to simplify the searching space besides L 1 , L 2 and L n layers vertically and horizontally. Then, it find the optimal coalition structure value. The result of the experiment proved that it greatly reduced the searching space. When coalition values meet uniform distribution and normal distribution respectively, the searching times of LVAA can be reduced by 78% and 82% than Sandholm's for agent number 18 and 23.
---
paper_title: Negotiation decision functions for autonomous agents

paper_content:

We present a formal model of negotiation between autonomous agents. The purpose of the negotiation is to reach an agreement about the provision of a service by one agent for another. The model defines a range of strategies and tactics that agents can employ to generate initial offers, evaluate proposals and offer counter proposals. The model is based on computationally tractable assumptions, demonstrated in the domain of business process management and empirically evaluated.
---
paper_title: Agent-Based Cloud Computing

paper_content:

Agent-based cloud computing is concerned with the design and development of software agents for bolstering cloud service discovery, service negotiation, and service composition. The significance of this work is introducing an agent-based paradigm for constructing software tools and testbeds for cloud resource management. The novel contributions of this work include: 1) developing Cloudle: an agent-based search engine for cloud service discovery, 2) showing that agent-based negotiation mechanisms can be effectively adopted for bolstering cloud service negotiation and cloud commerce, and 3) showing that agent-based cooperative problem-solving techniques can be effectively adopted for automating cloud service composition. Cloudle consists of 1) a service discovery agent that consults a cloud ontology for determining the similarities between providers' service specifications and consumers' service requirements, and 2) multiple cloud crawlers for building its database of services. Cloudle supports three types of reasoning: similarity reasoning, compatibility reasoning, and numerical reasoning. To support cloud commerce, this work devised a complex cloud negotiation mechanism that supports parallel negotiation activities in interrelated markets: a cloud service market between consumer agents and broker agents, and multiple cloud resource markets between broker agents and provider agents. Empirical results show that using the complex cloud negotiation mechanism, agents achieved high utilities and high success rates in negotiating for cloud resources. To automate cloud service composition, agents in this work adopt a focused selection contract net protocol (FSCNP) for dynamically selecting cloud services and use service capability tables (SCTs) to record the list of cloud agents and their services. Empirical results show that using FSCNP and SCTs, agents can successfully compose cloud services by autonomously selecting services.
---
paper_title: Self-organization through bottom-up coalition formation

paper_content:

We present a distributed approach to self-organization in a distributed sensor network. The agents in the system use a series of negotiations incrementally to form appropriate coalitions of sensor and processing resources.Since the system is cooperative, we have developed a range of protocols that allow the agents to share meta-level information before they allocate resources. On one extreme the protocols are based on local utility computations, where each agent negotiates based on its local perspective. From there, a continuum of additional protocols exists in which agents base decisions on marginal social utility, the combination of an agent's marginal utility and that of others. We present a formal framework that allows us to quantify how social an agent can be in terms of the set of agents that are considered and how the choice of a certain level affects the decisions made by the agents and the global utility of the organization.Our results show that by implementing social agents, we obtain an organization with a high global utility both when agents negotiate over complex contracts and when they negotiate over simple ones. The main difference between the two cases is mainly the rate of convergence. Our algorithm is incremental, and therefore the organization that evolves can adapt and stabilize as agents enter and leave the system.
---
paper_title: Automated negotiation with decommitment for dynamic resource allocation in cloud computing

paper_content:

We consider the problem of allocating networked resources in dynamic environment, such as cloud computing platforms, where providers strategically price resources to maximize their utility. Resource allocation in these environments, where both providers and consumers are selfish agents, presents numerous challenges since the number of consumers and their resource demand is highly dynamic. While numerous auction-based approaches have been proposed in the literature, this paper explores an alternative approach where providers and consumers automatically negotiate resource leasing contracts. Since resource demand and supply can be dynamic and uncertain, we propose a distributed negotiation mechanism where agents negotiate over both a contract price and a decommitment penalty, which allows agents to decommit from contracts at a cost. We compare our approach experimentally, using representative scenarios and workloads, to both combinatorial auctions and the fixed-price model used by Amazon's Elastic Compute Cloud, and show that the negotiation model achieves a higher social welfare.
---
paper_title: Methods for Task Allocation Via Agent Coalition Formation

paper_content:

Task execution in multi-agent environments may require cooperation among agents. Given a set of agents and a set of tasks which they have to satisfy, we consider situations where each task should be attached to a group of agents that will perform the task. Task allocation to groups of agents is necessary when tasks cannot be performed by a single agent. However it may also be beneficial when groups perform more efficiently with respect to the single agents' performance. In this paper we present several solutions to the problem of task allocation among autonomous agents, and suggest that the agents form coalitions in order to perform tasks or improve the efficiency of their performance. We present efficient distributed algorithms with low ratio bounds and with low computational complexities. These properties are proven theoretically and supported by simulations and an implementation in an agent system. Our methods are based on both the algorithmic aspects of combinatorics and approximation algorithms for NP-hard problems. We first present an approach to agent coalition formation where each agent must be a member of only one coalition. Next, we present the domain of overlapping coalitions. We proceed with a discussion of the domain where tasks may have a precedence order. Finally, we discuss the case of implementation in an open, dynamic agent system. For each case we provide an algorithm that will lead agents to the formation of coalitions, where each coalition is assigned a task. Our algorithms are any-time algorithms, they are simple, efficient and easy to implement.
---
paper_title: Random geometric graphs

paper_content:

We analyze graphs in which each vertex is assigned random coordinates in a geometric space of arbitrary dimensionality and only edges between adjacent points are present. The critical connectivity is found numerically by examining the size of the largest cluster. We derive an analytical expression for the cluster coefficient, which shows that the graphs are distinctly different from standard random graphs, even for infinite dimensionality. Insights relevant for graph bipartitioning are included.
---
paper_title: Self-organization through bottom-up coalition formation

paper_content:

We present a distributed approach to self-organization in a distributed sensor network. The agents in the system use a series of negotiations incrementally to form appropriate coalitions of sensor and processing resources.Since the system is cooperative, we have developed a range of protocols that allow the agents to share meta-level information before they allocate resources. On one extreme the protocols are based on local utility computations, where each agent negotiates based on its local perspective. From there, a continuum of additional protocols exists in which agents base decisions on marginal social utility, the combination of an agent's marginal utility and that of others. We present a formal framework that allows us to quantify how social an agent can be in terms of the set of agents that are considered and how the choice of a certain level affects the decisions made by the agents and the global utility of the organization.Our results show that by implementing social agents, we obtain an organization with a high global utility both when agents negotiate over complex contracts and when they negotiate over simple ones. The main difference between the two cases is mainly the rate of convergence. Our algorithm is incremental, and therefore the organization that evolves can adapt and stabilize as agents enter and leave the system.
---
paper_title: Agent Organized Networks Redux

paper_content:

Individual robots or agents will often need to form coalitions to accomplish shared tasks, e.g., in sensor networks or markets. Furthermore, in most real systems it is infeasible for entities to interact with all peers. The presence of a social network can alleviate this problem by providing a neighborhood system within which entities interact with a reduced number of peers. Previous research has shown that the topology of the underlying social network has a dramatic effect on the quality of coalitions formed and consequently on system performance (Gaston & deslardins 2005a). It has also been shown that it is feasible to develop agents which dynamically alter connections to improve an organization's ability to form coalitions on the network. However those studies have not analysed the network topologies that result from connectivity adaptation strategies. In this paper the resulting network topologies were analysed and it was found that high performance and rapid convergence were attained because scale free networks were being formed. However it was observed that organizational performance is not impacted by limiting the number of links per agent to the total number of skills available within the population. implying that bandwidth was wasted by previous approaches. We used these observations to inform the design of a token based algorithm that attains higher performance using an order of magnitude less messages for both uniform and non-uniform distributions of skills.
---
paper_title: Agent Organized Networks Redux

paper_content:

Individual robots or agents will often need to form coalitions to accomplish shared tasks, e.g., in sensor networks or markets. Furthermore, in most real systems it is infeasible for entities to interact with all peers. The presence of a social network can alleviate this problem by providing a neighborhood system within which entities interact with a reduced number of peers. Previous research has shown that the topology of the underlying social network has a dramatic effect on the quality of coalitions formed and consequently on system performance (Gaston & deslardins 2005a). It has also been shown that it is feasible to develop agents which dynamically alter connections to improve an organization's ability to form coalitions on the network. However those studies have not analysed the network topologies that result from connectivity adaptation strategies. In this paper the resulting network topologies were analysed and it was found that high performance and rapid convergence were attained because scale free networks were being formed. However it was observed that organizational performance is not impacted by limiting the number of links per agent to the total number of skills available within the population. implying that bandwidth was wasted by previous approaches. We used these observations to inform the design of a token based algorithm that attains higher performance using an order of magnitude less messages for both uniform and non-uniform distributions of skills.
---

Title: Self-Adaptation-Based Dynamic Coalition Formation in a Distributed Agent Network: A Mechanism and a Brief Survey

Section 1: INTRODUCTION
Description 1: Introduce the background, motivation, and main contribution of the paper regarding self-adaptation-based dynamic coalition formation in multiagent systems.

Section 2: AGENT NETWORK MODEL
Description 2: Define the formal structure of the agent network, including agents, their resources, states, and roles.

Section 3: COALITION FORMATION MECHANISM
Description 3: Describe the proposed mechanism for dynamic coalition formation, including the steps involved and the negotiation protocol used.

Section 4: How Does an Agent Adjust DoI Values?
Description 4: Explain the procedure and algorithm for agents to adjust their degree of involvement (DoI) values to minimize penalties while joining new coalitions.

Section 5: EXPERIMENTS AND ANALYSIS
Description 5: Present the experimental setup, results, and analysis, comparing the proposed mechanism with other coalition formation mechanisms.

Section 6: CONCLUSION
Description 6: Summarize the findings, contributions, and potential applications of the proposed mechanism, and suggest future research directions.