第3期 王中林，等：一种多智能体领航跟随编队新型控制器的设计 ·299· 如可用于编队控制、交通流控制、分布式信息融合以 来验证该算法的正确性及实际可行性。 及生物、经济、工程等领域1 1相关的图论基础 随着无线通信技术以及计算机技术的快速发 展，使多个智能体组成的群体系统通过协调、合作来 为了讨论方便，简单介绍一些文中能够用到的 完成原本由单个智能体无法或难以完成的工作已经 图论中的一些基本的概念和相关的标记符号。更多 成为可能。多智能体系统具有单个智能体难以拥有 图论细节可参阅文献[15]。 的丰富的感知能力、高效率的并行执行能力、优秀稳 图论在连通系统中是非常重要且有效的数学分 定的鲁棒性和卓越的容错能力等优势，因此使得智 析工具。一个无向图G=(V,E)是由非空有限顶点 能体在实际工作环境中的可适应性及实用性均得到 集合和无序的元素偶对ek的集合组成，其中e4= 了大幅提高。而多智能体编队问题是对于多智能体 (:,)∈E称为图的边。文中假设不存在从一个 协调合作问题所开展的研究中的一个典型应用。多 顶点到它自身的边(：，：)，而且由于图G是无向 智能体编队控制主要是指多个智能体在群体运动过 图，所以有H(,)∈E,(,)∈E。如果(， 程中，能够在克服环境限制的同时还保持着期望队 )∈E,那么可以说巴是：的邻居顶点，则顶点， 形，最终都能够顺利到达指定目的地的控制技术。 的邻居顶点集合定义为N:={j:(:,y)∈E,j≠ 多智能体的编队控制是目前对多智能体协调合作问 }。图中顶点：到顶点的一条路径是指从起始 题进行研究的重要基础，引起了国内外广大学者的 顶点：到终止顶点：过程中一系列顶点对组成的连 关注，是国内外进行多智能体系统研究的热点课题。 续的边。如果无向图中任何2个顶点至少有一条路 目前，常用的多智能体编队控制方法主要有分布式 径，那么就说这个图是连通的，否则就是非连通的。 控制、基于行为法、虚结构法、人工势场法和领航跟 在无向图中，用A=(a,)。xn来表示系统的权重 随法等)。 邻接矩阵，其中ag满足aa=0且a防=a:≥0。在无 在以上几种编队方法中，领航一跟随法得到了 向图G中，节点：的度定义为d:=Σa,其中j∈ 广泛应用，并且成为最普遍采用的编队方法之 N。则图G的度矩阵为对角阵D=diag(d,d2,…, 一[6。领航跟随法的基本思想是在多个智能体组 d.)。那么图G的拉普拉斯(Laplacian)矩阵L= 成的群体中，某个智能体被指定为领航者，其余作为 D-A,显然L是对称矩阵。从L的定义中，可以知 它的跟随者，跟随者以一定的距离间隔跟踪领航智 道L的每一行元素之和为零，即L·1。=0,这里 能体的位置和方向1。对于领航一跟随法有2种 1。=(1,1,…,1).x1,从而可以很容易得到L的其中 控制器形式[5，)：控制器和l-p控制器。【-p控制器 一个特征值为零，其对应的特征向量为1。。 的控制目标是使跟随者和领航者之间的距离和相对 转角达到设定值9町。-l控制器考虑的是3个机器人 2控制算法设计 之间的相对位置问题，当跟随者和2个领航者之间 在介绍算法设计之前，这里先对系统的连接拓 的距离达到设定值时，就可以认为整个队形稳定了。 扑图G做一个简要的说明。文中图G的邻接矩阵 文中通过引入基于邻居的局部控制律以及基于 包括两部分，一部分是所有跟随者之间组成的连通 邻居的状态估计规则[9-3]设计了一种领航跟随编 图G的邻接矩阵用表示，相应图G的度矩阵用D表 队算法的新型控制器，在控制器中通过简单地设定 示，而领航者和每个跟随者之间的连接矩阵用B表 跟随者和领航者之间的相对坐标即可轻松实现任意 示。假设系统中包括领航者共有n+1个智能体，那 形状编队，并为了将所有跟随者相对于领航者的相 么A为n×n的对称矩阵：B为n×n的对角矩阵， 对坐标统一映射到领航者的坐标系中，在控制器中 对角线上的元素为跟随者和领航者之间的连接权重 引入了“坐标旋转公式”)，用于实现整个队形的 值，文中假定图G总是连通的，则B对角线上的元 对称轴和领航者的运动方向平行，即所编队形随着 素的值至少有一个不为零，即至少有一个跟随者和 领航者的运动方向的改变做相应旋转。文中设计的 领航者是直接连通的，但这种连通是单向的，就是说 这种新型控制器，既突破了-（控制器中机器人个数 领航者的运动不受跟随者的影响。当系统的拓扑图 的限制又避免了-φ控制器设计偏复杂的缺点。文 在一定时刻变化时，则图G被认为是这n+1个智能 中分别给出了固定拓扑和切换拓扑下的系统稳定编 队的充分条件及相应的证明。文章的最后分别通过 体组成的所有可能的拓扑图集合S={G1,G2,…, MATLAB仿真和在Amigobot机器人平台上做实验 Gw}中的一个，定义P={1,2,…,M}为拓扑图的索如可用于编队控制、交通流控制、分布式信息融合以 及生物、经济、工程等领域［１ ⁃ ４］ 。 随着无线通信技术以及计算机技术的快速发 展，使多个智能体组成的群体系统通过协调、合作来 完成原本由单个智能体无法或难以完成的工作已经 成为可能。 多智能体系统具有单个智能体难以拥有 的丰富的感知能力、高效率的并行执行能力、优秀稳 定的鲁棒性和卓越的容错能力等优势，因此使得智 能体在实际工作环境中的可适应性及实用性均得到 了大幅提高。 而多智能体编队问题是对于多智能体 协调合作问题所开展的研究中的一个典型应用。 多 智能体编队控制主要是指多个智能体在群体运动过 程中，能够在克服环境限制的同时还保持着期望队 形，最终都能够顺利到达指定目的地的控制技术。 多智能体的编队控制是目前对多智能体协调合作问 题进行研究的重要基础，引起了国内外广大学者的 关注，是国内外进行多智能体系统研究的热点课题。 目前，常用的多智能体编队控制方法主要有分布式 控制、基于行为法、虚结构法、人工势场法和领航跟 随法等［５］ 。 在以上几种编队方法中，领航—跟随法得到了 广泛应 用， 并 且 成 为 最 普 遍 采 用 的 编 队 方 法 之 一［６］ 。 领航跟随法的基本思想是在多个智能体组 成的群体中，某个智能体被指定为领航者，其余作为 它的跟随者，跟随者以一定的距离间隔跟踪领航智 能体的位置和方向［７］ 。 对于领航—跟随法有 ２ 种 控制器形式［５ ， ８］ ：控制器和 ｌ⁃φ 控制器。 ｌ⁃φ 控制器 的控制目标是使跟随者和领航者之间的距离和相对 转角达到设定值［９］ 。 ｌ⁃ｌ 控制器考虑的是 ３ 个机器人 之间的相对位置问题，当跟随者和 ２ 个领航者之间 的距离达到设定值时，就可以认为整个队形稳定了。 文中通过引入基于邻居的局部控制律以及基于 邻居的状态估计规则［９ － １３ ］ 设计了一种领航跟随编 队算法的新型控制器，在控制器中通过简单地设定 跟随者和领航者之间的相对坐标即可轻松实现任意 形状编队，并为了将所有跟随者相对于领航者的相 对坐标统一映射到领航者的坐标系中，在控制器中 引入了“坐标旋转公式” ［１４］ ，用于实现整个队形的 对称轴和领航者的运动方向平行，即所编队形随着 领航者的运动方向的改变做相应旋转。 文中设计的 这种新型控制器，既突破了 ｌ⁃ｌ 控制器中机器人个数 的限制又避免了 ｌ⁃φ 控制器设计偏复杂的缺点。 文 中分别给出了固定拓扑和切换拓扑下的系统稳定编 队的充分条件及相应的证明。 文章的最后分别通过 ＭＡＴＬＡＢ 仿真和在 Ａｍｉｇｏｂｏｔ 机器人平台上做实验 来验证该算法的正确性及实际可行性。 １ 相关的图论基础 为了讨论方便，简单介绍一些文中能够用到的 图论中的一些基本的概念和相关的标记符号。 更多 图论细节可参阅文献［１５］。 图论在连通系统中是非常重要且有效的数学分 析工具。 一个无向图 Ｇ ＝ （Ｖ，Ｅ） 是由非空有限顶点 集合和无序的元素偶对 ｅｋ 的集合组成，其中 ｅｋ ＝ （ｖｉ，ｖｊ） ∈ Ｅ 称为图的边。 文中假设不存在从一个 顶点到它自身的边 （ｖｉ，ｖｉ）， 而且由于图 Ｇ 是无向 图，所以有 ∀（ｖｉ，ｖｊ） ∈ Ｅ， （ｖｊ，ｖｉ） ∈ Ｅ 。 如果 （ｖｉ， ｖｊ） ∈ Ｅ ，那么可以说 ｖｊ 是 ｖｉ 的邻居顶点，则顶点 ｖｉ 的邻居顶点集合定义为 Ｎｉ ＝ ｛ｊ：（ｖｉ，ｖｊ） ∈ Ｅ，∀ｊ ≠ ｉ｝ 。 图中顶点 ｖｉ 到顶点 ｖｊ 的一条路径是指从起始 顶点 ｖｉ 到终止顶点 ｖｊ 过程中一系列顶点对组成的连 续的边。 如果无向图中任何 ２ 个顶点至少有一条路 径，那么就说这个图是连通的，否则就是非连通的。 在无向图中，用 Ａ ＝ （ａｉｊ）ｎ×ｎ 来表示系统的权重 邻接矩阵，其中 ａｉｊ 满足 ａｉｉ ＝ ０ 且 ａｉｊ ＝ ａｊｉ ≥ ０。 在无 向图 Ｇ 中，节点 ｖｉ 的度定义为 ｄｉ ＝ Σａｉｊ ，其中 ｊ ∈ Ｎ。 则图 Ｇ 的度矩阵为对角阵 Ｄ ＝ ｄｉａｇ（ｄ１ ，ｄ２ ，…， ｄｎ ） 。 那么图 Ｇ 的拉普拉斯（ Ｌａｐｌａｃｉａｎ） 矩阵 Ｌ ＝ Ｄ －Ａ ，显然 Ｌ 是对称矩阵。 从 Ｌ 的定义中，可以知 道 Ｌ 的每一行元素之和为零，即 Ｌ·１ ｎ ＝ ０，这里 １ ｎ ＝ （１，１，…，１）ｎ×１ ，从而可以很容易得到 Ｌ 的其中 一个特征值为零，其对应的特征向量为 １ ｎ 。 ２ 控制算法设计 在介绍算法设计之前，这里先对系统的连接拓 扑图 Ｇ 做一个简要的说明。 文中图 Ｇ 的邻接矩阵 包括两部分，一部分是所有跟随者之间组成的连通 图 Ｇ － 的邻接矩阵用表示，相应图 Ｇ － 的度矩阵用 Ｄ 表 示，而领航者和每个跟随者之间的连接矩阵用 Ｂ 表 示。 假设系统中包括领航者共有 ｎ ＋ １ 个智能体，那 么 Ａ 为 ｎ × ｎ 的对称矩阵； Ｂ 为 ｎ × ｎ 的对角矩阵， 对角线上的元素为跟随者和领航者之间的连接权重 值，文中假定图 Ｇ 总是连通的，则 Ｂ 对角线上的元 素的值至少有一个不为零，即至少有一个跟随者和 领航者是直接连通的，但这种连通是单向的，就是说 领航者的运动不受跟随者的影响。 当系统的拓扑图 在一定时刻变化时，则图 Ｇ 被认为是这 ｎ ＋ １ 个智能 体组成的所有可能的拓扑图集合 Ｓ ＝ ｛Ｇ１ ，Ｇ２ ，…， ＧＭ ｝ 中的一个，定义 Ｐ ～ ＝ ｛１，２，…，Ｍ｝ 为拓扑图的索 第 ３ 期 王中林，等：一种多智能体领航跟随编队新型控制器的设计 ·２９９·