多智能体蜂拥的研究

多智能体系统蜂拥问题的研究 1

1绪论

1.1研究背景

蜂拥是一种大数量相互影响的具有普遍群体目标的个体集体行为的一种表现。数十年来，依靠个体间基本的相互影响的涌现现象已经吸引了来自不同领域的科学家们，他们包括动物行为、物理、生物、社会学和微机科学等[1-12]。这些主体的例子一般为鸟、鱼、鸽子、蚂蚁、蜜蜂和人群。这些生物在运动能力、视觉能力等方面有限，但通过相互之间的交互构成大规模群体，能够将有限的个体能力聚集起来，克服单个个体能力上的不足，高效的完成觅食、迁徙、躲避天敌等活动。在这样的群体系统中，由于单个个体仅具有有限的局部感知能力，仅能够获取存自己能力范围内的局部信息，而无法获取整个群体的全局信息，因此系统中就不存在集中式的协调控制机制，而具有分散式、分布式系统的特点。如何通过局部信息交换产生全局的系统行为足近年来的一个研究热点。

一般将实际中具有上述现象的系统抽象为多智能体系统(Multi-Agent Systems ，MAS)，该系统具有一个有趣的性质：在许多由大量动态演化的个体组成的系统中，往往会涌现出全局协调一致的行为。一般而言，构成该系统的个体并不知道整个系统的全局信息，每个个体只能根据它所拥有和感知的局部信息（如它所能够观察到的其它个体的行为）来调整自身的行为。也就是说，整个系统是通过分布式的个体凋整而不是集中控制方式实现全局协调一致行为的。具有这样性质的系统在实际中是普遍存在的，除了生物系统会表现出全局一致的性质，一些非生物系统也会出现这种一致性现象，例如，悬挂在一个横梁上的钟摆在一段时间后会出现同步摆动，演出结束后观众的掌声发生同步，网路上的路由器最终会以同步的方式发送路由消息，从而引起的网络拥塞，以及人们通过大桥时的步伐同步，从而引起大桥的共振等。对于这类现象的产生机理，研究者将其纳入复杂网络的范畴内进行研究，得出这样的结论：在这些复杂系统中，每一个个体都是一个动力学系统，而诸多的动力学个体之间存在着某种特殊的耦合关系，这些系统中的个体根据自身能够感知的局部信息经过动态演化而达到整个系统的同步。本质上．复杂网络的同步的机理与多智能体系统协调现象是一致的。

截止目前对蜂拥动态行为的建模和分析按照研究方法来分类最常用的方法有三种：基于个体描述的方法，也称为拉格朗日方法；连续流方法，也称为欧拉方法；以及离散系统模型方法。以上三种方法中，基于个体描述的模型，是以常微分方程组来描述所有个体的运动，这是对连续变化对象建模的一个自然的方法。连续流模型则采用偏微分方程来描述蜂拥分布形成的密度场中局部的反应散现象，研究其稳定性和运动性质。离散系统模型方法是用离散时间方程组来描述，研究其互相作用下的集体行为。

第一批对蜂拥(Flocking)的从理论角度进行研究的物理学家有Vicsek[13]等，

多智能体系统蜂拥问题的研究 2

Toner&Tu[14]，Shimoyama[15]等，和Levine[16]等。Vicsek等的研究内容主要涌现在个体控制系统中速度匹配的势能（这并不意味着蜂拥），而Toner&Tu采用了连续介质力学接近。Levine等创造了一个基于个体的相互影响的系统，这种循环蜂拥系统被称作循环蚂蚁工厂。另一种连续模型是由Mogilner&Ekdstein-Keshet[17]和Topaz&Bertozzi[18]提出的。Helbing等使用经验法的基于个体的模型研究了蜂拥。

1.2群体智能理论及研究方法

1.2.1群体智能概述

群智能理论的基本原理[19-20]是以生物社会系统(Biology social system)作为依托，也就是由简单个体组成的群体与环境以及个体之间的互动行为。这种生物社会性的模拟系统利用局部信息产生难以估量的复杂群体行为。

群体智能并不是所有生物种群都具有的特性，它是那些具有社会性特征的群居生物个体合作进行某些活动时才会产生的涌现现象。关于群体智能行为的生物原型，Bonabeau描述了生物蚂蚁群体的一些行为，如觅食、劳动分工、尸体聚集、巢穴构造、合作运输等，并分别对其建模，然后设计了一系列算法、多主体系统(MAS)和多机器人系统[31]。集中介绍了社会性昆虫的行为建模和蚁群优化算法及其性能。Kennedy通过观察鸟群的协同运动，开创了微粒群优化这一新型群体智能方法的研究领域，并以此为基础提出了以下基本观点[21]：

1)人类智能的产生源于社会交往； 2)文化和认知是人类社交的结果。

对鱼群的研究，也属于群体智能的理论范畴。群体智能研究成果和理论体系，可以用来指导我们对鱼群形成、组织体系、群体行为及其涌现出的群体智能的研究。群体智能是一种通过模拟自然界生物群体行为来实现人工智能的方法。由单个简单个体完成的任务，可以涌现出复杂的智能，充分体现了整体和大于个体的叠加。群体智能利用群体优势，在没有集中控制，不提供全局模型的前提下，为复杂问题寻找解决方案[22]。普遍意义上，群体智能强调个体行为的简单性、群体的涌现特性、以及自下而上的研究策略。群体智能的本质是由许多简单个体组成的群体，群体之间能够通过简单的交互、合作和协作，来完成某一项任务。群体智能在已有的应用领域中都表现出较好的寻优性能，因而引起了相关领域研究者的极大关注。其中涌现是群体智能中一个比较重要的概念，群体智能中的智能就是大量个体在无中心控制的情况下体现出来的宏观有序的行为。这种大量个体表现出来的宏观有序行为就是涌现现象。如果没有涌现现象，就无法体现智能。因为涌现是简单的个体行为在特定组织结构下，积累到一定程度，所表现出来的整体现象，所以，对群体智能的研究必须既研究各个部分，又研究各个部分之间的相互作用关系。

Millionas M. M在1994年提出群体智能应遵循的五条基本原则[23]，分别为：

多智能体系统蜂拥问题的研究 3

1)邻近原则，动物群体能够进行简单的空间和时间计算； 2)品质原则，动物群体能够响应环境中的品质因子；

3)多样性反应原则，动物群体的行动范围不应该局限在小范围内； 4)稳定性原则，动物群体不应该在每次环境变化时都改变自身的行为；

5)适应性原则，在所需代价不太高的情况下，动物群体能够在适当的时候改变自身的行为。

1.2.2群体智能的主要优点

群体智能具有以下优点[24]：

1)群体中相互合作的智能体是分布的，这样更能够适应当前网络环境下的工作状态。

2)没有中心控制与数据，这样的系统更具有鲁棒性，不会由于某一个或者某几个智能体的故障而影响整个问题的求解。

