Organisational adaptation of multi-agent systems in a peer-to-peer scenario

Organisations in multi-agent systems (MAS) have proven to be successful in regulating agent societies. Nevertheless, changes in agents’ behaviour or in the dynamics of the environment may lead to a poor fulfilment of the system’s purposes, and so the entire organisation needs to be adapted. In this paper we focus on endowing the organisation with adaptation capabilities, instead of expecting agents to be capable of adapting the organisation by themselves. We regard this organisational adaptation as an assisting service provided by what we call the Assistance Layer. Our generic Two Level Assisted MAS Architecture (2-LAMA) incorporates such a layer. We empirically evaluate this approach by means of an agent-based simulator we have developed for the P2P sharing network domain. This simulator implements 2-LAMA architecture and supports the comparison between different adaptation methods, as well as, with the standard BitTorrent protocol. In particular, we present two alternatives to perform norm adaptation and one method to adapt agents’ relationships. The results show improved performance and demonstrate that the cost of introducing an additional layer in charge of the system’s adaptation is lower than its benefits.     

Analyzing and visualizing multiagent rewards in dynamic and stochastic domains

The ability to analyze the effectiveness of agent reward structures is critical to the successful design of multiagent learning algorithms. Though final system performance is the best indicator of the suitability of a given reward structure, it is often preferable to analyze the reward properties that lead to good system behavior (i.e., properties promoting coordination among the agents and providing agents with strong signal to noise ratios). This step is particularly helpful in continuous, dynamic, stochastic domains ill-suited to simple table backup schemes commonly used in TD(λ)/Q-learning where the effectiveness of the reward structure is difficult to distinguish from the effectiveness of the chosen learning algorithm. In this paper, we present a new reward evaluation method that provides a visualization of the tradeoff between the level of coordination among the agents and the difficulty of the learning problem each agent faces. This method is independent of the learning algorithm and is only a function of the problem domain and the agents’ reward structure. We use this reward property visualization method to determine an effective reward without performing extensive simulations. We then test this method in both a static and a dynamic multi-rover learning domain where the agents have continuous state spaces and take noisy actions (e.g., the agents’ movement decisions are not always carried out properly). Our results show that in the more difficult dynamic domain, the reward efficiency visualization method provides a two order of magnitude speedup in selecting good rewards, compared to running a full simulation. In addition, this method facilitates the design and analysis of new rewards tailored to the observational limitations of the domain, providing rewards that combine the best properties of traditional rewards.     

Artificial institutions: a model of institutional reality for open multiagent systems

Software agents’ ability to interact within different open systems, designed by different groups, presupposes an agreement on an unambiguous definition of a set of concepts, used to describe the context of the interaction and the communication language the agents can use. Agents’ interactions ought to allow for reliable expectations on the possible evolution of the system; however, in open systems interacting agents may not conform to predefined specifications. A possible solution is to define interaction environments including a normative component, with suitable rules to regulate the behaviour of agents. To tackle this problem we propose an application-independent metamodel of artificial institutions that can be used to define open multiagent systems. In our view an artificial institution is made up by an ontology that models the social context of the interaction, a set of authorizations to act on the institutional context, a set of linguistic conventions for the performance of institutional actions and a system of norms that are necessary to constrain the agents’ actions.     

Learning to trust in the competence and commitment of agents

For agents to collaborate in open multi-agent systems, each agent must trust in the other agents’ ability to complete tasks and willingness to cooperate. Agents need to decide between cooperative and opportunistic behavior based on their assessment of another agents’ trustworthiness. In particular, an agent can have two beliefs about a potential partner that tend to indicate trustworthiness: that the partner is competent and that the partner expects to engage in future interactions. This paper explores an approach that models competence as an agent’s probability of successfully performing an action, and models belief in future interactions as a discount factor. We evaluate the underlying decision framework’s performance given accurate knowledge of the model’s parameters in an evolutionary game setting. We then introduce a game-theoretic framework in which an agent can learn a model of another agent online, using the Harsanyi transformation. The learning agents evaluate a set of competing hypotheses about another agent during the simulated play of an indefinitely repeated game. The Harsanyi strategy is shown to demonstrate robust and successful online play against a variety of static, classic, and learning strategies in a variable-payoff Iterated Prisoner’s Dilemma setting.     

Is There a Future for AI Without Representation?

