Distributed Multi-agent Continuous-time Optimization: Unbalanced Directed Graphs and Constrained Networked Games

University Of California-Riverside, Riverside CA

Investigators

Abstract

Multi-agent systems have numerous applications. Distributed continuous-time optimization algorithms are vital in multi-agent systems and can serve as continuous-time solvers to provide distributed solutions to optimization problems. Despite recent progress on distributed continuous-time optimization, the existing results primarily assume a balanced network topology or graph and the agents being selfless to aim for team optimality. Simply speaking, a graph is balanced if for each agent, the number of team members that send information to the agent is equal to the number of team members that receive information from the agent. Unfortunately, in reality, the interaction (communication or sensing) graph is often directed and unbalanced due to heterogeneity, nonuniform communication/sensing powers, and/or sensing with a limited field of view. In some real-world applications, the agents might be selfish and desire to optimize their own cost functions with respect to their own actions in response to their opponents' actions (noncooperative networked game). Despite some recent results on distributed optimization over unbalanced directed graphs and distributed solutions to constrained networked games, they are still at a primitive stage with unrealistic assumptions and restrictive limitations. Existing results on distributed optimization over unbalanced directed graphs primarily rely on communication. However, in some applications, communication might not be available or desirable (e.g., robots deployed in a communication denied or unfriendly environment) and the agents have to rely on only local sensing (e.g., relative position measurements via onboard sensors) instead of communication. Existing results on distributed general games with incomplete information about opponents' actions primarily assume no coupled constraints among agents and a stationary Nash equilibrium. However, in reality there often exist coupled constraints among agents in games due to quota restriction, energy balance, or market discipline, and the Nash equilibrium could evolve with time in response to real-time changes. These issues pose significant challenges and become even more challenging when the graph among agents is not only unbalanced directed but switching. Unfortunately, despite their relevance and importance, these issues are largely unexplored. The goal of this proposal is to address the realistic challenges caused by unbalanced directed graphs and constrained networked games in distributed continuous-time optimization with only local information and local interaction. The proposal consists three thrusts. The first thrust is on distributed continuous-time optimization over unbalanced directed graphs. The PI will design and analyze novel nonsmooth distributed optimization algorithms that are robust to switching unbalanced directed graphs and amenable to applications relying on only local sensing between neighbors without the need for communication. The PI will tackle the case with general constraints and the case involving both time-varying cost functions and constraints. The second thrust is on distributed continuous-time constrained networked games. The PI will design and analyze novel distributed Nash equilibrium seeking algorithms for general games with incomplete information about opponents' actions to address coupled nonlinear constraints, real-time tracking of a dynamic Nash equilibrium evolving with time, and switching unbalanced directed graphs. The third thrust is experimental demonstration on robotic networks. The proposed research will solve many open problems in distributed control and optimization and significantly advance theory and applications in multi-agent systems. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.