（控制理论与控制工程专业论文）基于单亲遗传算法的robocup机器人足球比赛策略研究.pdf

r e s e a r c ho ns t r a t e g yi nt h em i d d l e - s i z el e a g u eo f r o b o c u p b a s e do np a r t h e n o g e n e t i ca l g o r i t h m b y l ig e n b e ( c h a n g s h au n i v e r s i t yo fs c i e n c e t e c h n o l o g y ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro f e n g i n e e r i n g i n c o n t r o lt h e o r ya n dc o n t r o le n g i n e e r i n g l n c h a n g s h au n i v e r s i t yo fs c i e n c e t e c h n o l o g y s u p e r v i s o r p r o f e s s o rl im a o j u n a p r i l ，2 0 11 长沙理工大学 学位论文原创性声明 一 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名： e l 觏：汐f | 年玉具以e l 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并l a - j 国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩f - i 或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密日。 ( 请在以上相应方框内打“4 ) 作者签名：厍互 日期：汐年月撕 名：妇麓日期刎年手月7 日 摘要 机器人足球系统是一个多机器人系统。r o b o c u p 中型组比赛环境具有动态、 对抗和不确定性的特性。本文在研究多机器人协作特别是r o b o c u p 中型组比赛环 境下的多机器人协作策略研究成果的基础上，结合r o b o c u p 中型组机器人的实际 情况，设计了一套基于单亲遗传算法的多机器人协作机制，实现了多机器人系统 稳定的动态协作。然后特别针对多机器人动态角色分配和避障策略问题，设计了 一个基于单亲遗传算法的动态角色分配方案以及全局避障策略，最终实现了多个 机器人初步的战术配合。 针对r o b o c u p q 口型组比赛提出的动态阵型选择算法建立了动态协作模型，将 多个智能体组合成一个拥有共同目标的团队，完成给定的任务分配和站位配合。 实现了基于动态阵型变换的多智能体动态协作。通过实现各种阵型之间的动态变 换，满足了不同情况的协作要求，显著提高了球队的整体竞赛能力。 r o b o c u p 中型组的机器人动态角色分配问题是一个典型的组合优化问题，解 决这一问题的传统方法是贪心法，但贪心法易陷入局部最优解。本文提出的基于 单亲遗传算法的r o b o c u p 中型组的机器人动态角色分配策略有效地解决了这一 问题。试验结果显示了这种方法在解决r o b o c u p 中型组机器人动态角色分配问题 时的有效性。 在r o b o c u p 中型组足球机器人系统避障策略的设计中使用单亲遗传算法，使 机器人能动态地避开障碍物并找到一条从给定起始点到目标点的较短路径。阐述 了具体算法的设计与实现，给出了试验结果。根据避障策略的特点改进了遗传操 作，增加了基因复制操作，加快种群进化，得到了较好的效果。 本文针对r o b o c u p 中型组机器人协作问题的研究，理论结合实际，根据现有 平台提出了真实环境中多机器人的协作策略，为r o b o c u p 中型组机器人协作问题 的进一步研究和应用设计奠定了基础。 关键词：r o b o o u p ；协作策略；阵型选择；角色分配：避障：单亲遗传算法 a bs t r a c t s y s t e m o fs o c c e r - r o b o t i sa s y s t e m o fm u l t i r o b o t t h e c o m p e t i t i o n e n v i r o n m e n to ft h em i d d l e s i z e l e a g u eo fr o b o c u pi sd y n a m i ca n dw i t ht h e c h a r a c t e r i s t i c so fc o n f r o n t a t i o na n du n c e r t a i n t y s ot h e a p p r o p r i a t ed e s i g n i n go f c o o p e r a t i v es t r a t e g yi st h ek e yt oi t so v e r a l lp e r f o r m a n c e b a s eo nt h er e s e a r c ho f t h e m u l t i r o b o t c o o p e r a t i o n ，e s p e c i a l l yi n t h ec o m p e t i t i o ne n v i r o n m e n to ft h e m i d d l e s i z el e a g u eo fr o b o c u p ，am u l t i r o b o tc o o p e r a t i o nm e c h a n i s mi sd e s i g n e d b a s e do np a r t h e n o - g e n e t i ca l g o r i t h ma n dc o m b i n e dw i t ha c t u a ls i t u a t i o no ft h e m i d d l e - s i z el e a g u eo fr o b o c u p i ta c h i e v e sad y n a m i cc o o p e r a t i o nw i t hs t a b i l i t yi n m u l t i - r o b o ts y s t e m e s p e c i a l l yf o rm u l t i r o b o tr o l ed y n a m i ca l l o c a t i n gp r o b l e ma n d o b s t a c l e - a v o i d a n c es t r a t e g y ，a na l g o r i t h mo nr o l ed y n a m i ca l l o c a t i n ga n dg l o b a l o b s t a c l e - a v o i d a n c ei sd e s i g n e d ，a n du l t i m a t e l ya c o o p e r a t i o nt a c t i c so fm u l t i r o b o ti s a c h i e v e d ad y n a m i cf o r m a t i o n s e l e c t i n ga l g o r i t h m f o rt h em i d d l e - s i z e l e a g u e o f r o b o c u pi sp r o p o s e d m u l t ia g e n t sa r el i n k e di n t oag r o u pt oa c h i e v eac o m m o ng o a l t h r o u g hf o r m a t i o n ac o o p e r a t i o nm o d e li sb u i l tt oc a r r yo u tt h ea l l o c a t i o na n d s t a n d i n g - l o c a t i o nc o o p e r a t i o nf o rap r e a s s i g n e dt a s k t h e s es t r a t e g i e sa r ep e r f o r m e d t oa c h i e v ed y n a m i cc o o p e r a t i o nb a s e do nt h ed y n a m i cf o r m a t i o ns w i t c h i n gb e t w e e n d i f f e r e n tf o r m a t i o n s t h e r e f o r e ，t h er e q u i r e m e n to fd i f f e r e n ts t a g e si ss a t i s f i e d ，a n d t h et o t a la b i l i t yo ft h et e a mi nt h eg a m ei sn o t a b l yi m p r o v e d i nv i e wo fa l g o r i t h mo nr o l ed y n a m i ca l l o c a t i n go fr o b o c u p ，p a r t h e n o g e n e t i c a l g o r i t h mi si n t r o d u c e dt og e tan e a r o p t i m i z e ds o l u t i o no fr o l ea l l o c a t i n gp r o b l e m p a r t h e n o - g e n e t i ca l g o r i t h m w h i c hi sf r o mt h e ”s u r v i v a lo ft h ef i t t e s t ”m e c h a n i s mo f n a t u r a l s e l e c t i o n ，g e t st h es o l u t i o ne v o l v i n gi n t oan e a r o p t i m i z e da tl a s t a n di t s o l v e st h ep r o b l e mt h a tt h es o l u t i o ni se a s yt oe n t e rl o c a lo p t i m i z a t i o nb yu s i n gt h e g r e e d ya l g o r i t h m i nt h e c a l c u l a t i o n e x p e r i m e n t a l r e s u l t si n d i c a t et h a t p a r t h e n o - g e n e t i ca l g o r i t h mh a st h ec h a r a c t e r i s t i co fg l o b a lo p t i m a l i t y ，a n di tc a n s a t i s f yt h er e q u i r e m e n to fr e a l t i m e s ot h et o t a la b i l i t yo ft h et e a mi nt h eg a m ei s i i n o t a b l yi m p r o v e d d e s i g no fa no b s t a c l e - a v o i d a n c es t r a t e g yb a s e do np a r t h e n o g e n e t i ca l g o r i t h m s i nt h em i d d l e - s i z el e a g u eo fr o b o c u pw h i c hm a k e st h er o b o ta v o i do b s t a c l e sa n d f i n das h o r t e s tp a t hf r o ms t a r t i n gp o i n tt ot h et a r g e tp o i n t ，a n dt h er e a l i z i n gp r o c e s s o ft h i s a l g o r i t h m a r ei n t r o d u c e di nd e t a i l i nt h i s p a p e ra c c o r d i n g t ot h e c h a r a c t e r i s t i c so fc o d i n g ，as i n g l ep o i n to fg e n ec l o n eo p e r a t i o ni sa d d e di ng e n e t i c m a n i p u l a t i o no fp a r t h e n o g e n e t i ca l g o r i t h m sw h i c hc a na c c e l e r a t et h ep o p u l a t i o n e v o l u t i o n a r y t h es i m u l a t i o nr e s u l t si n d i c a t et h a tt h i sa l g o r i t h mc a nm a k et h er o b o t a v o i do b s t a c l e sa n df i n dt h eo p t i m a lp a t h t h i sr e s e a r c hf o rt h ec o o r d i n a t i o np r o b l e mi nt h em i d d l e s i z e l e a g u e o f r o b o c u pc o m b i n e sb o t ht h e o r ya n dr e a l i t y ac o o r d i n a t i o ns t r a t e g yo fm u l t i - r o b o ti n t h er e a ls i t u a t i o n si sd e s i g n e d ，a c c o r d i n gt ot h ee x i s t i n gp l a t f o r m i ti saf o u n d a t i o n o ff u r t h e rr e s e a r c ha n dd e s i g no fa p p l i c a t i o no nt h ec o o r d i n a t i o n p r o b l e mi n t h e m i d d l e s i z el e a g u eo fr o b o c u p k e yw o r d s ：r o b o c u p ；s t r a t e g yo fc o o p e r a t i o n ：f o r m a t i o ns e l e c t i n g ：r o l e a l l o c a t i n g ；o b s t a c l e - a v o i d a n c e ：p a r t h e n o - - g e n e t i ca l g o r i t h m i i i 目录 摘i i 8 邑i a b s t r a c t i i 第一章绪论 1 1机器人足球的起源与概况1 1 2机器人足球研究的意义1 1 3 r o b o c u p 中型组介绍2 1 4 国内外研究现状4 1 5 本文的主要工作5 第二章r o b o c u p 中型组协作策略分析 2 1 r o b o c u p 中型组系统介绍7 2 1 1 r o b o c u p 中型组比赛情况7 2 1 2 r o b o c u p 中型组机器人组成结构8 2 1 3 r o b o c u p 中型组机器人软件系统结构一9 2 1 4 r o b o c u p 中型组比赛环境1 l 2 2 r o b o c u p 中型组比赛协作策略1 2 2 2 1 动态阵型选择策略12 2 2 2 动态角色分配1 5 2 2 3 避障策略1 8 2 3本章小结1 9 第三章单亲遗传算法 3 1 单亲遗传算法与常规遗传算法的比较2 0 3 2单亲遗传算法的特点2 0 3 3单亲遗传算法的运行过程2 1 3 3 1 单亲遗传算法的编码方式2 3 3 3 2 单亲遗传算法的遗传算子2 3 3 3 3 单亲遗传算法的个体评价2 6 3 3 4 单亲遗传算法的选择方式2 7 3 3 5 单亲遗传算法的终止条件2 8 3 3 6 算法参数设置2 8 3 4改进的单亲遗传算法遗传算子2 9 3 5本章小结- 2 9 第四章基于单亲遗传算法的策略模型 4 1 基于单亲遗传算法的角色分配3 1 4 1 1 角色的效用评估3 1 4 1 2 基于单亲遗传算法的角色计算3 l 4 2基于单亲遗传算法的避障策略3 3 4 2 。l 避障区域设置3 3 4 2 2 基于单亲遗传算法的避障策略3 3 4 3 本章小结3 6 第五章实例仿真与分析 5 1角色分配结果分析3 7 5 2 避障策略结果分析一3 8 5 3 本章小结3 9 总结与展望4 0 参考文献4 2 致谢4 5 附录a ( 攻读硕士学位期间发表论文目录) 4 6 附录b( 攻读硕士学位期间参与相关课题) 4 7 第一章绪论 多智能体系统( m u l t i - a g e n ts y s t e m ，简称m a s ) 的研究是由多个智能体基于一 定的协调机制组成的自组织系统。它通过相互通信和协调，以实时方式解决分散 存在的多智能体在复杂的动态环境下的知识处理问题。因此，m a s 的发展将知识 系统发展为开放和分布的知识系统，是人工智能发展史上的一个新的突破。 机器人世界杯足球锦标赛( r o b o tw o r l dc u p ，简称r o b o c u p ) 是一个以m a s 和分布式人工智能( d i s t r i b u t e da r t i f i c i a li n t e l l i g e n c e ，简称d a i ) 为主要研究背景的 大型比赛和学术活动，为促进d a i 与m a s 的研究与发展提供了一个标准平台。 本章介绍了机器人足球的起源和概况以及r o b o c u p 中型组的基本情况，讨论 了机器人足球研究的意义，并分析了国内外r o b o c u p 中型组的研究现状，最后介 绍了本文的主要工作。 1 1 机器人足球的起源与概况 1 9 9 2 年，加拿大不列颠哥伦比亚大学的a l a nm a c k w o r t h 教授在新加坡世界科 学出版社出版的计算机视觉：系统、理论与应用上发表的论文o ns e e i n gr o b o t s ) ) 中首次提出了一个重要设想一一通过研究可以进行足球比赛的机器人来促进相关 领域的发展。并在同年1 0 月，于日本东京举行了关于人工智能领域重大挑战的 研讨会中为促进相关领域研究针对制造和训练机器人进行足球比赛进行了探讨。 1 9 9 6 年，以促进分布式人工智能与智能机器人技术的研究与教育为使命的 r o b o c u p 国际联合会成立。1 9 9 7 年，机器人足球在第1 5 届国际人工智能联合大会 上被正式列为人工智能的一项挑战。并在日本的名古屋举行了首届r o b o c u p 比赛 及会议。它的最终目标是到2 0 5 0 年左右，由一支完全自主的机器人所组建的足球 队在遵循国际足联正式规则的前提下能够战胜人类世界冠军队。此后每年举办一 届，至此机器人足球成为人工智能和机器人学的新的标准问题。 1 2 机器人足球研究的意义 r o b o c u p 既是一个标准问题，也是一个划时代的计划。机器人足球研究的意 图是将r o b o c u p 作为促进人工智能和机器人学研究的工具。在过去1 0 年研究的基 础上，这个目标依旧是人工智能与机器人学今后4 0 年的重大挑战。这不是一个短 期内能完成的目标，需要很长的时间以及大量的研究人员付出极大的努力。但从 这个目标衍生出了一系列方向有利的子目标，以此来带动这个领域的长期发展。 这是一个划时代的计划。 一个成功的划时代计划必须完成一个引人注目的目标。阿波罗太空计划就是 一个最成功的例子。在阿波罗计划中，美国制定了“送一个宇航员登陆月球并安 全返回地球 的目标。“这是一个人的一小步，却是人类的一大步。目标的完成 本身就是。苓人类的历史性事件。为达到这个目标而发展的技术也成了美国工业 强大的技术和人员基础。因此机器人足球发展过程中的研究成果也将会成为今后 工业发展的技术基础。 同时r o b o c u p 也是一个标准问题，可以用来评价各种不同的理论、算法和体 系结构。同样作为标准问题的计算机国际象棋与r o b o c u p 的领域特征却是不同的： 表1 1 国际机器人象棋对抗赛和机器人足球研究背景特征的区别 环境状态改变获取信息传感器信息控制方式 国际象棋静态回合制完全符号式集中 r o b o c u p动态实时不完全非符号式分布 r o b o c u p 是人工智能研究的典型问题，是一个可以用以检验多智能体系统优 劣程度的标准试验平台。r o b o c u p 所研究的动态环境以及具有实时性的知识处理 将人工智能发展到一个新的层次，毫无疑问将会成为人工智能发展史上的第二个 里程碑。 1 3 r o b o c u p 中型组介绍 机器人足球赛涉及人工智能、机器人学等诸多领域的前沿研究和技术集成， 是一种高科技的对抗赛。国际上最具影响的f i r a 和r o b o c u p 两大世界杯机器人 足球赛。 r o b o c u p 中型组比赛项目在1 9 9 7 年第一届比赛时就已设立，同时设立的只有 小型组和仿真组比赛，此后还不断增加了一些新的项目，如类人机器人比赛及机 2 器人挑战赛等。每个比赛项目的规则都各不相同，研究的侧重点也各不相同，因 此对机器人和环境的要求与设定也各不相同，本文主要研究的是r o b o c u p 中型组 比赛。 图1 1r o b o c u p 中型组比赛实际场地 图1 2r o b o c u p 中型组比赛标准场地 r o b o c u p 中型组比赛是在两支由全自主的机器人所组成的球队间展开的。参 加比赛的所有机器人都不允许配备外部传感器，所有传感器都必须安装在机器人 本体上，机器人之间的信息共享和战术协调都通过比赛规则限定的无线通信来实 现。场上比赛的每支球队最多可以有5 名机器人球员，但是其中1 名机器人必须 3 是守门员。机器人在地上的投影最小为3 0 c m x 3 0 e m ，最大为5 0 e r a x 5 0 c m 。机器 人高度最小为4 0 c m ，最大为8 0 c m ，守门员的高度最高可以为9 0 e r a 。单个机器人 的质量不能超过4 0 k g 。 r o b o c u p 中型组比赛技术委员会在每一届的比赛前确定并公布该届比赛所采 用的场地尺寸。2 0 0 9 年r o b o c u p 中型组比赛标准场地尺寸为长1 8 m x1 2 m ，而且 未来场地还有不断扩大的趋势。同时每年的比赛规则都会随着参赛机器人的技术 水平的不断提高而进行广泛讨论并最终通过技术委员会做出部分修改。 r o b o c u p 中型组机器人因具有全自主性以及高度对抗性的特点，故技术要求 较高，需要解决的主要关键技术有： ( 1 ) 实时图像处理、图像识别及机器人定位； ( 2 ) 运动控制； ( 3 ) 复杂环境下的多机器人协作； ( 4 ) 非完整信息条件下的分布式决策。 r o b o c u p 中型组机器人足球赛最能体现出参赛队伍的相关领域的研究水平， 因其要求机器人完全自主，且所涉及的领域较多，是众多学科中前沿研究的集合。 1 4 国内外研究现状 多机器人系统的研究在2 0 世纪4 0 年代中期1 至2 0 世纪7 0 年代早期进展缓慢。 之后，多智能体之间的协调与交互成为了d a i 领域一个主要的研究方向1 2 1 ，但主 要是处理软件智能体的问题。直至8 0 年代后期，多机器人协作才成为机器人界一 个热门话题，并进行了一些实际的研究工作，例如：c e b o t t 3 l 、s w a r m h l 、 a c t r e s s t 5 】、g o f e r t 6 j 等，但这些研究由于受到条件限制，主要集中在仿真方面。 直到9 0 年代后期，研究平台才从仿真平台转移到机器人实体上。发展到今天，多 机器人系统研究成为机器人学和分布式人工智能的一个重要研究方向，研究平台 也日益丰富多样。例如，r o b o c u p 就是一个优秀的多机器人系统研究平台。 多机器人协作问题的研究最初是从控制的角度出发：多机器人的协作策略和 方法实际上只是一种控制算法；研究者根据控制理论( 如神经模糊控制等) 提出各种 系统协作的控制结构( 如传统的基于过程的控制、模块化的控制以及分层递阶式控 制体系) 用以提高系统的协作能力p 】。此后随着d a i 理论的发展，逐渐将m a s 概 4 念引入到多机器人系统，给多机器人系统协作的研究带来了重大的影响。目前， 基于m a s 的多机器人协作己成为机器人学研究领域的热点，也是多机器人协作研 究的一个重要方向。 在机器人足球比赛领域，多个机器人之间的协作问题也一直是各个队伍的研 究热点。受基础学科发展及环境复杂性的限制，以分布式和完全自治为特点的中 型组的多机器人协作问题研究相对仿真组和小型组较为滞后，目前中型组的研究 也在硬件体系结构构建、底层运动控制、视觉传感信息融合、图像处理和模式识 别等机器人个体行为方面的研究不断发展的基础上逐步深入多机器人协作方面。 随着比赛的发展和研究的深入，中型组机器人个体技能不断提高，已经基本具备 了完成简单协作配合的能力。因此，在r o b o c u p 中型组的实体机器人上实现多机 器人协作成为当前各球队的迫切需求。 r o b o c u p 中型组机器人比赛是一个分布式的动态、对抗和不确定性环境，所 需传感器均集成于机器人自身，各机器人信息既具有不完整性，同时还具备互补 性；而仿真环境是对现实环境进行的理想化处理，所以仿真组的研究成果被应用 到实体机器人上并不是一个简单的移植过程。应用过程中可能会出现很多新的问 题，比如：传感器信息不准确，通信部分失效，执行器延时，执行能力限制等。因 此需要针对中型组的具体特点来改进仿真组的研究成果，使其具有更好的鲁棒性 和容错性。目前在r o b o c u p 中型组中，多机器人协作研究还处于起步阶段，还有 很多理论和实践问题值得深入研究。r o b o c u p2 0 0 6 、r o b o c u p2 0 0 7 中型组冠军一 一德国o s n a b r u c k 大学的b r a i n s t o r m e r st r i b o t s 球队对仿真和实物之间的区别进行 了深入分析并提出了相应的解决方法弘1 ，并连续两年在球队描述文档中把机器学习 放在了研究热点的第一位p 1 0 j 。r o b o c u p 中型组的其他队伍也陆续开始尝试在实体 机器人上应用强化学习等智能方法n ，解决将仿真研究应用到实物的过程中出现 的一系列问题。因此，在实物机器人上融合仿真研究成果，应用机器学习等智能 方法解决真实环境下的多机器人协作问题成为r o b o c u p 中型组研究的一个重要方 向和发展趋势。 本文的主要工作 我校机器人竞赛培训基地的r o b o c u p 中型组机器人足球队组建于2 0 0 8 年。组 5 建初期，工作重点以熟悉机器人硬件体系结构、图像处理以及运动控制等机器人 个体性能方面为主，在多机器人协作方面的工作不够深入，存在角色分配不灵活、 协作策略单一、动态避障效果较差等问题。基于此，目前逐步开始研究多机器人 协作策略。本文的主要工作正是基于以上背景，详细设计了一套基于单亲遗传算 法的多机器人协作机制，实现了r o b o c u p 中型组机器人的动态角色分配和全局避 障策略。 本文的主要工作包括：结合r o b o c u p 中型组比赛环境的实际情况，设计了一 套基于单亲遗传算法的多机器人协作机制，实现了多机器人系统稳定的角色分配； 然后特别针对多机器人动态角色分配和避障策略问题，设计了基于单亲遗传算法 的动态角色分配方案以及全局避障策略，最终实现了多个机器人初步的战术配合。 本文详细论述了本人在建立球队的过程中主要的研究工作，包括动态阵型选 择、动态角色分配、机器人的避障策略等。 第二章分析了r o b o c u p 中型组比赛环境的特殊性；对多机器人协作机制进行 深入研究；构建适用于r o b o c u p 中型组机器人的多机器人协作机制理论框架。 第三章全面介绍了单亲遗传算法，分析了单亲遗传算法与传统遗传的相同和 不同之处。并详细阐述了单亲遗传算法的运行过程。针对第四章将要介绍的基于 单亲遗传算法的避障策略的编码特点改进了遗传操作，提出了基因复制算子。 第四章对动态角色分配与避障策略的模型进行了分析，详细地阐述了基于单 亲遗传算法的动态角色分配与避障策略算法的具体设计步骤。 第五章针对基于单亲遗传算法的动态角色分配与避障策略算法进行了仿真， 在不失一般性的情况下得到了不错的结果，证实了算法的有效性。算法计算的结 果不仅具有有效性，而且能满足r o b o c u p 中型组比赛实时性的要求。 6 国i ；i - i 垦幢 一一隧囊孽参o ，嗣 l i 。， 。j i ：，；器， 。 ：j j ? 爹i 坠二当陵；毖融彩黝燃渤。撬缢缸貔；巍貔，瀚辐，漱貔二涵赫握。垅础二妇虢施。；妊蠡。蕴巍，施戤；。蔬圆 r o b o c u p 中型组比赛中每支球队由5 个机器人组成，根据比赛规则的规定， 除守门员外，机器人的硬件结构设计是相同的，以配合协作策略的实行，实现角 色的互换以及协作策略的适时调整( 其中因守门员是固定的，可以设计与守门员 角色相应的硬件结构) 。参加比赛的机器人的硬件配置必须符合r o b o c u p 中型组标 准。 如图2 1 所示，比赛全程由主裁判控制，场外的助理裁判根据主裁判的判定控 制裁判盒，裁判盒将指令发送给参赛双方的教练机，再由教练机将指令发送给场 上己方机器人。所有比赛的机器人之间都是通过无线通信来实现信息的交互。 2 1 2 r o b o c u p 中型组机器人组成结构 r o b o c u p 中型组机器人采用模块化设计，图2 2 所示为机器人的总体结构， 可分为以下几个模块： ( 1 ) 全景视觉模块：由全向反射镜面和摄像机两部分组成。采用由双曲面镜、 球面镜、圆锥面镜等曲面反射镜和普通摄像机组成的全景镜头，双曲面 镜全景摄像机实物图如图2 3 所示。此种方式可以一次获得全景图像， 但大多常规曲面镜的成像原理不符合透视成像原理，因此会带来成像与 实际场景相比有一定程度的形变【1 2 】。 曩 全景视觉系统 上位机笔记本 下位机控制模块 ( 保护罩内) 盘球装置 击球装置 全向轮 图2 2r o b o c u p 中型组机器人结构图 8 双曲面镜 摄像机 图2 3 带双曲面镜的全景摄像机示意图 ( 2 ) 上位机控制模块：这是机器人的核心部分，是机器人的“大脑 。由一 台笔记本电脑来完成图像处理，通信和实时决策，并通过串口向下位机 的控制器发送运动指令。 ( 3 ) 下位机控制模块：本系统选用t m s 3 2 0 l f 2 4 0 7 a 处理器作为三轮全向移 动机器人运动控制的控制器，完成接收上位机( 笔机本电脑) 传来的运 动控制指令，然后根据接收到的运动指令控制机器人运行以实现规划的 运动。良好的底层运动控制系统除了要满足快速性和准确性要求外，还 要考虑以后机器人硬件平台的改进与更新的问题，化软件的模块、可移 植性、可再升级性，以及整个底层运动控制系统的可移植性3 1 。 ( 4 ) 盘球及击球装置：机器人盘球通过机器人前面的2 个电机带动轮子转动 时产生的轮子与球的摩擦力来实现的。击球装置是利用电容放电，使电 磁继电器将球“踢 出去。 ( 5 ) 全向轮：双轮差动驱动方式机器人是一非完整系统，其轨迹规划较为复 杂，运动轨迹归结为直线和圆弧。而三轮全向移动机器人为完整系统， 有三个自由度，对于机器人的三个参数oy0 ) 是无约束的，两点之间 可以直线运动，并可在行进中转向以调整姿态角【l4 1 ，其运动轨迹可归结 为折线。 2 1 3r o b o c u p 中型组机器人软件系统结构 控制程序用以实现r o b o c u p 中型组机器人的自主控制，使机器人全自主的对 信息进行处理并做出实时决策。其主要结构如图2 4 所示： 9 图2 4r o b o c u p 中型组机器人软件总体构架 ( 1 )颜色阈值模块：记录了球场标定模块标定的各个颜色的y u v 或者h i s 阈值结果，这些是进一步图像分割的基础。 ( 2 )图像采集模块：负责实时采集全景和前向视觉，并捕获单帧图像。 ( 3 )全景视觉模块：对捕获的单帧全景图像进行识别，识别的结果是各个 目标( 球、障碍物、白线等等) ，并计算出机器人的自身位置。 ( 4 )决策模块：根据视觉模块、通信模块以及记忆缓冲模块的输出结果进 行判断，其结果为机器人的运行方向和射门的开启。 ( 5 )基本动作模块：根据决策模块的输出结果控制个体的动作，比如追球、 盘球、自动摆位、射门、避障等等。 ( 6 )记忆缓冲模块：对全向视觉模块的输出结果进行过滤，并记忆上几个 决策周期的结果。 ( 7 )通信模块：与网络控制模块进行通信，以接受其发送的命令，并把自 身的信息发送给网络模块，以达到监控的目的。 ( 8 )球员协作模块：针对其它球员传送过来的信息进行综合分析，以达到 协作完成某一具体任务的目的。 r o b o c u p 中型组机器人控制程序采用多线程机制。本系统主要有两个线程： 球员线程与决策线程。这两个线程通过信号量实现同步关系。球员线程的运行一 个周期后，设置决策信号量有效，决策线程检测到决策信号量后开始运行，决策 1 0 线程运行一个周期后，设置球员信号量有效，然后球员线程检测到球员信号量有 效后开始第二个周期的运行，周而复始，直至比赛结束。 2 1 4 r o b o o u p 中型组比赛环境 从r o b o c u p 中型组比赛状况来看，r o b o c u p 中型组比赛环境具有以下特性： ( 1 ) 动态性。足球比赛是一个动态的过程，比赛中双方的机器人都在不断 的运动并实施自己的比赛策略，任务环境是不断进行实时变化的。 ( 2 ) 高度对抗性。机器人足球比赛是两支参赛机器人球队进行高度对抗的 活动，比赛时各机器人间产生碰撞、对抗都是不可避免的。因此必定 会促使比赛环境发生不可预知的变化。 ( 3 )不确定性。由于环境的动态变化以及比赛时复杂环境中的噪声对信息 识别与传递的干扰造成了比赛环境的不确定性。 正是r o b o c u p 中型组比赛环境的这些特性，使其在多机器人协作研究中具有 不可比拟的优越性【”】： ( 1 ) 实时。r o b o c u p 中型组比赛要求机器人必须实时地对环境做出反应。 ( 2 ) 策略。好的策略可以使机器人的协作在比赛中明显的体现出来，获得 更好的比赛成绩。 ( 3 ) 协作。协作的好坏不但直接影响到比赛成绩，而且为了提高r o b o c u p 中型组比赛的技术水平，从2 0 0 9 年起的比赛规则中规定，定位球的发 球必须要由机器人协作配合实现，否则视为犯规，可见协作策略在机 器人足球比赛中至关重要。 、 ( 4 )通信。由于比赛时场上的通信环境复杂，不够流畅的通信将直接影响 机器人的协作。故r o b o c u p 中型组比赛作为一个通信方式的测试平台 可以很好的反应出通信方式的优劣。 ( 5 ) 评价。r o b o c u p 中型组比赛环境是验证分布自治多机器人系统的最佳 平台。 本文将从动态阵型选择开始分析，然后再对应每个机器人分配角色，再针对 每个机器人提出一种全局的避障方式。 2 2 r o b o c u p 中型组比赛协作策略 机器人协作策略的设计必须考虑协作策略的实时性及其智能性之间的协调问 题。实用的协作策略既要充分结合集中式的优点，同时也要囊括分布式结构的优 点。在此基础上根据特定的情况进行有针对性的设计。基于此，受实际足球赛的 启发本章设计了一套适用于r o b o c u p 中型组的协作策略，从阵型的选择入手，构 造一个整体协作框架；再根据相应的阵型对角色进行合理的分配；最后设计了一 种基于全局形势的避障策略。协作策略算法将在第四章进行详细介绍。 2 2 1动态阵型选择策略 之前有不少参赛队伍使用静态阵型选择6 儿1 7 l ，这种阵型选择策略灵活性较差， 在场上形势多变时将无法应对。针对r o b o c u p 中型组比赛的特殊环境所设计的多 机器人协作策略的关键在于要有能适应局势变化的协作模型【1 明9 1 。其中协作框架的 确定又是协作模型研究的前提伫0 1 呤。而阵型之所以是r o b o c u p 比赛中的一个重要 概念，就是因为它是机器人足球比赛中协作策略的一个协作框架。在比赛中，一 般将阵型看作是对环境中智能体进行角色分配的方案，即一种协作模型。机器人 可以通过阵型提供的信息来预测己方其它机器人的位置、动作等情况，并依照自 己所被分配的角色和任务根据环境的变化做出决策。 将影响每个机器人做出决策选择相应阵型的因素伫2 1 定义为阵型因子 ( f o r m a t i o ne l e m e n t ) ，每个阵型由8 种阵型因子组成，分别为： ( 1 )阵形编号标识f n ； ( 2 ) 队员编号标识r n = i ( f = 1 , 2 1 1 ) ； ( 3 )球员角色r a ； ( 4 ) 队员初始坐标r i = ( 一，咒) ； ( 5 )球对球员的吸引因子觥e ； ( 6 )对方球员对球员吸引因子r r e ； ( 7 )比分形势因子s e ； ( 8 ) 球员坐标变化的上、下限值，和。 2 2 1 1动态阵型选择策略 机器人之间要实现协作，必须首先完成相互之间的通讯。在动态选择阵型算法 1 2 中，机器人通讯交流的信息主要有以下几个方面： ( 1 )是否申请改变阵型； ( 2 ) 是否投标( 向所有机器人发送自己经计算后得出的是否改变阵型的意 见) ； ( 3 )自己所选择的最优