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

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

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.