The roles that have been developed in the Role view are the fundamental abstractions that decouple the functional aspects of the system from the agents. However, some functional aspects require the collaboration of several agents in order to be fulfilled and these collaborations must be specified by the system designer in one way or another.
The general purpose of any interaction between agents in a multiagent system is conflict resolution. Therefore, I will now describe how a system engineer can track down the abstract ideas behind the conflict resolution process into a concrete implementation. To this end, we shall decompose the interaction design process into three layers of abstraction: the intent layer, the protocol layer and the transport layer. The design process thus proceeds from the most abstract level towards an implementation by refining and extending the concepts on the next higher level.
The intent layer is the highest level of abstraction of the interaction design process where the system designer specifies the general nature of the interaction process, i.e. the purpose of the interaction. The interaction purpose describes why the agents interact with one another. For example, the purpose of interaction can be co-operation where the agents will usually work together to jointly solve a given problem. The agents are thus usually not self-interested as long as the overall system task is solved. A typical example for such a situation is decomposition. This interaction scheme achieves a hierarchical decomposition of the overall system task into sub-tasks. Ideally, these sub-tasks are independent from each other and can thus be worked on separately. Whether a task decomposition is feasible usually depends on the structure of the problem domain which is mainly characterized by its coherence. A very dense problem space is usually non-separable i.e. it cannot be split into several parts and is thus resistant against task decomposition. A separable problem space, on the other hand, often offers a natural decomposition into several independent parts that can be worked on in parallel.
Therefore, task decomposition is usually in suited for separable problem domains where the decomposition requires some sort of explicit co-ordination. A certain degree of direct interaction between the agents is desirable but not necessary. The approach scales rather well and can therefore be used in small agent systems as well as in larger ones. The co-operative behavior that is necessary to achieve a smooth task decomposition can either be built into the agents by the designer or it can develop over time in that the agents learn that co-operative behavior usually pays.
Another possible purpose of agent interaction is competition. In that case, the agents usually interact to optimize an external property and simulate a market-place where (abstract) prices for resources are negotiated. Ideas such as Market-Oriented Programming are attempts to capture problems of distributed resource allocation with little information. The major advantage of these approaches is that the agents need not provide internal information to external authorities as the only information that is exchanged is the price. Market-based mechanisms can be implemented in a centralized form where the agents interact with a matchmaker agent that is responsible for bringing together sellers and buyers. This form of Market-Oriented Programming has the advantage that the degree of communication is low because all agents are linked to the matchmaker. Furthermore, the trade can be performed anonymously. In its decentralized form, each agent is linked to any other potential trading partner and the agents negotiate directly without using an intermediate matchmaker. Although this approach has a higher degree of communication overhead it has the advantage that no global pricing scheme takes places which can help the individual agents to increase their profits.
In any case, Market-Oriented approaches are well suited for competitive agent societies that interact directly. The structure of the problem domain is not as relevant but the idea of a market suggests that a separable domain is preferable. Whereas a decentralized market scheme is suitable for small agent societies, a centralized scheme scales rather well as long as the matchmaking process is sufficiently simple and can thus be better used for larger societies.
Another high level decision that must be made before going into more specific details of the interaction design is the mode of interaction that will be pre-dominant in the application. The agents in the multiagent system either interact directly, for example by direct peer-to-peer communication or they interact indirectly via the environment. Direct interaction usually requires some facilitator that brings together the agents that want to interact with each other. Such a service is often provided by the agent management framework, e.g. FIPA. Indirect interaction, on the other hand, is typical for a real or a virtual environment where the agents meet for some purpose. It is not limited to verbal communication alone; the agents can communicate without explicit message exchange making it more flexible and suitable for agents that have only limited communication skills.
The last important requirement to be analyzed on this level of abstraction are scalability requirements. Scalability is of the interaction scheme is an important issue that has seldom been addressed in the existing literature. In small systems, it is feasible that any agent can communicate with any other agent in the system. But as the systems grows, the exponential growths of message exchange that is introduced into the system can easily become prohibitive. Designing a system that works well for 10 agents is often a straightforward task; however, scaling the system up to, say, 10000 agents is often a completely different matter and may require a re-design of major parts if the operational size of the system was neglected during the design and test phase. The question of scalability is usually handled in the Society view of the system but it also play are role in the design of the interaction schemes. If the system is likely to be large, it is necessary to find scalable forms of interaction in order to ensure later the scalability of the entire system
After these high level requirements on the interaction processes have been laid out, the system designer should have a fairly good -- although still very rough -- idea about how to proceed. Therefore, we can now turn the a more specific characterization of the interaction schemes.
Protocols are means to describe the general control flow within an interaction. Generally, an interaction protocol consists of two distinct phases. In the first phase, the agents (or at least one of the agents) must be able to signal a request that it wants to start an interaction scheme with one or more other agents. This part of the interaction is usually covered by the agent framework such as and it will therefore not be treated in this section.
Another aspect that I would like to mention only briefly in this section is the problem of the mutual understanding between agents from different sources. Several agent communication languages have been proposed, but it seems that the KQML (Knowledge Query and Manipulation Language) has become a de-facto standard as agent communication language. However, I will only give a short introduction to the basic ideas of the KQML and direct the interested reader to the original sources.
The goal of the KQML project is to develop a method for distributing information among different systems that clearly separate the semantics of the domain-independent protocol from the semantics of the domain-dependent message. KQML messages have a fixed structure that allows each receiving agent to understand the message structure. To understand the content of the message, the agent must have additional knowledge.
The basic structure of any KQML message is the following:
(<KQML-Performative>
:sender <word>
:receiver <word>
:language <word>
:ontology <word>
:content <expression>
...
)
Each message consists at least of a so-called performative. Performatives were introduced in speech act theory to describe the illocutionary force (i.e. the intended meaning) of an utterance. Speech act theory was discovered by multiagent researchers as a valuable tool to describe the meaning of messages that are exchanged between agents.
The structure of a KQML message is divided into several fields that have fixed semantics. In the above example, the :language, :ontology, :ontology and :content field define the language in which the message is expressed, the vocabulary of the language and the message itself, respectively. The content language can be anything from user defined data structures up to LISP or PROLOG Programs or SQL queries. One of the most common content languages is the Knowledge Interchange Format (KIF).
KQML messages or any other types of messages define single messages that are exchanged between the agents, a more complicated matter is to organize the orderly exchange of sequences of messages. Therefore, we will no turn to the main part of this section and discuss how these interaction protocols can be specified in a natural and manageable way.
For an example of an interaction protocol, consider an English auction. There, an auctioneer offers a product at a particular price to a group of bidders. Each of the bidders individually decides to accept that price or to decline the offer. If one of the bidders accepts the current price, the auctioneer raises the price by a fixed rate and asks the group of bidders again if any of them accepts the new price. If this is the case, the price is raised again and the cycle repeats until none of the bidders is willing to pay the current price. Then, the last bidder who accepted the price is given the product.
In this example, we can identify the major elements of interaction protocols. First, we can separate the participating agents into different groups. In this case, we have two groups: the auctioneer and the bidders. Each group has a set of associated incoming and outgoing messages an internal functions that decide about their next action. We will refer to the set of messages and behaviors that are associated with a group of agents as a role that can be played by an agent. Please note that the roles that are discussed in this view are interaction roles as opposed to functional roles as they were discussed in the Role view. Note also that just with functional roles, agents are not limited to a single interaction role. For example, the auctioneer in the English auction can be a bidder in another auction at the same time.
The second important aspect of an interaction protocol besides the participating roles, is the temporal ordering of function evaluation and the messages that are exchanged. For example, it would not make sense or would be impossible for the bidder to decide on an offer and to decline it before it has even received the offer. Therefore, the interaction protocol determines the flow of control within each role as well as between different roles.
The final step in the interaction design process is to map the abstract messages that have been defined in the protocol specification onto the concepts of a concrete agent framework or operating system. Due to the wast number of different ways that have been proposed as message exchange methods, I will only pick two approaches that are very common in multiagent systems in order to illustrate the typical problems that are dealt with on this level of abstraction.
A straightforward way to implement a message exchange mechanism between two agents is surely to use simple message passing between the participating agents. In this approach, each agent has a unique identification tag and an agent that wants to send a message to another agent adds this tag to the message before the message is handed over to the message passing system that is responsible for delivering the message to the addressee. This sort of message passing is usually referred to as one-to-one or point-to-point communication. Often, it is convenient to allow a single message to be delivered to several receivers at the same time, i. e. the sender need not re-send the same message to each receiver one after the other. While this multicast option is only a matter of convenience, a broadcast message is substantially different. In the case of a broadcast, the message is delivered to all agents that are known to the communication system, i. e. the sender of a broadcast message does not know which other agents will finally receive the message that is sent out as a broadcast message. This is comparable to the situation of a radio or television station that is ultimately unaware who receives the program that is broadcasted.
Another important aspect of direct message passing is whether the messages are sent and received synchronously or asynchronously. In the first case, a potential receiver must enter an explicit waiting state before it can receive any messages while in the second case, a message can arrive at any time in the addressees control flow. Hence the label asynchronous messages in this respect.
Besides one-to-one and one-to-many (broadcast) message passing, a second communication architecture is quit common in agent-based systems: blackboards. Blackboard architectures date back to the early days of distributed problem solving and have undergone intensive research since then. In its generic form, several agents are connected to a central authority that encapsulates a particular data structure. A transaction monitor shown in the figure is responsible for controlling the access to the joint data structure and to ensure the validity of each access. Each of the agents connected to the blackboard can read and manipulate the joint data. However, the perception (reading) of the data is not necessarily the same for all agents. Each agent receives only data that has undergone a filtering process that limits the perception of this agent. This individualized scheme enables the designer for example to use blackboard architectures as the basis for distributed virtual worlds. Blackboards are suitable for a wide range of problem domains that have a non-separable structure. The approach works for either competitive as well as co-operative settings and is not limited to a particular form of interoperation. Furthermore, blackboard architectures usually scale well and are thus suitable for large agent societies. As we have said above, blackboards can be used to implement virtual words and thus simulate a indirect interoperation scheme.