This paper investigates the prospects of Rodney Brooks’ proposal for AI without representation. It turns out that the supposedly characteristic features of “new AI” (embodiment, situatedness, absence of reasoning, and absence of representation) are all present in conventional systems: “New AI” is just like old AI. Brooks proposal boils down to the architectural rejection of central control in intelligent agents—Which, however, turns out to be crucial. Some of more recent cognitive science suggests that we might do well to dispose of the image of intelligent agents as central representation processors. If this paradigm shift is achieved, Brooks’ proposal for cognition without representation appears promising for full-blown intelligent agents—Though not for conscious agents.     

High survivability of a large colony through a small-world relationship

In this article, energy trophallaxis, i.e., distributed autonomous energy management methodology inspired by social insects and bat behavior, and its advantages, are shown by a series of computer simulations to address the survivability of organized groups of agents in a dynamic environment with uncertainty. The uncertainty of the agents’ organizational behavior is represented by two Lévy distributions. By carefully controlling energy donation behavior based on these distributions, we can examine the survivability of a larger group that traditional methods cannot analyze. As a result, even a small degree of friendship throughout the organization makes the group’s survivability improve dramatically.     

A game-theoretic framework to identify overlapping communities in social networks

In this paper, we introduce a game-theoretic framework to address the community detection problem based on the structures of social networks. We formulate the dynamics of community formation as a strategic game called community formation game: Given an underlying social graph, we assume that each node is a selfish agent who selects communities to join or leave based on her own utility measurement. A community structure can be interpreted as an equilibrium of this game. We formulate the agents’ utility by the combination of a gain function and a loss function. We allow each agent to select multiple communities, which naturally captures the concept of “overlapping communities”. We propose a gain function based on the modularity concept introduced by Newman (Proc Natl Acad Sci 103(23):8577–8582, 2006), and a simple loss function that reflects the intrinsic costs incurred when people join the communities. We conduct extensive experiments under this framework, and our results show that our algorithm is effective in identifying overlapping communities, and are often better then other algorithms we evaluated especially when many people belong to multiple communities. To the best of our knowledge, this is the first time the community detection problem is addressed by a game-theoretic framework that considers community formation as the result of individual agents’ rational behaviors.     

Dynamic scheduling model of computing resource based on MAS cooperation mechanism

Allocation of grid resources aims at improving resource utility and grid application performance. Currently, the algorithms proposed for this purpose do not fit well the autonomic, dynamic, distributive and heterogeneous features of the grid environment. According to MAS (multi-agent system) cooperation mechanism and market bidding game rules, a model of allocating allocation of grid resources based on market economy is introduced to reveal the relationship between supply and demand. This model can make good use of the studying and negotiating ability of consumers’ agent and takes full consideration of the consumer’s behavior, thus rendering the application and allocation of resource of the consumers rational and valid. In the meantime, the utility function of consumer is given; the existence and the uniqueness of Nash equilibrium point in the resource allocation game and the Nash equilibrium solution are discussed. A dynamic game algorithm of allocating grid resources is designed. Experimental results demonstrate that this algorithm diminishes effectively the unnecessary latency, improves significantly the smoothness of response time, the ratio of throughput and resource utility, thus rendering the supply and demand of the whole grid resource reasonable and the overall grid load balanceable. Supported by the Natural Science Foundation of Hunan Province (Grant No. 06JJ2033), and the Society Science Foundation of Hunan Province (Grant No. 07YBB239)     

Facility layout design using virtual multi-agent system

This paper presents a novel approach to the facility layout design problem based on multi-agent society where agents’ interactions form the facility layout design. Each agent corresponds to a facility with inherent characteristics, emotions, and a certain amount of money, forming its utility function. An agent’s money is adjusted during the learning period by a manager agent while each agent tries to tune the parameters of its utility function in such a way that its total layout cost can be minimized in competition with others. The agents’ interactions are formed based on market mechanism. In each step, an unoccupied location is presented to all applicant agents, for which each agent proposes a price proportionate to its utility function. The agent proposing a higher price is selected as the winner and assigned to that location by an appropriate space-filling curve. The proposed method utilizes the fuzzy theory to establish each agent’s utility function. In addition, it provides a simulation environment using an evolutionary algorithm to form different interactions among the agents and makes it possible for them to experience various strategies. The experimental results show that the proposed approach achieves a lower total layout cost compared with state of the art methods.     

An agent-based recommender system for developing customized families of products

