Decentralized decision-making on robotic networks with hybrid performance metrics

Abstract

The past decade has witnessed a rapidly growing interest in decentralized algorithms for collective decision-making in cyber-physical networks. For a large variety of settings, control strategies are now known that either minimize time complexity (i.e., convergence time) or optimize communication complexity (i.e., number and size of exchanged messages). Yet, little attention has beed paid to the problem of studying the inherent trade-off between time and communication complexity. Generally speaking, time-optimal algorithms are fast and robust, but require a large (and sometimes impractical) number of exchanged messages; in contrast, communication optimal algorithms minimize the amount of information routed through the network, but are slow and sensitive to link failures. In this paper we address this gap by focusing on a generalized version of the decentralized consensus problem (that includes voting and mediation) on undirected network topologies and in the presence of “infrequent” link failures. We present and rigorously analyze a tunable, semi-hierarchical algorithm, where the tuning parameter allows a graceful transition from time-optimal to communication-optimal performance (hence, allowing hybrid performance metrics), and determines the algorithm's robustness, measured as the time required to recover from a failure. An interesting feature of our algorithm is that it leads the decision-making agents to self-organize into a semi-hierarchical structure with variable-size clusters, among which information is flooded. Our results make use of a novel connection between the consensus problem and the theory of gamma synchronizers. Simulation experiments are presented and discussed.