Optimal Design of Observable Multi-Agent Networks: A Structural System Approach

可观测多智能体网络的最优设计:结构系统方法

abstract

本文介绍了一种设计可观察的有向多智能体网络的方法，这些网络：1）在通信相关成本函数下是最小化的，或2）在可能的直接通信故障情况下是等效的。可观察的多智能体网络的特点是使用基于有向通信图拓扑的邻居规则来更新状态，以便共享关于其状态的信息；此外，每个智能体可以推断出所有智能体共享的初始信息。
确保1)得到满足的充分条件是通过将原始问题简化为旅行商问题(TSP)来实现的。
对于2)所述的情况，示出了最小网络存在的充分条件等价于TSP的两个不相交解的存在性。
结果通过使用近似解来说明合作路径跟随多网络车辆的例子，涉及该领域。

一、问题定义

$\gamma$是我们关注的参数，例如无人机队形中每个无人机的位置参数
假设每个智能体的状态更新遵循线性动力学，由一个矩阵A决定 。$\dot{\gamma }(t)=A\gamma (t)$
属于线性时不变系统（LTI），具体来说是一个一阶线性常微分方程组。
关于求解方法：

1. 解析解法：
   通过矩阵指数求解：$\gamma (t)=e^{At}\gamma (0)$ 需要先对矩阵A进行对角化或Jordan分解
2. 数值解法：
   欧拉法、Runge-Kutta法等常微分方程数值解法
   MATLAB中的ode45等求解器
3. 结构特性分析：
   论文中特别关注的是系统的结构可观测性
   通过图论方法分析通信拓扑结构
   转化为旅行商问题（TSP）来优化通信成本

关键是要确保矩阵A的选择满足：(1)通信成本最小化；(2)系统对每个智能体都可观测。论文通过将这个问题转化为图论中的TSP问题来寻找最优解

通信成本 :哈达玛积(逐元素乘法)

可观测性：M只关注是否连接，不关注连接强度。

问题$\overline{P_1}$转化为：寻找最优的结构$\bar{M}$

它的目标还是最小化通信成本，但约束条件更强了:即使任意一条直接的通信链路失效，也就是我们把$\bar{M}$ 中的某一项 $M_{ij}$强制设为零，系统仍然要保持结构可观测性。这意味着我们的网络设计不能太依赖于某几条关键链路，得有一定的冗余度。

二、定理

智能体是一个节点，如果智能体i可以接受智能体j的信息，则有从j指向i的有向边。
结构可观测性就等价于在这个图上存在某种特殊的结构，比如能够被不相交的环覆盖，或者存在完美匹配，这保证了信息可以通过某种方式传递到所有节点。

不可约：图本身是一个强连通分量，也就是说，从任何一个智能体触发，都能通过通信链路到达其他任何一个智能体。排除了一些过于分散或分块的结构作为候选解。

如果我们能找到一个不可约的通信矩阵$A^{\ast }$,使的总成本最低，那么这个结构去掉自环后，其通信路径实际上就是旅行商问题的一个解。更妙的是，如果我们在这个TSP解的基础上给，给每个智能体加上自环通信，也就是允许自己给自己发消息，那么这个增强后的结构$\bar{A}$就是我们最初想解决的结构可观测性问题P1的一个解。 这意味着，我们可以通过求解TSP来间接找到P1的解。

充分条件：如果一个通信结构$\bar{A}$，当忽略掉自环之后，其通信路径恰好是TSP问题的最优解。并且包含自环后，整个图能够被不相交的环覆盖，那么这个$\bar{A}$就是我们想要的P1问题的解。
求解框架：先解TSP,再检查覆盖条件。

P1的解不够鲁棒，因为他们可能只有一条唯一的路径来保证可观测性。
引理4说：一个鲁棒的解至少需要每个节点有两个输入，并且图里至少有两条独立的闭合回路。
定理3给出构造方法：如果我们能找到两个不同的P1解，$\bar{A}$和$\overline{A^{\prime }}$,他们的通信图格子包含恰好n条变的不相交闭合路径，那么将这两个解合并，也就是$\bar{A}\cup \overline{A^{\prime }}$ ,则能得到一个满足P2要求的鲁棒解。

三、应用

一个典型的例子就是协同路径跟踪，比如让一群无人机或者无人车按照预定的路线飞行或行驶，并且保持一定的队形。这里面通常有两个控制器:一个是路径跟踪控制器，负责让单个车辆紧贴自己的那条路径;另一个是协调控制器，负责调整每个车辆在路径上的相对位置参数 gammai，从而实现整个编队的队形控制。这个协调控制器要想工作得好，就必须知道或者能估计出所有其他车辆的${\gamma }_i$参数，这就离不开我们前面讨论的通信网络及其可观测性了。

这里有两个关键要求:第一，系统要稳定，最好是边际稳定，也就是特征值都在复平面的左半边或者虚轴上，而且在虚轴上只能有一个零特征值。第二，这个零特征值对应的右特征向量必须是全1向量，这保证了所有智能体最终能达到一致。好消息是，定理4告诉我们，对于任何一个满足P1或P2条件的结构A上横线，我们都可以构造出满足这两个条件的数值矩阵A。
具体方法很简单:先把所有非自环的连接$A_{ij}$设为正数，然后让每个对角线元素$A_{ii}$等于它所在行其他元素绝对值之和的相反数。

现在来看一个具体的例子:六个自主水下航行器AUV组成一个三角队形协同运动。我们假设通信成本与智能体间的距离平方成正比，距离越远，通信成本越高。我们的任务就是设计一个通信网络，既能保证队形控制，又能满足可观测性要求，同时尽量省钱。

具体步骤是这样的:首先，用Christofides算法近似求解TSP，得到一个成本较低的通信路径，比如Agent1到Agent2到Agent3到Agent4到Agent2到Agent5到Agent6再到Agentl。
根据这个路径结构，利用定理2构造出一个P1的解A。
由于成本是对称的，A的转置也是P1的解。
接着，根据定理3和推论2，将A和A的转置合并，得到一个鲁棒的P2解A撇。
最后，用定理4的方法给A和A撇填充具体的数值，进行仿真验证。