Distributed Resource Allocation Algorithm for Second-order Multi-agent Systems in Continuous-time
-
摘要:
针对二阶多智能体系统中的分布式资源分配问题, 本文设计两种连续时间算法. 基于KKT (Karush−Kuhn−Tucker, 卡罗需−库恩−塔克)优化条件, 第一种控制算法利用节点局部不等式及其梯度信息来约束节点状态. 与上述梯度方法不同, 第二种控制算法包括一致性梯度下降法和固定时间收敛映射算子, 其中固定时间收敛映射算子确保算法的节点状态在固定时间收敛到局部约束集, 一致性梯度下降法目的是确保节点迭代到资源分配问题最优解. 两种控制算法都对状态无初始值约束, 且控制参数都是常数. 利用凸优化理论和固定时间李雅普诺夫方法, 分别分析了上述控制策略在有向平衡网络条件下的渐近和指数收敛性. 最后通过数值仿真验证了所设计算法在一维和高维资源分配问题的有效性.
Abstract:For the distributed resource allocation problem in second-order multi-agent systems (MASs), this paper proposes two continuous-time distributed algorithms. Based on the KKT (Karush-Kuhn-Tucker) optimal condition, the constrained state of each agent is ensured by applying the information of the local inequality constraints and its gradient in the first proposed control algorithm. Different from the previous gradient method, the second proposed algorithm consists of two parts: a consensus-based gradient descent algorithm and a fixed-time convergent projection operator, in which the projection operator plays a key role in ensuring local inequality constraints and the optimal solution of the distributed resource allocation problem is guaranteed by the gradient descent iteration. The above two proposed algorithms with constant control parameters is initialization-free. Based on convex optimization theory and fixed-time Lyapunov analysis, the asymptotic and exponential convergence results are given for weight-balanced directed network, respectively. Finally, the effectiveness of our proposed algorithm in one-dimensional and high-dimensional resource allocation problems is validated by several simulations.
-
表 1 案例1各节点参数
Table 1 System parameters in case 1
Agent $a_{i1}$ $a_{i2}$ $a_{i3}$ 功率约束 $d_i$ $x_i(0)$ 1 2 3 0.5 $[20,40]$ 45 40 2 1 4 1.5 $[25,35]$ 40 24 3 0.5 5 3 $[35,50]$ $25$ 35 4 1.5 2 1 $[25,45]$ 35 45 5 1 3.5 2.5 $[30,47]$ 30 28 6 1.5 4.5 2 $[28,42]$ 40 50 -
[1] Yang S F, Liu Q S, Wang J. Distributed optimization based on a multiagent system in the presence of communication delays. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2017, 47(5): 717-728 doi: 10.1109/TSMC.2016.2531649 [2] He X, Huang T W, Yu J Z, Li C J, Zhang Y S. A continuous-time algorithm for distributed optimization based on multiagent networks. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2019, 49(12): 2700-2709 doi: 10.1109/TSMC.2017.2780194 [3] Zhu Y N, Yu W W, Wen G H, Chen G R. Projected primal–dual dynamics for distributed constrained nonsmooth convex optimization. IEEE Transactions on Cybernetics, 2020, 50(4): 1776-1782 doi: 10.1109/TCYB.2018.2883095 [4] 洪奕光, 张艳琼. 分布式优化: 算法设计和收敛性分析. 控制理论与应用, 2014, 31(7): 850-857 doi: 10.7641/CTA.2014.40012Hong Yi-Guang, Zhang Yan-Qiong. Distributed optimization: Algorithm design and convergence analysis. Control Theory & Application, 2014, 31(7): 850-857 doi: 10.7641/CTA.2014.40012 [5] 谢佩, 游科友, 洪奕光, 谢立华. 网络化分布式凸优化算法研究进展. 控制理论与应用, 2018, 35(7): 918-927 doi: 10.7641/CTA.2018.80205Xie Pei, You Ke-You, Hong Yi-Guang, Xie Li-Hua. A survey of distributed convex optimization algorithms over networks. Control Theory & Application, 2018, 35(7): 918-927 doi: 10.7641/CTA.2018.80205 [6] 王龙, 卢开红, 关永强. 分布式优化的多智能体方法. 控制理论与应用, 2019, 36(11): 1820-1833 doi: 10.7641/CTA.2019.90502Wang Long, Lu Kai-Hong, Guan Yong-Qiang. Distributed optimization via multi-agent systems. Control Theory & Application, 2019, 36(11): 1820-1833 doi: 10.7641/CTA.2019.90502 [7] 杨涛, 柴天佑. 分布式协同优化的研究现状与展望. 中国科学: 技术科学, 2020, 50(11): 1414-1425 doi: 10.1360/SST-2020-0040Yang Tao, Chai Tian-You. Research status and prospects of distributed collaborative optimization. Scientia Sinica Technologica, 2020, 50(11): 1414-1425 doi: 10.1360/SST-2020-0040 [8] Nedic A, Ozdaglar A, Parrilo P A. Constrained consensus and optimization in multi-agent networks. IEEE Transactions on Automatic Control, 2010, 55(4): 922-938 doi: 10.1109/TAC.2010.2041686 [9] Bianchi P, Hachem W, Iutzeler F. A coordinate descent primal-dual algorithm and application to distributed asynchronous optimization. IEEE Transactions on Automatic Control, 2016, 61(10): 2947-2957 doi: 10.1109/TAC.2015.2512043 [10] Wang P, Lin P, Ren W, Song YD. Distributed subgradient-based multiagent optimization with more general step sizes. IEEE Transactions on Automatic Control, 2018, 63(7): 2295-2302 doi: 10.1109/TAC.2017.2763782 [11] Yang S P, Tan S C, Xu J X. Consensus based approach for economic dispatch problem in a smart grid. IEEE Transactions on Power Systems, 2013, 28(4): 4416-4426 doi: 10.1109/TPWRS.2013.2271640 [12] Xu Y, Han T R, Cai K, Lin Z Y, Yan G F, Fu M Y. A distributed algorithm for resource allocation over dynamic digraphs. IEEE Transactions on Signal Processing, 2017, 65(10): 2600-2612 doi: 10.1109/TSP.2017.2669896 [13] Yang T, Lu J, Wu D, Wu J F, Shi G D, Meng Z Y, et al. A distributed algorithm for economic dispatch over time-varying directed networks with delays. IEEE Transactions on Industrial Electronics, 2017, 64(6): 5095-5106 doi: 10.1109/TIE.2016.2617832 [14] Xing H, Mou Y T, Fu M Y, Lin Z Y. Distributed bisection method for economic power dispatch in smart grid. IEEE Transactions on Power Systems, 2015, 30(6): 3024-3035 doi: 10.1109/TPWRS.2014.2376935 [15] Li C J, Yu X H, Yu W W, Huang T W, Liu Z W. Distributed event-triggered scheme for economic dispatch in smart grids. IEEE Transactions on Industrial Informatics, 2016, 12(5): 1775-1785 doi: 10.1109/TII.2015.2479558 [16] Xing H, Fu M Y, Lin Z Y, Mou Y T. Decentralized optimal scheduling for charging and discharging of plug-in electric vehicles in smart grids. IEEE Transactions on Power Systems, 2016, 31(5): 4118-4127 doi: 10.1109/TPWRS.2015.2507179 [17] Li H Q, Lu Q G, Huang T W. Distributed projection subgradient algorithm over time-varying general unbalanced directed graphs. IEEE Transactions on Automatic Control, 2019, 64(3): 1309-1316 doi: 10.1109/TAC.2018.2849616 [18] Yang T, Yi X L, Wu J F, Yuan Y, Wu D, Meng Z Y, et al. A survey of distributed optimization. Annual Reviews in Control, 2019, 47: 278-305 doi: 10.1016/j.arcontrol.2019.05.006 [19] Zhang J Q, You K Y, Cai K. Distributed dual gradient tracking for resource allocation in unbalanced networks. IEEE Transactions on Signal Processing, 2020, 68: 2186-2198 doi: 10.1109/TSP.2020.2981762 [20] He X, Ho D W C, Huang T W, Yu J Z, Abu-Rub H, Li C J. Second-order continuous-time algorithms for economic power dispatch in smart grids. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2018, 48(9): 1482-1492 doi: 10.1109/TSMC.2017.2672205 [21] 张青, 弓志坤, 杨正全, 陈增强. 多智能体系统的自适应群集分布式优化. 控制理论与应用, 2019, 36(4): 666-672 doi: 10.7641/CTA.2018.80562Zhang Qing, Gong Zhi-Kun, Yang Zheng-Quan, Chen Zeng-Qiang. Distributed optimization for adaptive flocking of multi-agent systems. Control Theory & Applications, 2019, 36(4): 666-672 doi: 10.7641/CTA.2018.80562 [22] 周琪, 陈广登, 鲁仁全, 白伟伟. 基于干扰观测器的输入饱和多智能体系统事件触发控制. 中国科学: 信息科学, 2019, 49(11): 1502-1516 doi: 10.1360/SSI-2019-0105Zhou Qi, Chen Guang-Deng, Lu Ren-Quan, Bai Wei-Wei. Disturbance-observer-based event-triggered control for multi-agent systems with input saturation. Scientia Sinica Information, 2019, 49(11): 1502-1516 doi: 10.1360/SSI-2019-0105 [23] 杨彬, 周琪, 曹亮, 鲁仁全. 具有指定性能和全状态约束的多智能体系统事件触发控制. 自动化学报, 2019, 45(8): 1527-1535Yang Bin, Zhou Qi, Cao Liang, Lu Ren-Quan. Event-triggered control for multi-agent systems with prescribed performance and full state constraints. Acta Automatica Sinica, 2019, 45(8): 1527-1535 [24] 陈刚, 李志勇. 集合约束下多智能体系统分布式固定时间优化控制, 自动化学报, DOI: 10.16383/j.aas.c190416Chen Gang, Li Zhi-Yong. Distributed fixed-time optimization control for multi-agent systems with set constraints, Acta Automatica Sinica, DOI: 10.16383/j.aas.c190416 [25] 杨涛, 徐磊, 易新蕾, 张圣军, 陈蕊娟, 李渝哲. 基于事件触发的分布式优化算法, 自动化学报, DOI: 10.16383/j.aas.c200838Yang Tao, Xu Lei, Yi Xin-Lei, Zhang Sheng-Jun, Chen Rui-Juan, Li Yu-Zhe. Event-triggered distributed optimization algorithms, Acta Automatica Sinica, DOI: 10.16383/j.aas.c200838 [26] Deng Z H, Liang S, Yu W Y. Distributed optimal resource allocation of second-order multiagent systems. International Journal of Robust and Nonlinear Control, 2018, 28(14): 4246-4260 doi: 10.1002/rnc.4233 [27] Chen G, Li Z Y. A fixed-time convergent algorithm for distributed convex optimization in multi-agent systems. Automatica, 2018, 95: 539-543 doi: 10.1016/j.automatica.2018.05.032 [28] Dai H, Jia J P, Yan L, Fang X P, Chen W S. Distributed fixed-time optimization in economic dispatch over directed networks. IEEE Transactions on Industrial Informatics, 2021, 17(5): 3011-3019 doi: 10.1109/TII.2020.3010282 [29] Lin W T, Wang Y W, Li C J, Yu X H. Predefined-time optimization for distributed resource allocation. Journal of the Franklin Institute, 2020, 357(16): 11323-11348 doi: 10.1016/j.jfranklin.2019.06.024 [30] Cherukuri A, Cortes J. Initialization-free distributed coordination for economic dispatch under varying loads and generator commitment. Automatica, 2016, 74: 183-193 doi: 10.1016/j.automatica.2016.07.003 [31] Yi P, Hong Y G, Liu F. Initialization-free distributed algorithms for optimal resource allocation with feasibility constraints and application to economic dispatch of power systems. Automatica, 2016, 74: 259-269 doi: 10.1016/j.automatica.2016.08.007 [32] Li K X, Liu Q S, Yang S F, Cao J D, Lu G P. Cooperative optimization of dual multiagent system for optimal resource allocation. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2020, 50(11): 4676-4687 doi: 10.1109/TSMC.2018.2859364 [33] Deng Z H, Nian X H, Hu C. Distributed algorithm design for nonsmooth resource allocation problems. IEEE Transactions on Cybernetics, 2020, 50(7): 3208-3217 doi: 10.1109/TCYB.2019.2901256 [34] Li R R. Distributed algorithm design for optimal resource allocation problems via incremental passivity theory. Systems & Control Letters, 2020, 138: Article No. 104650 [35] Chen G, Guo Z J. Initialization-free distributed fixed-time convergent algorithms for optimal resource allocation. IEEE Transactions on Systems, Man, and Cybernetics: Systems, DOI: 10.1109/TSMC.2020.3005169 [36] Cherukuri A, Cortes J. Distributed generator coordination for initialization and anytime optimization in economic dispatch. IEEE Transactions on Control of Network Systems, 2015, 2(3): 226-237 doi: 10.1109/TCNS.2015.2399191 [37] Zhao T Q, Ding Z T. Distributed initialization-free cost-optimal charging control of plug-in electric vehicles for demand management. IEEE Transactions on Industrial Informatics, 2017, 13(6): 2791-2801 doi: 10.1109/TII.2017.2685422 [38] Guo Z, Chen G. Predefined-time distributed optimal allocation of resources: A time-base generator scheme. IEEE Transactions on Systems, Man, and Cybernetics: Systems DOI: 10.1109/TSMC.2020.2997697 [39] Wang D, Wang Z, Wen C Y, Wang W. Second-order continuous-time algorithm for optimal resource allocation in power systems. IEEE Transactions on Industrial Informatics, 2019, 15(2): 626-637 doi: 10.1109/TII.2018.2881974 [40] Liang S, Zeng X L, Hong Y G. Distributed sub-optimal resource allocation over weight-balanced graph via singular perturbation. Automatica, 2018, 95: 222-228 doi: 10.1016/j.automatica.2018.05.013 [41] Yang Q, Chen G, Ren J H. Continuous-time algorithm for distributed constrained optimization over directed graphs. In: Proceedings of the IEEE 15th International Conference on Control and Automation (ICCA). Edinburgh, UK: IEEE, 2019. 1020−1025 [42] Zhu Y N, Ren W, Yu W W, Wen G H. Distributed resource allocation over directed graphs via continuous-time algorithms. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2021, 51(2): 1097-1106 doi: 10.1109/TSMC.2019.2894862 [43] Deng Z H. Distributed algorithm design for resource allocation problems of second-order multiagent systems over weight-balanced digraphs. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2021, 51(6): 3512-3521 doi: 10.1109/TSMC.2019.2930672 [44] Deng Z H, Liang S, Hong Y G. Distributed continuous-time algorithms for resource allocation problems over weight-balanced digraphs. IEEE Transactions on Cybernetics, 2018, 48(11): 3116-3125 doi: 10.1109/TCYB.2017.2759141 [45] Deng Z H, Wang L. Distributed event-triggered algorithm for optimal resource allocation of second-order multi-agent systems. IET Control Theory & Applications, 2020, 14(14): 1937-1946 [46] Li S L, Nian X H, Deng Z H. Distributed resource allocation of second-order multiagent systems with exogenous disturbances. International Journal of Robust and Nonlinear Control, 2020, 30(3): 1298-1310 doi: 10.1002/rnc.4830 [47] Polyakov A. Nonlinear feedback design for fixed-time stabilization of linear control systems. IEEE Transactions on Automatic Control, 2012, 57(8): 2106-2110 doi: 10.1109/TAC.2011.2179869 -