3)可以不通过智能体间直接通信，而采用非直接通信进行合作，系统具有更好的可扩充性，使得系统中由于智能体数量的增加而增加的系统通信耗费较小。

4)系统中每个智能体的能力非常简单，以至于每个智能体的执行时间都比较短，且实现也较简单，具有简单性。

5)智能体相互作用能突现出整体的行为，系统所有上层智能行为都是通过智能体的基本规则相互作用产生的，所以在多任务情况下，对于每一子任务可以分别编制、调试、学习。

6)群体智能中，信息处理原则是基于发生在实际生命中大量并行处理过程。群体智能系统的强并行性大大地增强了系统的运算速度及能力。

7)人工生命中的一个重要原则，就是整体大于部分和的思想。由于群体智能的整体行为是由智能体行为突现而产生的，智能体在相互作用中的负关系将会因智能体自身的相互作用规则而消减，正关系将得以增强。对于智能体之间的冲突和任务协调等问题，由底层智能体相互作用的规则解决，减少上层对智能体之间的协作、协调控制，避免了上层控制干预下层动作的情况，使得每一层次的控制任务都非常清晰，增加了系统协作协调效率。

1.2.3群体智能的主要缺点

群体智能的研究还处于萌芽阶段，还存在很多不足，主要问题如下[25]：

1)群体智能的思想是根据对生物群体观察得来的，是概率算法，从数学上对于它们的正确性与可靠性的证明仍比较困难。

2)这些算法都是专用算法，一种算法只能解决某一类问题，各种算法之间的相似性很差。

3)系统高层次的行为是需要通过低层次智能体间的简单行为交互突现产生。单个个

多智能体系统蜂拥问题的研究 4

体控制的简单并不意味着整个系统设计的简单。

4)系统设计时也要保证多个智能体简单行为交互能够突现出所希望看到的高层次复杂行为。这可以说是群体智能中一个极为困难的问题。 1.2.4群体智能的底层机制研究

自组织[26]：自组织是一种动态机制，由底层单元的交互而呈现出系统的全局性的结构。交互的规则仅仅依赖于局部信息，而不依赖于全局的模式[23]。自组织是系统自身涌现出的一种性质。系统中没有一个中心控制模块，也不存在一个部分控制另一部分。自组织的特点就是通过利用同一种介质或者媒体创建时间或空间上的结构。比如蚂蚁筑的巢、寻找食物时的路径等。正反馈群体中的每个具有简单能力的个体表现出某种行为，会遵循已有的结构或者信息指引自己的行动，并且释放自身的信息素，这种不断的反馈能够使得某种行为加强。尽管一开始都是一些随机的行为，大量个体遵循正反馈的结果是呈现出一种结构。自然界通过系统的自组织来解决问题。理解了大自然中如何使生物系统自组织，就可以模仿这种策略使系统自组织。

间接通信[26]：群体系统中个体之间如何进行交互是个关键问题。个体之间有直接的交流，如触角的碰触、食物的交换、视觉接触等， 但个体之间的间接接触更为微妙，已有研究者用Stigmergy来描述这种机制：也就是个体感知环境，对此做出反应，又作用于环境。Grasse首先引入Stigmergy来解释白蚁筑巢中的任务协调[27]。Stigmergy在宏观上提供了一种将个体行为和群体行为联系起来的机制。个体行为影响着环境，又因此而影响着其它个体的行为。个体之间通过作用于环境并对环境的变化做出反应来进行合作。总而言之，环境是个体之间交流、交互的媒介。从蚂蚁觅食到蚂蚁聚集尸体到蚂蚁搬运、筑巢，个体之间的通信机制总是离不开Stigmery机制，对于环境的作用，通常由各种各样的信息素来体现。

涌现[26]：群体智能中的智能就是大量个体在无中心控制的情况下体现出来的宏观有序的行为。这种大量个体表现出来的宏观有序行为称之为涌现现象。没有涌现现象，就无法体现出智能。因此，涌现是群体智能系统的本质特征。只知道孤立的个体行为并不能了解整个系统的情况，仅仅研究孤立的部分无法有效地研究整体性质，因此，对涌现现象的研究必须既研究各个部分，又研究各个部分之间的相互作用[28]。“遗传算法之父”约翰·霍兰在文献[29]中对涌现现象进行了较为深入的探索。他认为涌现现象的本质是“由小生大，由简入繁’’，并且把细胞组成生命体，简单的走棋规则衍生出复杂的棋局等现象都视为涌现现象。他认为神经网络、元胞自动机等可以算作涌现现象的模型。群体智能的涌现现象与系统论和复杂系统中阐述的涌现本质上是相同的，它是基于主体的涌现。1979年霍夫施塔特对基于主体的涌现作了描述，整个系统的灵活的行为依赖于相对较少的规则支配的大量主体的行为。研究群体智能系统，要弄清涌现现象的普遍原理，建立由简单规则控制的模型来描述涌现现象的规律。

多智能体系统蜂拥问题的研究 5

1.3MAS（Multi-Agent System）系统

如果说对单个智能体的研究是将传统人工智能研究领域的方法集成在一个实体上进行的话，那么，对多智能体系统（Multi-Agent system，MAS)的研究，则是对群体智能的更进一步的拓展。在MAS中，整个系统所表现出来的智能或者说行为，不仅仅是多个智能体行为的简单叠加，它所显示出来的整个社会的行为存在更多的不确定因素，更为复杂，难以预测。

1.3.1MAS（Multi-Agent System）概念

对于MAS[30]的研究起源于上个世纪七十年代后期的分布式人工智能Distributed Artificial Intelligence，DAI)，它有两大研究方向：分布式问题求解(Distributed Problem solving，DPS)与MAS。DPS主要研究的是对于一个给定的问题，如何将任务在一组节点之间进行分配。这些问题求解节点可能因为所拥有的资源、能力、信息等的不足，而需要相互合作，以期共同完成任务。这是一种从系统的观点、在设计阶段就进行问题分解、求解规划及解答合成的方式。而在近年来得到越来越多关注的MAS，则更加强调了问题求解节点的自治性。

研究由多个自治的智能体组成的MAS，更重要的在于研究智能体之间的联系以及整个系统所表现出来的特性。正是由于智能体之间的联系的多样性，使得整个系统呈现出复杂、难以预测的现象。这是一个高度交叉的研究领域。无论是从其理论方面，还是应用方面，均涉及到众多领域的相关内容，如计算机学科、经济学、哲学、社会学、心理学、生态学和组织科学，而研究者从不同的方面给予不同的侧重。

计算机科学：这是MAS的起源领域，从而有着广泛的研究内容。从MAS的计算理论出发，研究在分布式/并发环境下，任务的分解与分配，智能体之间的协调、协作、通信、死锁预防与解决等。在人工智能方面，有智能体的规划、调度以及智能体之间的协商。

