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

分布式多智能体连续时间优化：不平衡有向图和约束网络博弈

• 批准号: 1920798
• 负责人: Wei Ren
• 金额: $ 38万
• 依托单位: University of California-Riverside
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-09-01 至 2023-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1920798&HistoricalAwards=false
• 关键词: Distributed; Multi; agent; Continuous; time

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.

多代理系统有许多应用程序。分布式连续的时间优化算法在多代理系统中至关重要，并且可以作为连续的时间求解器，以提供优化问题的分布式解决方案。尽管最近在分布式连续时间优化方面取得了进展，但现有结果主要假设一个平衡的网络拓扑或图形，并且代理人无私地瞄准了团队最佳性。简而言之，如果对于每个代理商，将信息发送给代理的团队成员的数量等于接收来自代理信息的团队成员的数量，则图形是平衡的。不幸的是，实际上，由于异质性，不均匀的通信/传感能力和/或感应有限的视野，相互作用（通信或传感）图通常是指向和不平衡的。在某些现实世界中，代理商可能是自私的，并且希望根据对手的行动（非合作式网络游戏）来优化自己的成本功能，以优化自己的成本功能。尽管在不平衡的有向图和分布式解决方案上对受约束的网络游戏进行了分布式优化的最新结果，但它们仍处于原始阶段，具有不切实际的假设和限制性限制。在不平衡的有向图上分布式优化的现有结果主要依赖于通信。但是，在某些应用程序中，通信可能无法可用或可取（例如，部署在拒绝或不友好环境中的机器人），而代理人必须仅依靠本地传感（例如，通过板上传感器进行相对位置测量）而不是通信。现有的关于分布式一般游戏的结果，其中包含有关对手行动的不完整信息，主要假设代理商和固定的NASH平衡没有耦合的约束。但是，实际上，由于配额限制，能源平衡或市场纪律，游戏中通常存在耦合的限制，而纳什均衡可能会随着时间的推移而演变，以响应实时变化。当代理商之间的图形不仅是不平衡的定向，而且切换时，这些问题构成了重大挑战，并变得更具挑战性。不幸的是，尽管它们的相关性和重要性，但这些问题在很大程度上尚未探索。该提案的目的是解决由不平衡的有向图造成的现实挑战，并仅通过本地信息和本地互动而在分布式连续的时间优化中限制了网络游戏。该提议包括三个推力。第一个推力是在不平衡的有向图上进行分布式连续时间优化。 PI将设计和分析新颖的非平滑分布式优化算法，这些算法可用于切换不平衡的定向图，并适合仅依靠邻居之间的本地感应的应用，而无需进行通信。 PI将通过一般限制来解决此案，并涉及随时间变化的成本功能和约束。第二个推力是在分布式连续时期约束的网络游戏上。 PI将设计和分析新颖的分布式NASH平衡，以寻求通用游戏的算法，并提供有关对手的行动，以解决耦合非线性约束的动作，实时跟踪动态NASH随时间发展的动态NASH平衡，以及不平衡的定向图。第三个推力是机器人网络上的实验演示。拟议的研究将解决分布式控制和优化方面的许多开放问题，并在多机构系统中显着提高理论和应用。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛影响的评估来支持的。

项目成果

Distributed Continuous-Time Algorithms for Optimal Resource Allocation With Time-Varying Quadratic Cost Functions

• DOI: 10.1109/tcns.2020.3020972
• 发表时间: 2020-12
• 期刊: IEEE Transactions on Control of Network Systems
• 影响因子: 4.2
• 作者: Bo Wang;Shan Sun;W. Ren

Robust Distributed Average Tracking for Double-Integrator Agents Without Velocity Measurements Under Event-Triggered Communication

• DOI: 10.1109/tcns.2020.3038844
• 发表时间: 2021-06
• 期刊: IEEE Transactions on Control of Network Systems
• 影响因子: 4.2
• 作者: Yong Ding;W. Ren;Yu Zhao

A Scaling-Function Approach for Distributed Constrained Optimization in Unbalanced Multiagent Networks

• DOI: 10.1109/tac.2021.3131678
• 发表时间: 2022-11
• 期刊: IEEE Transactions on Automatic Control
• 影响因子: 6.8
• 作者: Fei Chen;Jin Jin-Jin;Linying Xiang;W. Ren

Distributed economic dispatch via a predictive scheme: Heterogeneous delays and privacy preservation

• DOI: 10.1016/j.automatica.2020.109356
• 发表时间: 2021
• 期刊: Autom.
• 作者: Fei Chen;Xiaozheng Chen;Linying Xiang;W. Ren

Distributed Time-Varying Optimization With State-Dependent Gains: Algorithms and Experiments

• DOI: 10.1109/tcst.2021.3058845
• 发表时间: 2021-03
• 期刊: IEEE Transactions on Control Systems Technology
• 影响因子: 4.8
• 作者: Shan Sun;Yifan Zhang;Peng Lin;W. Ren;J. Farrell