一阶二阶多智能体一致性控制介绍及Matlab程序

本文的详细代码在https://github.com/Say-Hello2y/MultiAgentSystem中可找到。

---

前言：多智能体控制的应用

智能体本是人工智能领域的概念，控制领域的智能体一般指具有一定的 动力学和运动学特性且能同周围环境及其他个体交换信息的实体。在过去的十几 年里，多智能体系统 (multi-agent systems, MAS) 的协同控制问题受到了国际控制界越来越多的关注。多智能体系统的建模起源于群居动物，如昆虫，鱼群，鸟 群等 。这些群居动物能够共同完成一些单个个体很难完成的任务。

图1. 自然界的协同控制
一致性是多智能体控制的一个基本目标，许多多智能体任务都可转换为特殊的一致性控制任务。下面给出多智能体一致性任务分类：
图2. 多智能体一致性分类

一、基础知识：图论与代数

1.图论介绍

图论（graph theory），是组合数学分支，和其他数学分支，如群论、矩阵论、拓扑学有着密切关系。图是图论的主要研究对象。图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。
在多智能体研究领域，通常假定智能体之间通过通信网络或者传感器网络交换信息，采用有向图（Directed graphs）或无向图（Undirected graphs）来描述智能体之间的信息交换。无向图是指连接之间是没有方向的，即若节点A与节点B有连接，则意味着A可以和B通信，B也可以和A通信，而若为有向图，A，B之间的通信关系并不是一致的，即A可以和B通信不能推出B可以和A通信。

2.图的Laplacian矩阵

在介绍图的Laplacian矩阵之前，先引入图的邻接矩阵（Adjacency matrix）的概念，无向图的邻接矩阵计算方法是每条边为对应的单元加上1，而每个自环加上2。这样让某一节点的度数可以通过邻接矩阵的对应行或者列求和得到。如下图所示

图3. 无向图的邻接矩阵
有向图的邻接矩阵一般是不对称的。可以有如下定义：
定义一：定义有向图的邻接矩阵中的某个元素 $A_{ij}$代表：
1.从i指向j的边的数目
或
2.从j指向i的边的数目
第一种定义广泛用于图论和社会网络分析（如：社会学、政治学、经济学、心理学）。
第二种更加常见于其他应用学科（如：动态系统、物理、网络学），这些学科有时用邻接矩阵A表示图上的线性动力， 这里使用第二种定义。给大家举个栗子，见下面的草图
图4. 有向图的例子

采用第二种定义,则
$$A=\left[\begin{array}{cccccc}0& 0& 0& 0& 0& 1\\ 1& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0\\ 1& 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 0& 0\\ 0& 0& 1& 0& 1& 0\end{array}\right]\text{\hspace{1em}(1)}$$
以2,3节点为例，$A_{32}$代表矩阵第三行第二列，具体意义为象征第3个智能体与第2个智能体之间的通信关系，采用邻接矩阵的第二种定义则由于2节点到3节点有一条有向线段故$A_{32}=1$，而4节点没有指向3节点故$A_{34}=0$。
定义二：图的入度矩阵D，入度矩阵是一个对角矩阵，对角线元素为终点在这个节点的边的条数，采用第二种定义的话，有向图的入度矩阵对角线元素就为邻接矩阵对应行和。
$$D=\left[\begin{array}{cccccc}1& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 2& 0& 0\\ 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 2\end{array}\right]\text{\hspace{1em}(2)}$$
定义三：图的laplacian矩阵：$L=D-A$，由定义可知laplacian矩阵行和为0
$$L=\left[\begin{array}{cccccc}1& 0& 0& 0& 0& -1\\ -1& 1& 0& 0& 0& 0\\ 0& -1& 1& 0& 0& 0\\ -1& 0& -1& 2& 0& 0\\ 0& 0& 0& -1& 1& 0\\ 0& 0& -1& 0& -1& 2\end{array}\right]\text{\hspace{1em}(3)}$$
关于图论方面就介绍到这里，下面介绍如何根据图的Laplacian矩阵设计多智能体一致性控制器。

二、一阶二阶多智能体一致性控制介绍及代码（Matlab）

本文的详细代码在https://github.com/Say-Hello2y/MultiAgentSystem中可找到。

1. 一阶智能体