经济学：主要是应用经济学中的对策论(Game Theory)来研究智能体之间的交互问题，如规划、协商、学习等问题。当被认为是理性的多个智能体因为某项任务进行协商时，从各自的利益出发，对其他智能体的信念、意图进行推理，选择最优策略。传统的对策论中参预者之间没有通信，只是根据完全的或者是不完全的信息进行决策。当应用到智能体的协商过程中时，则相应地进行了很多改进，如将通信行为引入协商过程。

社会学：包含有两个方面——以人类社会研究来对MAS中存在的现象进行研究，以及以MAS来仿真人类社会中可能的现象。对于前者可包括众多的内容，如对伦理、规范、组织等的研究：而对于后者，包括对于人类社会秩序、合作、冲突、协商等的仿真，主要讨论某种特定的社会现象在某种情况下是如何涌现出来的，并以观察到的规律来解释和理解人类社会中的现象，并加以预测。同时，对社会伦理、规范、承诺、义务、权利等约束概念的研究，智能体在社会体系中遵循的规范、以防止恶意欺诈、使得社会

多智能体系统蜂拥问题的研究 11

图2-2分离

2.1.2聚合

聚合规则是使智能体间具有凝聚力，保持队列的紧凑，如图2-3所示。为了能够产生聚合的群体行为，智能体需要获得其邻域内其它智能体的位置信息，并计算出邻域内智能体位置的平均值，由此产生一个作用于该邻域内所有智能体的吸引力，这样使得智能体向平均位置方向运动。

图2-3聚合

2.1.3速度匹配

速度匹配规则使各个智能体与其邻域内其他智能体的速度保持一致。如图2-4所示。为了能够实现速度匹配，每个智能体需要获得邻域内其它智能体速度信息，计算出邻域内智能体的平均速度。通过速度匹配，可以使得智能体速度大小和方向与这个邻域内所有智能体速度的平均值保持一致。

多智能体系统蜂拥问题的研究 12

图2-4速度匹配

2.2 智能体蜂拥算法的数学基础

2.2.1蜂拥的数学拓扑结构：共识网络（Proximity Nets）

图G由节点和边的集合(v,?)组成，其中节点集为V?{1,2...,n}，边集为

??{(i,j):i,j?V,j?i}(即，图G一般为有向图，且不存在自我回路)。如果

(i,j)???(j,i)??，则图G为无向图。|V|和|?|值分别为图的度和模值。对于动态网

络系统，|?|可表征系统的通讯复杂性。

图的邻接矩阵（adjacency matrix）A?[aij]中不包含0元素。如果邻接矩阵的元素中含有非0和1的元素，则称对应的图为加权图。这里，我们大多使用拥有位置决定邻接矩阵元素值的加权图。对于一个无向图G，邻接矩阵A是对称的（或者AT?A）。节点i的邻居集合定义为

Ni?{j?v:aij?0}?{j?v:(i,j??)}

（2-1）

令qi?Rm表示节点i的位置，其中i?V。向量q?col(q1,...,qn)?Q?Rmn被称为图中所有节点构成的配置。这是一个由包含图及节点构成的数据对(G,q)组成的配置。

现在考虑一群动态智能体，其动力学方程如下：

?.?qi?pi, ?.??pi?ui, （2-2）

多智能体系统蜂拥问题的研究 13

这里qi,pi,ui?Rm（即m=2或3）其中i?V。使用基于粒子的蜂拥模型点于连续模型的优点是连续模型不能进行进一步智能体传感、交流，而且，不能使用计算机计算。

令r?0表示两个智能体之间的距离。一个半径为r的球型空间（见图2-5）确定智能体i的空间范围定义为

Ni?{j?v:||qj?qi||?r}

m （2-3）

其中||..||是R中的欧几里德标准。给定一个匹配的边界r>0，一个共识网络

G(q)?(V,?(q))可以由V定义，并且?可表示如下。

（2-4）

?(q)?{(i,j)?v?v:||qj?qi||?r,i?j}

图2-5智能体i的邻域

显然G(q)?(V,?(q))依靠q来确定。框架(G,q)叫做邻接结构。如果所有智能体的相互作用范围是相同的，共识网络G(q)就成为了一个无向图。N个点的共识网络一般是下面的假设的一种：1）智能体的球形范围没有一定的半径，或2）每个智能体使用圆锥型范围使用确定它的邻居。在这篇文章中，所有的共识网络都是双向的图形。 2.2.2蜂拥的几何结构：??Lattic（?格子）

为了让现实生活中的集群获得明显的空间秩序，人们使用一个??Lattic结构来建立目标蜂拥智能体的几何结构。为了完成这个，人们寻求满足所有智能体之间的距离都满足期望值d，对于每个智能体q取感知范围为共识网络G(q)。以上可以用描述下列代数公式描述：

||qj?qi||?d,?j?Ni(q) （2-5）

公式2-5中的解q扮演蜂拥智能体构造的期望值（即蜂拥的几何模型）。

多智能体系统蜂拥问题的研究 14

定理1.（??Lattic）一个??Lattic是所有q满足方程2-5的一个结构。我们把d和k=r/d分别作为??Lattic的期望值和感知期望比。

图2-6展示了??Lattic的图形例子。 结构q由以下不等式描述：

???||qj?qi||?d??,?(i,j)??(q) （2-6）

图2-6?格子的例子，其中（a）为分布式?格子，（b）为节点n=150的类似?格子

以下方程可以计算出结构q和??Lattic之间的差距

E(q)?1(|?(q)|?1)n???(||qi?1j?Nij?qi||?d) （2-7）

其中?(z)?z2被称为成对势能（注意其他的势能标准也可以被使用）。他的能量偏差可以被视为n个节点的光滑势能函数。可以证明，??Lattic是所有结构q中最小的势能函数，而且达到最小值0。对于一个包含不确定的边长?的??Lattic，能量偏差可以被定为

E(q)?|?(q)||?(q)?1|?2??2??d,???1

22这意味着??Lattic是n个点的最低能量构造。 2.2.3 ??Norm和光滑邻接元素

为了建立光滑的蜂拥势能和每个共识网络的邻接矩阵，人们定义了称为??Norm的一个非负映射。

其为Rm?R?0（不只一个标准），定义为

多智能体系统蜂拥问题的研究 15

||z||??1[1??||z||?1]

2? （2-8）

其中参数?>0，梯度??(z)??||z||?由以下定义

??(z)?z1??||z||2?z1??||z||? （2-9）

??Norm的?在本文之后不变。

碰撞函数（bump function）?h(z)是变量从0光滑变到1的函数。这里，人们用碰撞函数建立光滑的势能函数，其含有有限的间断和光滑的邻接矩阵。以下是一种可以选用的碰撞函数

?1,z?[0,h)?(z?h)?1?h(z)??[1?cos(?)],z?[h,1]

(1?h)?2?0,otherwise? （2-10）

这里h?(0,1)。可以看出来?h(z)是一个光滑函数，使用这个碰撞函数，我们可以定义邻接矩阵A(q)，它的成员为

aij(q)??h(||qj?qi||?/r?)?[0,1],j?i （2-11）