Electronic markets and web-based content have improved traditional product development processes by increasing the participation of customers and applying various recommender systems to satisfy individual customer needs. Agent-based systems based on agents’ roles and tasks can provide appropriate tools to solve product design problems by recommending design knowledge and information. This paper introduces an agent-based recommender system to support designing families of products based on customers’ preferences in dynamic electronic market environments. In the proposed system, a market-based learning mechanism is applied to determine the customers’ preferences for recommending appropriate products to customers of the product family. We demonstrate the implementation of the proposed recommender system using a multi-agent framework. Through simulated experiments, we illustrate that the proposed recommender system can help determine the preference values of products for customized recommendation and market segment design in various electronic market environments.     

Handling Communication Restrictions and Team Formation in Congestion Games

There are many domains in which a multi-agent system needs to maximize a “system utility” function which rates the performance of the entire system, while subject to communication restrictions among the agents. Such communication restrictions make it difficult for agents that take actions to optimize their own “private” utilities to also help optimize the system utility. In this article we show how previously introduced utilities that promote coordination among agents can be modified to be effective in domains with communication restrictions. The modified utilities provide performance improvements of up to 75 over previously used utilities in congestion games (i.e., games where the system utility depends solely on the number of agents choosing a particular action). In addition, we show that in the presence of severe communication restrictions, team formation for the purpose of information sharing among agents leads to an additional 25 improvement in system utility. Finally, we show that agents’ private utilities and team sizes can be manipulated to form the best compromise between how “aligned” an agent’s utility is with the system utility and how easily an agent can learn that utility.     

Modeling dynamic environments in multi-agent simulation

Real environments in which agents operate are inherently dynamic—the environment changes beyond the agents’ control. We advocate that, for multi-agent simulation, this dynamism must be modeled explicitly as part of the simulated environment, preferably using concepts and constructs that relate to the real world. In this paper, we describe such concepts and constructs, and we provide a formal framework to unambiguously specify their relations and meaning. We apply the formal framework to model a dynamic RoboCup Soccer environment and elaborate on how the framework poses new challenges for exploring the modeling of environments in multi-agent simulation.     

An ontology based approach to organize multi-agent assisted supply chain negotiations

Effective supply chain management (SCM) comprises activities involving the demand and supply of resources and services. Negotiation is an essential approach to solve conflicting transaction and scheduling problems among supply chain members. The multi-agent system (MAS) technology has provided the potential of automating supply chain negotiations to alleviate human interactions. Software agents are supposed to perform on behalf of their human owners only when equipped with sophisticated negotiation knowledge. To better organize the negotiation knowledge utilized by agents and facilitate agents’ adaptive negotiation decision making ability, an ontology-based approach is proposed in this paper. Firstly, the multi-agent assisted supply chain negotiation scheme is presented to configure the general design components of the negotiation system, covering the agent intelligence modules, the knowledge organization method and the negotiation protocol. Then, the ontology-based negotiation knowledge organization method is specified. The negotiation knowledge is separated into shared negotiation ontology and private negotiation ontology to ensure both the agent communicative interoperability and the privacy of strategic knowledge. Inference rules are defined on top of the private negotiation ontology to guide agents’ reasoning ability. Through this method, agents’ negotiation behaviors will be more adaptive to various negotiation environments utilizing corresponding negotiation knowledge.     

Evolutionary mechanism design: a review

The advent of large-scale distributed systems poses unique engineering challenges. In open systems such as the internet it is not possible to prescribe the behaviour of all of the components of the system in advance. Rather, we attempt to design infrastructure, such as network protocols, in such a way that the overall system is robust despite the fact that numerous arbitrary, non-certified, third-party components can connect to our system. Economists have long understood this issue, since it is analogous to the design of the rules governing auctions and other marketplaces, in which we attempt to achieve socially-desirable outcomes despite the impossibility of prescribing the exact behaviour of the market participants, who may attempt to subvert the market for their own personal gain. This field is known as “mechanism design”: the science of designing rules of a game to achieve a specific outcome, even though each participant may be self-interested. Although it originated in economics, mechanism design has become an important foundation of multi-agent systems (MAS) research. In a traditional mechanism design problem, analytical methods are used to prove that agents’ game-theoretically optimal strategies lead to socially desirable outcomes. In many scenarios, traditional mechanism design and auction theory yield clear-cut results; however, there are many situations in which the underlying assumptions of the theory are violated due to the messiness of the real-world. In this paper we review alternative approaches to mechanism design which treat it as an engineering problem and bring to bear engineering design principles, viz.: iterative step-wise refinement of solutions, and satisficing instead of optimization in the face of intractable complexity. We categorize these approaches under the banner of evolutionary mechanism design.     

Automata for Epistemic Temporal Logic with Synchronous Communication

