基于有向图的多智能体系统异步优化的分布式模型预测控制

《Automatica》:Distributed model predictive control with asynchronous optimization for multi-agent systems over directed graphs

【字体: 大 中 小 】 时间:2026年09月24日 来源:Automatica 6.2

编辑推荐:

   摘要 本文研究了在有向图上同时存在解耦约束和耦合约束条件下线性多智能体系统的分布式模型预测控制(DMPC)问题。通过利用拉格朗日方法和Fenchel共轭函数,我们将DMPC优化问题重构为其对偶问题,以处理耦合约束。为了解决该对偶问题,我们提出了一种新颖的非同步分布式推送求和

  

摘要

本文研究了在有向图上同时存在解耦约束和耦合约束条件下线性多智能体系统的分布式模型预测控制(DMPC)问题。通过利用拉格朗日方法和Fenchel共轭函数,我们将DMPC优化问题重构为其对偶问题,以处理耦合约束。为了解决该对偶问题,我们提出了一种新颖的非同步分布式推送求和约束优化(ADPSCO)算法,该算法消除了时钟同步的需求,显著提高了计算效率。在固定步长的温和条件下,我们证明了所提出的ADPSCO算法以??-线性收敛率??(??^??)收敛到最优解,其中0
引言

模型预测控制(MPC)因其能够系统地处理约束、优化性能和保证稳定性而引起了极大的研究兴趣(Liu等人,2019,Mayne,2014)。然而,传统的MPC采用集中式计算且可扩展性有限,不适用于多智能体系统(MASs)。为了解决这一局限,DMPC作为一种有前景的方法应运而生,它将优化任务分解,使所有智能体能够并发地求解各自的子问题。近年来,一些典型的DMPC问题已得到解决,如一致性(Li等人,2024)、编队(Xu等人,2025)和输出调节(Xiao等人,2024)。

在过去十年中,现有的优化方法为解耦约束下MASs的DMPC问题提供了有效的工具。然而,工程应用中的MASs通常受到耦合约束的影响,如耦合状态和输入约束。它们的出现使得每个智能体难以使用现有方法以分布式方式求解优化问题。这促使研究人员开发了一些值得注意的方法来应对这些问题。例如,针对无向图上具有耦合约束的MASs,已经提出了顺序DMPC方法(Müller等人,2012,Richards和How,2007,Trodden和Richards,2010,Trodden和Richards,2013)。顺序DMPC方法允许每个智能体按照预定义的顺序求解其优化问题,这在本质上限制了计算效率。为了解决这一问题,并行化DMPC方法(Gro?和Stursberg,2016,Trodden,2014)通过允许所有智能体同时求解其优化问题来扩展了顺序DMPC方法。然而,并行化DMPC方法要求每个智能体与其他所有智能体直接通信,这对网络提出了严格要求,即使对于中等规模的MASs也是如此。此外,值得注意的是,顺序和并行化DMPC方法都不能保证整体系统的 optimality(最优性)。

相比之下,拉格朗日对偶理论可以有效地处理耦合约束,同时实现整体系统的 optimality(最优性)。近年来,基于该理论开发了许多分布式算法,用于解决无向图上同时具有解耦和耦合约束的MASs的DMPC问题,如对偶分解(Doan等人,2011,Giselsson和Rantzer,2010)和交替方向乘子法(ADMM)(Bai等人,2022,Li等人,2021,Li等人,2023,Wang和Ong,2017),两者都以??(1/??)的子线性收敛率收敛。为了提高收敛率,发展了加速对偶分解(Giselsson等人,2013,Giselsson和Rantzer,2013)和快速对偶梯度(FDG)(Wang和Ong,2018)算法,但它们严格局限于无向图。此外,这些算法(Giselsson等人,2013,Giselsson和Rantzer,2013,Wang和Ong,2018)的收敛率已知为??(1/??2),仍然只是子线性的。最近,针对有向图上具有耦合约束的MASs的DMPC问题,还开发了一些其他分布式算法,如隐私保护的分布式投影梯度算法(Zhao等人,2023)和推送求和对偶梯度(PSDG)算法(Jin等人,2021),两者都实现了??(1/√??)的子线性收敛率。上述所有算法(Bai等人,2022,Doan等人,2011,Giselsson等人,2013,Giselsson和Rantzer,2010,Giselsson和Rantzer,2013,Jin等人,2021,Li等人,2021,Li等人,2023,Wang和Ong,2017,Wang和Ong,2018,Zhao等人,2023)仅实现了子线性收敛率,适用于无向或有向图上具有耦合约束的DMPC问题。相比之下,对于具有耦合线性等式约束的优化问题,ADMM在强凸性下实现了??-线性收敛率(Nishihara等人,2015)。由于具有线性收敛率的算法需要更少的迭代和计算时间,因此它们在实际应用中更加理想。