其中对于任何i和q，ra?||r||?，aii(q)?0。对于h?1，?h(z)是一个指示函数，其当在[0,1]时为1，在其它范围为0。使用这个指示函数，可以创造出一个依靠0-1的邻接网络。

2.2.4 涌现势能函数

涌现势能函数V(q)是含有智能体群的不定映射V:Rmn?R?0。其中所有势能函数的解的最小值是V(q)，反之亦然。在这篇文章中，涌现势能是指能量偏离函数的一个平滑的形式，其梯度势能是离散的。

?(z):R?0?r?0是一组吸引/排斥的成对的势能，其最小值在z?d取得，而且

定义变为0在r实现，之后，以下的函数

?(q)?12???(||qij?ij?qi||?)

（2-12）

是一个涌现的势能函数，但是两个不同节点具有相同位置即qi?qj的情况是不可能

多智能体系统蜂拥问题的研究 16

发生的。为了解决这个问题，人们改写方程（5），方程如下

||qj?qi||??d?,?j?NI(q) （2-13）

其中da?||d||?。因此，可以得到以下势能函数 V(q)?12???ij?ia(||qj?qi||?) （2-14）

这里?a(z)是光滑的成对的吸引/排斥势能（由公式2-16给出），其中有限的间断在

ra?||r||?取得，全局最小值为z?da。

为了建立一个含有有限间断的光滑的成对的势能函数，我们加入功能函数?a(z)它对于所有z?ra为0。定义这个功能函数是

?a(z)?ph(z/ra)?(z?da)?(z)?12[(a?b)?1(z?c)?(a?d)] （2-15）

其中?1(z)?z/1?z2而且?(z)是一个s型函数满足0?a?b,c?|a?b|/4ab从而满足?(0)?0。这个成对的吸引/排斥势能在公式（2-14）中定义为

z?a(z)???daa(s)ds. （2-16）

这个函数的曲线在图2-7中给出。

图2-7在有限间断的光滑势能?a(z)

多智能体系统蜂拥问题的研究 17

2.3蜂拥控制算法介绍

本节首先介绍自由空间蜂拥的离散算法，其针对的是带有动态属性qi?ui的α智能体。自然界中的α智能体可对应于鸟类，蜜蜂，鱼和蚂蚁。之后，介绍考虑到了障碍和集体的影响的β智能体和γ智能体算法。这些算法的基础是蜂拥中的α智能体和它们互相的影响。

在自由蜂拥中，每一个?智能体接收到三项信号

ui?fi?fi?figdr.. （2-17）

其中三个分量分别是速度、障碍和反馈影响。这里有一个蜂拥中的群体向一个方向移动的例子，Olfati-Saber提出两个离散算法来建立在三维空间中的蜂拥运动。

在一个群体中的具有客观的蜂拥表现的微粒/智能体称作α智能体。这里介绍三种关于α智能体的可扩展的蜂拥算法。第一种蜂拥算法是一种基于梯度的具有速度匹配的算法。事实表明，这种算法体现了Reynolds所有三个规则。

第二种算法是蜂拥在自由m空间运动中的主要算法。这个算法有一个附加的条件γ-智能体，它对群体的目标进行考虑。在分析算法2的过程中，会提出两个猜测，关于蜂拥的空间秩序的关键性解释，和相互连接的移动智能体网络的自组织性。

第三算法具有避障功能。通过β-智能体表现障碍的影响。这些智能体是运动的而且在障碍的边界运动。之后，通过第三种算法的设计和分析，人们可以塑造多种类涌现势能。可以表明，蜂拥的跟踪问题可以通过没有领导者的点对点架构解决。 2.3.1蜂拥控制基本算法（算法1）

由于Reynolds所提出的三条基本规则实际上是基于系统环境中智能体的位置和速度来考虑的。因此，考虑N智能体在n维的欧式空间中运行，假设第i个智能体的运动方程为：

?.?qi?pi, ?.??pi?ui, （2-18）

其中q代表智能体i的位置向量，p代表智能体i的速度向量，u代表智能体i的控制输入（加速度）向量。此时的蜂拥问题就转化为，当输入值u满足什么条件时，能够使得N个智能体的群体行为满足Reynolds所提出的三条规则。

其研究的主要工具是图的应力元素，定义与共识网络G(q)的边(i,j)相对应的应力为

多智能体系统蜂拥问题的研究 18

sij(q)??a(||qj?qi||?)1??||qj?qi||?,(i,j)??(q). （2-19）

不相邻智能体之间的应力元素为0。算法1的蜂拥可以用应力和邻接元素表示成以下形式

上述方程包含了三条Reynolds法则，代表了速度匹配，和蜂拥的聚合，分离规则。

ijijui?a?s(q)(qj?qi)??a(q)(qj?qi)?ui?ui.gd为了证明这一事实，让我们定义Si(q)?我们得到

ui?qg?sij(q).

?sij(q)(qj?qi)?Si(q)(qi??qi?).

（2-20）

是的智能体i的相邻位置加权平均。因此，每个智能体遵循下列规定：a）如果

，则远离加权相邻中心。这与智能体

Si(q)?0，则移向相邻加权中心。b)如果Si(q)?0的速度一致性一起证明了算法1满足三项Reynolds法则。

令时刻t每个智能体的邻域为Ni(t)，他是智能体i能感受到智能体的集合，把智能体视为节点，当两个智能体之间有影响时，把两节点相连，构成边。这些由节点和边组成无向图G(t)。如果每个智能体（节点）邻域内的智能体都不随时间而变化，那么该无向图也不随时间而变化，此时系统具有固定的拓扑结构。如果对于网络中的某个智能体，上一时段在其邻域范围内的一些智能体在某时刻动到了其邻域之外，或者上一时段不在其邻域范围内的一些智能体在某时刻移动到了其临域内，则称系统具有切换拓扑结构。

图G(t)对应的邻接矩阵为A(G(t))?[aij(t)]，其中

??1,j?Ni(t)?aij(t)??, ??0,j?Ni(t)?aii(t)?0? （2-21）

图G(t)的拉普拉斯矩阵为L(G(t))??(G(t))?A(G(t))，其中度矩阵?(G(t))是一个对角矩阵，其中第i个对角元是节点i的度。L(t)是一个对称的半正定矩阵，它的零特征值的数目等于图G(t)中的连通子图的数目。当图G(t)连通时，则L(G(t))的零特征值数目为1，其中对应的特征值向量为全1向量，而且其他特征值均为正。

如果只考虑要求系统中所有的智能体的速度达到一致，就可以对智能体的速度方程

多智能体系统蜂拥问题的研究 19

通过一致算法来实现速度匹配。对于任意两个智能体，若时间趋近于无穷大时，它们的速度向量趋近于相同，则称它们的速度达到一致。连续时间系统的一致算法可以取为：

ui(t)??(pj(t)?pi(t))??aij(t)(pj(t)?pi(t))?lij(t)vj(t) （2-22）

