群机器人系统的建模与仿真

群机器人系统的建模与仿真 曾建潮 1, 薛颂东 1、2 （1.太原科技大学 系统仿真与计算机应用研究所，太原 030024；2.兰州理工大学 电信工程学院，兰州 730050） 摘 要：围绕群机器人学的起源与发展，针对群机器人系统与其他多机器人系统的区分准则及系 统级功能特征，讨论个体机器人的交互、通信、协调控制机制和自组织、模式形成等群机器人研 究中的主要问题，洞悉群机器人的研究概貌和既有研究成果，明确其研究方向。通过回顾概括群 机器人系统的主要建模与仿真方法，以个体之间及个体与环境之间的局部交互机制为前提，使感 知能力有限的个体机器人在协调控制算法作用下涌现群体智能完成规定的复杂任务，突出群机器 人规模可伸缩的系统特征。 关键词：群机器人；群体智能；有限感知；局部交互；协调控制；建模 中图分类号：TP242.6 文献标识码：A 文章编号： Modeling and Simulation Approaches to Swarm Robotic Systems Zeng Jian-chao1，Xue Song-dong1,2 (1. Division of System Simulation & Computer Application, Taiyuan University of Science and Technology, Taiyuan 030024, China; 2. College of Electrical & Information Engineering, Lanzhou University of Technology, Lanzhou 730050, China) Abstract：Concentrating on the desirable properties of swarm robotic systems, some key problems in swarm robotics such as limited sense, local interaction, communication among individuals and with environment, cooperation control and self-organization as well as pattern formation are discussed for the sake of getting an insight into sources and development of swarm robotics and understanding the criteria used to distinguish swarm robotics research from other multi-robot studies. To discern the research emphasis on swarm robotics, we describe the disciplinary profile and existing research findings. Then, the main modeling and simulation methods of swarm robotics are summarized. Finally, this survey shows that large numbers of relatively simple robots with limited sense capabilities and local interaction mechanism may emerge swarm intelligence to handle those prescribed complex tasks in scalable manner. Key words：swarm robotics; swarm intelligence; limited sense; local interaction; cooperative control; modeling 引 言1 群机器人是特殊的多机器人系统，由许多同构的自主机 器人组成，具有典型的分布式系统特征。与集中式控制系统 相比，完成同样任务的群体系统的成员结构，可设计得相对 简单。因此，群系统个体具有模块化、适合大规模生产、具 有互换性等特点[1]。群机器人学是研究能力有限的个体机器 人如何在局部交互机制和协调控制算法作用下涌现群体智 能以合作完成相对复杂的规定任务。因为群一般是高度冗余 的，群体系统就比控制系统具有更强的抗扰动能力；由 于存在冗余性，群就具备了动态适应工作环境的能力，也便 有可能执行远超出结构复杂的单体机器人能力的任务。群机 器人的研究源于生物学启发，是群体智能在多机器人系统的 应用[2]。可以认为，群机器人研究是一般意义上的多机器人 收稿日期：2008-xx-xx 修回日期：xxxx-xx-xx 基金项目：国家自然科学基金（60674104） 作者简介：曾建潮(1963-), 男, 陕西大荔人, 汉, 博士, 教授, 博导, 研究 方向为复杂系统建模与控制、智能计算、群体智能行为仿真、群机器人； 薛颂东(1968-), 男, 河南孟州人, 汉, 博士生, 副教授, 研究方向为群体 智能行为仿真、群机器人协调控制。 系统被赋予群体智能属性后的新兴研究领域[3]，其系统建 模和仿真体现出有别于通常意义下多机器人系统的特点。明 晰其系统特征和所涉问题方可能进行建模并仿真。 1 系统界定 约 20年前，学界在研究元胞自动机时用元胞机器人构 造如下系统：一组（group）简单机器人像机体细胞那样按 照某种模式自组织成复杂结构[4]。后来用术语 swarm 取代 group使之形象化。群机器人与分布式自主机器人等术语并 非数量的标识，协调背后隐藏的有限感知和局部交互原 则才是根本。与群对应的控制结构的规模可变，单元数量从 数个到成千上万个甚至数以百万计。事实上，绝大多数群机 器人文献提及的仅是规模很小的群，这是因为个体数量庞大 使得系统造价昂贵[1]。 1.1 系统特征 研究显示，社会性昆虫协调控制的背后并不存在中心协 调机制，然而从系统级层面看却是鲁棒、柔性、规模可伸缩 的。这样的特征为群机器人系统所梦寐以求[5]： （1）鲁棒性要求群机器人在系统性能较低时也不失控， 即便个体机器人发生功能障碍或整个群受到环境干扰时亦 然。这种鲁棒性可归结为以下因素：第一，系统冗余。个体 的功能缺失可由其他的个体补充，即个体相对于群体而言是 非必需的；第二，分散协调。破坏系统的某一部分并不能阻 止系统的控制。协调是整个系统涌现的特性；第三，个体的 简单性。与一个结构复杂功能繁多、能够完成同样任务的单 体机器人相比，群中的个体结构要相对简单，而简单意味着 发生功能障碍的可能性小；第四，感知的多样性。大量分布 的个体感知能增加整个系统的总信噪比。 （2）柔性要求群机器人系统能针对不同任务进行灵活 配置。这可从蚁群中几类性质相差甚远的任务如觅食、围猎、 编队等加以理解。在觅食任务中，蚂蚁在环境中独立搜索食 物，其搜索行为通过排放在环境中的信息素加以协调[6]；围 猎任务则要求蚂蚁产生比单个个体大得多的力量将猎物拖 到洞中。每只蚂蚁都用颚钳牢猎物，向不同的方向拖拉。看 似随机的拖拉行为通过某种协调形成合力施加在猎物上；而 编队任务中，蚂蚁用身体作为通信媒介获得协调形成一个类 似链条的物理结构，它们用自己的颚夹持着伙伴的腿，顺序 相拖施加很大的力量。群机器人也应有这样的柔性，针对环 境变化利用不同的协调策略提供解决不同任务的方法。 （3）系统规模的可伸缩性要求群机器人系统应在群的 规模发生很大变化时也能自如控制。也就是说，控制群体的 协调机制应保证不受群体规模变化的影响。 1.2 判别准则 群机器人强调物理实现、实体之间及实体与环境之间的 交互等，即关注如何设计物理上相对简单的 agent，以便从 agent 之间和 agent 与环境的局部交互中涌现期望的集体行 为。从某种意义上说，群机器人与群体智能的涵盖面一样广。 诚然，群机器人是多机器人的一种，但从功能层面看与其他 的多机器人系统又有明显区别[5]。 （1）机器人的自主性。无疑，组成群机器人系统的个 体机器人是自主的，即个体机器人应是能够与环境交互的物 理实体。由分布式感知元件组成的传感器网络由于不具备运 动能力，不应视为群机器人系统。然而有理由相信，对传感 器网络的研究与群机器人高度相关[7]。变形机器人系统中的 单元通过彼此连接或脱开而运动，只要不存在中央规划和控 制中心，这类系统则可被界定为群机器人范畴。 （2）机器人的数量。群机器人的研究涉及个体的协调。 因此，仅仅对数量很少的机器人的控制可行，但不考虑系统 规模的伸缩性则不属于群机器人的范畴。尽管明确给出个体 数量的下限尚不可行，但不少人认为群的规模应至少维持在 10-20个个体的水平[5]；另外，尽管可能把个体机器人的成 本控制在较低水平，但用大量的机器人组成一个群体系统， 其试验维护费用依旧是制约研究的主要障碍。因此，我们秉 持这样的观点，可以开展较小规模群机器人的研究，如Balch 只用了 1-8个[8]，但是必须考虑规模的伸缩性。 （3）机器人的同构性[8]。群中的个体数量应该很多， 角色分工却不宜多。也就是说，用角色分工过细的群机器人 进行的研究，无论群有多大，都应认为群的系统特征较不显 著。例如，对机器人足球队的研究通常不属于群机器人的范 畴，因为每个机器人都被一个凌驾于队伍控制的外部 agent 赋予了不同角色，他们的角色是高度异构的[9]。针对群机 器人的同构性程度的判断，Balch提出了按群熵分级的衡量 标准[10]。 （4）个体机器人的能力应相对低下。与规定的任务相 比，个体机器人的能力相对较小。也就是说，或者个体机器 人自己完成这些任务有困难，需要一组机器人合作完成；或 者使用一组机器人可改善系统性能。对于第一种情形，蚂蚁 围猎就是一个例子，因为单只蚂蚁要猎获很大的猎物是不可 能的。蚂蚁觅食时排放到地面上的信息素则是间接通信的例 子，据信这可提高觅食的效率。Sugawara的研究[11]显示， 用一组简单的移动机器人搜索在环境中呈非均匀分布的目 标，能使群体系统性能提高的程度超过线性。请注意，该准 则并非限制机器人的软硬件系统的复杂性。有限的个体能力 不应绝对化，这是与任务的复杂性相对而言的。 （5）机器人应仅具有局部感知和通信能力。该约束保 证了机器人间的协调是分布式的。实际上，群机器人中使用 全局通信很可能导致规模不可伸缩并因而违反第二条准则。 当然，作为一种手段，下载通用控制程序到每个机器人或外 部统一发出指令使所有机器人终止工作，这样的全局通信是 可以接受的，只要不将其用于机器人间的协调即可。 2 交互通信 为进行合作，个体机器人之间须交互磋商。因此，通信 是群机器人系统的关键问题。一些研究虽然在探讨无通信合 作，但依据通信使系统效率得到提高更为实际[12]。在生物 群体模型中，个体之间有直接的交流，如触角的触碰、食物 的交换等，但个体间的间接接触更为微妙，可用 stigmergy 描述这种机制：个体感知环境对此做出反应并反作用于环 境。环境是个体之间交互的媒介。对于环境的作用，通常借 助信息素来体现[6],[13]。这样，类似于正反馈的机制最终 将使绝大多数个体满足某种最优指标，涌现出群体层次的宏 观特性。 上世纪 90 年代中期，有人探讨了通信对多 agent 机器 人系统性能的影响。通过设计三种社会性的昆虫任务，评估 了三种不同类型的通信，并进行了仿真研究[8]。按照个体 的交互方式可以将通信分为三类[14]： （1）通过环境实现交互。即以环境作为通信媒介，这 是简单的交互方式，机器人之间无明确通信。机器人随着任 务的执行改变环境，进而帮助其他机器人完成任务。 （2）通过感知实现交互。机器人位于传感器检测范围 内时，可以相互感知对方的存在。感知是局部交互，机器人 之间亦无明确通信。这要求机器人具有区分机器人与环境物 体的能力。由于每个机器人都具有相对独立的传感器系统， 整个系统的信息融合和有效利用是一个重要问题。Payton用 智能车辆集中感知系统证实了其效果[13]。 (3) 通过直接型和广播型等明确的通信实现交互。尽管 网络通信提供了机器人通信的基本解决，但适合群机器 人实时性要求的通信协议、网络拓扑结构及通信方式尚待研 究。群机器人作为典型的分布式控制系统，网络结构是其特 征之一。但是，群机器人系统的通信与面向数据处理和信息 共享的计算机网络通信有很大差异。若机器人之间过分依赖 通信获取信息，则当个体数量增加，系统通信需求将呈指数 增长。因此，既要研究适合群机器人的通信机制，又要利用 个体机器人的局部感知和推理能力，研究机器人基于合作伙 伴的行为推断，辅之以必要的通信控制策略[12],[15]。 3 协调控制 协调控制属于群机器人系统中的高级控制任务。在群机 器人中，个体和群体都要协调动作以实现群体功能。群机器 人研究对象包括个体行为、群体行为两个层次。前者包括个 体对环境的感知、学习、响应及自适应动作的协调。个体机 器人控制系统是实现个体行为的基础，它要求个体具有较强 的协作性与自主性[14]。群体行为是个体行为的集成，典型 的群体行为有集中行为、分散行为和编队行为等[15]。 （1）个体机器人的体系结构及物理实现。一般地，个 体机器人应具有以下功能：有限感知能力、局部规划能力、 非全局通信能力、任务分解能力、任务分配能力、学习能力 和控制与决策能力等[14]。这里特别强调任务分配能力和学 习能力。Kalra基于不同任务分配机制进行了研究[16]；另外， 设计协作行为的控制参数值是困难的，故希望机器人能在线 学习控制参数值以优化系统性能并适应环境变化。Pugh[17] 和 Li[18]分别阐述了机器人采用不同机器学习技术进行学 习的问题。机器人的物理实现应着重考虑控制器设计、传感 器布置及多源信息融合等，使机器人通过与环境交互有效学 习。 （2）群机器人的体系结构与组织结构。体系结构提供 了机器人活动和交互的框架，决定着机器人间的信息关系和 控制关系。群体体系结构是实现协作行为的基础，决定了机 器人的合作能力。群机器人体系结构研究如何根据任务类 型、个体能力等确定群机器人的规模及相互关系。从控制方 式和信息交互方式上看，群体系结构有分层和分布两类[14]。 （3）机器人的定位。群体模式通过个体间的交互涌现 出来，而群中并不存在全局的协调控制系统，这便意味着每 个机器人都有自己的局部协调控制系统，要具备在各自的局 部协作系统框架内定位相邻个体的能力，所以机器人对相邻 个体的快速准确定位是极为重要的[19]。单体机器人定位技 术主要有绝对定位和相对定位两类，传统的多机器人定位技 术有的直接将单体定位技术用于多机器人情形，但多数通过 卡尔曼滤波或粒子滤波等复杂的运算将内部传感器和外部 传感器信息进行融合估计[20]。所用的检测手段呈多元化： 超声波、光线、声音等不一而足[21]。严格说来，这些定位 技术对于未知环境下的群机器人系统并不理想，因为其复杂 的计算开销严重挑战有限的机器人资源。因此，侧重于相对 定位技术的开发和控制算法设计值得探索。Cui[22]使用多 个能力有限的简单移动 agent协同搜索和定位范围很大的区 域中数量不确定的有害气体泄露源。Pugh[23]用三边定位技 术开发了相对定位模块，并将该系统用在基于微粒群算法的 群机器人搜索问题研究中[24]。Rothermich研究了群机器人 的分布式定位问题[25]。Spears采用三角法对相邻个体机器 人的定位技术进行了研究[26]。Kelly 介绍了用于室内群机 器人试验的定位、通信系统，采用板上红外线探测等技术感 知机器人间的相对位置[27]。 4 建模与仿真 模型是实际系统的抽象，通过模型研究有助于理解系统 内部的作用规律。因此，群机器人系统特征须在其模型中得 以体现。特别地，群机器人建模的重要性还体现在对系统规 模伸缩性的研究上，因为这是群机器人的一个重要特征，控 制算法经常是针对多达成百上千个机器人进行的。但是可观 的机器人制造维护费用严重挑战大规模试验的开展[3]。 4.1 建模 这里提出四种群机器人系统的建模方法。应该声明，群 机器人有别于确定性系统的本质特点决定了模型与实际系 统具有相当差异，尚待进一步研究。 4.1.1 基于传感器-执行器的建模法 机器人的传感器和执行器及环境物体是群机器人系统 的主要组成部分。引入传感器、执行器、环境物体的模型后， 再对机器人间的交互及机器人与环境的交互行为进行建模 是该法的基本。采用该法的关键，是要将交互行为接近 真实并尽可能简化，这在系统规模扩大时显得特别重要。但 不容否认的是，要求交互行为真实与尽量简单化之间是矛盾 的，需要进行必要的折中[3]。 4.1.2 微观建模法 微观建模法是用数学方法对个体机器人及其交互建模。 此法将机器人的行为定义为若干个状态及状态间的变迁组 合，这些状态由机器人的内部事件和环境中的外部事件触 发。这种建模法与后面将要阐述的宏观建模法的区别主要是 模型粒度。即微观法针对个体机器人建模，而宏观法直接对 系统级的行为进行模型抽象。 作为微观和宏观建模法的特殊情形，群机器人学引入了 概率微观和概率宏观模型。通过给机器人行为（微观模型） 或系统状态（宏观模型）之间的变迁概率赋值，可以很方便 地将系统行为和环境噪声集成到系统的概率模型中。在概率 微观模型中，所有变迁事件的概率都是用真实机器人进行试 验后获得的[3]。 4.1.3 宏观建模法 宏观建模法是另外一种数学建模法。在宏观建模法中， 系统行为被定义为差分方程，表示在某个时间步处于每个特 定状态的机器人平均个数。 在微观模型中，每个机器人均需要迭代，但宏观建模法 只需要每次得到模型的稳定状态。与微观建模法相比，尽管 此特性允许宏观模型具有很大的加速比，但微观模型允许研 究较为细微的特性。换言之，当宏观模型能够很快得到粗略 的全局行为时，微观模型得到的全局行为更为实际，虽然所 耗时间较长。与微观模型类似，用概率宏观模型处理群机器 人的系统噪声也较为简单[3],[28]。 4.1.4 扩展微粒群算法建模法 微粒群算法是对群居生物行为的抽象，具有明显的生物 学内涵，多用于非线性函数的优化。群机器人则面向特定应 用，这些应用由若干基准问题构成，如搜索、编队、协作搬 运等。通过对微粒群算法和群机器人基准问题的特点对比分 析，可知在这些任务中二者存在映射关系[24]。据此可对微 粒群算法进行适当修改和扩展，以机器人对外界信号的检测 值作为适应值，以通信范围内的机器人为感知邻域，应用 Lbest 模型的微粒群算法确定机器人个体的移动方向、速度 及期望位置。再根据机器人的运动学和动力学特性控制机器 人运动，同时结合通信模式、通信周期及采样周期等因素实 时计算机器人的移动位置。所处环境存在障碍及考虑机器人 尺寸时，可进行路径规划。这样便可将微粒群算法模型作为 机器人的行为控制模型，用于群机器人运动行为的协调控 制，从而涌现群体智能[2],[24]。 4.2 仿真 仿真系统可以采用面向对象的程序设计语言自建，也可 以购买商业仿真工作包。利用商业工具包中的标准库模型的 确可以很快地进行简单群体系统的仿真。然而，当需要对系 统特性较复杂部分进行仿真时，便会发现采用商业工具包降 低了仿真的可控性和灵活性。这是因为，任何库中的模型也 不可能涵盖群机器人系统的方方面面，总是需要建立专门的 模型或者修改既有的模型。对用户来说，采用商业工具包与 处理模型算法本身的细节相比，通常需要花费更多的精力来 处理仿真结构方面的规则和限制。一般认为，群机器人面向 具有特定背景的应用，自建仿真系统更易处理动态界面等问 题。如果确实需要处理大量仿真试验数据，可以将获得的自 定义格式数据导入商业数据处理平台做进一步的处理。 5 结束语 国内外对群机器人的研究取得了相当进展，参与研究的 科研机构也不断增多。但与工业机器人相比，在实用性上尚 有巨大差距。如何进一步研究可资借鉴的生物群体的行为模 型，抽象行为规则并通过有限感知和局部交互等群体智能原 则获得期望的涌现性群体行为，如何将多个抽象层次的群体 系统建模方法和群体优化算法应用于群机器人在特定背景 下的实际控制问题，如何用形式化方法描述和预测群体涌现 性，进而提高群机器人系统的运行可靠性，实现群机器人系 统的工程化建模、仿真和实际应用，还要做许多艰巨细致的 探索研究工作。 参考文献: [1] Beni G. From Swarm Intelligence to Swarm Robotics [C]// Lecture Notes in Computer Science, v3342. Berlin: Springer-Verlag, 2005. p 1-9. [2] 薛颂东, 曾建潮. 群机器人研究综述[J], 模式识别与人工智能, 2008, 21(2): 177-185. [3] Bayindir L, Sahin E. A Review of Studies in Swarm Robotics [J]. Turk J Elec Engin (S1300-0632), 2007, 15(2): 115-147. [4] Fukuda T, Nakagawa S. Approach to the Dynamically Reconfigurable Robotic System [J]. J of Intelligent & Robotic Systems (S0921-0296), 1988(1): 55-72. [5] Sahin E. Swarm Robotics: From Sources of Inspiration to Domains of Application [C]// Lecture Notes in Computer Science, v 3342. Berlin: Springer-Verlag, 2005. p 10-20. [6] Dorigo M, Bonabeaub E, Theraulaz G. Ant Algorithms and Stigmergy [J]. Future Generation Computer Systems (S0167-739X), 2000(16): 851-871. [7] Akyildiz I F, Su W, Sankarasubramaniam Y, et al. Wireless Sensor Networks: A Survey [J]. Computer Networks (S1389-1286), 2002(38): 393-422. [8] Balch T. Communication, Diversity and Learning: Cornerstones of Swarm Behavior [C]// Lecture Notes in Computer Science, v 3342. Berlin: Springer-Verlag, 2005. p 21-30. [9] Kitano H, et al. RoboCup: A Challenge AI Problem [J]. AI Magazine (S0738-4602), 1997. [10] Balch T. Hierarchic Social Entropy: An Information Theoretic Measure of Robot Group Diversity [J]. Autonomous Robots (S0929- 5593), 2000, 8: 209-238. [11] Sugawara K, Sano M. Cooperative Acceleration of Task Performance: Foraging Behavior of Interacting Multi-Robots System [D]. Physica D, 100(3), 1997, p 343-354. [12] 苏治宝, 龚建伟, 熊光明等. 多机器人系统的研究内容与发展趋 势 [EB/OL]. [2007]. http://www.gjwtech.com/controlrobot/research contentofmultirobotsystem.htm. [13] Payton D, Estkowski R, Howard M. Pheromone Robotics and the Logic of Virtual Pheromones [C]// Lecture Notes in Computer Science, v 3342. Berlin: Springer-Verlag, 2005. p 45-57. [14] 谭民, 范永, 徐国华. 机器人群体协作与控制的研究[J]. 机器人, 2001, 23(2): 178-182. [15] 张海英, 刘祚时, 林桂娟. 群体机器人研究的现状和发展[J]. 电子 技术应用, 2004, 30(2): 1-3. [16] Kalra N, Martinoli A. A Comparative Study of Market-Based and Threshold-Based Task Allocation [R]. EPFL, Lausanne, Switzerland, SWIS-IP1, Feb 2006. [17] Pugh J, Martinoli A. Multi-Robot Learning with Particle Swarm Optimization [C]// Proc. of Autonomous Agents and Multi-Agent Systems. Hakodate, Japan, 2006. p 441-448. [18] Li L, Martinoli A, Abu-Mostafa Y S. Learning and Measuring Specialization in Collaborative Swarm Systems [J]. Adaptive Behavior (S1059-7123), 2004, 12(3-4): p 199-212. [19] Feng L, Borenstein J, Everett H R. Where am I - Sensors and Methods for Autonomous Mobile Robot Positioning [R]. UM-MEAM-94-21, Univ. Michigan, Ann Arbor, 1994. [20] Martinoli A, Pont F, Siegwart R. Multi-Robot Localization Using Relative Observations [C]// Proc. of the 2005 IEEE Int. Conf. on Robotics and Automation. Barcelona, Spain, Apr 2005, P 2808-2813. [21] 姜键, 赵杰, 李力坤. 面向群智能机器人系统的声音协作定向[J]. 自动化学报, 2007, 33(4): 385-390. [22] Cui X, Hardin C T, Ragade R K, et al. A Swarm Approach for Emission Source Localization [C]// The 16th IEEE Int. Conf. on Tools with Artificial Intelligence. Boca Raton, Florida, Nov, 2004. [23] Pugh J, Martinoli A. Relative Localization and Communication Module for Small-Scale Multi-Robot Systems [C]// Proc. of the IEEE Int. Conf. on Robotics and Automation. Miami, Florida, USA, May 15-19, 2006. [24] Xue S D, Zeng J C. Control over Swarm Robots Search with Swarm Intelligence Principles [J], J. of System Simulation (S1004-731X), v 20, n 13, Jul 5, 2008. p 3449-3454. [25] Rothermich J A, Ecemis M I, Gaudiano P. Distributed Localization and Mapping with A Robotic Swarm [C]// Lecture Notes in Computer Science, v 3342. Berlin: Springer-Verlag, 2005. p 58-69. [26] Spears W, Hamann J, Maxim P, et al. Where are you? [C]// SAB Swarm Robotics Workshop, 2006. [27] Kelly I, Martinoli A. A Scalable, On-Board Localisation and Communication System for Indoor Multi-Robot Experiments [J]. Sensor Review (S0260-2288), Special Issue on Sensor Simulation and Smart Sensors. 2004, 24(2): 167-180. [28] Lerman K, Martinoli A, Galstyan A. A Review of Probabilistic Macroscopic Models for Swarm Robotic Systems [C]// Lecture Notes in Computer Science, v 3342. Berlin: Springer-Verlag, 2005. p 143-152.