Coordination in multi-agent systems

To make coordination in multi-agent systems, we have to identify several characteristics. First, we have to identify the common problems that underlie any coordination situation. then we have to choose the mechanism to solve the coordination problem, a general coodination mechanisms that can be applied to a variety of situations. Finally, we have to focus in the applicability and usability of a given coordination mechanism. Identify the factors determining the applicability of the coordination mechanism. For instance, the numbe of agents in the system environment or the rate of change in the environment.

Identifing the common problems or reasons to any coordination situation:

[1 Jennings, 1996] and [2 Nwana, 1996] give many reasons that might necessitate coordination in multi-agent systems. The more important are:

• Meeting global constraints: If there are global budget limits, then agents must make agreements.
• Distributed information, expertise or resources: Often, a task cannot be performed by a single agent alone. If the required capabilities are distributed among the agents, coordination is necessary.
• Dependencies between the agents' actions: For instance, different tasks may need the same resources or there may exist a precedence relation between tasks.
  

The coordination can be seen of the point of view of an individual agent [3 Decker and Lesser, 1994]. Based on the definition of coordination given by [1 y 2], that is, that coordination is the act of managing interdependencies between activities. [3] say that there is a coordination problem if one of the following conditions is met:

• The actions agents affects the performance.
• The order of the actions affects performance.
• The execution time affects the performance.

We can also find general coordination processes that occur in many domains:

• Coordinated goal selection.
• Coordinated resource allocation.
• Coordinated sequencing (one activity after the other) and synchronizing (activities at the same time).

[5 Durfe, 2001] concludes that the applicability of every coordination mechanism has its limits:

It does not possible, however to devise a coordination strategy that works well under all circumstances; whatever strategy we adopt, certain situations can stress it to the breaking point.

[5] Identifies three varying properties (dimensions) of an interaction situation: The agent population, the task environment and the solution propierties.

The most obvios properties that impact the usability of a coordination strategy are:

Agent population: Quantity, the number of agents. Heterogeneity, agents can have different capabilities, internal architectures and communication languages. Complexity, how predictable the agents are.

Task environment: Degree of interaction, large and small groups of agents. Dynamics, The rate at which the environment changes. Distributivity, tasks can originate centrally or distributively.

Solution properties: Quality, the quality of a solution by judging how well it coordinates agent interactions (how efficient it is utilizing agent resources). Robustness, changes in the environment invalidate the plans or goals of agents. Overhead limitations, communication bandwidth may be limited.