对于固定拓扑结构来说，如果无向图G(t)为连通；或者对于切换拓扑结构来说，如果存在无穷多个非空时间段内无向图的并为连通，那么各个智能体的速度最终能够达到一致。

近年来，许多控制学者通过利用速度一致性和人工势能函数梯度的方法构造蜂拥控制算法以实现Reynolds的蜂拥规则。对于智能体i，其控制输入为：

ui?fi?figd （2-23）

其中右边第一项为人工势能函数梯度，用于实现分离和聚合两条规则。第二项用速度一致性算法，用于实现智能体之间的速度匹配。对于固定拓扑结构，如果拓扑结构是全连通的，则所有的智能体的速度大小和方向将会渐进趋近于一致，系统智能体之间的势能会达到最小，智能体之间不会发生碰撞；对于切换拓扑结构，如果智能体切换前后，拓扑结构图始终能够保持连通则所有的智能体的速度仍然会渐进趋于一致，智能体的势能会达到最小且不会碰撞。

当蜂拥算法1的初始条件是任意选取时，可能会产生分裂象，如图2-8所示。整个群体被分为三个子组，每个子组内的智能体只能与自己子组内的智能体交换信息，而且在自己内部子组中达到局部蜂拥现象，但对于整个群体来说产生了分裂现象；只有当各分组在运行中碰巧相遇，这样子组之间才会发生信息交换。蜂拥控制的实现此时严重依赖于初始值的分布。

图2-8分裂现象

多智能体系统蜂拥问题的研究 20

2.3.2具有单个虚拟领导者的蜂拥控制算法（算法2）

Olfati-Saber针对切换拓扑结构的基本蜂拥算法1容易形成分裂现象，在其基础上增加了关于位置和速度反馈项。对于智能体i，他的控制输入函数为：ui?uig?uid?uir 或

ui????(||qj?qi||?)nij??aij(q)(pj?pi)?fi(qi,pi,qr,pr) （2-24）

r其中uir反映智能体受到来自领导者的影响，定义如下

ui?fi(qi,pi,qr,pr)??c1(qi?qr)?c2(pi?pr),c?0

rr其中(pr,qr)是领导者智能体的速度和位置，一个领导智能是动态或固定的智能体，可以被看到作为移动的汇合点。当领导者智能体是固定的时，(pd,qd)是一个固定的矢量对，这指出了领导者智能原始的位置和速度。当一个领导者智能体是动态的，它有下面的模型。

.?qr?pr,??.??pr?fr(qr,pr), （2-25）

在初始能量有限的假设条件下，Olfati-saber证明了在控制算法2的作用下，Reynolds的三条规则均可以实现，其中包括聚合，速度匹配和避免碰撞。该算法初始值任意选取时，即使因为出是值得原因而分成了各个子组，最终也能保证实现蜂拥，避免发生分裂现象。

2.3.3障碍物环境下的蜂拥算法（算法3）

迄今为止，本文所介绍的多智能体的蜂拥控制都是假设在个不存在障碍物的环境中，智能体的移动不受环境的限制的。对于运动环境中存在障碍物的情形，显然，障碍物对智能体的影响与其二者间的距离有关。智能体和障碍物之间距离存在某一临界值，当两者的距离小于此临界值时，障碍物则会对智能体“产生”排斥力来阻止智能体继续接近障碍物，以避免最终相撞；而二者之间距离大于等于此临界值时，则障碍物与智能体间不存在任何作用力。另外，如果要求智能体集中到达目标位置，显然，目标点对智能体的影响与其二者问的距离也是有关。随着距离的减小，目标点对智能体“产生”吸引力越小，直至智能体到达目标点的吸引力为零。

为了方便表示，Olfati-Saber除了将真正的智能体表示成?智能体，虚拟领导者表示成?智能体外，当智能体和障碍物距离小于临界距离时，把障碍对?智能体的排斥表示

多智能体系统蜂拥问题的研究 21

成?智能体。智能体绕过障碍物时，如图2-9。

图2-9（a）墙壁形障碍物，（b）球形障碍物

定义智能体和障碍物的排斥力方程为

??(t)??h(z/d?)(?1(z?d?)?1)

（2-26）

其中d??|||qi,k?qi||?,?k?Ni?(t),?1?z/1?z2。方程在距离逐渐增大到z=d时，作用力光滑变为0，之后一直为零。它们之间的人工势能函数为

??????(s)ds?0 （2-27）

最终，Olfati-Saber设计除了在障碍物环境下的虚拟领导者的蜂拥控制算法：

ui?fi?fi?figdr （2-28）

其中第一项是基本算法，第二项是避免碰撞，第三项是使智能体达到目标点，具体表示如下

ui?c1ui??a??(||q??c???(||qa1aj?qi||?)ni,j?c2j?qi||?)ni,j??a(q)(p?p)??c?a(q)(p?p)

ijji2ijjia （2-29）

ui??c1?1(qi?qr)?c2(pi?pr)?其中nij?qj?qi1??||qj?qi||2，ni,k?qi,k?qi1??||qi,k?qi||2。

2.4算法仿真结果

多智能体系统蜂拥问题的研究 22

本小节将应用Matlab工具对之前介绍的Olfati-Saber提出的前两种算法进行数值仿真，对理论结果进行验证。下面具体给出仿真参数：仿真时间loop=300，参数??0.1，智能体个数n?50，感知半径r=6，网格结构Lattice期望距离d=5，ph(z)参数h=0.9，a=1，b=2，智能体初始速度范围[?1,1]，智能体初始位置范围为[50]?[50]，领导者智能体参数c1=0.1c2=0.2，离散步长step=0.1。

Matlab仿真框架如下：

1）对智能体初始个数、速度、位置进行初始化。

2）实现各智能体对其感知半径范围内智能体的感知，具体实现为对邻接矩阵

A?[aji]赋值，若智能体

j在智能体i的感知半径内，则[aji]?0，否则[aji]?1。

3）分别用Matlab实现算法1ui?ui????(||qj?qi||?)nij??aij(q)(pj?pi)和算法2：

???(||qj?qi||?)nij??aij(q)(pj?pi)?fi(qi,pi,qr,pr)，求出当前各智能体的加

r速度矢量。

4）用已知量求下时段的各参数，方程为q(t+1)=q(t)+step*p(t)，p(t+1)=p(t)+step*u(t)。 5）通过求得的新阶段智能体的速度，位置矢量，进行下阶段计算。

6）进行loop次运算，每次保存个时间段的智能体速度位置信息，并最后将图形绘制出来。

2.4.1仿真算法1分裂结果

