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

多智能体系统有许多应用。分布式连续时间优化算法在多智能体系统中是至关重要的，它可以作为连续时间求解器为优化问题提供分布式解决方案。尽管最近的分布式连续时间优化的进展，现有的结果主要是假设一个平衡的网络拓扑结构或图形和无私的代理人的目标是团队最优。简单地说，如果对于每个代理，向代理发送信息的团队成员数量等于从代理接收信息的团队成员数量，则图是平衡的。不幸的是，在现实中，交互（通信或感测）图往往是定向和不平衡的，由于异质性，不均匀的通信/感测功率，和/或感测有限的视野。在一些现实世界的应用中，代理人可能是自私的，并希望优化自己的成本函数相对于他们自己的行动，以响应他们的对手的行动（非合作网络游戏）。尽管最近的一些结果的分布式优化不平衡有向图和分布式解决方案的约束网络游戏，他们仍然处于原始阶段，不切实际的假设和限制性的限制。现有的不平衡有向图上的分布式优化结果主要依赖于通信。然而，在一些应用中，通信可能不可用或不期望（例如，部署在通信被拒绝或不友好的环境中的机器人）并且代理必须仅依赖于本地感测（例如，经由机载传感器的相对位置测量）而不是通信。现有的关于对手行动信息不完全的分布式一般博弈的结果主要假设代理之间没有耦合约束和静态纳什均衡。然而，在现实中，由于配额限制，能量平衡或市场纪律，纳什均衡可能会随着时间的变化而演变，在游戏中的代理之间往往存在耦合约束。这些问题提出了重大的挑战，变得更具挑战性的图形之间的代理不仅是不平衡的有向，但切换。不幸的是，尽管他们的相关性和重要性，这些问题在很大程度上是unexplored.The目标的建议是解决现实的挑战所造成的不平衡有向图和约束网络游戏在分布式连续时间优化只有本地信息和本地交互。该提案包括三个重点。第一个推力是分布式连续时间优化不平衡有向图。PI将设计和分析新的非光滑分布式优化算法，这些算法对切换不平衡有向图具有鲁棒性，并且适用于仅依赖于邻居之间的局部感知而无需通信的应用程序。PI将处理具有一般约束的情况以及涉及时变成本函数和约束的情况。第二个重点是分布式连续时间约束网络游戏。PI将设计和分析新的分布式纳什均衡寻求算法，用于解决耦合非线性约束，实时跟踪随时间演变的动态纳什均衡，以及切换不平衡有向图的不完全信息的一般游戏。第三个重点是机器人网络的实验演示。该研究将解决分布式控制和优化中的许多开放性问题，并显著推进多智能体系统的理论和应用。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.