工程科学学报，第40卷，第8期：893-900,2018年8月 Chinese Journal of Engineering,Vol.40,No.8:893-900,August 2018 DOI:10.13374/j.issn2095-9389.2018.08.001;http://journals.ustb.edu.cn 多机器人编队控制研究进展 贾永楠，李 擎四 北京科技大学自动化学院，北京100083 ☒通信作者，E-mail:liqing@ics.usth.cu.cm 摘要首先介绍了传统的编队控制方法的定义、特点和常用方法及优缺点，并将传统编队控制时代定义为前编队控制时 代.随着多智能体技术的发展，将多智能体技术引入到编队控制问题中，诞生了众多新的研究成果，称为后编队控制时代。后 编队控制时代以多智能体技术为基础，随着通信技术、计算机技术、人工智能技术的发展而逐渐壮大起来，并受到了学者的广 泛关注.前编队控制时代强调多机器人通过编队协作完成单个机器人无法实现的任务，提高任务完成效率且缩短任务完成时 间.后编队控制时代则是在前编队控制时代的基础上，更强调低成本、同步性和协同性，但却不那么重视每个个体的任务分 工，甚至是按照规则自由分配任务，不再有“不可替代”的个体存在.最后给出了研究编队控制问题的基本思路和目前尚待解 决的关键问题. 关键词机器人：编队控制：多智能体技术：大规模系统：分布式控制 分类号V249.1 Research development of multi-robot formation control JIA Yong-nan,LI Qing School of Automation and Electrical Engineering,University of Science and Technology Beijing,Beijing 100083,China Corresponding author,E-mail:liqing@ies.ustb.edu.cn ABSTRACT Multi-robot formation control is one of the most important research directions in the field of robotics.In this paper,the definition and characteristics of multi-robot formation control were given and several traditional formation control methods were intro- duced,such as leader-follower method,behavior-based method,artificial potential method,and virtual structure method,and their ad- vantages and disadvantages were stated.The era in which these traditional control methods are applied is termed as "Former Formation Control Era"(FFCE).Following the development of multi-agent theory,the multi-agent technology has become popular and is consid- ered as an efficient solution to the multi-robot system formation control problem,and it has generated several favorable results.The era in which this technology is adopted is termed the "Post Formation Control Era"(PFCE).In this era,the multi-agent theory has gained much attention following the developments in the communication technology,computation technology,and artificial intelligence technol- ogy.The FFCE emphasizes that multiple robots are able to accomplish complex tasks that are unachievable by a single robot,while forming a desired formation,which improves the efficiency of a required task as well as shorten the completion time of the task.Howev- er,the PFCE emphasizes much more cost-effectiveness,synchronization,and coordination than the FFCE.Meanwhile,the PFCE does not pay much attention to the task assignment for each individual,but assigns each sub-task autonomously to each individual on the ba- sis of simple rules,and there exists no "irreplaceable"individual.Finally,this paper presented the basic steps for solving the forma- tion control problem using multi-agent technologies. KEY WORDS robots;formation control;multi-agent technology;large-scale system;distributed control 收稿日期：2017-09-29 基金项目：国家自然科学基金青年资助项目(61603362)：国家博士后基金资助项目(2016M600923):北京科技大学基本科研业务费资助项目 (2017年度)
工程科学学报,第 40 卷,第 8 期:893鄄鄄900,2018 年 8 月 Chinese Journal of Engineering, Vol. 40, No. 8: 893鄄鄄900, August 2018 DOI: 10. 13374 / j. issn2095鄄鄄9389. 2018. 08. 001; http: / / journals. ustb. edu. cn 多机器人编队控制研究进展 贾永楠, 李 擎苣 北京科技大学自动化学院, 北京 100083 苣 通信作者, E鄄mail: liqing@ ies. ustb. edu. cn 摘 要 首先介绍了传统的编队控制方法的定义、特点和常用方法及优缺点,并将传统编队控制时代定义为前编队控制时 代. 随着多智能体技术的发展,将多智能体技术引入到编队控制问题中,诞生了众多新的研究成果,称为后编队控制时代. 后 编队控制时代以多智能体技术为基础,随着通信技术、计算机技术、人工智能技术的发展而逐渐壮大起来,并受到了学者的广 泛关注. 前编队控制时代强调多机器人通过编队协作完成单个机器人无法实现的任务,提高任务完成效率且缩短任务完成时 间. 后编队控制时代则是在前编队控制时代的基础上,更强调低成本、同步性和协同性,但却不那么重视每个个体的任务分 工,甚至是按照规则自由分配任务,不再有“不可替代冶的个体存在. 最后给出了研究编队控制问题的基本思路和目前尚待解 决的关键问题. 关键词 机器人; 编队控制; 多智能体技术; 大规模系统; 分布式控制 分类号 V249郾 1 收稿日期: 2017鄄鄄09鄄鄄29 基金项目: 国家自然科学基金青年资助项目(61603362);国家博士后基金资助项目(2016M600923);北京科技大学基本科研业务费资助项目 (2017 年度) Research development of multi鄄robot formation control JIA Yong鄄nan, LI Qing 苣 School of Automation and Electrical Engineering, University of Science and Technology Beijing, Beijing 100083, China 苣 Corresponding author, E鄄mail: liqing@ ies. ustb. edu. cn ABSTRACT Multi鄄robot formation control is one of the most important research directions in the field of robotics. In this paper, the definition and characteristics of multi鄄robot formation control were given and several traditional formation control methods were intro鄄 duced, such as leader鄄follower method, behavior鄄based method, artificial potential method, and virtual structure method, and their ad鄄 vantages and disadvantages were stated. The era in which these traditional control methods are applied is termed as “Former Formation Control Era冶 (FFCE). Following the development of multi鄄agent theory, the multi鄄agent technology has become popular and is consid鄄 ered as an efficient solution to the multi鄄robot system formation control problem, and it has generated several favorable results. The era in which this technology is adopted is termed the “Post Formation Control Era冶 (PFCE). In this era, the multi鄄agent theory has gained much attention following the developments in the communication technology, computation technology, and artificial intelligence technol鄄 ogy. The FFCE emphasizes that multiple robots are able to accomplish complex tasks that are unachievable by a single robot, while forming a desired formation, which improves the efficiency of a required task as well as shorten the completion time of the task. Howev鄄 er, the PFCE emphasizes much more cost鄄effectiveness, synchronization, and coordination than the FFCE. Meanwhile, the PFCE does not pay much attention to the task assignment for each individual, but assigns each sub鄄task autonomously to each individual on the ba鄄 sis of simple rules, and there exists no “irreplaceable冶 individual. Finally, this paper presented the basic steps for solving the forma鄄 tion control problem using multi鄄agent technologies. KEY WORDS robots; formation control; multi鄄agent technology; large鄄scale system; distributed control
.894. 工程科学学报，第40卷，第8期 众所周知，多机器人系统（又称群体机器人）的 机器人系统能够按照既定的路线运行，并且保持指 诞生主要是由于当时技术所限，单体机器人的智能 定的队形.队形的变换，通常是指在队形行进过程 性无法突破，因此希望藉由多机器人之间的协调、合 中，当多机器人系统遇到障碍物时，为了躲避障碍物 作来应对单体机器人无法完成的复杂任务.而这一 而需要临时变换成易于通过障碍物的队形，在通过 思想受到了科研界和工程界的高度关注.其中，编 障碍物之后，队形再变换回初始队形状态.在任务 队控制问题是多机器人系统协调、合作的基础和难 的执行过程中，由于环境的复杂性，队形的形成、保 点.多年来，诞生了大量的研究成果，并形成了以跟 持和变换三个子过程通常会切换发生.队形的形成 随领航者法山、虚拟结构法]、基于行为控制法[3)、 和队形的保持可以由不同编队控制策略完成，也可 人工势场法[4]为代表的多种编队控制方法.发展至 以由某一较为系统的编队控制策略完成.而队形的 今，上述编队控制方法已经相对成熟且各有优势. 变换因为受外部环境驱动，所以一般会选择另外一 针对具体工程问题，也常常将这些方法组合使用，以 种控制策略来实现.在同一复杂任务执行过程中， 达到期望的编队控制效果. 不同控制策略之间常常需要设计一定的判断条件， 然而，时至今日，科技发展速度之快超乎想象. 实现不同控制策略的切换.如图1所示，根据任务 当搭载了深度学习智能算法的阿尔法狗多次战胜当 执行环境的不同，编队控制问题可分为无人机编 今世界最顶级的棋手时，单体机器人的智能性被认 队[5-6)、机器鱼编队7-】、轮式机器人编队[0-)等 为已经有了飞速的提升，甚至具备完成某些复杂任 等.多机器人编队控制在工业、农业，甚至军事领域 务的能力.在这种形势下，以编队控制为代表的多 都具有重要的应用价值和广泛的应用前景， 机器人协同模式是否该退出历史舞台了呢？答案是 在多年编队控制的研究过程中，逐渐形成了以 否定的.与此形成鲜明对比的是，科研界和工程界 跟随领航者、基于行为法、人工势场法、虚拟结构法 对多智能体协同控制的关注比以前更为高涨，并且 为代表的多种成熟、稳定的编队控制策略，并广泛应 对多机器人编队控制有了新的认识和注解.因此， 用于边防巡逻、资源探测、搜索营救等各种实际应用 本文将重点从全新的角度对当前及未来多机器人编 中.跟随领航者法的基本思想是指定系统中某一个 队控制方法的研究进展进行阐述 或多个机器人为领航者，其余机器人为跟随者.跟 本文组织结构如下：第1部分概述传统编队控 随领航者的策略非常通俗易懂.领航者机器人一般 制的定义及常见控制方法的基本思想和优缺点，第 为可以得到全局信息或是接收到具体任务执行方式 2部分从全新角度阐述多机器人编队控制的新思 的机器人，而跟随者机器人通常以领航者的位置和 路，第3部分列举了当前多机器人编队控制领域的 姿态为基准，以指定的间距和相对姿态跟随领航者 最新研究成果，第4部分归纳总结多机器人编队控 的运动.因此，通过控制领航者的轨迹，就可以控制 制领域有待深入研究的关键问题， 整个机器人系统的整体行为.但跟随领航者方法具 有致命的缺陷，一旦领航者失效，系统就迅速瓦解， 1编队控制的定义及常见研究方法 不再具有任务执行能力.因此，跟随领航者法不能 机器人的出现是为了将人类从繁复、危险或是 单独使用.改进的方法通常有两种：一是与其他编 未知的工作环境中解脱出来.然而单体机器人在信 队控制方法结合，优势互补：二是通过增加领航者的 息的获取、处理、控制等方面的能力有限，随着工作 数量或引入领航者更替的规则来改进跟随领航者方 环境复杂程度的增加，迫切需要依靠多机器人的协 法.基于行为法的思想非常简单，即设计一系列机 同来提升系统的任务执行能力，完成单体机器人难 器人的基本行为，如避障、导航、巡航等，利用基本行 以独立完成的复杂任务 为的组合来实现全局的编队行为.基于行为法针对 多机器人编队控制是一种特殊的协同任务，即 具体问题常常非常有效，但也有为人诟病的缺点，比 在一定的编队控制策略的作用下，所有机器人能够 如很难对行为进行数学分析，且队形难以保持.虚 从某一初始状态逐渐形成期望的队形.机器人编队 拟结构法是将队形对应为刚性的虚拟结构体，每个 控制主要包含三个子任务，即队形的形成、队形的保 机器人以结构体中对应的顶点为跟随目标，从而将 持和队形的变换.队形的形成，即一群具有随机初 编队问题转化为跟踪问题来解决.该方法常用于无 始状态的机器人，在一定的编队控制策略作用下，逐 避障要求的编队任务中.人工势场法是通过在机器 渐形成有序的期望队形.一般所谓的编队控制都是 人系统内设计虚拟的势场来约束各个机器人的行 指队形的形成.队形的保持则是指队形形成之后， 为，常用的势场力有两种，一是吸引力，二是排斥力
工程科学学报,第 40 卷,第 8 期 众所周知,多机器人系统(又称群体机器人)的 诞生主要是由于当时技术所限,单体机器人的智能 性无法突破,因此希望藉由多机器人之间的协调、合 作来应对单体机器人无法完成的复杂任务. 而这一 思想受到了科研界和工程界的高度关注. 其中,编 队控制问题是多机器人系统协调、合作的基础和难 点. 多年来,诞生了大量的研究成果,并形成了以跟 随领航者法[1] 、虚拟结构法[2] 、基于行为控制法[3] 、 人工势场法[4]为代表的多种编队控制方法. 发展至 今,上述编队控制方法已经相对成熟且各有优势. 针对具体工程问题,也常常将这些方法组合使用,以 达到期望的编队控制效果. 然而,时至今日,科技发展速度之快超乎想象. 当搭载了深度学习智能算法的阿尔法狗多次战胜当 今世界最顶级的棋手时,单体机器人的智能性被认 为已经有了飞速的提升,甚至具备完成某些复杂任 务的能力. 在这种形势下,以编队控制为代表的多 机器人协同模式是否该退出历史舞台了呢? 答案是 否定的. 与此形成鲜明对比的是,科研界和工程界 对多智能体协同控制的关注比以前更为高涨,并且 对多机器人编队控制有了新的认识和注解. 因此, 本文将重点从全新的角度对当前及未来多机器人编 队控制方法的研究进展进行阐述. 本文组织结构如下:第 1 部分概述传统编队控 制的定义及常见控制方法的基本思想和优缺点,第 2 部分从全新角度阐述多机器人编队控制的新思 路,第 3 部分列举了当前多机器人编队控制领域的 最新研究成果,第 4 部分归纳总结多机器人编队控 制领域有待深入研究的关键问题. 1 编队控制的定义及常见研究方法 机器人的出现是为了将人类从繁复、危险或是 未知的工作环境中解脱出来. 然而单体机器人在信 息的获取、处理、控制等方面的能力有限,随着工作 环境复杂程度的增加,迫切需要依靠多机器人的协 同来提升系统的任务执行能力,完成单体机器人难 以独立完成的复杂任务. 多机器人编队控制是一种特殊的协同任务,即 在一定的编队控制策略的作用下,所有机器人能够 从某一初始状态逐渐形成期望的队形. 机器人编队 控制主要包含三个子任务,即队形的形成、队形的保 持和队形的变换. 队形的形成,即一群具有随机初 始状态的机器人,在一定的编队控制策略作用下,逐 渐形成有序的期望队形. 一般所谓的编队控制都是 指队形的形成. 队形的保持则是指队形形成之后, 机器人系统能够按照既定的路线运行,并且保持指 定的队形. 队形的变换,通常是指在队形行进过程 中,当多机器人系统遇到障碍物时,为了躲避障碍物 而需要临时变换成易于通过障碍物的队形,在通过 障碍物之后,队形再变换回初始队形状态. 在任务 的执行过程中,由于环境的复杂性,队形的形成、保 持和变换三个子过程通常会切换发生. 队形的形成 和队形的保持可以由不同编队控制策略完成,也可 以由某一较为系统的编队控制策略完成. 而队形的 变换因为受外部环境驱动,所以一般会选择另外一 种控制策略来实现. 在同一复杂任务执行过程中, 不同控制策略之间常常需要设计一定的判断条件, 实现不同控制策略的切换. 如图 1 所示,根据任务 执行环境的不同,编队控制问题可分为无人机编 队[5鄄鄄6] 、机器鱼编队[7鄄鄄9] 、轮式机器人编队[10鄄鄄13] 等 等. 多机器人编队控制在工业、农业,甚至军事领域 都具有重要的应用价值和广泛的应用前景. 在多年编队控制的研究过程中,逐渐形成了以 跟随领航者、基于行为法、人工势场法、虚拟结构法 为代表的多种成熟、稳定的编队控制策略,并广泛应 用于边防巡逻、资源探测、搜索营救等各种实际应用 中. 跟随领航者法的基本思想是指定系统中某一个 或多个机器人为领航者,其余机器人为跟随者. 跟 随领航者的策略非常通俗易懂. 领航者机器人一般 为可以得到全局信息或是接收到具体任务执行方式 的机器人,而跟随者机器人通常以领航者的位置和 姿态为基准,以指定的间距和相对姿态跟随领航者 的运动. 因此,通过控制领航者的轨迹,就可以控制 整个机器人系统的整体行为. 但跟随领航者方法具 有致命的缺陷,一旦领航者失效,系统就迅速瓦解, 不再具有任务执行能力. 因此,跟随领航者法不能 单独使用. 改进的方法通常有两种:一是与其他编 队控制方法结合,优势互补;二是通过增加领航者的 数量或引入领航者更替的规则来改进跟随领航者方 法. 基于行为法的思想非常简单,即设计一系列机 器人的基本行为,如避障、导航、巡航等,利用基本行 为的组合来实现全局的编队行为. 基于行为法针对 具体问题常常非常有效,但也有为人诟病的缺点,比 如很难对行为进行数学分析,且队形难以保持. 虚 拟结构法是将队形对应为刚性的虚拟结构体,每个 机器人以结构体中对应的顶点为跟随目标,从而将 编队问题转化为跟踪问题来解决. 该方法常用于无 避障要求的编队任务中. 人工势场法是通过在机器 人系统内设计虚拟的势场来约束各个机器人的行 为,常用的势场力有两种,一是吸引力,二是排斥力. ·894·
贾永楠等：多机器人编队控制研究进展 ·895· (a) 图1各种机器人编队.(a)[和(b)[无人机编队：(c)[⑧)和(d)[列机器鱼编队：()[]和()[2]轮式机器人编队 Fig.1 Formation control of certain kinds of robots:(a)[s]and (b)[6]formation control of unmanned aerial vehicles;(e)(s]and (d)]formation control of robotic fish:(e)(]and (f)(]formation control of mobile robots 机器人运动的目标（如位置等）对机器人产生一定 作效率，其核心思想重在“协作(collaboration)”. 的吸引力，促使机器人朝目标的方向移动，为保证机 2编队控制新思想 器人之间的安全移动，当机器人之间的距离小于安 全距离的时候，会在机器人之间产生一定的排斥力， 近年来，科学技术飞速发展，特别是计算机、通 使得机器人无法靠得更近，从而避免机器人之间的 信、大数据、人工智能等技术的突破昭示着机器人时 碰撞.当吸引力和排斥力达到平衡时，机器人间的 代的到来.单体机器人的智能性因此迅速得到提 距离达到稳定，并形成期望的队形.虽然人工势场 升.当单个机器人的智能性可以媲美甚至超越人类 法在实际编队控制中应用广泛，但由于人工势场法 时，多机器人协同控制仍然有其存在的必要，时代赋 容易陷入局部极值点，使得人工势场法的应用也受 予了多机器人编队控制以新的使命一那就是从成 到了一定的限制. 本、效率和规模的角度，对多机器人的协同控制进行 本文将以上述方法为代表的多机器人编队控制 重新的思考和定位. 时代称为前编队控制时代.这一时期的特点是以任 后编队控制时代主要朝两个方向进行延伸.一 务为导向，偏重于针对小规模（几个到几十个机器 是由于硬件技术的发展，赋予单体机器人更好的定 人)的多机器人系统的实际任务设计编队控制策 位感知、数据处理、运动控制等能力，由此带来了一 略，很难有较为系统、完整的编队控制解决方案.这 些新的研究思路和方法.该方向可以认为是前编队 一阶段的编队控制大多通过机器人之间的合作来提 控制时代的直接延伸，由于单体机器人智能性的提 升系统的任务完成能力，同时降低工作时间、提高工 升，使得多机器人系统执行更为复杂的协同任务成
贾永楠等: 多机器人编队控制研究进展 图 1 各种机器人编队. (a) [5] 和(b) [6] 无人机编队; (c) [8] 和(d) [9] 机器鱼编队; (e) [11] 和(f) [12] 轮式机器人编队 Fig. 1 Formation control of certain kinds of robots: (a) [5] and (b) [6] formation control of unmanned aerial vehicles; (c) [8] and (d) [9] formation control of robotic fish; (e) [11] and (f) [12] formation control of mobile robots 机器人运动的目标(如位置等)对机器人产生一定 的吸引力,促使机器人朝目标的方向移动,为保证机 器人之间的安全移动,当机器人之间的距离小于安 全距离的时候,会在机器人之间产生一定的排斥力, 使得机器人无法靠得更近,从而避免机器人之间的 碰撞. 当吸引力和排斥力达到平衡时,机器人间的 距离达到稳定,并形成期望的队形. 虽然人工势场 法在实际编队控制中应用广泛,但由于人工势场法 容易陷入局部极值点,使得人工势场法的应用也受 到了一定的限制. 本文将以上述方法为代表的多机器人编队控制 时代称为前编队控制时代. 这一时期的特点是以任 务为导向,偏重于针对小规模(几个到几十个机器 人)的多机器人系统的实际任务设计编队控制策 略,很难有较为系统、完整的编队控制解决方案. 这 一阶段的编队控制大多通过机器人之间的合作来提 升系统的任务完成能力,同时降低工作时间、提高工 作效率,其核心思想重在“协作(collaboration)冶. 2 编队控制新思想 近年来,科学技术飞速发展,特别是计算机、通 信、大数据、人工智能等技术的突破昭示着机器人时 代的到来. 单体机器人的智能性因此迅速得到提 升. 当单个机器人的智能性可以媲美甚至超越人类 时,多机器人协同控制仍然有其存在的必要,时代赋 予了多机器人编队控制以新的使命———那就是从成 本、效率和规模的角度,对多机器人的协同控制进行 重新的思考和定位. 后编队控制时代主要朝两个方向进行延伸. 一 是由于硬件技术的发展,赋予单体机器人更好的定 位感知、数据处理、运动控制等能力,由此带来了一 些新的研究思路和方法. 该方向可以认为是前编队 控制时代的直接延伸,由于单体机器人智能性的提 升,使得多机器人系统执行更为复杂的协同任务成 ·895·
·896· 工程科学学报，第40卷，第8期 为可能.二是受自然界中群居生物的协同行为启 扰能力强等优势.由于采用分布式控制协议、自组 发，将多智能体技术应用于多机器人系统的编队控 织网络架构，使得单体机器人功能的失效并不会影 制中去，使得大规模（数以百计）机器人系统的协同 响最终整个系统任务的完成度，同时也便于系统规 控制问题得以解决，这也是后编队时代最核心和特 模的扩展，系统配置的灵活性大大提高，可有效应对 色之处. 多种复杂任务 多智能体系统是近年来发展迅速的一门综合 综上所述，新的编队控制时代已经到来.其核 性、多学科交叉的复杂性科学4-】，涉及控制、数 心特点是强调单一个体仅具有有限的智能性，依靠 学、生物、物理、计算机、通信等，受到了众多科研工 简单规则和邻居间的局部交互，呈现出复杂的编队 作者的高度关注.其灵感来源于群居动物的群体优 协同行为，依靠数量优势完成勘探、搜救等复杂任 势.如图2所示，自然界中的鸟群、蜂群、鱼群、鸽群务.从工程应用角度来看，新的编队控制时代的优 等常常呈现出宏大壮观、绚丽多姿的复杂群体协同势是低成本、大规模、高效率。与传统编队控制时代 编队运动，用于觅食、迁徙、躲避敌害或是应对外界 相比，更强调同步性(synchronization)、协同性(coor- 突发情况].这些群体的特点是单个个体的智能 dination),但却不那么重视每个机器人的任务分工， 性有限，属于低等动物群体行列，但就是这些低等动 甚至可以按照规则自由分配任务，不再有“不可替 物依靠群体的力量在适者生存的自然选择条件下赢 代”的个体存在 得了生存的机会.大量的科学观察与实验已经发 3编队控制最新进展 现：在整体上呈现出复杂群体行为的系统，其个体行 为往往却是相对简单的，甚至其个体行为并不是以 基于上述思想，众多学者围绕编队控制开展了 自我意志为转移，而是完全根据其邻居行为的变化 深入的研究，并得到了许多研究成果 而变化.他们通常通过简单的规则和局部的交互， 图论是多智能体技术的基础，将图论的相关知 最终在整体上涌现出规则有序的群集行为[20-21]. 识引入编队控制中，可方便地对系统进行描述，且易 除了提高任务完成效率、降低任务完成时间等 于扩展、删减、增加系统中个体数量.一个图通常由 传统编队控制的优势外，将多智能体技术引入编队 顶点和边组成.将每个机器人看作顶点，机器人之 控制之后，新的编队控制系统还具有鲁棒性强、抗干 间的交互关系看作是边，那么多机器人系统就构成 (b) 图2自然界中的协同现象.(a)鸟群（图片来自www.cp.m):(b)蜂群（图片来自NEW YORK POST):(c)鱼群（图片来自东方IC): (d)鸽群（图片来自cm.dreamstime.com) Fig.2 Coordination phenomena in nature:(a)a flock of birds (source:www.cfp.cn);(b)swarm of bees source:New York Post);(c)school of fish source:east IC);(d)herd of pigeons source:en.dreamstime.com))
工程科学学报,第 40 卷,第 8 期 为可能. 二是受自然界中群居生物的协同行为启 发,将多智能体技术应用于多机器人系统的编队控 制中去,使得大规模(数以百计)机器人系统的协同 控制问题得以解决,这也是后编队时代最核心和特 色之处. 图 2 自然界中的协同现象. (a) 鸟群(图片来自 www. cfp. cn); ( b) 蜂群(图片来自 NEW YORK POST); ( c) 鱼群(图片来自东方 IC); (d) 鸽群(图片来自 cn. dreamstime. com) Fig. 2 Coordination phenomena in nature: (a) a flock of birds (source: www. cfp. cn); (b) swarm of bees (source: New York Post); (c) school of fish ( source: east IC); (d) herd of pigeons (source: cn. dreamstime. com)) 多智能体系统是近年来发展迅速的一门综合 性、多学科交叉的复杂性科学[14鄄鄄18] ,涉及控制、数 学、生物、物理、计算机、通信等,受到了众多科研工 作者的高度关注. 其灵感来源于群居动物的群体优 势. 如图 2 所示,自然界中的鸟群、蜂群、鱼群、鸽群 等常常呈现出宏大壮观、绚丽多姿的复杂群体协同 编队运动,用于觅食、迁徙、躲避敌害或是应对外界 突发情况[19] . 这些群体的特点是单个个体的智能 性有限,属于低等动物群体行列,但就是这些低等动 物依靠群体的力量在适者生存的自然选择条件下赢 得了生存的机会. 大量的科学观察与实验已经发 现:在整体上呈现出复杂群体行为的系统,其个体行 为往往却是相对简单的,甚至其个体行为并不是以 自我意志为转移,而是完全根据其邻居行为的变化 而变化. 他们通常通过简单的规则和局部的交互, 最终在整体上涌现出规则有序的群集行为[20鄄鄄21] . 除了提高任务完成效率、降低任务完成时间等 传统编队控制的优势外,将多智能体技术引入编队 控制之后,新的编队控制系统还具有鲁棒性强、抗干 扰能力强等优势. 由于采用分布式控制协议、自组 织网络架构,使得单体机器人功能的失效并不会影 响最终整个系统任务的完成度,同时也便于系统规 模的扩展,系统配置的灵活性大大提高,可有效应对 多种复杂任务. 综上所述,新的编队控制时代已经到来. 其核 心特点是强调单一个体仅具有有限的智能性,依靠 简单规则和邻居间的局部交互,呈现出复杂的编队 协同行为,依靠数量优势完成勘探、搜救等复杂任 务. 从工程应用角度来看,新的编队控制时代的优 势是低成本、大规模、高效率. 与传统编队控制时代 相比,更强调同步性(synchronization)、协同性(coor鄄 dination),但却不那么重视每个机器人的任务分工, 甚至可以按照规则自由分配任务,不再有“不可替 代冶的个体存在. 3 编队控制最新进展 基于上述思想,众多学者围绕编队控制开展了 深入的研究,并得到了许多研究成果. 图论是多智能体技术的基础,将图论的相关知 识引入编队控制中,可方便地对系统进行描述,且易 于扩展、删减、增加系统中个体数量. 一个图通常由 顶点和边组成. 将每个机器人看作顶点,机器人之 间的交互关系看作是边,那么多机器人系统就构成 ·896·
贾永楠等：多机器人编队控制研究进展 ·897· 了一个交互网络，也成为拓扑图.如果机器人彼此 题[29]和基于距离(distance-based)的编队控制问 是邻居，有交互，那么该边的值为1：反之，则为0. 题[0].其中重点针对基于距离的编队控制问题进 不同邻居间的相互影响程度也可以不同，那么边的 行了详细的分类，包括无向编队和有向编队.Oh等 值就可能是0到1之间的某一个值，这样的拓扑图 还总结了未来可应用于编队控制的多种多智能体方 就称为有权重的图. 法，包括蜂拥(flocking)[3]、估计法(estimation-- 在机器人编队控制中，每个机器人常常被看作 based))、单纯基于距离的控制方法[3]、基于角度 质点.这里也需要对机器人进行建模.多智能体技 (angle-based)的控制方法[]、包围(containment)控 术中常常将智能体看作一阶或是二阶积分器的形 制]和圆环跟随(cyclic pursuit)I36]等等. 式，但是机器人本体往往是非线性的，因此还需要针 随着传感器技术的发展，视觉传感器信息技术 对机器人自身的物理和运动约束，设计合理的机器 成为了原有感知、导航、通信手段的一个重要补充. 人模型。多智能体技术本身的鲁棒性和良好的抗干 于是基于视觉的编队控制问题成为一个新的研究热 扰能力使得考虑较为复杂的机器人模型，并开展深 点[37-41].例如，当GPS信号被切断、机器人无法得 入地数学分析和仿真验证成为可能.目前影响最为 到自己的位置信息时，Montijano等提出了基于视觉 广泛的模型有两种，分别是Boid模型[2]和Vicsek 的分布式编队控制方法，在不需要外部定位信息的 模型[2s].Boid模型是l986年由Reynolds发明的一 前提下，也可以有效解决多机器人的编队控制问 种用于模拟鸟类等动物的群体运动的计算机模型. 题).Wang等甚至提出一种不依赖个体之间的相 Vicsek模型则由匈牙利物理学家Vicsek T及其合作 对位置信息和通信、而只靠视觉信息来解决领航者- 者于1995年从统计力学的角度提出，不仅算法简 跟随者编队控制问题的新方法[3].Moshtagh等则 单，而且能比较真实的模拟自然界的鸟群、鱼群等的 设计了完全基于视觉信息的分布式控制协议，针对 同步现象.此外，Vicsek模型还可以通过改变个体 具有非完整约束的机器人的运动协同问题展开研 的密度以及噪声的强度得到不同群集协同运动. 究】，他们虽然考虑了机器人之间的避碰问题，但 多智能体技术的基础是一致性协议.一致性协 与编队策略是解耦关系.Morozova则提出了利用虚 议的思想是把邻居行为的差异作为个体的反馈控制 拟领航者和排斥势函数来解决一阶和二阶积分器模 量来对个体的行为进行调节.该算法思想简单易 型的分布式编队控制中的避碰和避障问题[].此 懂，实用性强，因此得到了学者和工程师的认可.早 外，Jia和Wang则是利用蜂拥算法来解决多机器鱼 在2006年，任伟等就提出了利用一致性的方法解决 的编队控制及避碰问题，其中一致性算法用于实现 多机器人的编队控制问题2].同年，Gennaro等提 群体行为的协调，势函数则用于形成队形及避免碰 出利用分布式导航函数来设计协同协议实现多智能 撞[].连通性保持也是实现多智能体系统一致性的 体的编队控制，导航函数的最小值对应期望的编队 重要条件之一.Poonawala等针对考虑避碰和分布 结构[].基于多智能体理论，系统往往在时间趋向 式连通性保持的多轮式机器人系统的编队控制问题 于无穷时才能达到稳定，即形成期望的编队.为了 展开研究[].采样数据和时延也是工程实践中不 满足工程应用，Xao等提出了在有限时间内解决多 可忽视的因素，L山等利用分布式控制协议解决了 智能体编队控制问题的方案，并给出了系统的分析 考虑采样数据和时延因素的多移动机器人的编队控 和证明.他们还提出将队形信息划分成全局信息和 制问题[4).Dong等在考虑时延的前提下，利用一致 局部信息两类，群体内只有少数个体可以获得全局 性解决了高阶线性时变的多智能体系统的编队控制 队形信息并负责系统的导航工作，其他个体则依靠 问题，并给出了充分和必要条件4].此外，针对机 局部信息来实现跟随编队行为.这样的设计方法可 器人自身、外界环境干扰等诸多不确定因素以及输 以大大降低交互和计算的数据量，便于实现各种复 入输出有界等约束条件，许多学者在绵队控制问题 杂编队控制任务[2]. 中又引入了诸多智能控制算法，包括分层控制6] Oh等针对基于多智能体技术的编队控制问题 自适应控制[)、预测控制4]、神经网络[-0]等等. 给出了较为系统的阐述].简要介绍了一般线性 围绕多智能体技术的编队控制问题的优秀研究 系统、积分器模型和非线性模型的编队控制问题. 成果还有很多，这里不再一一赘述.希望能够通过 根据个体的感知能力和交互能力将多智能体编队控 以上简单的介绍起到抛砖引玉的效果，引起更多学 制问题分为基于位置(position-based)的编队控制问 者的关注，共同完善多智能体“后编队控制时代”的 题[】、基于位移(displacement-.based)的编队控制问 研究成果
贾永楠等: 多机器人编队控制研究进展 了一个交互网络,也成为拓扑图. 如果机器人彼此 是邻居,有交互,那么该边的值为 1;反之,则为 0. 不同邻居间的相互影响程度也可以不同,那么边的 值就可能是 0 到 1 之间的某一个值,这样的拓扑图 就称为有权重的图. 在机器人编队控制中,每个机器人常常被看作 质点. 这里也需要对机器人进行建模. 多智能体技 术中常常将智能体看作一阶或是二阶积分器的形 式,但是机器人本体往往是非线性的,因此还需要针 对机器人自身的物理和运动约束,设计合理的机器 人模型. 多智能体技术本身的鲁棒性和良好的抗干 扰能力使得考虑较为复杂的机器人模型,并开展深 入地数学分析和仿真验证成为可能. 目前影响最为 广泛的模型有两种,分别是 Boid 模型[22] 和 Vicsek 模型[23] . Boid 模型是 1986 年由 Reynolds 发明的一 种用于模拟鸟类等动物的群体运动的计算机模型. Vicsek 模型则由匈牙利物理学家 Vicsek T 及其合作 者于 1995 年从统计力学的角度提出,不仅算法简 单,而且能比较真实的模拟自然界的鸟群、鱼群等的 同步现象. 此外,Vicsek 模型还可以通过改变个体 的密度以及噪声的强度得到不同群集协同运动. 多智能体技术的基础是一致性协议. 一致性协 议的思想是把邻居行为的差异作为个体的反馈控制 量来对个体的行为进行调节. 该算法思想简单易 懂,实用性强,因此得到了学者和工程师的认可. 早 在 2006 年,任伟等就提出了利用一致性的方法解决 多机器人的编队控制问题[24] . 同年,Gennaro 等提 出利用分布式导航函数来设计协同协议实现多智能 体的编队控制,导航函数的最小值对应期望的编队 结构[25] . 基于多智能体理论,系统往往在时间趋向 于无穷时才能达到稳定,即形成期望的编队. 为了 满足工程应用,Xiao 等提出了在有限时间内解决多 智能体编队控制问题的方案,并给出了系统的分析 和证明. 他们还提出将队形信息划分成全局信息和 局部信息两类,群体内只有少数个体可以获得全局 队形信息并负责系统的导航工作,其他个体则依靠 局部信息来实现跟随编队行为. 这样的设计方法可 以大大降低交互和计算的数据量,便于实现各种复 杂编队控制任务[26] . Oh 等针对基于多智能体技术的编队控制问题 给出了较为系统的阐述[27] . 简要介绍了一般线性 系统、积分器模型和非线性模型的编队控制问题. 根据个体的感知能力和交互能力将多智能体编队控 制问题分为基于位置(position鄄based)的编队控制问 题[28] 、基于位移(displacement鄄based)的编队控制问 题[29]和基于距离 ( distance鄄based) 的编队控制问 题[30] . 其中重点针对基于距离的编队控制问题进 行了详细的分类,包括无向编队和有向编队. Oh 等 还总结了未来可应用于编队控制的多种多智能体方 法, 包 括 蜂 拥 ( flocking ) [31] 、 估 计 法 ( estimation鄄 based) [32] 、单纯基于距离的控制方法[33] 、基于角度 (angle鄄based)的控制方法[34] 、包围(containment)控 制[35]和圆环跟随(cyclic pursuit) [36]等等. 随着传感器技术的发展,视觉传感器信息技术 成为了原有感知、导航、通信手段的一个重要补充. 于是基于视觉的编队控制问题成为一个新的研究热 点[37鄄鄄41] . 例如,当 GPS 信号被切断、机器人无法得 到自己的位置信息时,Montijano 等提出了基于视觉 的分布式编队控制方法,在不需要外部定位信息的 前提下,也可以有效解决多机器人的编队控制问 题[37] . Wang 等甚至提出一种不依赖个体之间的相 对位置信息和通信、而只靠视觉信息来解决领航者鄄鄄 跟随者编队控制问题的新方法[38] . Moshtagh 等则 设计了完全基于视觉信息的分布式控制协议,针对 具有非完整约束的机器人的运动协同问题展开研 究[41] ,他们虽然考虑了机器人之间的避碰问题,但 与编队策略是解耦关系. Morozova 则提出了利用虚 拟领航者和排斥势函数来解决一阶和二阶积分器模 型的分布式编队控制中的避碰和避障问题[42] . 此 外,Jia 和 Wang 则是利用蜂拥算法来解决多机器鱼 的编队控制及避碰问题,其中一致性算法用于实现 群体行为的协调,势函数则用于形成队形及避免碰 撞[9] . 连通性保持也是实现多智能体系统一致性的 重要条件之一. Poonawala 等针对考虑避碰和分布 式连通性保持的多轮式机器人系统的编队控制问题 展开研究[43] . 采样数据和时延也是工程实践中不 可忽视的因素,Liu 等利用分布式控制协议解决了 考虑采样数据和时延因素的多移动机器人的编队控 制问题[44] . Dong 等在考虑时延的前提下,利用一致 性解决了高阶线性时变的多智能体系统的编队控制 问题,并给出了充分和必要条件[45] . 此外,针对机 器人自身、外界环境干扰等诸多不确定因素以及输 入输出有界等约束条件,许多学者在编队控制问题 中又引入了诸多智能控制算法,包括分层控制[46] 、 自适应控制[47] 、预测控制[48] 、神经网络[49鄄鄄50]等等. 围绕多智能体技术的编队控制问题的优秀研究 成果还有很多,这里不再一一赘述. 希望能够通过 以上简单的介绍起到抛砖引玉的效果,引起更多学 者的关注,共同完善多智能体“后编队控制时代冶的 研究成果. ·897·