Inter-Agent Interaction

The described topologies define the interaction of an agent with another one, or entity, but it is still needed to define how they interact. Interactions are paramount notions for defining MAS [2]. An interaction between agents can only take place if they can act or communicate and if there are situations where they can get toge­ther, such as the need to fulfill a common objective. Interactions may be conducted under the form of discussions between at least two agents and can occur in numerous situations: the rescue of an agent by others, a conversation between two agents, the implicit agreement when two agents have to decide which one goes first, the cooperation of several agents to fulfill a common task, and so on.

Interactions are usually required when agents have to satisfy a common objec­tive while taking into account their limited resources and individual skills. Getting together to fulfill a common objective involves that some agents are part of a possibly emerging organization, as described in the previous section. Therefore, every agent organization is the result of these interactions and of the place where they take place. The dynamical characteristics of interactions then implies that new agent organizations are likely to be formed as new objectives have to be satisfied. Agents can for example form coalitions [45] if it helps them reach their goals.

Defining interactions between agents depends on answers to the following questions: What is the nature of their goals? What are their resources? Which skills do they possess to fulfill these goals? Several criteria can be used to classify interactions. These criteria include the nature of the goals pursued by the agents, their relationship to external resources, and their individual skills with respect to the task at hand:

• Typically, agents are engaged in competitive tasks when their goals are con­tradictory, whereas they cooperate or co-evolve when their individual goals are compatible (that is when the satisfaction of a goal by an agent does not interfere with the possibility of satisfying another goal by another agent). Maintaining the balance between electricity supply and generation is an example of problem where cooperation is essential.

• External resources include all environment elements that agents need to satisfy a goal, such as raw materials, energy, available amounts of space and time, etc. For example, every energy source or power line has a limited capacity. Limited resources can lead agents to conflicts as they will likely need the same resources at the same moment and at the same place than other agents. Such conflictual situations can generally be resolved by the coordination of agent actions.

• The last criterion relates to whether the task can be pursued by a single agent rather than by a group of agents, and if each one of them has the appropriate skills to perform its subtask. An energy source can for example not store energy, and neither does a load.

To enable interoperability, interactions are structured and follow common rules called protocols. Basic and common types of interactions are requests, queries, subscriptions, and propositions. An example is the FIPA-Request protocol [46]: an agent can formulate a request, that other agents can accept or refuse (Fig. 15.20).

Those interactions are limited, and combinations of them are often used instead. There are several types of such complex interaction protocols: contracting, auc­tions, bargaining, voting, and brokering.

• The contract-net protocol is an example of contracting, defined in FIPA spec­ification SC00029 [47]. This task-sharing protocol consists in a collection of agents forming a contract network. Two categories of agents are distinguished: the manager, and contractor agents. A typical round (see Table 15.3) starts with a call for proposals sent by the initiator. A deadline can be set to limit the duration spent waiting for answers. Contractors (participants) can then emit proposals (prices, time to execute an action, etc.) or refuse. The initiator eval­uates the proposals and selects zero, one or several agents to perform the task to be fulfilled. The selected participants are free to accept or refuse this offer.

• Agents can interact and distribute tasks through auctions. Four main types of auctions are commonly used: English, Dutch, sealed first price or Vickrey, and Walrasian auctions.

English auctions are the most common ones. Participants bid openly against each other, with each subsequent bid higher than the previous one. A reser­vation price (the minimum price) may be set by the auctioneer. The auction ends when no participant is willing to bid further. FIPA defines a specification for English auctions in XC00031 [48].

– In Dutch auctions, the auctioneer starts with a high price which is lowered until some participant accepts the announced price. This type of auctions is also defined by FIPA in its XC00032 specification [49].

– With sealed first-price auctions, all bidders simultaneously submit their bids, and the winner is the one with the highest bid. Bidders can only submit a single bid. Vickrey auctions are identical except that the winner pays the second highest submitted price [50].

– Walrasian auctions are more complex and enable matching supply and demand in a market of perfect competition. A market clearing price is set so that the total demand equals the amount of sold goods, and leads to a general equilibrium [51]. This type of auctions was proposed for use on electricity markets using locational margin pricing [52].

• Bargaining is an alternative to auctions for pricing goods, i. e., when prices are not fixed and can be negotiated. The goods can for example be split into several parts and be themselves subject to bargaining. As humans, agents can employ various strategies to reach their goals.

• Interactions can also happen under the form of votes. Voting protocols, such as Robert’s rules of order (RONR) [53], define procedures for conducting votes

Table 15.3 A summary of the conversation between the initiator and the participants (con­tractors) in a contract-net protocol according to the FIPA specification

Initiator

Direction

Participants

Call for proposals Accept or reject proposals

Propose or refuse

Inform of the end/result of the round or of a failure

between agents. Voting can be used to take decisions when votes are very simple (e. g., yes or no). Similarly to votes during elections, various rules can be adopted for selecting the winner(s).

• Another interaction type specified by FIPA is brokering [54]. An agent can for example request a broker to find other agents who can answer a query; the broker would then relay the answer back to the initiator.

Numerous other interaction protocols, sometimes derived from domains such as game theory, can be employed. Custom interactions can for example be based on Petri nets; consensus theory can be used for reaching a group agreement even in the presence of faults [55, 56]; the Shapley value can help finding solutions to cooperative games [57, 58]; etc.

Leave a reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>