Beyond Consensus: A Distributed Optimization Approach for Complex Coordination in Large-scale Dynamic Networks
Abstract
Consensus algorithms and graph theory have played a significant role in the study of networked systems for more than half a century. For example, they have developed an understanding of how self-organized behaviors, such as bird flocking, fish schooling, synchronization, and population agreement, can emerge through local interactions. Furthermore, they have been instrumental in the development of distributed algorithms for a wide variety of applications in multi-agent networks, such as formation control, rendezvous, robot coordination, and distributed estimation. Central to all these applications is the notion of achieving an agreement. Agreement means that every agent in the population shares a joint decision, opinion, or value. Thus consensus algorithms, by providing a distributed mechanism to achieve agreement, have established a systematic framework for designing distributed controllers whose coordination objective can be formalized by the agreement on some quantity, e.g., time, position, direction, etc. However, while consensus has shown to be a very versatile and widely applicable form of coordination, many problems cannot be cast as an agreement problem and therefore are not suitable for consensus algorithms. The goal of this project is to develop a theoretical framework for the design and analysis of distributed algorithms that simultaneously coordinate, control, and optimize agents in networks of interconnected dynamical systems. Our work seeks to move past the computation of a shared reference --as consensus algorithms do-- and develop the next generation algorithms that can achieve more sophisticated coordination schemes, guaranteeing efficiency in real-time, adapting to the environment, while ensuring a stable and robust behavior of the overall system. To achieve this goal, this project will use mathematical optimization as a tool for characterizing the desired coordination scheme, and as a mean for developing the algorithm that performs it. More precisely, this project will use an optimization problem to encode --within its objective function and constraints-- the required coordination goals we would like the whole system to achieve. After formulating the problem, this project will leverage the vast variety of distributed optimization algorithms that exist today (Gradient Descent, Primal-dual, ADMM, etc.) to develop coordination algorithms that can distribute (in real-time) the computation of the input that each agent requires to achieve the coordination goal. However, without accounting for the dynamics of each agent and its interconnections, the real-time computation of these set-points can render the system unstable. This project will tackle this challenge by combining tools from optimization theory, such as convexity and monotonicity, and tools from control theory, such as robust analysis and integral quadratic constraints, to analyze the effect of the interactions between physical dynamics and optimization algorithms. More precisely, this project will develop a systematic study to characterize: (1) the efficiency and coordination properties of the steady-state, (2) sufficient conditions for convergence, (3) bounds on the rate of convergence, and (4) the robustness of the combined optimization algorithm (cyber) + dynamic agents (physical) system. The successful execution of this project will provide a systematic design framework of distributed algorithms for the efficient coordination of large-scale multi-agent systems. Furthermore, it will offer a foundational theoretical framework for studying the stability, performance, and robustness of system that combine continuous time dynamics and discrete time optimization algorithms. In particular, it will enable control theory with mechanisms to simultaneously compute and update optimal set-points in real-time without affecting system stability, and it will allow optimization algorithms to run faster without the need to worry about physical system dynamic
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Oct 23, 2018
- Source ID
- W911NF1710092
Entities
People
- Enrique Mallada Garcia
Organizations
- Army Contracting Command
- Johns Hopkins University
- United States Army