第4卷第4期 智能系统学报 Vol.46.4 2009年8月 CAAI Transactions on Intelligent Systems Ag.2009 doi:10.3969/i.issn.1673-4785.2009.04.005 分布式多机器人通信仿真系统 蔡自兴，任孝平，邹磊 (中南大学信息科学与工程学院，湖南长沙410075)】 摘要：针对目前多机器人通信仿真系统较少的问题，进行了多机器人通信仿真系统的设计研究.提出的多移动机 器人通信仿真系统设计方案，侧重于反映通信网络的拓扑变化情况，以及多个机器人之间是如何进行通信的.仿真 系统预留了机器人控制算法的接口，便于结合机器人避碰、任务分配、连通覆盖等进行综合研究.多机器人覆盖研究 是目前多移动机器人和无线传感器网络中的一个研究热点，针对这个问题，采用了虚拟力分配策略，使得多机器人 在保持连通性的同时尽可能大地覆盖某一区域，最后以六边形覆盖为约束条件进行了区域覆盖，并实现了该仿真系 统的原型.实验表明，该仿真系统能准确地模拟多机器人在保持相互通信的情况下，达到最大化的区域覆盖.证实了 基于虚拟力覆盖策略的有效性. 关键词：多机器人系统；仿真系统；通信网络；连通覆盖；虚拟力 中图分类号：TP33.01文献标识码：A文章编号：16734785(2009)04030905 A simulated communications system for distributed multi-robots CAI Zi-xing,REN Xiao-ping,ZOU Lei (School of Information Science and Engineering,Central South University,Changsha 410075,China) Abstract:An architecture for simulating a communication system for multi-robots was developed and tested.The proposed system primarily reflects changes in the communication modes of robots and the topology of their communi- cation network.A modularized design technology was adopted.Some interfaces were reserved in advance for re- search in areas such as robot avoidance,task distribution and coverage connectivity,and so on.At present,multi- robots coverage is a research hotspot in the field of multiple mobile robots and wireless sensor networks.We devel- oped a special strategy to allocate robots using virtual forces among them;the robots would then cover the monitored area as much as possible.It has been proven that a regular hexagon provides maximum coverage with least waste; this was the basis of our approach.Experiments showed that this distributed algorithm moved robots to extend their coverage by the virtual force among robots while maintaining network connectivity.This proves the effectiveness of the virtual force coverage strategy. Keywords:multi-robots system simulation system;communication network;coverage connectivity;virtual force 随着任务的复杂化，单个机器人执行任务的缺可少的21.除了经典的CEBOT、ACTRESS系统，各 点越来越明显，有些任务对单个机器人来说是很难 研究机构提出了很多的多机器人系统平台，如：Cou 或无法完成的，而采用多机器人团队协作完成任务 gaar31、MinDART!4)、CoCoAs1等.目前对多移动机 是一个较好的选择.多机器人在协作完成一项任 器人通信的研究已取得了一定的进展，研究内容主 务时，需要相互的信息融合和共享，因此通信是必不 要包括：多移动机器人通信方式、多移动机器人通信 语言、多移动机器人通信网络拓扑结构、多移动机器 收稿日期：200905-12. 人通信协议、基于多移动机器人通信的应用研究等. 基金项目：国家自然科学基金资助项目(90820302,60805027)；国家 博士点基金资助项目(200805330005)；湖南省院士基金资 然而目前的多机器人通信技术远未成熟，还需要进 助项目(2009J4030);质检公益行业科研专项项目 (20081002). 行大量的实验以实现在不可靠环境中机器人的可靠 通信作者：任孝平.E-mail:xiaopingren(@gmail..com. 通信.机器人一般较为昂贵，直接在实体上进行控制
310 智能系统学报 第4卷 算法、协助策略和通信测试的实验投资较大.算法的 信网络，R:表示第i个机器人，相应的机器人集合为 合理性、有效性可以通过计算机仿真进行初步验证， R={R,R2,…,Rn},IRI=N.R位于一个方形观察 然后再通过实际的多机器人系统进行实验验证，因 区域A内.开始时，机器人R:在仿真区域A内随机 此有必要建立多机器人仿真系统用来对相关的算法 选择一个目的点D,然后机器人R选择以满足在 进行计算机仿真验证.当前几种典型的仿真系统 [0,vm]内均匀分布的某个速度：移动到达目的点 有CMU和Georgia Institute of Technology共同开发 D后，停留（用t:表示机器人移动的剧烈程度，t:= 的的TeamBot系统[6；专用于机器人足球的Soccer 0表示机器人是连续移动的).机器人R:的移动速 Server软件；Georgia Institute of Technology计算学 率：和移动方向0：的选择与机器人R,(i≠)不相 院的MissionLab系统[] 关.停留时间结束后，机器人R又随机选择另一个 上述这些多机器人仿真系统，着重研究的是多 目的点D并向其运动. 目标观测、未知环境探测、地图构建、路径规划、机器 在该种模型中，如果v小而专：长，则通信网络 人足球、群体搬运等问题].在对多机器人通信系 的拓扑相对稳定；如果v大而（短，通信网络的拓 统仿真研究方面相对较少.虽然有很多针对通信协 扑则有较高动态性.使用该模型的网络链路存活时 议仿真的工具如NS2、OPENT等，然而学习仿真工 间较长，易于形成稳定的拓扑 具本身就是一个较难的过程，更难以结合机器人避 仿真程序启动 碰、任务分配等进行综合研究.本文提出的多移动机 器人通信仿真系统，侧重于反映多个机器人之间的 随机场景文作生成 通信机制以及通信网络拓扑变化情况，并预留了机 读取运动文件 器人控制算法的接口，便于扩展进行综合研究.最后 启动相关线程 以多机器人连通覆盖的研究背景实现了该仿真系统 绘制机器人线程 的原型 机器人运动线程 1多机器人通信网络仿真系统 通信线程 线程关闭 多机器人团队在一个未知区域内执行任务，相 互之间通过通信网络进行信息的传递和共享，根据 仿真结束 多机器人环境下的通信网络的需求，通信网络仿真 图2要线程启动示意图 系统由如图1所示几个模块组成，其中的虚线框是 Fig.2 Main threads in system 预留的接口。 1.2运动仿真模块 多机器人通信 机器人行为模型建立之后，接下来就是机器人 网络仿真系统 动态过程的模拟.如图2所示，运动仿真模块主要有 2个线程.其中绘制机器人线程是根据机器人当前 机器人行绘制不 运动仿 通信模块 :避碰策略、路径门 为模型境模型真模块 :规划、队形控制等 的坐标绘制新机器人线程；机器人运动线程是不断 机器人控制算法目 改变机器人运动轨迹的线程，包括机器人运动速度 机2器人 与实体机器人！ :以及移动方向日：，它将改变了的机器人坐标存入 之间通信 1的通信接口} RobotState数据结构中.RobotState用于存储机器人 图1多机器人通信仿真系统结构 的全局运动状态以及环境信息， Fig.1 Structure of communication stimulation system 1.3通信模块 1.1机器人行为模型 通信模块是该仿真系统的核心.机器人需要发 机器人行为模型主要包括机器人的分布、运动 送信息的时候它就可以立即发送；如果要完成较远 速率、运动规律等，用于描述机器人的运动情况」 距离的通信，则可以通过中间机器人进行信息转发； 采用合适的行为模型对于分析机器人通信性能和运 在某个移动机器人脱离通信范围的情况下，其余机 动规律具有重要的意义[o, 器人应该能够自适应地重新组成新的网络，而不影 考虑一个由N个随机分布的机器人形成的通 响整个团队的工作
第4期 蔡自兴，等：分布式多机器人通信仿真系统 .311· 1.3.1相关概念 对方的组结构， 首先给出一些定义1，机器人用R(i=1,2, 6)由于某种原因A中无α状态R,A中其他R …j,n)表示. 进行新的组长选举，选出新的组长管理本组。 定义1链路状态.链路状态包括单向和双向， 大规模移动机器人组建的通信网络中，分级管 分别记为入和ω链路.文中采用同构机器人，故建立 理机器人的策略可以显著提高通信的效率，每个机 的通信链路均为双向链路。 器人周期性地广播Ak消息，其他机器人收到非自 定义2组长.组长管理着它附近的机器人，如 身发送的Ack消息后记录在本机.通过这些邻居机 图3中的R4和R。·组长的推选依据一定的算法，未 器人的信息，构造组结构，组长管理组员，从而形成 能充当组长的机器人还有2种状态：组员和未定状 2级通信结构.上述规则5)描述的是组结构重构的 态.规定组长、组员、未定状态分别为B、y状态 过程.当2个组移动到能互相收到对方的Ack消息 定义3组结构.α状态R和B状态R组成的 时，进行组长的选举，2个组融合成一个组.通过这 组结构称为A{R,R}.规定：在一个组结构A中，a 种机制，可以自适应地调整机器人团队中的组结构 状态R到A中R都有一条0链路.如图3所示，A 的规模.其余更多的细节参见文献[11]. {R4,R2,R,R}中R4为a状态，R2、R3R为B状 在通信网络建立起来之后，由组长机器人控制 态，R4到R2、R3、R,之间均为o链路 成员机器人，成员机器人根据组长发送的指令执行 R 相应的运动策略。 1.4基于虚拟力的多机器人覆盖策略 区域覆盖是指对一个指定区域用一系列称为一 跳覆盖区的小区域（圆）将其有重叠地完全覆 盖21.覆盖问题是传感器网络和移动自组网中的一 个重要议题，已有的研究多数集中在如何保证工作 的节点能够完全覆盖一个指定的区域上，在覆盖的 图3多机器人通信网络 同时保持网络的连通性，可以保证网络在具有一定 Fig.3 Multi-robots communication network 的有效覆盖度的同时能够连通工作， 定义4网关.如果R∈A∩B,则R为网关如 图3所示，R3∈{R4,R2,R3,R}且R3∈{Rg,R,R4, R,R,R。,则R3为网关.网关可以用于在2个组 之间转发消息。 定义5Ac消息.R每隔时间t发送一次Ack 消息，通知周围R发送者R的存在， 1.3.2建立多机器人通信网络 在1.3.1定义的基础上，建立多机器人通信网 络的规则如下： 图4初始机器人受力分析 1)R初始化的时候均为y状态，周期性发送 Fig.4 Forces analysis of initial robots Ack消息. 如图4所示，假设有3个机器人R1、R2、R3,f2 2)y状态R从&状态R收到Ack消息，且R 是R对R2的斥力f2是R对R2的斥力.力的大小 与R之间有o链路，则R加入R所在的组结构， f可由式(1)确定31： 同时变为B状态。 3)B状态R在时间r后，仍没有收到α状态R 11=4),4,<2: (1) 10,fdg≥2re 的Ack消息，变为y状态. 方向0g=arctan(k;),其中k;是机器人R:到R,连线 4)Y状态R在时间T后，仍没有收到α状态 的斜率，「。为机器人的通信半径.不妨令机器人R、 R的Ack消息，变为a状态 R2a、R2()、R3的坐标分别为(x1,y1)、(x2,y2)、 5)α状态R:与ax状态R之间有o链路，一定 (（x'2,y'2)和(x3,y3),则k2和k2如下： 时间后，则R或R,按一定的策略放弃α状态，加入
·312. 智能系统学报 第4卷 k12=tan012=（y2-y,)/(x2-x), 置分布如图6所示.启动通信网络之后，即开始进行 (2) k32=tan032=(y3-y2)/(x3-x2). 组结构的构建，选择开始仿真，机器人节点开始做随 f2和f作用在R2的合力F2=f2+f2大小为 机运动，由于有排斥力的约束，运动过程中机器人的 IFI= 位置是按照最大覆盖的要求运动的，组长受力运动 2+f+2ff(sin 0sin 02 Cos 0n2Cos 02). 过程如图7所示.机器人最终覆盖结果如图8所示. (3) 合力F2的方向为 k2= :组长 √1+kf代d2）)+1+2f(d2) (4) k2√1+fd2)+k21+品f代d2) 合力F2促使机器人R2(,移动到一个新的位 . 置R2(m移动轨迹方程如式(5)所示： y'2=k2x'2+y2-k22 (5) 当机器人受某种约束的时候，则停止运动.在该 系统中，为了保证使覆盖的区域达到最大，机器人移 动的距离应满足达到六边形覆盖的要求13]，即 1R,R2m)1=(3r)2且IR3R2a)I=(W5e)2. 图6机器人的初始位置 由于在通信网络中存在组长和成员2种节点， Fig.6 Initial deployment of robots 形成一种层次网络结构，因此这种基于虚拟力的覆 盖策略只在组长机器人之间执行，这样能有效地节 省机器人之间的通信量和运动距离，能有效地节省 机器人的能量。 2仿真系统的实现 在第1部分仿真系统结构的设计基础上，对该 系统用VC++6.0和Matlab进行了相应的实现.系 统仿真界面如图5所示 图7组长机器人受力运动过程 Fig.7 Movement procedure of robots by forces 图5通信仿真系统界面 Fig.5 Interface of communication system 用户可以自定义仿真机器人数、最小速度、最大 速度、仿真时间等数据.由于机器人能量和信号发射 功率的限制，每个机器人都有最大通信距离.本系统 图8机器人最终覆盖结果 仿真采用同构机器人，机器人参数均相同.定义好这 Fig.8 Final deployment of robots 些参数之后，产生随机运动场景文件，机器人初始位
第4期 蔡自兴，等：分布式多机器人通信仿真系统 ·313· [9]原魁，李园，房立新.多移动机器人系统研究发展近 3 结束语 况[J].自动化学报，2007,33(8)：785-794 在多移动机器人相互协作完成任务的过程当 YUAN Kui,LI Yuan,FANG Lixin.Multiple mobile robot 中，机器人所采用的通信方式的优劣是任务完成的 systems:a survey of recent work[J].Acta Automatica Sini- ca,2007,33(8):785-794. 保障之一.本文分析了现有多机器人仿真平台通信 [10]王建新，李健，朱贤曼.MANET中节点的运动模型和 网络的仿真方面的一些不足，提出了一种通信网络 性能分析J刀.计算机工程，2006,32(19)：125-130. 仿真平台的系统设计方案.可自定义仿真参数和为 WANG Jianxin,LI Jian,ZHU Xianman.Performance a- 其他控制算法预留了接口，使该系统具有良好的人 nalysis of mobility models in MANET[J].Computer Engi- 机交互功能.文中以多机器人系统中的连通覆盖问 neering,2006,32(19):125-130. 题为例，对该仿真系统进行了实现 [11]任孝平，蔡自兴.基于移动自组网的多机器人远程监控 通过进一步编程，用户可以在仿真系统中嵌入 [J].华中科技大学学报：自然科学版，2008,36(Sup 自己的控制算法和分析日志函数，使该仿真平台可 I):239-242. 以方便地对通信网络进行仿真和性能分析。 REN Xiaoping,CAI Zixing.Remote monitoring of multi- mobile robots based on ad hoc network [J].Joumal of 参考文献： Huazhong University of Science and Technology:Nature [1]谭民，王硕，曹志强.多机器人系统[M].北京：清华 Science Edition,2008,36(Sup I):239-242. 大学出版社，2005：10-11. [12]任孝平，蔡自兴，陈爱斌.一种移动自组网的区域覆盖 策略[J].计算机工程，2008,34(2)：159-162. [2]黎萍，杨宜民.多机器人系统任务分配的研究进展 REN Xiaoping,CAI Zixing,CHEN Aibin.Area-covering [J].计算机工程与应用，2008,44(17)：201-205. LI Ping,YANG Yimin.Progress of task allocation in muti- tactics for ad Hoc network [J].Computer Engineering. 2008,34(2):159-162. robot systems[J].Computer Engineering and Application, [13]AKKAYA K,JANAPALA S.Maximizing connected cover- 2008,44(17):201-205. [3]HELSINGER,THOME A,WRIGHT M T.Cougaar:a scal- age via controlled actor relocation in wireless sensor and actor networks [J].Computer Networks,2008,52(14): able,distributed multi-Agent architecture[J].IEEE Int Con 2779-2796. on Systems,Man and Cybernetics,2004,2(10/13):1910- 作者简介： 1917. 蔡自兴，男，1938年生，教授、博士 [4]PAUL E R,AMY L,HARINI V,MONICA L,MARIA G. 生导师，主要研究方向为人工智能、机 Performance evaluation of a multi-robot search retrieval system:experiences with MinDART[J].Joumal of Intelli- 器人、智能控制等.获科教奖励30多 项，其中国家级奖励2项，省部级奖励 gent and Robotic Systems,2008,52(3/4):363-387. [5]KOUTSONIKOLAS D,DAS S M HU Y C.CoCoA:coor- 20多项.发表学术论文550余篇，出版 dinated cooperative localization for mobile multi-robot ad hoc 专著和教材26部. networks[C]//26th IEEE Interational Conference on Dis- 任孝平，男，1984年生，博士研究 tributed Computing Systems.Lisboa,Portugal,2006 (4/ 生，主要研究方向为多机器人系统、通 7）:9. 信网络等】 [6]TUCKER B.Behavioral diversity in learning robot teams [D].Atlanta,USA:College of Computing,Georgia, 1998. [7]ITSUKI N,HITOSHI M.Soccer server and researches on multiagent systems[C]//Pro of the IROS96 Workshop on 邹磊，男，1985年生，硕士研究 RoboCup.0saka,1996:1323-1327. [8]王佳，吴晓蓓，徐志良.多机器人系统的互联控制问题 生，主要研究方向为多机器人系统、无 线传感器网络等。 讨论[J].控制工程，2007,14(5)：527-531. WANG Jia,WU Xiaobei,XU Zhiliang.Discussion on in interconnection control problems of multi-robot systems[J]. Control Engineering,2007,14(5):527-531