当蜂拥算法1的初始条件是任意选取时，由于初始状态是任意的，所有的智能体不一定能够形成一个连通的拓扑结构，因此可能会产生分裂象，如图2-10所示。整个群体被分为五个子组，每个子组内的智能体只能与自己子组内的智能体交换信息，而且在自己内部子组中达到局部蜂拥现象，但对于整个群体来说产生了分裂现象；只有当各分组在运行中碰巧相遇，这样子组之间才会发生信息交换。蜂拥控制的实现此时严重依赖于初始值的分布。本算法无法在任一条件下实现蜂拥，但是其体现了全部Reynolds原则，为了解决这一问题，Olfati提出了算法2，加入了领导智能体的概念，以避免蜂拥的分裂现象。

多智能体系统蜂拥问题的研究 23

图2-10算法1 仿真分裂结果，n=50

2.4.2算法二仿真结果

图2-11在2维空间中，50个智能体在算法2作用下的涌现行为。最初，50个智能体是随机落在50?50平面空间中的。各个智能体的初始速度坐标是均匀随即从[-1,1]中选取的。与之相对用，领导智能体的初始信息与普通智能体相同。离散步长取值为step=0.1，循环次数loop=100对涌向行为进行仿真，并记录各时间的智能体位置速度信息，在下图中，分别展示了采样时间为0.1，1，2，3，5，10秒的智能体信息。从仿真结果看到，在含有领导智能体的情况下，任意状态下智能体可以实现蜂拥，并使所有的智能体速度大小方向一致，并能形成Lattice结构。

多智能体系统蜂拥问题的研究 24

图2-11. 算法2仿真结果

2.5小结

本章对Reynolds原则和Olfati三种算法进行了详细的介绍，算法1通过各智能体对周围环境的感知形成蜂拥，算法2解决了算法1中由于感知信息不足造成的分裂现象。通过应用Matlab工具对Olfati提出的算法1和算法2进行了仿真，发现算法1在网络初始状态不连通的情况下会产生分裂，而加入虚拟领导者的算法2能较好的避免分裂实现蜂拥。在本章的基础上，我们将针对一些在实际应用中可能出现的问题对Olfati的算法进行改进。

多智能体系统蜂拥问题的研究 25

3 Oflati蜂拥算法改进

前面的章节已经对蜂拥问题的数学描述和Olfati算法进行了详细的介绍，并应用Matlab工具对Olfati提出的算法1和算法2进行了仿真。在此基础上，本章主要针对Olfati提出的算法2从两方面进行改进。

首先，Olfati算法2为了使所有智能体能够形成蜂拥避免分裂现象，每个智能体都知道虚拟领导者的信息，这种方法在现实生活中不易于实现。经一些科学研究表明，在自然界的大部分群集智能体系统中往往只有少部分个体能够感知虚拟领导者的信息，比如，鱼群在觅食过程中只有少部分鱼知道食物的信息，然后把信息传递给附近的智能体，形成蜂拥。本章将针对这一现象，研究仅有部分智能体感知虚拟领导者信息的情况下，群集系统的蜂拥实现情况。

其次，Olfati算法2尽管能够实现蜂拥结果，使每个智能体的速度方向与虚拟领导者速度方向达到一致。然而，在领导者智能体速度时变时，智能体不能够很好的跟踪领导者的速度大小，然而在实际应用中，虚拟领导者的速度一般均为时变。针对此问题，本章将研究当虚拟领导者速度时变时，如何改进蜂拥算法以期达到较好的跟踪效果。

为了开展将要进行的工作，在此首先对Olfati算法2进行简要的回顾介绍。 Olfati-Saber针对切换拓扑结构的基本蜂拥算法1容易形成分裂现象，因为在其基础上增加了关于位置和速度的反馈项。对于智能体i，他的控制输入函数为：

ui?ui?ui?uigdr或

ui????(||qj?qi||?)nij??aij(q)(pj?pi)?fi(qi,pi,qr,pr) （3-1）

r其中uir反映智能体受到来自领导者的影响，uig为速度一致项，uid为人工势能梯度函数。在初始能量有限的假设条件下，Olfati-saber证明了在控制算法2的作用下，Reynolds的三条规则均可以实现，其中包括聚合，速度匹配和避免碰撞。该算法初始值任意选取时，即使网络拓扑结构不连通分成几个子组，最终也能保证实现整体蜂拥，避免发生分裂现象。

3.1部分智能体感知虚拟领导者时蜂拥实现研究

3.1.1引言

之前提出的算法2通过对每个智能体添加引导反馈来实现跟踪目标的功能，假设每个智能体都具有领导智能体的信息，这样的假设的好处是能够保证每个智能体都能够内聚并达到其玩的速度，然而，这个假设和自然中的很多实例是不相符合的。

在自然界中，群体中往往只有很少的个体具有引导信息，比如食物所在的位置或者

多智能体系统蜂拥问题的研究 26

迁移的路线等等。例如，研究鱼群中只有少量鱼具有迁移的路线信息，但是他们能够引导整个鱼群游向期望的地点；人类社会中只有一部分人对未来有明确的认识，但整个人类社会能不断前进。这说明，只需要群体中很少的一部分智能体具有引导信息，群体中的绝大部分智能体就可以达到期望的群体行为。 3.1.2少数个体具有引导信息的蜂拥控制算法

本算法将在算法2中进行一些改进，对加速度方程（2-29）改写如下（算法A1）：

ui????(||qj?qi||?)nij??aij(q)(pj?pi)?M(qr,qi)?fi(qi,pi,qr,pr) （3-2）

r其中当qi含有qr的信息时，M(qr,qi)?1，表示智能体能够感知虚拟领导者的信息。当qi不含有qr的信息时，M(qr,qi)?0，表示智能体不能感知虚拟领导者的信息。通过引入上述数学符号，我们可通过控制M(qr,qi)的值来控制接收到虚拟领导者信息的普通智能体的数目。 3.1.3仿真结果

本节在n个智能体之中随机选取一定比例的智能体作为具有引导信息的智能体。图3-1显示了在n取为100和200的情况下，能够跟随领导智能体的普通智能体所占的百分比，这些数据都是在10次仿真后取平均值的结果。其中仿真周期loop=300，步长step=0.1。

图3-1具有引导信息的智能体百分比同跟随百分比的关系图

从图中可以看到，在一个群体中，能够跟随领导智能体的数目是能感知引导信息智能体的递增函数，当比例占到0.1时，有60%的智能体能够跟随领导智能体。通过两条

多智能体系统蜂拥问题的研究 27

曲线的比较我们可以看出，当智能体总数目增多时，更小比例的智能体就能够满足一定比例跟随的要求。通过以上仿真结果表明，在群集系统中，尤其是大规模群集中，只要控制少部分智能体感知虚拟领导者的信息，群集中的大部分智能体即可达到蜂拥。这一现象对实际应用具有引导性作用，比如应用大规模的传感器对某一目标系统进行跟踪，即使仅有少量传感器能够检测到目标系统状态，只要传感器网络能够在一段时间内保持合并连通，即可有效地对目标系统进行较好的跟踪，这样也可以帮助大量减少传感器的检测能量损耗。

3.2 具有变速度虚拟领导者改进蜂拥算法

3.2.1引言

