引用本文

时侠圣, 杨涛, 林志赟, 王雪松. 基于连续时间的二阶多智能体分布式资源分配算法. 自动化学报, 2021, 47(8): 2050−2060 doi: 10.16383/j.aas.c200968

Shi Xia-Sheng, Yang Tao, Lin Zhi-Yun, Wang Xue-Song. Distributed resource allocation algorithm for second-order multi-agent systems in continuous-time. Acta Automatica Sinica, 2021, 47(8): 2050−2060 doi: 10.16383/j.aas.c200968

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200968

关键词

二阶多智能体，分布式资源分配，初值自由，映射算子，一致性梯度下降 

摘要

针对二阶多智能体系统中的分布式资源分配问题, 本文设计两种连续时间算法. 基于KKT (Karush−Kuhn−Tucker, 卡罗需−库恩−塔克)优化条件, 第一种控制算法利用节点局部不等式及其梯度信息来约束节点状态. 与上述梯度方法不同, 第二种控制算法包括一致性梯度下降法和固定时间收敛映射算子, 其中固定时间收敛映射算子确保算法的节点状态在固定时间收敛到局部约束集, 一致性梯度下降法目的是确保节点迭代到资源分配问题最优解. 两种控制算法都对状态无初始值约束, 且控制参数都是常数. 利用凸优化理论和固定时间李雅普诺夫方法, 分别分析了上述控制策略在有向平衡网络条件下的渐近和指数收敛性. 最后通过数值仿真验证了所设计算法在一维和高维资源分配问题的有效性.

文章导读

随着控制技术的发展, 将控制技术与优化算法相结合, 以分布式方式求解网络优化问题成为近年来的研究热点[1-7]. 作为网络优化领域里一个重要分支, 资源分配在网络系统中有很广泛的应用, 例如能源系统中的经济调度和通讯网络中的网络利用率最优化等问题.

近些年来, 基于离散时间算法的分布式优化问题已经得到了一些很好的结果. 例如, 文献[8-10]等针对有约束或无约束最优协调问题设计了一种基于梯度的算法. 而对于强连通有向网络下的资源分配问题, 文献[11-13]等基于多智能体一致性理论, 分别设计一种基于余量和基于Push-sum (推和)的分布式优化算法. 更多离散时间算法可参考文献[14-19]及它们的引用文献, 其中收敛速度最快的为文献[17]的线性收敛, 但是依然无法预知其收敛时间. 另一方面, 随着信息物理系统和连续时间控制技术的发展[20-25], 利用基于连续时间的分布式控制策略也已被广泛应用于解决资源分配问题, 特别是其中的有限/固定/预定时间收敛理论, 更符合实际系统需求. 为了解决无向网络下的无约束资源分配问题, 基于多智能体一致性理论, 文献[26]设计了一种指数收敛速度二阶连续时间算法. 不同于文献[26]的渐近式收敛, 文献[27-30]分别设计一种基于固定时间和预定时间收敛的连续时间算法. 在此基础上, 文献[31-35]提出了一种考虑不等式约束的分布式算法, 该算法利用映射算子将节点状态限制在不等式约束集合内, 从而得到了一种无初值约束分布式算法, 并在文献[35]中实现了固定时间收敛. 与映射法不同, 文献[36-38]和文献[39]利用精确罚函数法将局部等式约束转移到目标函数中, 分别设计了一阶和二阶连续时间算法. 而对于有向网络下的资源分配问题, 也有很多学者提出了解决方法, 例如奇异摄动算法[40]、原始对偶算法[41]、映射法[42]、二阶连续时间算法[43]以及微分映射法[44].

