In most multiagent systems with communicating agents, the agents have the luxury of using reliable, multi-step negotiation protocols (see [1] for instance). They can do so primarily when communication is reliable and the cost of communication relative to other actions is small. For example, in Cohen's convoy example [2], the communication time required to form and maintain a convoy of vehicles is insignificant compared to the time it takes the convoy to drive to its destination. Similarly, message passing among distributed information agents is typically very quick compared to the searches and services that they are performing. Thus, it makes sense for agents to initiate and confirm their coalition while guaranteeing that they will inform each other if they have trouble fulfilling their part of the joint action.
Conversely, this paper considers multiagent environments with unreliable, high-cost communication. For example, if there is only a single, low-bandwidth, unreliable communication channel for all the agents, and if the agents must sacrifice valuable resources in order to communicate, then although inter-agent communication may be beneficial, the agents' behaviors must not depend upon it.
One clear example of such an environment is the Soccer Server--a widely used robotic soccer simulator--with a single, low-bandwidth, unreliable communication channel for all 22 agents and with high communication costs [8]. We use this domain for the research reported here. Another example domain is one that uses aural communication in crowded settings. Both people and robots using aural sensors ( [4]) must contend with multiple simultaneous audible streams. They also have a limit to the amount of sound they can process in a given amount of time, as well as to the range within which communication is possible. A third example of such an environment is arbitrarily expandable systems. If agents aren't aware of what other agents exist in the environment, then all agents must use a single universally-known communication channel, at least in order to initiate communication.
This paper presents techniques for dealing with the obstacles to inter-agent communication in such environments, particularly those with several teams of agents.