在虚拟领导者具有变速度的情况下，Olfati-Saber证明了他的算法最终能够使所有的智能体达到相同的速度，但是，通过实际数值仿真表明，最终所有智能体的速度并不等于领导智能体的速度。针对该问题，本节将对Olfati-Saber算法2进行改进，使得所有的智能体最终能够跟踪上虚拟领导者的速度。这一点对跟踪问题十分有用，比如应用无人驾驶飞行器编队对某一不明飞行器进行跟踪，如果仅仅能够实现编队，而无法跟踪上目标系统，则无法进行有效跟踪。 3.2.2算法描述

Olfati-Saber的算法2能够有效地实现蜂拥，即所有的智能体都能够收敛到一个相同的速度。然而，这个速度在一般情况下并不等于领导智能体的速度，本节将提出一种改进的蜂拥控制算法，该算法能够使所有的智能体能够准确的跟踪虚拟领导者的速度值。本节改进的蜂拥控制算法A1如下：

ui????(||qj?qi||?)nij??aij(q)(pj?pi)?fi(qi,pi,qr,pr)?fr(qr,pr)（3-3）

r其中fr(qr,pr)为领导智能体的加速度信息。

在控制输入中加入领导者加速度信息，这在实际应用中也是可实现的。我们可以通过检测智能体的速度或位置应用观测器对加速度进行估计。从以下的仿真结果可看出，速度跟随情况得到了明显的改善。 3.2.3仿真及结果

本节首先对原始算法的智能体速度跟随方向情况进行仿真，虚拟领导者原始速度为在[-1,1]之间的随机取值，且进行匀速直线运动，普通智能体为随机选取的所有智能体中的10个，步长step=0.1s，周期loop=800，如图3-2所示。

之后，本节分别对原始算法（图3-3）和改进算法（图3-4）进行虚拟领导者为变速度时的仿真比较，普通智能体为随机选取的所有智能体中的10个，此时虚拟领导者在

多智能体系统蜂拥问题的研究 28

加速度为fr?[cos(qrx),cos(qry)]T，步长取值step=0.1，周期loop=800。

iii最后，本节将首先对改进算法A1在虚拟领导者为变速度时进行仿真，并进一步研究当接收虚拟领导者信息数占智能体总数为10%时的蜂拥情况(图3-5)。智能体总数目n=100。

在以下的仿真结果中，原始算法为Olfati算法2。

图3-2虚拟领导者匀速运动时原始算法中速度方向与速度模的跟随情况

粗红线为领导者速度信息，细蓝线为普通智能体速度信息

多智能体系统蜂拥问题的研究 29

图3-3虚拟领导者变速运动时原始算法中速度方向与速度模的跟随情况

粗红线为领导者速度信息，细蓝线为普通智能体速度信息

多智能体系统蜂拥问题的研究 30

图3-4虚拟领导者变速运动时改进算法A1中速度方向与速度模的跟随情况

粗红线为领导者速度信息，细蓝线为普通智能体速度信息

多智能体系统蜂拥问题的研究 36

5 结论及展望

群体智能中的个体在无中心控制的情况下体现出来的宏观有序的行为称之为涌现现象。蜂拥问题作为一种典型的涌现现象在自然界中普遍存在，比如鱼群、鸟群、蜂群等。随着国防工业的进一步发展，蜂拥控制被应用于多智能体系统合作控制中，比如无人驾驶飞行器群的控制、海底自治潜艇群的控制，无人深入地区多机器人的群集控制等。本文重点对多智能体的蜂拥控制算法进行了分析研究。

本文的主要工作如下：

（1）本文根据Reynolds法则和Olfati的经典算法，应用Matlab工具搭建了多智能体系统蜂拥控制的算法框架，实现了Olfati算法1和算法2。为多智能体蜂拥行为的研究提供了分析基础。

（2）本文对Olfati算法1和算法2进行了仿真，仿真结果验证了算法1的局限性，既只有在特定的初始条件下（初始状态各个智能体构成的拓扑网络是连通的）才能够形成群体的蜂拥，而在一般情况时，算法1会导致群体的分裂。通过对算法2的仿真研究发现，加入单个虚拟领导者能够改善算法1的弊端，即算法不依赖于智能体初始状态，在任意的初始条件下，多智能体系统都能形成蜂拥，达到格子状结构。

（3）本文在Olfati算法2的基础上，对其进行了三方面的分析和改进：

首先Olfati算法2为了使所有智能体能够形成连通拓扑结构，每个智能体都感知虚拟领导者的信息，这种方法在现实生活中是不易实现的，科学研究表明在自然界中往往只有一部分个体能够感受到领导者信息，之后把信息传递给附近的智能体，进而形成蜂拥。本文针对该现象，研究了仅有部分智能体具有领导者信息时的群集蜂拥问题。通过应用Matlab工具进行仿真，发现仅有部分智能体感知虚拟领导者信息时，依旧有大部分智能体能够达到蜂拥。且当需要实现相同比例的蜂拥时，规模越大的群集所需感知虚拟领导者信息的智能体比例越小。

其次，Olfati算法2尽管已经能够实现蜂拥结果，并使每个智能体的速度方向均和领导者智能体达到一致。然而，在领导者智能体具有变速度情况时，智能体不能够很好的跟踪领导者的速度大小。本文通过对算法进行改进，在反馈信息中加入了领导者加速度分量，使智能体的速度模能够较好地跟踪虚拟领导者的速度模。最后通过仿真对两种算法的速度模跟踪情况进行了仿真，仿真结果表明改进算法相比于原始算法而言，普通智能体的速度模量能够更好的跟随虚拟领导者的速度模量。

最后，Olfati算法2只研究了群体中含单个虚拟领导者的情况，然而在实际应用中，一个群集系统可能会受到多个虚拟领导者的影响。本文对Olfati算法2进行改进，将单个虚拟领导者扩展到多个虚拟领导者情形，并通过仿真验证了改进算法能够很好地克服Olfati算法在直接扩展到多领导者时普通智能体之间相互影响的情况。

对未来工作的展望：

多智能体系统蜂拥问题的研究 37

本文对Olfati算法进行了仿真，并对其进行了改进，但仍存在很多问题可作为下一步的研究方向。

（1）本文对多智能体系统的蜂拥算法进行的实现和改善，已经能够很好的通过Reynolds原则实现智能群体的蜂拥活动。然而，目前的研究还局限在计算机仿真阶段，没有在实际中应用，将蜂拥问题应用到实际中如车队编队，卫星覆盖区域等领域，进一步发现实际应用存在的问题，将会对蜂拥理论有很大的推进作用。

（2）本文在绘制接收领导者信息智能百分比同蜂拥个数百分比的关系曲线时是通过多次运算取平均值的方法进行仿真的，这种方法并不具有严格的可重复性，在之后的工作中，可对这部分进行严格的数学分析，从而得到可重复的实验方法将成为工作的一个重点。