We suggest that developing automata theoretic foundations is relevant for knowledge theory, so that we study not only what is known by agents, but also the mechanisms by which such knowledge is arrived at. We define a class of epistemic automata, in which agents’ local states are annotated with abstract knowledge assertions about others. These are finite state agents who communicate synchronously with each other and information exchange is ‘perfect’. We show that the class of recognizable languages has good closure properties, leading to a Kleene-type theorem using what we call regular knowledge expressions. These automata model distributed causal knowledge in the following way: each agent in the system has a partial knowledge of the temporal evolution of the system, and every time agents synchronize, they update each other’s knowledge, resulting in a more up-to-date view of the system state. Hence we show that these automata can be used to solve the satisfiability problem for a natural epistemic temporal logic for local properties. Finally, we characterize the class of languages recognized by epistemic automata as the regular consistent languages studied in concurrency theory.     

No-beacon collective circular motion of jointly connected multi-agents

In this paper, a decentralized control algorithm is proposed for a group of nonholonomic vehicles to form a class of collective circular motion behavior. Without the guidance of a global beacon, the desired collective behavior occurs provided that the multi-agent system is jointly connected. Moreover, a repulsion mechanism is considered to improve the distribution evenness of the agents’ circular motion phases and hence to avoid collision. The effectiveness of the approach is verified through both theoretical analysis and numerical simulation. Moreover, some interesting variations of the circular motion model are investigated to enrich the collective behaviors.     

Power in threshold network flow games

Preference aggregation is used in a variety of multiagent applications, and as a result, voting theory has become an important topic in multiagent system research. However, power indices (which reflect how much “real power” a voter has in a weighted voting system) have received relatively little attention, although they have long been studied in political science and economics. We consider a particular multiagent domain, a threshold network flow game. Agents control the edges of a graph; a coalition wins if it can send a flow that exceeds a given threshold from a source vertex to a target vertex. The relative power of each edge/agent reflects its significance in enabling such a flow, and in real-world networks could be used, for example, to allocate resources for maintaining parts of the network. We examine the computational complexity of calculating two prominent power indices, the Banzhaf index and the Shapley-Shubik index, in this network flow domain. We also consider the complexity of calculating the core in this domain. The core can be used to allocate, in a stable manner, the gains of the coalition that is established. We show that calculating the Shapley-Shubik index in this network flow domain is NP-hard, and that calculating the Banzhaf index is #P-complete. Despite these negative results, we show that for some restricted network flow domains there exists a polynomial algorithm for calculating agents’ Banzhaf power indices. We also show that computing the core in this game can be performed in polynomial time.     

A multiagent framework for coordinated parallel problem solving

Today’s organizations, under increasing pressure on the effectiveness and the increasing need for dealing with complex tasks beyond a single individual’s capabilities, need technological support in managing complex tasks that involve highly distributed and heterogeneous information sources and several actors. This paper describes CoPSF, a multiagent system middle-ware that simplifies the development of coordinated problem solving applications while ensuring standard compliance through a set of system services and agents. CoPSF hosts and serves multiple concurrent teams of problem solving contributing both to the limitation of communication overheads and to the reduction of redundant work across teams and organizations. The framework employs (i) an interleaved task decomposition and allocation approach, (ii) a mechanism for coordination of agents’ work, and (iii) a mechanism that enables synergy between parallel teams.     

Adaptive decision-making frameworks for dynamic multi-agent organizational change

This article presents a capability called Adaptive Decision-Making Frameworks (ADMF) and shows that it can result in significantly improved system performance across run-time situation changes in a multi-agent system. Specifically, ADMF can result in improved and more robust performance compared to the use of a single static decision-making framework (DMF). The ADMF capability allows agents to dynamically adapt the DMF in which they participate to fit their run-time situation as it changes. A DMF identifies a set of agents and specifies the distribution of decision-making control and the authority to assign subtasks among these agents as they determine how a goal or set of goals should be achieved. The ADMF capability is a form of organizational adaptation and differs from previous approaches to organizational adaptation and dynamic coordination in that it is the first to allow dynamic and explicit manipulation of these DMF characteristics at run-time as variables controlling agent behavior. The approach proposed for selecting DMFs at run-time parameterizes all domain-specific knowledge as characteristics of the agents’ situation, so the approach is application-independent. The presented evaluation empirically shows that, for at least one multi-agent system, there is no one best DMF for multiple agents across run-time situational changes. Next, it motivates the further exploration of ADMF by showing that adapting DMFs to run-time variations in situation can result in improved overall system performance compared to static or random DMFs.