第1期 刘佳，等：多智能体系统及其协同控制研究进展 ·3 Agent组成一个Aget团体.根据Agent的工作范围 阵构成的.无向边集合中，结点没有起点和终点之分， 和职能，可将其分为 也就是说，(：，)就意味着(，：)，因此，无向图是有 a)管理Agent:负责MAS的管理，一般一个系统 向图的一种特殊情况.一个结点”：的入度和出度分别 中只有一个管理Agent; 用degn（:)和deg(:)来表示，且 b)功能Agent:具有通用的任务执行能力，能够 协助管理Agent完成一些系统任务，是一类不受应 dga）=Ao.dg(a）=月o 用领域影响的工具Agent; 图G中的结点：是平衡的(balanced)当且仅当 c)应用Agent:具有特殊领域中的事务处理功 该结点的入度和出度相等，即degm（:)= 能，一般一个系统中有多个应用Agent. degom(:).图G是平衡图的充分必要条件是这个图 2)完全自治式组织结构（分布式） 中所有结点都是平衡的，即有 在这种结构中，Agent之间没有管理与被管理 degin（v:)=degou(:),Vi∈L. 的关系，每个Agent都可以自主地实现自己的目标. 一个有向图G是强连通的(strongly connected) 这种方式最能体现MAS的灵活性、社会性和每个 当且仅当图G的任意的2个不同结点之间有一条 Agent的自治性，但这种方式运行的稳定性和可控 有向路径.一个有向图包含生成树，当且仅当它有一 个根结点，从任意的其余结点出发，都存在路径可以 性较差 到达这个根结点. 3)问题求解组织结构（混合式） 权重图的Laplacian矩阵定义为L=[l;],其 这是Agent为了协同完成一项任务而形成的一 种动态组织结构，各Agent之间的关系式是动态变 中，l=∑4，对于ij,g=-a到 2.2MAS群集运动及控制研究 化的.从Agent之间的关系来看，这种结构介于主从 MAS群集(Swarming/Flocking）行为是复杂性 式与完全自治式结构之间. 科学的一个焦点问题.Swarming是指一个由大量自 2MAS协同控制研究进展 治个体组成的集合，在无集中式控制和全局模型的 情况下，一般通过个体的局部感知作用和相应的反 经过20多年的发展，MAS的研究已经在理论和 应行为，使整体呈现出涌现行为.在一个MAS中，所 应用方面取得了很大的进展.MAS一个显著特征是： 有的Agent最终能够达到速度矢量相等，相互间的 系统中每个Agent的能力有限，而大量这样的个体聚 距离稳定，则被称为Flocking问题.自然界中存在很 集到一起，通过相互作用会产生有意义的社会活动或 多群集行为，例如：鸟群迁徙时会整齐编队，在遇到 完成单个Agent所不能完成的任务.因此，MAS研究 障碍时，这种队形还可以自动调整：野生动物群和鱼 领域中一个重要的问题就是设计正确的控制策略，使 群在遇到攻击时会形成一个合理的编队逃跑，而不 MAS完成给定任务，即MAS的协同控制问题.近年 是一哄而散；蚁群在觅食时能够在食物与居住地之 来，MAS的协同控制已经成为国内外诸多研究人员 间选取一条最优路径，并且，当环境变化时，它们会 关注的热点问题，本节先简要介绍研究协同控制问题 对路径进行重新选择.这些是群集行为极具代表性 通常使用的代数图论，然后从MAS群集运动和协同 的例子 控制一致性问题2个方面，论述近年来国内外在多 1987年，Reynolds提出一个模仿动物聚集的计 Agent协同控制方面的研究发展状况 算机模型，这个基本的群集模型包括3条规则： 2.1代数图论 1)聚集(cohesion):所有Agent改变当前位置并向其 有向图G=(V,E,A)由一个有限顶点（或结点） 邻近成员的平均位置运动；2)分离(separation):运 集合V={,2,…,vn}、一个有向边的集合ECV×V 动过程中，相邻的Agent避免发生碰撞；3)调整(a- 和权重矩阵A所构成.eg=(:,)∈E叫做边，第1 lignment):所有Agent速度大小和方向改变基于其 个元素：称为边的起点，第2个元素巴称为边的终 邻近成员的平均值。 点，边的方向从：指向v连接权值矩阵为A=[a], 1995年，Vicsek等人提出了多自主移动Agent 且对于i∈I(1=1,2,…,n)有：i≠j,ag>0,对于 模型[61： Vi∈I:a=0.类似地可以定义无向图，无向图是由一 x(t+1)=x:(t)+:(t)△t,i=1,2,…,n 个有限顶点（或结点）集合、一个无向边集合和权重矩 式中：x:(t)为第i个Agent在t时刻的位置向量，在