（计算机应用技术专业论文）多移动机器人团队合作下的ad+hoc网络研究.pdf

缡要 透信是多移动概器入在实现圈队合作时的关键鞠素之一。在实际 应用时往往面对的是动态、复杂、非结构化的，没有或缺乏固定网络 设施的环境，在这种环境中，a dh o c 网络比一般的刚络表现出更好 的适应能力。a dh o c 黼络是一种特殊的无线移动通信网络，具有很 强的抗毁性，在多桃器人中利，| _ 3a dh o c 网络能为多机器人顺剥合作 完成任务提供保障。本文所做的研究正是基予a dh o e 网络展开的。 本论文来源于国家自然科学基金重点项目“未知环境中移动机器 人导航控制的理论与方法研究”( 项目号：6 0 2 3 4 0 3 0 ) 与国家基础研究项 目“多移动体协同技术的基础研究”( 项目号：a 1 4 2 0 0 6 0 1 5 9 ) 。研究 了多机器人间通过相互合作完成任务的协调与通信机制。主要内容如 下： 1 、提出了一个基于a dh o c 网络下瓣多移动机器人混合式团队合 作机制，此机制可以实现在多个a dh o e 网络间实行分布式协调和一 个网内集中式协调。 2 、对多移动机器人中的几种髌型a dh o c 嘲络路由协议进行分 析，比较其各自的特点、功能相应用环境。针对多机器人的一些运动 特性，利用n s 2 网络仿真软件对三种典型路由协议进行仿真和比较 分析，讨论了对于不同情况下适用于多移动机器人的a dh o e 路由协 议。 3 、通过分析由多机器人问的相对运动造成的不连续网络的现象， 改进了d s d v 路由协议。改进后的西议是一种适合移动机器人在不 连续多个a dh o c 网络上的路由协议一a n m r ( a d h o cn e t w o r k s r o u t i n gp r o t o c o lf o r m o b i l er o b o t s ) 。此协议缝够在实时变换的环境下 确保机器人协调算法的执行，解决出现的在多个a dh o e 网络中由于 机器人的移动造成的网络合并和分裂现象，能保证多机器人在合作完 成任务时对信息交互实时性较高的需要。 4 、多移动机器人团队在室内环境中执行寻找特 正目标的任务。 发现预定目标后，通过a dh o c 网间相对分布式协调与一个网内集中 式协调的祝箭，同一个a dh o c 嘲络内按个人或队长分配的计划朝各 自预定鲤标前进。在机器人的运动过程中，采用a n m r 路由协议首 先完成了两个a dh o c 网络的合并，之后又解决了网络内拓扑结构变 化的阿题，最后当网络发生分裂时进行路囊信息的更新，保证了网络 通信的实时陡。实验的成功实现对构建的多个a dh o c 网络问分布式 结构与一个a dh o c 网络内集中式结构的混合式合作机制，及提出的 a n m r 路由协议的有效性进行了验诞。 关键词多移动机器人，a dh o c 网络，a n m r 路由协议 l l a b s t r a c t c o m m u n i c a t i o ni so n eo ft h ec r i t i c a lf a c t o r si nm u l t im o b i l er o b o t s t e a mc o o p e r a t i o n t h em u l t im o b i l er o b o t st e a mi sa l w a y sc o n f r o n t e d w i t hv a r i e de n v i r o n m e n tw h i c hi sd y n a m i c ，u n s t r u c t u r e d ，w i t h o u to r l a c k i n go fn e t w o r ki n f f a s t r u c t u r e a dh o cn e t w o r kc a np u tu pm u c h b e t t e ra d a p t a b i l i t yu n d e rt h i sk i n do fe n v i r o n m e n t a dh o cn e t w o r ki sa n e s p e c i a l w i r e l e s sm o b i l ec o m m u n i c a t i o nn e t w o r k i th a sv e r ys t r o n g r e s i s t a n ta b i l i t ya n dc a np r o v i d eg u a r a n t e ef o rm u l t i r o b o ta c c o m p l i s h i n g t h et a s ks u c c e s s f u l l y t h er e s e a r c ho ft h i sd i s s e r t a t i o ni sb a s eo na dh o c n e t w o r k 弧i sd i s s e r t a t i o ni ss u p p o r t e db yt h ek e yp r o j e c to ft h en a t i o n a l n a t u r a ls c i e n c ef o u n d a t i o no fc h i n au n d e rg r a n tn o 6 0 2 3 4 0 3 0 ，r e s e a r c h o nt h e o r i e sa n dm e t h o d so fn a v i g a t i o nc o n t r 0 1f o rm o b i l er o b o t su n d e r u n k n o w ne n v i r o n m e n t ，a n db yt h en a t i o n a lf o u n d a t i o n a lr e s e a r c hp r o j e c t u n d e rg r a n tn o a 1 4 2 0 0 6 0 1 5 9 ，b a s i cr e s e a r c ho ns y n e r g e t i ct e c h n i q u e s f o rm u l t i - m o b il ea g e n t s a so n ep a r to ft h ep r o j e c t ，t h i sd i s s e r t a t i o na i m s a tt h ec o o p e r a t i o na n dc o m m u n i c a t i o nm e c h a n i s mo fm u l t im o b i l er o b o t s t oa c c o m p l i s ht h et a s k t 1 1 em a i nc o n t r i b u t i o na n dw o r ka r ed e s c r i b e da s f o l l o w s ： 1 、u n d e ra l lu n k n o w ne n v i r o n m e n t c o n s t r u c tac o m p o s i t em u l t i m o b i l er o b o t st e a mc o o p e r a t i o nm e c h a n i s mt h a t r e a l i z e sd i s t r i b u t e d c o o r d i n a t i o ni nm u l t ia dh o cn e t w o r k sa n dc e n t r a l i z e dc o o r d i n a t i o ni na s i n g l en e t w o r k 2 、a n a l y z e ds e v e r a lt y p i c a la dh o cn e t w o r kr o u t i n gp r o t o c o l sa n d c o m p a r et h e i rc h a r a c t e r i s t i c ，f u n c t i o na n da p p l i e df i l e d u s et h en s 一2 n e t w o r ks i m u l a t i o ns o f f w a r et oa n a l y z et h em o t i o n a lt r a i to fm u l t im o b i l e r o b o t s s i m u l a t ea n dc o m p a r et h et h r e er e p r e s e n t a t i v er o u t i n gp r o t o c o l s ， t h u sd i s c u s st h ea dh o cp r o t o c o l sw h i c ha d a p tt ot h em u l t im o b i l er o b o t s i nd i f i e r e n te n v i r o n m e n t 3 、i m p r o v eo n t h ed s d v r o u t i n gp r o t o c o lt h r o u g ha n a l y z i n gd i s c r e t e n e t w o r kp h e n o m e n o nw h i c hi sc o u r s e d b yr e l a t i v em o t i o no fm u l t i m o b i l er o b o t s t h ei m p r o v e d p r o t o c o li sa n m r ( a d - h o cn e t w o r k s i i i r o u t i n gp r o t o c o lf o rm o b i l er o b o t s ) w h i c hi sa d a p tt ot h em o b i l er o b o t i nd i s c r e t ea dh o cm u l t i n e t w o r k s 。t h i sp r o t o c o lc a na s s u r ei m p l e m e n t o fc o o p e r a t i o na l g o r i t h mi nt h er e a lt i m ec h a n g e de n v i r o n m e n t ，s o l v et h e n e t w o r k sm e r g ea n db r e a kp h e n o m e n o nb yr o b o tm o t i o na n dc a na s s u r e t h er e q u i r e m e n to fr e a lt i m ee x c h a n g ei n f o r m a t i o ni nt h ec o o p e r a t i o n t a s k 4 、d e s i g na n dr e a l i z et h et a s ko ft h em o b i l er o b o t st e a mt os e a r c h c h a r a c t e r i s t i co b j e c t su n d e rt h ei n d o o re n v i r o n m e n t w h e nf o u n dt h e p r e p a r a t o r yo b j e c t s ，e a c hr o b o ti nt h es a m ea d h o cn e t w o r km o v et o w a r d t h eo b j e c tt h r o u g hc o o r d i n a t em e c h a n i s mo ft h ed i s t r i b u t ec o o r d i n a t e a m o n ga dh o cn e t w o r k sa n do n en e t w o r kc e n t r a l i z ec 0 0 r d i n a t e d u r i n g t h ep r o c e s so fr o b o tm o v e m e n t ，a c c o m p l i s ht h em e r g e n c eo ft w oa dh o c n e t w o r k sb yt h ea 湛4 鼗p r o t o c o l 。t h e ns o l v et h ec h a n g ep r o b l e mo f n e t w o r ks t r u c t u r e l a s t l yu p d a t et h er o u t e n f o r m a t i o nw h e nt h en e t w o r k i sb r e a ku p 1 1 1 ea n m rp r o t o c o la s s u r e st h er e a lt i m ec a p a b i t i t yo f n e t w o r kc o m m u n i c a t i o ni nt h ew h o l ep r o c e s s t h es u c c e s so ft h e e x p e r i m e n tv a l i d a t e dv a l d i t vo fc o n s t r u c t i o no fd i s t r i b 强t e dc o o r d i n a t i o n i nm u l t ja dh o cn e t w o r k sa n dc e n t r a l i z e dc o o r d i n a t i o n nas i n g l e n e t w o r kc o m p o s i t em e c h a n i s m ，a n m rr o u t i n gp r o t o c 0 1 k 嚣yw o r d s ：m u l t im o b i l er o b o t s ，a dh o cn e t w o r k ，a n m rr o u t i n g p r o t o c o l 原创性声璞 本天声鹾，所墨交浆学霞论文是本太在譬舞指导f 遗行豹辫究 工作及取得韵研究成果。尽我所知，除r 论文中特剐加以标注和致谢 酶地穷外，涂文中不包食其缝太已经发裘或撰写过的勰究成果，连不 包含为获得中南大学或其他单位的学位斌证书耐使用过的材料。与我 共同工l 乍憋阕志对本醭究掰作躲贡献均已在在论文巾作了明磕的说 嚼。 作者签名：垒二墼 日期：型垒每己王月堡鼹 关予学位论文使孀授权说明 本人了解中南大学有关保髓、使用学位论文的规定，即；学校 有投绦蜜学燕论文，允许学位论文渡查瓣霹蠢阕；学摭爵强公森学位 论文的全部或部分内容，划1 以采刚复印、缩印缄其它乎段像存学位论 文；学校可投蕹晷家袋湖南省煮关蘩门瓣定邀交学位论文。 传者签名：金堑导群签巍纽圣基爨：墨照年羔露堡翳 硕士学位论文第一章绪论 第一章绪论 从2 0 世纪6 0 年代末期至今移动机器人的研究己发展了近四十年。现在，机 器人的本领还是非常有限的，不过，它正在迅速发展，并开始对整个工业生产、 太空和海洋探索以及人类生活的各方面产生越来越大的影响“1 。 1 1 课题研究背景及研究意义 从斯坦福研究院( s r i ) 的n i l s n i l s s e n 和c h a r l e s r o s e n 等人于1 9 6 6 年至1 9 7 2 年间研制的s h a k e y 【2 】自主移动机器人和最著名的名为g e n e r a le l e c t r i c q u a d r u p e d p 】步行机器人，到近几年来为探索外太空而研制的机器人1 9 9 6 1 9 9 7 年，美国国家航空与宇宙航行局发射的火星探路者( m a r sp a t h f i n d e r ) 和索 杰纳( s o j o u r n e rr o v e r ) 成功登陆火星1 4 j ，以及于2 0 0 4 年的1 月4 日和1 月 2 5 日登陆进行探测工作的火星漫游车勇气号( s p i r i tr o v e r ) 与机遇号 ( o p p o r t u n i t yr o v e r ) 等等，移动机器人已从一开始仅仅用于研究工作开始进入 到社会的许多方面。 而多机器人系统的研究始于2 0 世纪7 0 年代，随着机器人应用领域的不断拓 展、机器人工作环境复杂度、任务的加重，对机器人的要求也不再局限于单个机 器人，多机器人的研究已经成为机器人学研究的一个热点【5 】。利用多机器人来代 替单机器人很多时候在成本、效率等方面都具有优势，例如可以通过让多个简单 便宜的机器人合作来完成一个复杂昂贵的单机器人的工作。又如可以利用不同种 类的机器人通过不同组合来完成多种复杂不固定的任务，这比起单机器人来说灵 活性强得多。于是，人们开始研究尝试、止多移动机器人组队合作来完成一些复杂、 危险或人类无法到达的环境下完成一些救援、勘探的任务【6 j 。当今除了传统的核 废料和危险垃圾处理等工作外，现在也在为人道主义应用而研发机器人，其中之 一是扫雷，将威胁人类生命的地雷安全移走并销毁；另一个应用是城市人员搜救 1 7 1 ( 如地震、海啸、泥石流等灾害带来了大量惨重的伤亡) 。r a r k i n 领导的移动 机器人实验室一直致力于关于地面无人车辆系统( u gv ，u n m a n n e dg r o u n d v e h i c l e ) 的研究，该项目受美国国防部高级研究计划署d a r p a ( d e f e n s e a d v a n c e d r e s e a r c hp r o j e c ta g e n c y ) 的支持陋j 。2 0 0 2 年该项目进行到d e m oi i i 阶段，其目 标是为美国军队研制一队可投入战场使用的无人驾驶侦查车辆。r c a r k i n 的研 究小组对基于反应控制的机器人团队( 一组自治车辆) 在动态、危险环境下的协 同工作进行了深入研究。虽然现在这样的搜救机器人还没有真正投入于实际使 用，但是显然机器人能够进入一些狗和人类所无法进入的地方，这样可以降低搜 硕士学位论文第一章绪论 索时遭到损坏的建筑对工作人员的危险性。 如果要在这些危险复杂的环境中使用多机器人系统，则多机器人系统需要适 应任务的不断变化以及环境具有的非结构性与不确定性，系统必须具有高度的群 体智能或社会智能，对多移动机器人合作的研究也已不单纯是控制的协调，而是 整个系统的协调与合作。近年来，对多机器人系统的研究己越来越受到关注，组 成多机器人系统的机器人数目也越来越多一j ，对多机器人协调合作与通信机制问 题的研究越来越重要。通信是多机器人系统协调的关键，它的可靠性和容错性直 接影响到整个系统的合作协调能力i l ，而多机器人系统控制结构的复杂性决定 了系统信息交互方式的多样性。为了实现机器人的无缆运行，其通信方式一般都 采用无线通信，而a dh o c 网络则是随着近年计算机网络技术发展出现的一种分 布式结构的无线通信机制i l l l ，在多机器人通信中的应用日益增多。 因为多移动机器人在实际应用时面对的那些动态、复杂的非结构化环境中通 常都是没有或缺乏固定的网络设施，机器人又需要在通过通信来彼此交换信息共 同完成任务。而a dh o c 网络是一种特殊的无线移动通信网络，由于其中的所有 节点的地位平等，无需设置任何中心控制节点，具有很强的抗毁性。a dh o c 网 络有着广泛的应用场合，特别适合于战术通信、抢险救灾、紧急施工和集会等突 发性、临时性场合【l “，这些场合的共同点都是在没有或缺乏固定的网络设施的 条件下，因此研究a dh o c 网络在多移动机器人上的应用具有重要的意义。 本课题的研究是基于以上背景提出的，论文内容来源于国家自然科学基金重 点项目( 6 0 2 3 4 0 3 0 ) “未知环境中移动机器人导航控制的理论与方法研究”与国 家基础研究项目( a 1 4 2 0 0 6 0 1 5 9 ) “多移动体协同技术的基础研究”，主要研究有关 多机器人间相互合作完成任务的协调与通信机制部分，研究a dh o c 网络在多移 动机器人团队合作探索任务中的应用。 1 2 多机器人团队合作任务及通信的研究现状 1 2 1 多机器人系统研究现状 当前国内外在多机器人系统的研究中，普遍借鉴了人工智能领域中的多真体 ( m u l t i a g e n ts y s t e m ：m a s ) 系统盼1 4 】理论，其要点是把系统中的每一机器人看 作独立的真体( a g e n t ) 【l ”。真体的概念最早于2 0 世纪7 0 年代出现在分布式人 工智能( d a i ) 研究领域，分布式人工智能及以后的分布式问题求解的概念、体 系结构、协调合作的方式与策略等方面的研究已取得了很多成果【1 “。8 0 年代起 真体开始成为分布式人工智能研究的热点问题，而近1 0 年以来，多真体系统的 研究又成为了热点中的热点问题，并成为继面向对象方法之后出现的又一种进行 硕士学位论文第一章绪论 系统分析与设计的强有力的思想方法i l7 1 ，引起计算机、人工智能、自动化等领 域科技工作者的浓厚兴趣。 多真体系统是一个由多个真体组成的松散耦合又协同公事的系统，它可以由 多个智能和能力较低或较单一的真体组成，也可以由几个较复杂的真体成员为基 础结合其他简单多真体成员共同组成，多个多真体系统又可以组成更为复杂的真 体系统，这也就是多真体系统层次设计属性。在理论上，多真体系统具有四个主 要特性：环境的动态性、复杂性；真体的动态协调性；规划和推理的实时性；解 决的问题具有多目的多重制约性。多真体系统构造的核心就是把整个系统分成 若干个真体、自治的子系统，它们在地理上可以分散地单独去执行任务，同时可 以通过通信交换或共享一些信息，来相互协调、合作共同完成总体任务，其目标 主要是将大而复杂的系统( 软件和硬件系统) 建造成小的、彼此相互通信及协调 的、易于管理的系统。由于它的这些特点对于完成大规模和复杂的任务是非常有 优势的，所以有着十分广泛的应用领域，如制造业、过程控制、机器人协调、远 程通讯、交通控制、交通和运输管理、电子商务、数据库、医疗以及社会政治经 济系统等方面，也因此很快在军事、通信及其他应用领域得到了广泛的重视。 如今多机器人协调的系统在理论、实践等许多方面都取得了许多成果，并建 立了一些仿真实验系统，如c e b o r 、s w a r m 、a c t r e s s 、g o f e r 、a l l i a n c e 、 a r m y a n t 等系统【l 。而多真体团体在机器人竞赛中也正变得更为流行，尤其要 数两大国际机器人足球比赛：r o b o c u p 和m i r o s o t ，它是以多真体系统( m a s ) 与分布式人工智能( d a i ) 为主要研究背景，通过提供的一个标准的、易于评价 的比赛平台，以促进m a s 与d a i 的研究与发展i l 。目前多机器人系统的研究 还基本上处于理论研究阶段，对于多机器人系统体系结构与协作机制、信息交互 以及冲突消除、分布式传感、分布式规划与决策等方面将是多机器人系统的进一 步研究方向。 1 2 2 通信在多机器人团队合作任务中研究现状 多机器人团队合作主要是指多个真体问协作、联合行动以确保团队以一致性 方式运作的过程，一致性意味着团队中的多真体是作为一个整体而行动，即团队 行为显现的不是某个真体的行为，而是整个团队在运作1 2 。多机器人团体合作 时，机器人要基于一定的策略、协调机制和规则等有机的组织起来，机器人通过 组织结构知识获得关于系统整个行为的全局观点，而采取有效策略引导局部控制 实现协作i l 。团队合作不仅包括协作( c o o p e r a t i o n ) 而且包括协调( c o o r d i n a t i o n ) ， 多机器人协调是指多个机器人之间通过对目标、资源和思维状态等进行合理安 排，凋整各自的行为，以求最大可能地实现各自或系统的目标。协调是一种动态 硕十学位论文第一章绪论 行为，是机器人对环境及其他机器人的适应，它往往通过改变机器人的心智状态 来实现。而多机器人协作是指多个机器人通过协调各自的行为，合作完成共同目 标，协作是一种特殊类型的协调【6 1 。 一般来说多机器人系统工作的环境都比较大，各机器人分散于环境中，机器 人处理自身传感器获得的信息往往不够，还需要将其他机器人的传感信息与自身 的传感信息进行融合以获取对外部环境正确的和较全面的理解，因此机器人间需 要通过通信交互各自的信息来相互协调工作，使整个系统具有更强的获取外部信 息的能力。而且为了使整个机器人团队在协作完成任务时能够更好的协作行为， 避免机器人之间的冲突，其中很重要的一个关键就是其相互间的通信。通信作为 一种组织化机制，不仅存在于机器人个体之间、机器人个体与群体之间，还存在 于机器人群体与群体、机器人群体与人之间，是机器人团队合作任务活动中的关 键因素之一。 机器人间的通信方式一般分为两类，即隐式通信与显式通信【2 l j 。隐式通信 一般是机器人通过传感器感知所获得的其他真体行为的信息来实现。如无人操纵 的飞行器通过其自身的传感器持续得到其他车辆运动行动变化信息。而显式通信 主要是通过无线电方式，按一定的协议规范来相互发送或接受信息。机器人使用 无线通信由于面临许多不稳定的因素而常使通信得不到保障，一些研究者试图让 机器人间不需要显式通信或仅需要少量通信的合作机制来合作完成任务，如r c a r k i n 等提出的一种通过对全局制定行为合作计划，机器人间不需进行显式通信 来就可完成搜索任务的合作机制1 2 “，以及s i m o nc h n g 和l i np a d g h a m 在机器人 足球赛中建立的机器人具有各自角色特征和相应的责任策略，机器人间仅需少量 通信或者无通信的团队合作机制f 2 3 1 。另一些研究则希望利用显式通信来提高团 队内部或团队之间的合作能力，如m j m a t a r i e 等提出利用通信来提高分布式多 真体的学习，真体间通过通信来获得所需的传感信息和使从整体上合理进行任务 分配【2 4 1 ；还有m a r c u sj h u b e r 和t e d dh a r l e y 设计的n e t r e ka g e n t 游戏系统，它 是通过互联网连接的复杂实时的，可由多个游戏者多个团队参与的游戏，它主要 就是要求通过互联网来进行和提高团队的合作能力1 2 ”。 一种好的通信机制能使机器人团队间的合作更加协调有效，随着目前计算机 网络的无线通信技术的迅速发展，在多机器人团队合作中越来越多的使用有显式 通信的合作机制。 1 2 3a dh o c 网络在多机器人上的研究现状 a dh o e 网络的前身是分组无线网( p a c k e tr a d i on e t w o r k ) ，它的研究一开始 是源于军事通信的需要”1 。早在1 9 7 2 年时美国的d a r p a ( d e f e n s ea d v a n c e d 4 硕士学位论文第一章绪论 r e s e a r c hp r o j e c ta g e n c y ) 就启动了分组无线网项目p r n e t ，研究分组无线网在 战场环境下数据通信中的应用，此后又于1 9 8 3 年启动了s u r a n ( s u r v i v a b l e a d a p t i v e n e t w o r k ) 项目，研究如何将p r n e t 的成果加以扩展，以支持更大规模 的网络。1 9 9 4 年d a r p a 又启动了全球移动信息系统项目( g l o b a lm o b i l e i n f o r m a t i o ns y s t e m ) ，对能够满足军事应用需要的、可快速展开、高抗毁性的移 动信息系统进行全面深入的研究。1 9 9 1 年5 月成立的i e e e 8 0 2 1 l 标准委员会采 用了“a dh o c 网络”一词来描述这种特殊的、自组织、对等式多跳无线通信网 络，i e t f 则将其称为移动a d h o c 网络( m a n e t ，m o b i l e a d h o c n e t w o r k ) 。 由于a dh o c 网络能适应多移动机器人在实际应用时面对的没有或缺乏固定 的网络设施，动态、复杂的非结构化环境，满足机器人通过通信来彼此交换信息 共同完成任务的需要，因此在多机器人应用已越来越多。 在多移动机器人中采用a dh o c 网络来进行通信，则每个移动机器人相当于 a dh o c 网络中的一个节点，也就可以被认为是一个路由器，它们可以通过转发 邻机器人发送的报文信息来相互协调合作。在多移动机器人上利用a dh o c 网络 进行通信，国外许多研究人员已在此方面开始了大量的研究工作1 2 6 2 7 , 2 8 , 2 9 , 3 0 l ， 但大部分都是在假设有一个可靠持续的网络上的条件下进行的机器人任务实验。 而且a dh o c 网络在多移动机器人的研究一直以来都主要集中放在由机器人配置 构成的传感网络的信息共享性能上的提高口“，以及为了协助基于行为的多机器 人系统或反应式多机器人系统的协调1 2 4 1 。这些研究都主要在于提高大范围内感 知的信息交换，都仅仅是采用简单的广播消息的方式来传递所感知到的信息给所 有其他的机器人，而并没有研究怎样构建一个好的a dh o c 路由协议来进行和保 证机器人间的通信。 1 3 论文工作研究的主要内容 本论文在国家自然科学基金重点项目与国家基础研究项目的支持下，展开了 有关多机器人间相互合作完成任务的协调与通信机制的部分的研究与实验。研究 的主要内容主要分为以下几点： l 、提出了一个基于a dh o c 网络下的多移动机器人混合式团队合作机制， 此机制可以实现在多个a dh o c 网络问实行分布式协调和一个网内集中式协调。 其目的在于利用a dh o c 网络来使多移动机器人间在进行团队合作任务时能够具 有较好好的协调性、容错能力和可扩展性。 多个a dh o c 网络的实行分布式协调机制，即各个a dh o c 子网问的任务计 划相对独立，由各个每个a dh o c 网络独立设计执行。一个a dh o c 网络内的集 中式协调机制，此网络允许包括由单个机器人构成的网络，有利于建立在对环境 硕士学位论文 第一章绪论 认知上的计划可行性随着机器人对环境认知程度不断加深而增加或修改计划的 执行。集中式的协调也有利于集中多机器人收集到的信息进行总结再计划任务并 分配到单个的机器人，也能够防止机器人间的冲突。 2 、对多移动机器人中的几种典型a dh o c 网络路由协议进行分析，比较其 各自的特点、功能和应用环境。针对多机器人的一些运动特性，利用n s 2 网络 仿真软件对三种典型路由协议进行仿真和比较分析，讨论了对于不同情况下适用 于多移动机器人的a dh o c 路由协议。 3 、详细分析了由多机器人间的相对运动造成的不连续网络的现象，然后针 对这个现象对d s d v 路由协议改进了。改进后的协议是一种适合移动机器人在 不连续多a dh o e 网络上的路由协议一a n m r ( a d h o cn e t w o r k sr o u t i n gp r o t o c o l f o rm o b i l er o b o t s ) 。此协议能够在实时变换的环境下确保机器人协调算法的执 行，解决出现的在多个a dh o c 网络中由于机器人的移动造成的网络合并和分裂 现象，能保证多机器人在合作完成任务时对信息交互实时性较高的需要。 4 、根据现有的实验平台及实验环境，设计了多移动机器人团队执行寻找特 征目标的任务，即寻找形状为长方形、具有特定的颜色特征的目标，并到目标所 在地点。实验过程中采用a dh o c 网间相对分布式协调与一个网内集中式协调的 机制，同一个a d h o c 网络内按个人或队长分配的计划朝各自预定目标前进。并 利用a n m r 路由协议解决了在机器人的运动过程中，两个a dh o c 网络发生合 并、网络内发生拓扑结构变化及网络发生分裂现象，并进行路由信息的更新，以 保证了网络通信的实时性。实验的成功实现对构建的多个a dh o c 网络间分布式 结构与一个a dh o e 网络内集中式结构的混合式合作机制，及提出的a n m r 路 由协议的有效性进行了验证。 1 4 论文章节安排 本论文分为六章，论文结构安排如下： 第一章介绍课题的研究背景及研究意义，综述了多机器人团队合作任务及 通信的研究现状，分析比较了国内外在多机器人团队合作中采用a d h o c 网络方 面的研究现状。 第二章介绍多移动机器人系统与通信问题的基础理论知识，其中包括多移 动机器人系统体系结构及团队合作的基础理论与多移动机器人团队合作任务中 的通信问题两部分，并重点介绍了能适应在动态、复杂、非结构环境中团队合作 任务的多移动机器人a dh o c 网络。 第三章阐述了应用在多移动机器人中的几种典型a dh o e 网络路由协议， 比较了这些协议的特点和功能，并分析各种协议的不足和应用环境。然后根据机 硕士学位论文第一章绪论 器人的一些运动特性利用n s 2 网络仿真软件对三种典型路由协议进行仿真和比 较分析，最后讨论了对于不同情况下适用于多移动机器人上的a dh o c 路由协议。 第四章通过分析由多机器人间的相对运动造成的不连续网络，改进了 d s d v 路由协议，此改进后的协议是一种在不连续网络上适用的基于多移动机 器人多a dh o e 网络的路由协议a n m r ( a d h o cn e t w o r k sr o u t i n gp r o t o c o l f o rm o b i l er o b o t s ) 路由协议。并构建了一个在未知的动态环境下多移动机器人 团队的混合式的合作机制，此机制是在多个a dh o c 网络的实行分布式协调与一 个网内集中式协调。 第五章设计并完成在实验室环境中的多移动机器人团队寻找特征目标的任 务实验，对构建的在多个a dh o c 网络间实行分布式协调与一个网内集中式协调 的多移动机器人的混合式团队合作机制，及将d s d v 路由协议进行改进的协议 a n m r 路由协议有效性进行了验证。 第六章对本论文工作所进行的主要研究内容进行了总结，及下一步的研究 方向与展望。 硕士学位论文第二章多移动机器人系统与通信问题 第二章多移动机器人系统与通信问题 从2 0 世纪7 0 年代多机器人系统出现以来，国内外许多高校和研究机构对其 进行了广泛的研究。如在多机器人编队、围捕、清扫、机器人足球赛等许多领域 中，机器人间的合作都是很重要的研究重点。团队是多真体合作问题求解的有效 方式，在许多动态、复杂的应用环境中发挥着越来越重要的作用。从理论上说， 团队活动的本质特征是真体有共享的目标和共享的承诺、意图等联合思维状态， 它们的形成和演化严重依赖于真体间的通信1 3 “。 2 1 多移动机器人系统体系结构及团队合作的基础理论 2 1 1 多机器人团队合作理论 b r a t m a n 等指出团队合作中应该包括，真体有共享的承诺，当没有队友的参 与也不能够单独放弃承诺；真体问有互相协助的意图，即主动协助队友完成任务； 真体问有共同的目标，当出现意外情况时，真体能够接管队友未完成的任务。在 此基础上，很多研究者提出了一些很有影响力的理论体系，这些理论基础不需要 直接针对某一场景，而是要给团队合作提供一个广泛的推理过程或启发式方法 3 3 1 。 联合意图( j o i n ti n t e n t i o n ) 理论 联合意图理论1 3 4 ，3 5 】的主要内容是，团队的所有成员在完成一个联合任务时， 通过相互协商尽力去实现联合目标，在实现过程中，若有队员发现这个目标已经 完成，或者目标不可能完成，或是目标不相关的话，则它负责将此信念让所有队 友都认可这一信念。 可将此过程描述为： 联合任务又称联合持续目标( j p g ，j o i n tp e r s i s t e n tg o a l ) 是团队的成员共同 承诺，且队员问彼此信任地去完成的任务目标。如果设团队有成员x 、y ，联合 承诺去实现任务p ，q 是一个相关变量( 如动机，若q 为假，即不相关则放弃任 务p ) ，则可将联合持续目标表示为j p g ( x ，y ，p ，q ) 。当同时满足以下三个条件时， 团队将保持执行联合持续目标j p g ： 1 ) x ，y 都认为当前状态下p 为假，即任务p 未完成； 2 ) x ，y 都将使p 为真作为目标，即希望完成任务p ； 3 ) 除非p 已经被公认实现或不可能实现，或者q 为假，否则x ，y 都将一直 把p 作为自己的弱目标。 硕士学位论文第二章多移动机器人系统与通信问题 弱目标( w a g ，w e a ka c h i e v e m e n tg o a l ) 是指团队中的成员各自拥有的弱目 标，可表示为w a g ( x l iy ，p ， x ，y ) ，q ) ，即队中每个成员x 或y 认为任务p 处于 以下两种情况之时，有责任将其任务p 的状态成为团队中所有成员的信念即 j p g ： 任务p 目前为假，且将p 为真作为目标； p 被发现处于已实现或不可能实现，或者q 为假三种状态之一。 简单的说，此理论中弱目标( w a g ) 就是在没有公认为联合持续目标( j p g ) 时的局部目标。就是要一个成员把p 作为w a p 努力去实现，若发现p 已经处于 已实现或不可能实现或不相关状态时，就要设法让所有队友都认可这个信念，当 这个信念形成共识时，就成为了j p g 。目的就是要让p 达到所有队员都认为的终 止状态( 已实现、不可能实现、不相关状态之一) ，而要实现这一点，就要求团 队成员能随时更新团队状态，有较为完善的通信机制。 共享计划( s h a r e dp l a n ) 理论 共享计划理论t 3 6 i 与联合意图理论不同在于，联合意图理论中团队成员联合 定义了一个j p g ，而共享计划理论则没有共同目标的概念，是先由各队员共同制 订计划，再根据计划来指导各队员的行动，包括队员间的通信来使得队员自身、 子团体或整个团体能够协调完成任务。 一个团队( g r ，g r o u pa g e n t s ) 共同参加一个任务a 时，共享计划s p 是用 于分布式的分配规划好的任务。s p 又分为f s p ( f u l ls h a r e dp l a n ) 和p s p ( p a r t i a l s h a r e dp l a n ) ，全局共享计划f s p 是所有参与任务a 的成员全局共享规划制订的， 部分共享计划p s p 只与部分团队成员有关。 一个全局共享计划的过程可以描述为，当在确定执行一个任务旺时，所有团 队成员达成一个全局共享计划f s p 。共享计划包含的所有要完成的联合行动的各 方面细节和步骤的集合可表示为k ，艮的具体任务用d l 表示。用f s p ( p , g r ，t p ， t 。，r 。) 来表示，团队g r 在t p 时间定义的全局规划p ，根据行动集合r n 在t 。时 间完成任务。且当满足以下条件时f s p ( p , g r ，a ，t p ，t 。，k ) 有效： 1 ) 团队g r 中的所有成员都共同相信任务将在t n 时间完成； 2 ) 团队g r 中的所有成员都共同相信行动集合r 是完成任务c c 的任务集； 3 ) 对于行动集合r e c 中每一步具体任务采用递归的方法，计划中的每一步 会由一些团队成员组称g r 的子集g r k 来完成，g 凰用与g r 相同的方法定义。 共享规划理论理想上是希望能有很详细周全的全局共享计划f s p 来表达整 个团队的行动，但在实际的动态、实时的环境下很难达到真正的f s p ，使用更多 的是部分共享计划p s p ，因此制订的规划也常是阶段性的、局部性的，要最终形 成f s p 还要有相应的通信协议来协助完成。 9 硕士学位论文第二章多移动机器人系统与通信问题 s t e a m 模型 m i l i n dt a m b e 等提出的s t e a m l 3 7 1 模型是建立在联合意图与共享计划理论上 的一种通用模型，它不依赖特定领域的知识，真体可以通过此模型对通信和协作 进行自治、自动的推理，这样可以实现团队的灵活性，并且该模型具有很好的重 用性，已在仿真直升机作战、仿真机器人足球赛、虚拟环境和教育以及i n t e m e t 上的信息集成等不同领域得到了应用。 s t e a m 模型采用了联合意图理论的共同信念思想，通过给团队建立共同信 念和终止条件来实现给予团队的活动明确的目标和提供检测和支持的保证。 s t e a m 还借鉴了共享规划理论的共同规划的想法，提出了一种操作( o p e r a t o r s ) 的概念来更好的实现团队的动态组合及分工协作。操作的概念包括个体操作 ( i n d i v i d u a lo p e r a t o r s ) 和团队操作( t e a mo p e r a t o r s ) 两部份，团队操作其实就是 一个交互的团队规划。而一个操作在执行时是个体操作还是团队操作是动态决定 的，当某个真体触发一个操作时，由s t e a m 模型动态的决定这个操作是一个个 体执行，还是一个子团队执行，或是整