（3）本文的所有仿真实验都是在二维空间中实现的，而现实生活是在三维空间中进行的。所以将蜂拥问题扩展到三维空间实现很有必要。

多智能体系统蜂拥问题的研究 38

参考文献

[1] Reza Olfati-Saber. Flocking for Multi-Agent Dynamic Systems: Algorithms and Theory

[J]. IEEE Transactions on Automatic Control, 2006, 3:401-421.

[2] B.L. Partridge. The chorus-line hypothesis of maneuver in avian flocks [J].Nature, 1984,

309:344–345.

[3] B.L. Partridge. The structure and function of fish schools [J].Scientific American, 1982,

246:114–123.

[4] A. Okubo. Dynamical aspects of animal grouping: swarms, schools, flocks, and herds [J].

Biophysics, 1986, 22:1–94.

[5] C.W. Reynolds. Flocks, herds, and schools: a distributed behavior model[J].Computer

Graphics,1987,21:25–34.

[6] T. Vicsek, A. Cziro′ok, E. Ben-Jacob, I. Cohen, and O. Shochet .Novel type of phase

transition in a system of self-driven particles [J]. Physical Review Letters, 1995, 75: 1226–1229.

[7] J. Toner and Y. Tu. Flocks, herds, and schools: A quantitative theory of

flocking[J].Physical Review E, 1998, 58:4828–4858.

[8] N. Shimoyama, K. Sugawara, T. Mizuguchi, Y. Hayakawa, and M. Sano. Collective

motion in a system of motile elements [J].Physical Review Letters, 1996, 76: 3870–3873.

[9] E. Shaw. Fish in schools [J].Natural History, 1975, 84: 40–45.

[10] D. Helbing, I. Farkas, and T. Vicsek. Simulating dynamical features of escape panic[J].

Nature, 2000, 407: 487–490.

[11] T. Vicsek. A question of scale [J]. Nature, 2001, 411: 421–421.

[12] J. K. Parrish, S. V. Viscido, and D. Grunbaum. Self-organized fish schools: an

examination of emergent properties [J]. Biol. Bull, 2002, 202,296–305.

[13] D. Estrin, R. Govindan, J. Heidemann, and S. Kumar. Next century challenges: scalable

coordination in sensor networks [J] .Proceeding of Mobile Computing and Networking, 1999, 21: 263–270.

[14] A. Mogilner and L. Edelstein-Keshet. Spatio-temporal order in populations of self-

aligning objects: formation of oriented patches [J]. Physica D, 1996, 89: 346–367. [15]赵建. 鱼群集群行为的建模与仿真[D]. 太原: 太原工业大学. 2008.

[16]王澜. 基于广义相关性的多Agent交互作用研究[D]. 西安: 西北工业大学, 2006. [17]王玫, 朱云龙, 何小贤. 群体智能研究综述[J]. 计算机工程, 2005, 1: 194-196. [18]彭喜元, 彭宇, 戴毓丰. 群智能理论及应用[J]. 电子学报, 2003, 12: 1982-1988.

多智能体系统蜂拥问题的研究 39

[19]Bonabeau E,DorigoM, Theraulaz G Swarm Intelligence：From Natural to Artificial

Systems[M].New York: Oxford University Press，1999.

[20]约翰.霍兰.涌现一从混沌到有序[M].上海:上海科学技术出版社,2001.

[21]K E Parsopoulos, M N Vrahatis. Recent approaches to global optimization problems

through particle swarm optimization [J]. Natural Computing , 2002, 2:235-306. [22]约翰.H.霍兰.隐秩序[M].上海:上海科技教育出版社, 2000.

[23]肖人彬,陶振武.群集智能研究进展[J].管理科学学报,2007, 10：3-8．

[24] A. Jadbabaie, J. Lin, and A. S. Morse. Coordination of groups of mobile agents using

nearest neighbor rules[J]. IEEE Transactions on Automatic Control, 2003, 21:988–1001. [25] L. Moreau. Stability of multi-agent systems with time-dependent communication

links[J]. IEEE Trans. on Automatic Control, 2005, 50:169–182.

[26] W. Ren and R.W. Beard. Consensus seeking in multi-agent systems under dynamically

changing interaction topologies[J]. IEEE Transactions on Automatic Control, 2005, 50: 655–661.

[27] R. Olfati-Saber, A. Fax, and R. M. Murray. Consensus and cooperation in multi-agent

networked systems[J]. Proceedings of the IEEE 2005, 95(1):215-233.

[28] Y. Liu, K. M. Passino, and M. M. Polycarpou. Stability analysis of M-dimensional async-

hronous swarms with a fixed communication topology[J]. IEEE Transactions On Automatic Control , 2003, 48:76–95.

[29] V. Gazi and K. M. Passino. Stability analysis of swarms[J]. IEEE Transactions on

Automatic Control, 2003, 48:692–697.

[30]Gdi Caro, M Dofigo. AntNet. Distributed stigmergetic control for communications

networks[J]. Journal of Artificial Intelligence Research, 1998, 9: 317-365．

[31] A. Fax and R. M. Murray. Information flow and cooperative control of vehicle

formations [J]. IEEE Transactions on Automatic Control, 2004, 49:1465–1476.

[32] M. Mesbahi. On state-dependent dynamic graphs and their controllability properties [J].

IEEE Transactions on Automatic Control, 2005, 50: 387–392.

[33] J. Cort′es, S. Martinez, T. Karatas, and F. Bullo. Coverage control for mobile sensing

networks[J].IEEE Transactions on Robotics and Automation, 2004, 20:243–255. [34] P. O¨ gren, E. Fiorelli, and N. E. Leonard. Cooperative control of mobile sensor networks:

adaptive gradient climbing in a distributed environment [J].IEEE Transactions on Automatic Control, 2005, 49: 1292–1302.

[35] O. Khatib. Real-time obstacle avoidance for manipulators and mobile robots [J]. Int.

Journal of Robotics Research, 1986, l5: 90–98.

[36] E. Rimon and D. E. Koditschek. Exact robot navigation using artificial potential

多智能体系统蜂拥问题的研究 40

functions [J]. IEEE Transactions on Robotics and Automation, 1992, 15: 501–518. [37] M. Fiedler. Algebraic connectivity of graphs[J]. Czechoslovak Mathematical Journal,

1973, 23: 298–305.

多智能体系统蜂拥问题的研究 41

致谢

本次毕业课题从2010年3月至今进行了3个月的时间，在这段时间中，我在杨文老师的悉心指导下完成了大学以来最后的一项工作。在这段时间中，我成功地把大学所学应用到实际工作中，尤其是我的编程能力有了很大的提高。本文的完成，得到了杨文老师的很大帮助，她丰富的知识往往在我走入死角时给我进行恰当的点拨。可以说，本文的完成很大程度上源于杨文老师的帮助指导。在此，我对杨文老师表示真诚的感谢，感谢杨文老师帮我给大学画上了一个完美的句号。

本文来源：https://www.bwwdw.com/article/cus6.html