从实现角度来看,上述所有算法(Bai等人,2022,Doan等人,2011,Giselsson等人,2013,Giselsson和Rantzer,2010,Giselsson和Rantzer,2013,Jin等人,2021,Li等人,2021,Li等人,2023,Nishihara等人,2015,Wang和Ong,2017,Wang和Ong,2018,Zhao等人,2023)本质上属于同步算法,因为它们需要时钟同步。需要注意的是,同步算法可能导致迭代较快的智能体产生显著的同步等待时间,从而降低整体优化效率。因此,开发具有线性收敛率的非同步算法更为理想,因为它们不仅减少了迭代次数,还消除了时钟同步的需求,从而提高了优化效率。然而,据我们所知,针对有向图上同时受解耦和耦合约束的MASs的DMPC问题,这类非同步算法仍然相对未被充分探索。

基于上述观察,本文开发了一种具有非同步更新的ADPSCO算法,以在有向图上实现具有解耦和耦合约束的MASs的DMPC问题的??-线性收敛率。主要贡献总结如下:

(1) 开发了一种梯度校正一致性协议来处理对偶变量上的非负正交约束。基于该协议,结合新提出的非同步对偶梯度跟踪技术和推送求和技术,开发了一种新颖的ADPSCO算法,以非同步和分布式的方式求解DMPC问题的对偶问题。在我们的增广有向图的解析框架下,我们证明了所提出的ADPSCO算法以??-线性收敛率??(??^??)收敛到最优解,其中??∈(0,1),前提是固定步长保持在指定的上界范围内。

(2) 与为无向图设计的具有子线性收敛率的算法不同,如对偶分解(Doan等人,2011,Giselsson等人,2013,Giselsson和Rantzer,2010,Giselsson和Rantzer,2013)、ADMM(Bai等人,2022,Li等人,2021,Wang和Ong,2017)和FDG算法(Wang和Ong,2018),我们的ADPSCO算法具有??-线性收敛率,适用于有向图,这更为通用且具有挑战性。此外,与具有子线性收敛率的PSDG算法(Jin等人,2021)相比,我们的ADPSCO算法不仅以更少的迭代次数实现了??-线性收敛率,而且不需要时钟同步。这极大地提高了计算效率,使其在实际应用中更加理想。

(3) 为了进一步减少计算开销,开发了一种分布式终止准则,在解同时满足预定的次优性和耦合约束时终止ADPSCO算法。

(4) 最后,为有向图上同时受解耦和耦合约束的线性MASs开发了一种基于ADPSCO的迭代DMPC方法,并证明了其递归可行性和所得闭环系统的稳定性。

符号说明:设?、?^(??×??)、?^??和?^???分别表示非负整数集、??×??实矩阵集、??维欧几里德空间和非负正交。对于矩阵??,我们将其第(??,??)个元素、第??行、转置和谱半径分别记为??????、[??]??,∶、???和??(??)。对于实对称矩阵??,我们将其最大和最小特征值分别记为??_??????(??)和??_??????(??)。对于正定矩阵??,我们记为??>0。对于向量??,令??_??、???、‖??‖?、‖??‖?和‖??‖_??=√(???????),其中??>0,分别表示其第??个元素、转置、欧几里德范数、??范数和??-范数。对于两个向量??和??,?????(或?????)表示??中的所有元素都小于(或小于等于)??中的所有元素。对于集合??,令|??|表示其基数。符号?表示Kronecker积。对于两个满足??
问题描述