从前面的讨论可以看出, 目前只有一阶分布式优化算法在连续时间和离散时间情况下都取得了显著的效果. 而有关二阶多智能体分布式优化算法的文献不是很多. 其中文献[26, 45-46]研究了无约束资源分配问题, 并没有将节点局部不等式约束考虑进来. 但在许多工程应用中, 节点的决策会受到局部约束, 这些约束可能来自安全考虑、生产能力、执行能力等, 如电力系统中发电机的输出功率的边界限制[1]. 文献[39]和文献[43]分别利用精确罚函数法和微分映射法解决了资源分配问题中的局部不等式约束. 但是上述两篇文献所提出的算法都对初始状态进行限定. 而这种初始化协调过程可能只适应于静态网络. 然而对于一个动态网络来说, 一旦网络发生变化或者节点生产约束发生突变时, 就必须重新分配资源配置更改. 因此这些优化算法重新启动时, 必须重新进行初始化协调, 这大大降低了它们的适用性. 此外, 文献[26, 39, 45-46]中考虑的都是无向网络.

然而, 由于通信延迟等造成的通信中断会使得无向网络变成有向网络, 进而可能会使得一些基于无向网络的分布式算法失效. 另外, 无向网络是有向平衡网络的一个特例, 在工程应用中, 有向平衡网络比无向网络也更易于实现, 因此研究有向平衡网络上的资源分配问题是有意义的. 由于二阶多智能体系统的广泛存在, 如: 移动机器人、发电机等, 本文考虑二阶多智能体的分布式资源分配问题. 针对有向平衡网络下的资源分配问题, 本文首先利用局部不等式及其梯度设计第一种算法, 其次利用固定时间理论和映射算子设计第二种算法, 其中映射算子用于处理不等式约束, 且确保此不等式在固定时间内即可满足, 此方法可推广到同类型带局部不等式约束的分布式优化问题中.

本文所提算法创新点如下:

1) 相比于文献[26, 45-46], 本文将二阶多智能体节点的局部不等式约束考虑进来;

2) 与文献[39]的无向网络相比, 我们研究有向平衡网络下的资源分配问题;

3) 相比于文献[43], 本文所提两种算法均对初始值无要求, 且分别实现渐近和指数收敛;

4) 针对节点局部不等式约束, 本文结合了固定时间收敛理论和映射算子, 使得收敛速度上会比单纯使用映射算子方法的算法要快, 并通过案例仿真可以验证此性质.

本文后续内容结构如下: 在第1节中, 将完成问题描述以及预备知识, 其中预备知识包括代数图论、固定时间收敛理论等; 在第2节中, 首先进行算法设计, 分别是渐近收敛算法和指数收敛算法, 其次给出相应的最优性引理以及各自算法的收敛性分析; 在第3节中, 给出3个仿真案例;本文的总结与展望放在第4节中.

图 1  案例1中算法(8)的各发电机曲线图

图 3  基于案例1数据的算法性能对比

图 10  案例3中算法(8)和(9)的收敛速度比较

本文针对有向平衡网络下的带约束分布式资源分配问题, 基于固定时间映射算子和基于多智能体一致性的梯度下降法, 设计了两种基于二阶多智能体系统的连续时间算法. 所设计算法对节点初始状态无约束, 并且控制参数全为常数. 通过对一维和二维资源分配问题数值仿真, 本文所提算法的有效性也得以保证. 然而在实际系统中, 通信网络通常会存在信息交互延迟, 而信息延迟给算法分析带来了很大的困难. 此外, 非平衡有向网络在实际系统中也是存在的, 所以在后续研究中, 我们将考虑由通信延迟等造成的有向非平衡网络下二阶多智能体资源分配问题.

作者简介

时侠圣

中国矿业大学信息与控制工程学院讲师. 主要研究方向为分布式协同优化和网络化系统. E-mail: shixiasheng@cumt.edu.cn

杨涛

东北大学流程工业自动化国家重点实验室教授. 主要研究方向为工业人工智能, 信息物理系统, 分布式协同控制和优化. 本文通信作者. E-mail: yangtao@email.neu.edu.cn

林志赟

杭州电子科技大学自动化学院人工智能研究院教授. 主要研究方向为多智能体系统, 机器人与无人系统和网络化系统. E-mail: linz@hdu.edu.cn

王雪松

中国矿业大学信息与控制工程学院教授. 主要研究方向为机器学习, 人工智能, 复杂系统优化及控制. E-mail: wangxuesongcumt@163.com