多智能体一致性的概念，对一阶系统而言就是状态趋于一致，即在$t\to \infty$时，有$x_i\to x_j$成立。
最简单的智能体 (如阻尼器) 的动力学可用一阶积分器模型来描述 式中，
$$\dot{x_i}(t)=u_i(t),i=1,\dots ,N\text{\hspace{1em}(4)}$$

$x_i(t)\subset R^p$为智能体 i 的位置, $u_i(t)\subset R^p$为控制输入，N 为智能体的总数。这里假设控制输入可直接控制智能体的速度。Olfati-Saber 和 Murray 在文献中针对一阶积分器智能体网络提出了一种 一致性控制器
$$u_i(t)=-\sum _{j=1}^N{a}_{ij}(x_i(t)-x_j(t)),i=1,\dots ,N\text{\hspace{1em}(5)}$$

式中， $a_{ij}$为邻接矩阵的第 (i, j) 项。Olfati-Saber 指出，对于智能体的通信拓扑 为无向图的情形，只要无向图是连通的，那么，在上式的作用下，一阶积分器智能体网络能够实现一致，即，当$t\to \infty$时，有$x_i\to x_j$成立。而对于有向图而言， 包含一个有向生成树是智能体网络实现一致的充分必要条件。

该文献还指出，智能体的状态最后趋于一致的终值是由智能体状态的初值和通信拓扑图共同决定的，其终值可表示为 ${\sum }_{i=1}^N{r}_i{x}_i(0)$。其中$r=[r_1,\dots ,r_n{]}^T$ 为 Laplacian 矩阵与零特征值相关的左特征向量且有$1_N^{T}r=1$成立。一致性控制 器可看作是一种负反馈控制。对智能体 i 来说，先把它的状态和它所有邻居的 状态作差，再求和后作负反馈。这种一致性控制器的思想后来被广泛应用于各类智能体网络。
上例的matlab实现一阶多智能体一致代码如下

clear;
close all;
clc;
X0=[1;2;3;4;5;6];%状态初始值
dt=0.01;T=10;%步长与仿真时间
t=0:dt:T;
n=length(t);
x=X0;
A=[0 0 0 0 0 1;1 0 0 0 0 0;0 1 0 0 0 0;1 0 1 0 0 0;0 0 0 1 0 0;0 0 1 0 1 0];%邻接矩阵
D=diag(sum(A,2));%利用Laplacian 行和为0构造D矩阵
L=D-A%利用算法求出Laplacian矩阵
for i=1:n
  u(:,i)=-L*x;
  X(:,i)=x;
  x=dt*u(:,i)+x;
end
%画出状态图与u随时间的图像
figure(1);
plot(t,X)
title('status diagram');
xlabel('time');
ylabel('status');
legend('x1','x2','x3','x4','x5','x6');
figure(2);
plot(t,u)
title('velocity diagram');
xlabel('time');
ylabel('u');
legend('u1','u2','u3','u4','u5','u6');

2.二阶智能体一致性控制（ode45算法）

比一阶积分器模型稍复杂一些的智能体动力学模型是二阶积分器模型
$$\begin{gathered} \dot{x_i}(t)=v_i(t) \\ \dot{v_i}(t)=u_i(t)\text{\hspace{1em}(6)} \end{gathered}$$
式中，$x_i(t),v_i(t)\subset R^p$分别表示智能体 i 的位置和速度向量， $u_i(t)$仍表示控制输入。这里的二阶常系数微分方程可用来描述经典的牛顿第二定律模型，如自主车。二阶积分器模型假设控制输入可直接控制被控对象的加速度。对由上式描述的多智能体网络，Ren 提出了一种有效的一致性控制器。
$$u_i=-\sum _{j=1}^N{a}_{ij}((x_i(t)-x_j(t))+\gamma (v_i(t)-v_j(t))),i=1,\dots ,N\text{\hspace{1em}(7)}$$

式中，$\gamma >0$ 为待确定的常数增益。Ren 指出，对于连接的无向通信拓扑而言， 上式可使二阶积分器智能体的位置和速度都渐近趋于一致。但对于有向通信拓扑而言，则需要上式中的增益参数 $\gamma$满足条件
$$\gamma >\underset{\forall Re({\mu }_i)<0,Im({\mu }_i)>0}{\max }\sqrt{\frac{2}{|{\mu }_i|\cos ({\tan }^{-1}(\frac{Im({\mu }_i)}{-Re({\mu }_i)}))}}\text{\hspace{1em}(8)}$$