考虑具有以下??个智能体的线性MASs:
??_??(??+1)=??_????_??(??)+??_????_??(??),
其中??_??(??)∈?^{??_??}和??_??(??)∈?^{??_??}分别表示智能体??(??=1,2,…,??)的状态和输入。??_??∈?^{??_??×??_??}和??_??∈?^{??_??×??_??}分别为状态矩阵和输入矩阵。

假设1:对于每个智能体??,??_??(??)是可获得的,且(??_??,??_??)是稳定可控的。

每个智能体受解耦约束:
??_??(??)∈??_??,??_??(??)∈??_??,
其中??_????^{??_??}和??_????^{??_??}都是包含原点作为内点的紧凸集。此外,所有智能体都受DMPC优化约束。

为了实现对第2节中描述的控制目标,本小节制定DMPC优化策略。具体来说,给定预测时域??,??个智能体在每个时刻??协同优化各自的预测输入向量???_??(??)=[???_???(0|??),…,???_???(???1|??)]?,在解耦和耦合约束下最小化成本函数之和。这里,???_??(?|??)和???_??(?|??)分别表示时刻??的第?步预测输入和状态,它们沿着动力学???_??演化。

算法设计

在本小节中,我们提出一种ADPSCO算法来求解对偶问题(11)。

在非同步设置中,令??_??为智能体??的本地迭代索引。在第??_??次迭代时,我们为智能体??定义以下变量:
• 辅助变量:??_??^{??_??}、??_??^{??_??}、??_??^{??_??}∈?^{????}和??_??^{??_??}∈?;
• 对偶变量??的本地估计:??_??^{??_??}∈?^{????};
• 预测输入向量???_??(??)的更新值:???_??^{??_??}∈?^{????_??};
• 可行投影梯度:??_??^{??_??}∈?^{????}。

第??_??次迭代时相应的更新律设计如下:??_??^{??_??+1}=

迭代DMPC方法

对于给定的预测时域??,我们定义问题(9)的可行区域为?(??(??))={??(??):(9)可行},其中??(??)=[??_1?(??),…,??_???(??)]?。假设初始状态??(0)属于可行区域。在时刻??,从算法1获得的解表示为???_??^{??_??}=???_??(??)=[???_???(0|??),…,???_???(???1|??)]?。

取(32)中的第一个元素作为DMPC输入,即??_??(??)=???_??(0|??)。然后,基于算法1的迭代DMPC方法总结在算法2中。该

仿真例子

考虑改编自Zhu等人(2014)的具有20个智能体的线性MASs,它们被分为四组:第1组(智能体1-5)、第2组(智能体6-10)、第3组(智能体11-15)和第4组(智能体16-20)。每组的动力学描述如(1)所示,参数为:对于??=1,…,5,??_??=[0.2,1,0;0,1,0.5;0.1,0,0.1;0,0.1,0.2]且??_??=[1;0;0];对于??=6,…,10,??_??=[0,0.2,0.2;1,0,0.2;0,1,1.5]且??_??=[0;0;0.5];对于??=11,…,15,??_??=[0.7,0.8,0;0.1,0.7,0.1;0.1,0.1,0.5]且??_??=[0.2;0.1;0];对于??=16,…,20,??_??=[0,0,0.5;1,0,0.3;0,1,

结论

本文开发了针对有向图上同时受解耦和耦合约束的线性MASs的迭代DMPC方法。为了处理耦合约束,我们将原始优化问题重构为其对偶形式,并提出了一种新颖的ADPSCO算法来以非同步和分布式的方式求解它。我们证明了所提出的ADPSCO算法能够在无需同步等待的情况下实现??-线性收敛率。我们还开发了一种分布式

Pengbiao Wang于2020年获得中国东北大学控制理论与控制工程硕士学位,2024年获得中国北京理工大学控制科学与工程博士学位。自2024年8月起,他在中国香港城市大学担任博士后研究员。他的研究领域包括事件触发控制、模型预测控制、分布式优化、网络化系统与控制等。

Pengbiao Wang|Lu Liu|Gang Feng
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号