The role of information in multiagent coordination

The goal in networked control of multiagent systems is to derive desirable collective behavior through the design of local control algorithms. The information available to the individual agents, either attained through communication or sensing, invariably defines the space of admissible control laws. Hence, informational restrictions impose constraints on achievable performance guarantees. This paper provides one such constraint with regard to the efficiency of the resulting stable solutions for a class of networked resource allocation problems with submodular objective functions. When the agents have full information regarding the mission space, the efficiency of the resulting stable solutions is guaranteed to be within 50% of optimal. However, when the agents have only localized information about the mission space, which is a common feature of many well-studied control designs, the efficiency of the resulting stable solutions can be 1=n of optimal, where n is the number of agents. Consequently, in general such schemes cannot guarantee that systems comprised of n agents can perform any better than a system comprised of a single agent for identical environmental conditions. The last part of this paper highlights an algorithm that overcomes this limitation by allowing the agents to communicate minimally with neighboring agents.