式中，${\mu }_i$为矩阵 $-L$的第 i 个特征值。从这里可以看出，有向图下智能体实现 一致比无向图更加困难。同样，有向图需至少包含一个有向生成树。若智能体网络的位置和速度能趋于一致，则它们的终值由下式给出
$$\begin{gathered} x_i\to x_j\to \sum _{i=1}^N{r}_i{x}_i(0)+t\sum _{i=1}^N{r}_i{v}_i(0) \\ {v}_i\to v_j\to \sum _{i=1}^N{r}_i{v}_i(0)\text{\hspace{1em}(9)} \end{gathered}$$
给定邻接矩阵(无向图)
$$A=\left[\begin{array}{cccc}0& 1& 0& 1\\ 1& 0& 1& 0\\ 0& 1& 0& 1\\ 1& 0& 1& 0\end{array}\right]\text{\hspace{1em}(1)}$$
初始速度和初始状态一致$\mathbf{v},\mathbf{x}=[1,2,3,4{]}^T$,则使用ode45（ode45为一种微分方程解法，ode45表示采用四阶-五阶Runge-Kutta算法，它用4阶方法提供候选解，5阶方法控制误差，是一种自适应步长（变步长）的常微分方程数值解法，其整体截断误差为(Δx)^5。解决的是Nonstiff(非刚性)常微分方程。）
求解微分方程的二阶智能体一致性代码为

clear;
close all;
clc;
X0=[1;2;3;4];
V0=[1;2;3;4];
gamma=1;
A=[0 1 0 1;1 0 1 0;0 1 0 1;1 0 1 0];%邻接矩阵
D=diag(sum(A,2));%利用Laplacian 行和为0构造D矩阵
L=D-A;%利用定义求出Laplacian矩阵
u0=-(L*X0+gamma*L*V0);%u0初值
options = odeset('MaxStep', 1e-2, 'RelTol',1e-2,'AbsTol',1e-4);
[t,y] = ode45(@odefun,[0 15],[X0;V0;u0],options);
X=y(:,1:4);
V=y(:,5:8);
u=y(:,9:12);
%画图部分
figure(1);
plot(t,X)
title('status diagram');
xlabel('time');
ylabel('status');
figure(2);
plot(t,V)
title('velocity diagram');
xlabel('time');
ylabel('velocity');
figure(3)
plot(t,u)
title('acc diagram');
xlabel('time');
ylabel('u');
%函数部分
function dydt = odefun(t,y)
dydt = zeros(12,1);% 指定dydt为微分方程变量的导数，dydt代表（x1，x2，x3，x4，v1，v2，v3，v4，u1，u2，u3，u4）^T的导数，y代表
% （x1，x2，x3，x4，v1，v2，v3，v4，u1，u2，u3，u4）^T ，x代表位置，v代表速度，u代表控制变量即加速度
A=[0 1 0 1;1 0 1 0;0 1 0 1;1 0 1 0];%邻接矩阵
D=diag(sum(A,2));%利用Laplacian 行和为0构造D矩阵
L=D-A;%利用算法求出Laplacian矩阵
gamma=1;
dydt(1:4)=y(5:8);%
dydt(5:8)=y(9:12);%-(L*y(1:4)+gamma*L*y(5:8));
dydt(9:12)=-(L*y(5:8)+gamma*L*y(9:12));
end

参考文献

[1.]Seyboth, G.S., D.V. Dimarogonas, and K.H. Johansson, Event-based broadcasting for multi-agent average consensus. Automatica, 2013. 49(1).
[2.]冯元珍, 多智能体系统一致性问题综述. 长江大学学报(自然科学版), 2011. 8(03): p. 84-87+9.
[3.]龙晓军, 多智能体系统的有限时间一致性跟踪. 2015, 大连海事大学.
[4.]佘莹莹, 多智能体系统一致性若干问题的研究. 2010, 华中科技大学.
[5.]王国锋, 多智能体系统的一致性问题研究. 2017, 东北大学.
[6.]杨大鹏, 多智能体系统的事件驱动一致性控制与多 Lagrangian 系统的分布式 协同. 2015, 北京理工大学.