Mixed Centralized/Decentralized Coordination Protocols for Multi-Agent Systems

Abstract

This thesis uses a mixture of centralized and decentralized architectures and algorithms to develop coordination strategies for multi-agent systems. Conventionally, centralized and decentralized methods are viewed as belonging to distinct paradigms, each with its own features and drawbacks, and multi-agent coordination algorithms are typically classified as being exclusively one or the other. However, emerging technologies such as cloud computing make it feasible to incorporate some centralization into an otherwise decentralized system, and one may ask how to embrace this mix of centralized and decentralized information that is rapidly being integrated into various systems such as the smart power grid, swarms of robots, and cyber-physical systems. To address this question, two problem domains are considered. The first is that of asynchronous coordination, in which agents generate and share information with arbitrary timing. The second concerns private coordination, in which teams of agents must work together without revealing sensitive information. In both cases, mixing centralized and decentralized information enables successful coordination despite the challenges imposed by asynchrony and privacy, and theoretical performance guarantees are derived for each algorithm that is developed. Complementing these theoretical developments, robotic experiments are included that demonstrate the utility of these algorithms in practice.