基于Gossip算法的多智能体随机分布式一致性问题研究(2)
1.2 研究现状 多智能体系统协调控制问题的研究是从不同的领域开始的。计算机科学家对多智能体系统的研究有着很长的研究历史，为分布式计算这一领域的兴起开辟了道路。20世纪60年代，一些从事管理科学和统计学的专家提出了统计一致性的概念及相关问题。DeGroot 提出了加权平均的方法来估计一组个体共有的包含某些未知变量的概率分布函数[1]。截至上世纪 80年代，DeGroot 的这种统计一致性的思想在Benediktsson[2]、Weller[3]的文中重现。同时，很多科学家如动物行为学家、生物生态学家、物理学家研究动物的群体行为是从观察自然现象开始的。为了解决网络分布式计算，Borkar[4]、Tsitsiklis[5]等最早提出了分布式一致性问题。 Reynolds 在1987年提出的 Boid 模型[6]，将自然群体的集体行为用三条简单的规则来描述：避免碰撞原则、速度匹配原则及中心靠拢原则。通过计算机模拟仿真可以发现这些无统一指挥的群体通过个体之间相互交换信息及本能的反应，例如跟随临近的鸟飞，避免碰撞，最终形成有序的行为。1995年，Vicsek 等人[7]用一些非常简单的数学方程描述个体的动力学模型，用网络建立起个体之间的信息传递及一些简单的相互作用规则。通过计算机模拟仿真，发现了令人惊讶的结果，整个群体出现行为上的一致性。实质上，Vicsek 模型是 Reynolds 模型的一种特殊情况，它只考虑了三条规则中的速度匹配原则。到 2004年，Saber 和Murray利用图论和拉普拉斯矩阵理论论证系统的研究了分布式一致性问题，证明了通信拓扑图无向连通或平衡有向强连通时，多智能体系统能够达到状态平均一致性，至此，解决分布式一致性问题的基本理论框架被建立。 2006 年，Boyd 等对异步随机 Gossip 进行了系统性的研究[9]。认为在异步随机 Gossip 中各智能体都存在一个独立的时钟，并且各时钟的触发次数被以速率等于1的泊松过程建模，即每个周期等概率选择一个智能体。当某一智能体被选择后，依概率从其邻居集中随机选择一个智能体进行信息交互并完成状态更新。而异步随机 Gossip 放松了对各智能体时钟同步的要求，并且算法中各智能体之间随机建立通信链路，其优点是能更好适应分布式环境，降低了各智能体计算能力的要求，具有较好的扩展性和鲁棒性。文献综述Boyd 等在异步随机Gossip 基础上用概率意义证明了可使各智能体状态达到平均一致的问题，并指出异步随机 Gossip的收敛速度取决于概率化权重矩阵的第二大特征值，进而提出了通过优化通信概率矩阵来提高算法的收敛速度的方法。Boyd 等所给出的智能体异步时钟模型被广泛应用于对异步随机分布式一致问题的研究中，为提高异步随机 Gossip 算法的收敛速度， 众多学者提出了大量的改进算法，其中具有代表性的可归结为三类，即Geographic Gossip、Greedy Gossip、Broadcast Gossip。 2006 年至2008 年间，Dimakis 等研究了 Geographic Gossip 算法[10,11]，算法中假设各智能体已知自身与邻居节点的地理位置，根据已知的地理信息确定路径在一定范围内选择一个智能体进行信息交互，而不局限其邻居集中。Geographic Gossip 改进了经典异步随机 Gossip 算法的收敛速度，但该算法采用多跳通信方式，具有易受通信延迟、数据丢包等缺陷。
上一篇：ARM7永磁开关控制器软件设计