The Role of Information in Distributed Resource Allocation
Jason R. Marden · IEEE Transactions on Control of Network Systems · 2016
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 submodular resource allocation problems with applications to covering problems. When the agents have full information regarding the system, 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 system, 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 control designs cannot guarantee that systems comprised of n agents can perform any better than a system comprised of a single agent for identical system conditions. The last part of this paper focuses on a specific resource allocation problem, a static sensor coverage problem, and provides an algorithm that overcomes this limitation by allowing the agents to communicate minimally with neighboring agents.