（精密仪器及机械专业论文）足球机器人局势预测及路径规划算法研究(精密仪器及机械专业优秀论文).pdf

摘要 本文主要介绍了对足球机器人路径规划算法和局势预测算法所进行的研究 工作。 机器人足球比赛的环境是高度动态的，如何在比赛环境中规划出一条安全、 高效的路径是本文研究的重点之一。本文对几种常用的路径规划算法进行了研 究，并分析了各算法的优缺点，重点分拆了基于a 丰算法和基于遗传算法的路径 规划，并进行了仿真实验，然后在现有的机器人平台上进行了实验。 在采用基于a 木算法的路径规划算法中，首先对比赛环境进行栅格法建模，然 后利用胁算法进行搜索，首先利用斛算法搜索到一些可行的粗糙路径，即各个 可行栅格的链接，然后结合机器人的特性，对路径进行优化，最后得到的是一条 平滑、安全、最短的路径。 在利用遗传算法进行路径规划时，基本步骤与基于胁算法基本相同，建模采 用路径点链接图的方法，建模完成后，采用遗传算法进行搜索，搜索出路径后， 然后对路径进行优化，最终得到一条最优路径。 另外，由于足球机器人是一个多机器人环境，本文采用了集中式的路径协调 规划方法，按照任务的优先级，对各个机器人进行路径规划。 文章的另一重点是局势预测算法研究，由于足球机器人系统的固有特性，视 觉系统返回的信息与当前场上的信息存在一定的延时，为了降低延时的影响，必 须对机器人和球将来的运动进行预测。文章主要研究了基于k a l m a n 滤波和基于 神经网络的局势预测，并在现有平台上进行了实验。另外还对基于定性行为描述 的预测算法进行了简单的介绍。 关键词：足球机器人路径规划局势预测遗传算法胁算法神经网络 k a l m a n 滤波 a b s t r a c t t h i sp a p e ri sf o c 璐e do nr e s e a r c ho fp a t hp l a n n i n ga l g o r i t h ma n ds i t u a t i o n p r e d i c t i n ga l g o r i t h mo f s m a l l - s i z er o b o c u p r o b o t n l ee n v i r o n m e n to ft h er o b o t i cs o c c e rc o m p e t i t i o ni sd y n a m i c h o wt og e ta n o n - o b s t a c l ea n ds h o r t e s tp a t hf o rt h er o b o ti st h ef o c a lp o i n to ft h er e s e a r c h f i r s t l y , t h ec o m m o na l g o r i t h m so f p a t hp l a n n i n gi sd i s c u s s e d , t h ea d v a n t a g ea n dd i s a d v a n t a g e o fe a c ha l g o r i t h mm m l y z e d t h er e s e a r c ho fp a t hp l a n n i n gi sf o c u s e do nt h e a l g o r i t h m sb a s e do na - s t a ra n dg e n e t i ca l g o r i t h m ，t h et w oa p p r o a c h e si se v a l u a t e do n o u rs i m u l a t i o np l a t f o r m ，a l s oe v a l u a t et h et w 0a p p r o a c h e so nt h er e a l i t yr o b o t s w h e nu s ea - s t a ra l g o r i t h md o e st h ep a t hp l a n n i n g , t h ef i r s ts t e pi sm o d e l i n go f t h ee n v i r o n m e n t ，i nt h i ss t e p ，t h ee n v i r o n m e n td e c o m p o s e di ng i r d s s u b s e q u e n t l y , u s e a - s t a ra l g o r i t h mt of r e daf e a s i b l ep a t hf o rt h er o b o t mp a t hf i r s tg e ti sn o tt h eb e 吼 w en e e dc o m b m e o u rr o b o t sc a p a b i l i t ya n dt h e no p t i m i z et h ep a t hp o t s ，f i n a l l ya s m o o t h n e s s ，s e c u r i t ya n ds h o r t e s tp a t hg e t t h es t e pi ss i m i l a rt ot h ea a l g o r i t h mw h e ng a a l g o r i t h mi su s e d ，t h ed i f f e r e n c e i st h em e t h o do f e n v i r o n m e n tm o d e l i n ga n d p a t hs e a r c h am o d e l i n gm e t h o db a s e do n p a t h - p o tl i n kg r a p hw h i c hl i n k st h ep a t hp e t st o g e t h e ri su s e d s u b s e q u e n t l y , g ai s u s e dt of i n dt r a n s i t a b l ep a t h - p o t s o p t i m i z a t i o no f t h ep a t hp o t sa r en e e d e dt o ow h e na p a s s a i cp a t hf o u n d a l s oau s e m lp a t hc a nb eg o tf i n a l l y a sw ek n o w , ar o b o t i cs o c c e rt e a mh a sf i v er o b o t s ，s ot h e c o m p e t i t i o ni s a m u l t i - r o b o t se n v i r o n m e n t ，h o wt op l a nf i v er o b o t s p a t h s ? i nt h i sp a p e r ，am e t h o d c a l l e dc e n t r a l i z e dc o o r d i n a t e dp l a n n i n gw a sa d o p t e d ，w h i c hp l a n se a c hr o b o t sp a t h t h r o u g ht h et a s k sp r i o r i t yo f t h er o b o t s i t u a t i o np r e d i c t i n ga l g o r i t h mr e s e a r c hi sa n o t h e ri m p o r t a n tp a r to ft h i sp a p e r w e c a l lt h et i m ee l a p s e db e t w e e nm a k i n ga na c t i o nb ya is y s t e ma n dp e r c e i v i n gt h e c o m e q 啪c e so ft h a ta c t i o nb yv i s i o ns y s t e mi nt h ee n v i r o n m e n ti sc o n t r o ld e l a y i n o r d e rt or e d u c et h ee f f e c t so f t h es y s t e mi m m a n e n tc o n t r o ld e l a y , s i t u a t i o np r e d i c t i n g o ft h eg a m ef i e l di sn e e d e d m e t h o d sb a s e do nk a l m a nf i l t e ra n dn e u r a ln e t w o r ki s i n t r o d u c e di nt h i ss e c t i o n ，a l s oaa e wm e t h o db a s eo nq u a l i t a t i v em o t i o nd e s c r i p t i o n i ss i m p l yi n t r o d u c e d k e y w o r d s ：r o b o t i cs o c c e r , p a t hp l a n n i n g ，s i t u a t i o np r e d i c t i n g ，g e n e t i ca l g o r i t h m ， a + a l g o r i t h m ，n e u r a ln e t w o r k ，k a l m e nf i l t e r n 中国科学技术大学硕士学位论文 第一章足球机器人系统介绍 机器人技术是集运动学与动力学、机械设计与制造技术、计算机硬件与软件 技术、传感器技术、人工智能理论等诸多科学及技术于身的- - f 7 综合技术， 是“机电一体化”技术的典型代表。机器人技术的研究与发展可反映出一个国 家的经济和科技综合实力，机器人在各个领域的应用与普及，则可体现出一个 国家工业技术的发展水平。 1 1 机器人足球比赛介绍及其研究意义 1 9 9 2 年，加拿大大不列颠哥伦比亚教授a l a nm a c k w o r t h 在一次国际人工智 能会议上首次提出让机器人踢足球，其目的是通过机器人足球比赛，为人工智 能和智能机器人学科的发展提供一个具有标志性和挑战性的课题。此想法一提 出，就得到了各国科学家的普遍赞同和积极响应。世界诸多高校度重视，纷纷 派队参加比赛，比赛的种类也不断扩大，从最初的软件仿真比赛到2 0 0 0 年出现 了双足机器人踢球表演，直到今天的从仿真到真实机器人多种级别的比赛。机 器人足球发展的宏伟目标是力争到2 0 5 0 年，一支全部由人形足球机器人组成的 球队按照国际足联( f i f a ) 的规则与那当时的世界冠军队进行比赛，并且战胜这 支人类的冠军队。 机器人足球赛是由硬件或仿真机器人进行的足球赛，比赛规则与人类正规 的足球赛类似。目前，举办足球机器人比赛的国际组织有两个：机器人足球世 界杯( r o b o c u p ) 和国际机器人足球联合会( f i r a ) 。 其中r o b o c u p 机器人足球世界杯赛及学术大会( t h er o b o tw o r l d , u ps o c c e r g a m e sa n dc o n f e r e n c e s ) 是国际上级别最高、规模最大、影响最广泛的机器人 足球赛事和学术会议，每年举办一次。其比赛项目主要有：s i m u l a t i o n l e a g u e ( 仿 真组，又分为仿真2 d 和3 d ) 、s m a l i s i z el e a g u e ( f - 1 8 0 ) ( 小型组) 、m i d d l e - s i z e l e a g u e ( f 2 0 0 0 ) ( 中型组) 、s o n yl e g g e dr o b o tl e a g u e ( 四腿组) 和h u m a n o i d s l e a g u e ( 类人组) 5 种 r o b o c u p 机器人足球赛最重要的目的是推动各相关学科尤其是人工智能的 发展，检验信息自动化前沿研究一一特别是多智能体系统( m u l t i - - a g e n t s y s t e m ) 研究的最新成果，交流新思想和新进展。虽然机器人足球只有短短几 年历史，但在推动产、学、研结合方面的作用显著作且潜力巨大。因而r o b o c u p 机器人足球世界杯赛和学术大会受到了世界各国、特别是美、日、德等发达国 家的高度重视。 中国科学技术大学硕士学位论文 i 2 r o b o c u p 小型组国内外研究概况 小型组比赛是r o b o c u p 机器人足球世界杯赛的主要项目之一，自1 9 9 7 年第 一届r o b o c u p 比赛开始即是正式比赛项目。小型组主要研究在动态环境下使用 集中或者分布式的系统如何控制多智能体以及完成它们的协作，是多智能体集 中控制方法的良好的测试平台，具有典型的研究意义，其中涉及到视觉信息处 理，无线通讯，实时规划与决策控制等技术。 小型组的比赛在两支各有5 个机器人的队伍中进行。每个机器人的尺寸必 须能放进一个直径为1 8 0 n m 的圆筒，因此小型组也称作f - 1 8 0 组。小型组机器 人高度不能超过1 5 0 m m ，除非使用局部视觉系统( 即每个机器人都有各自的视觉 系统) 。比赛在5 0 0 0 m mx3 5 0 0 m m ( 2 0 0 7 年规则) 的铺有绿色地毯的场地上进行， 比赛用球是一个桔黄色的高尔夫球。 图l - 1 小型组比赛图片 在比赛过程中双方的参赛人员不能干预比赛，机器人足球队必须通过自身 的人工智能程序完全自主的理解和执行裁判的判罚。足球机器人必须自主的完 成发边界球、死球后的重新开球、球门球、角球、任意球、点球等复杂的球队 整体战术。 足球机器人比赛中双方对抗激烈、赛场情况瞬间万变。要想取得胜利，机 器人足球队必须拥有高度的智能，能够感知场上局势并能根据局势的变化迅速 和准确做出反应。而且，机器人足球队需要有足够的智能来进行各个队员之间 的相互配合，从而执行整体战术。这些都是当今世界人工智能领域的尖端问题， 它在工业自动化和国防等领域中有着重要的应用。 目前，美国、德国在小型组足球机器人研究方面处于世界领先水平。尤其 是美国的康奈尔( c o r n e l l ) 大学一直引领着小型组机器人的发展方向，他们将四 轮全向机构引入到小型组机器人的机构设计中，使机器人灵活性、稳定性显著 增强，其他小型者机器人的研究者们纷纷效仿。另外，康奈尔大学研制的机器 人已经由集控式决策转向分布式决策，这一技术的采用势必将小型组机器人的 2 中国科学技术大学硕士学位论文 研究推向一个新的高度。卡内基梅隆大学小型组的图像处理技术一直处于该领 域的前沿，现在大多数小型组机器人队采用的色标设计方法就是由卡内基梅隆 大学提出的，他们所研制的机器人在2 0 0 6 世界杯上获得了冠军。另外，德国的 f u f i g h t e r ，新加坡的l u c k s t a r 等都是小型组足球机器人领域的佼佼者。中国 的小型组足球就研究虽然起步较晚，但是发展比较迅速，中国科大在这方面取 得了不错得成绩，在国内处于领先水平，另外浙江大学在近几年也取得了很大 的进步。但是，国内的水平和国际领先水平仍然存在很大的差距。 1 3 本文研究内容概述 文章所述的研究工作对象是中国科大蓝鹰小型组机器人足球队，重点研究 了机器人的路径规划算法和局势预测算法，研究内容如下： ( 1 ) 系统分析和研究了足球机器人系统的体系结构及相关技术，了解了足 球机器人系统运行平台的环境特性和机器人小车的性能特征，为本文进行足球 机器人路径规划研究奠定必备的基础。 ( 2 ) 对目前应用于足球机器人路径规划的常用方法进行了研究和分析，讨 论了它们在足球机器人系统中的应用的可行性。 ( 3 ) 根据足球机器人系统环境模型的特点，对遗传算法和胁算法的路径规划 方法进行了研究，考虑到效率问题，确定使用胁算法进行路径规划。设计了基 于胁算法的路径规划程序，并在仿真平台上进行了验证。最后在实际比赛平台 验证了该方法的有效性。 ( 4 ) 局势预测算法研究，对卡尔曼滤波、神经网络算法进行了研究，阐述了 这两种方法的基本思想并进行了仿真试验，在这一部分的最后简单介绍了基于 定性场景描述的局势预测算法的基本思想。 以下为各章内容安排： 第一章介绍了r o b o c u p 小型组机器人的研究背景，意义。介绍了本队的研 究工作以及本文所述的研究工作在全系统中的位置和意义。 第二章是本文研究对象的四轮足球机器人系统概述，包括足球机器人各个 子系统的简单介绍，并介绍了整个系统的工作流程。 第三章对常用的路径规划算法进行了研究，对这些算法的基本思想进行了 阐述，并对各个算法的优缺点进行了简单评价。 第四章、第五章是本文的核心部分。第四章详细介绍了遗传算法的基本原 理、基本步骤，并在仿真平台上对算法进行了仿真试验；第五章详细介绍了a 宰 算法的基本原理及基本步骤，并介绍了集中式协调机制在多机器人路径规划中 的应用，最后在仿真平台上对算法进行了仿真验证。 中田科学技术大学硕士学位论文 第六章是本文另一个重要部分，主要研究机器人比赛中比赛场上的预测算 法，分别对卡尔曼滤波、神经网络等局势算法进行了研究，并对基于定性运动 场景描述的预测算法进行了简单介绍。 最后，第七章对本文研究工作进行了总结，对未来的研究工作做了进一步 的展望。 4 中国科学技术大学硕士学位论文 2 1 引言 第二章足球机器人系统介绍 随着机器人技术的发展，近年来在智能机器人技术领域兴起了多智能体的研 究方向，它的研究内容包括：群体协作、任务规划、多传感器融合、群体路径 规划等等。足球机器人是智能机器人技术研究的典型平台，它涉及机器人、智 能控制、数据融合、计算机技术、数字通讯、图象处理、机构学、运动学、人 工智能等多个领域，涵盖了所有机器人技术所涉及到的知识领域。在机器人足 球比赛中，不仅需要单个机器人有良好的带球、射门、截球等技巧，更重要的 是需要各个机器人之间能相互配合，共同完成任务。因此，足球机器人比赛是 推动多智能体( m u l t i a g e n t ) 技术发展的一个重要手段，足球机器人系统也是多 智能体系统( m a s ) 的一个良好实验平台。 2 2 机器人足球系统介绍 小型足球机器入系统包括：视觉、决策、无线通讯以及机器人车体四个子系 统。各子系统之间的相互关系见图2 1 。各个子系统的功能简要介绍如下： 视觉子系统在比赛时获得比赛场上的信息( 球和机器人的速度、方向、 位置，以及场地大小，球门位置，颜色等附属信息) ，并将处理过的信息转发给 决策系统 决策子系统是整个系统的核心部分，其主要实现的功能：信息预测处理、 多机器人运动协调、机器人角色任务分配执行、机器人路径规划、机器人运动 控制。 无线通信系统是决策系统和小车子系统连接的纽带，决策系统通过无线 通信系统向小车子系统发送控制命令，以使机器人按照决策系统的意图动作， 从而完成比赛。 小车子系统包括机械的机械结构本体，底层控制电路，底层控制软件。 比赛双方各拥有五个足球机器人。五个机器人在场上具有各自的角色，当然 每个机器人的角色不是固定的，丽是根据场上的形势来分配每个机器人的角色。 比赛中，根据场上的局势，五个机器人在决策系统的控制下，相互配合，完成 给定的任务。 5 中国科学技术大学硕士学位论文 图2 1 机器人足球队系统总体框图 图2 - 1 为机器人足球队系统构成及工作流程图。比赛中，整个系统按照如 下流程工作： 1 比赛时，悬挂于赛场上方的两个摄像机将比赛场地上的信息采集下来输 送给计算机内的图像处理子系统。 2 计算机内的图像处理子系统通过对球场图像信息进行处理，得到本方球 员、对方球员以及球的位置、速度、方向等信息以及一些附属信息。 3 这些信息通过一个s e r v e r 发送给决策系统，决策系统通过对这些信息 进行分析、处理后，根据分析的结果对当前比赛场上的形势进行评估并 从战术库中获得相应的战术，根据球队战术的要求为每一个机器人分配 “任务”，并为每个机器人生成其运动路径。除了生成机器人的路径， 还需要对机器人进行运动控制，以便最快最好的按照生成的路径运动， 并进一步执行决策分配的任务，通过运动控制算法得到了机器人的速度 和带球、击球和挑球等相关指令，最后通过无线通讯系统发送给各个足 球机器人。 4 每个足球机器人通过自身装备的无线通讯模块接收决策系统发给的指 令，小车系统内的控制子系统对这些指令进行解析后得到各个电机的转 速，并通过相应的底层控制算法来达到指定的速度，并执行相应的击球、 带球、挑球等动作。 6 中国科学技术大学硕士学位论文 下图为小型比赛时的场景示意图。 图2 - 2r o b o c u p 小型组机器人足球比赛场景示意图 可以看出，整个系统是一个闭环，图像部分不停的获得新的信息，而决策 部分则由这些新的信息生成相应的新的控制指令，然后机器人按照新的指令运 动，如此周而复始的运行，完成比赛。 2 3 视觉系统介绍 视觉系统主要由悬挂在比赛场地上方的摄像头( 或者摄像机) 、图像采集卡、 图像处理软件、网络服务器主机端组成。视觉系统的主要职责是采集比赛上的 有用信息，如：双方机器人和球的位置、速度、方向，球场边界、球门位置等 信息，这些信息将通过网路发送给决策，决策系统将依据这些信息对场上的形 势进行分析处理。 2 4 决策控制系统介绍 决策控制系统是一个多智能体系统( m u i t i - a g e n ts y s t e m ) 的协调控制系统。 它的主要功能是场上信息( 包括球，己方和对方的机器人) 的行为预测、攻防 策略选择、整体战术安排、机器人任务分配和指定、路径规划，运动控制等。 按照上述功能，决策控制部分采用分层控制处理结构，主要包括：信息预 测处理层、多智能体( 姒s ) 协调策略层、角色任务分配执行层、机器人路径规划、 机器人运动控制5 大部分，如图2 3 所示： 7 中国科学技术大学硕士学位论文 图2 - 3 决策系统框架 信息处理部分；处理场上基本信息，由于整个机器人系统运作过程中会产 生信息传递延时，视觉信息不能真实的反映当前机器人和球的位置坐标和方向， 需要对位置信息进行预测，以减小系统延迟造成的误差，最终得出综合信息供 后续决策使用。一般采用的办法有扩展卡尔曼滤波、线性模型、b p 神经网络等 方法。这一部分是本文讨论的问题之一。 局势分析及战术安排部分：一段时间内或者有一定目的的机器人队伍整体 决策称为战术。在执行每一个战术时，每个机器人都会分配到不同的任务，并 且每个战术都有它的应用条件，通过战术选择算法在比赛中决策系统能自适应 对手进行战术选择，对任何对手都能以最高效率进行比赛。这部分的主要功能 就是根据信息处理部分提供的信息，从战术库中选择有利于我方的战术。 角色分配部分：根据选择的战术，产生一个角色分配表，并将角色表中的 角色分配给各个机器人，同时根据给定的角色分配机器人的具体动作与目标位 置。 路径规划及运动控制、控制指令生成部分：根据分配的具体任务，按照一 定的算法生成各个机器人的路径，使机器人可以沿着这条路径以最快的时间安 8 中国科学技术大学硕士学位论文 全的到达目标点。常用的路径规划算法有：人工势场法，d e l a u n a y 三角法，几 何方法，随机扩展搜索算法等，这也是本文讨论的重点之一。完成路径规划之 后，还需要根据机器人的特性控制机器人运动。采用基于时自j 最有的b a n g b a n g 控制算法实现机器人的运动控制。： 最后，决策系统生成机器人的运动指令，通过无线通信子系统发送给机器人。 为了使决策程序的开发能不受其他子系统的进度影响，有必要开发一个能 模拟真实比赛情况的仿真软件，对机械，视觉，通讯部分都进行真实的模拟。 仿真平台具有以下功能： 1 机器人运动学特性及机器人的功能( 击球、带球、挑球等) 仿真 2 视觉系统仿真 3 无线通讯仿真 4 模拟裁判，对仿真过程进行简单的控制 具有了以上功能，仿真平台就完全可以脱离硬件来对决策程序进行仿真， 在仿真过程中加入一些调试信息即可不断的对决策程序改进。后面介绍的路径 规划，局势预测都是在这个仿真平台上实现的。图2 - 4 是我们所使用的仿真平 台的界面。 图2 - 4 决策系统仿真平台 9 中国科学技术大学硕士学位论文 2 5 无线通讯系统介绍 在小型足球机器人系统当中，无线通讯系统是衔接决策和机器人之间的纽 带，它负责将决策系统生成的指令发送给场上我方的机器人。是整个足球机器 人系统不可缺少的一环。无线通讯部分采用计算机串口和无线通讯系统接口， 原因是通过计算机串口传送数据非常方便且简单，目前我们传送的指令只有速 度指令及击球、挑球的指令，单位时间内传送的数据量很小，串口的数据吞吐 量已经能很好的完成指令的转发了，实际中的应用也证明了这一点。当然，随 着以后的小型组技术的发展，如果实现分布式决策的话，通信的数据量将增大， 通过网络转发数据将是首选。 2 6 足球机器人底层控制系统介绍 机器人在接收到指令之后，需要执行决策指令以完成相应的任务，这一部 工作就是由底层控制系统完成的。如图2 5 所示： 图2 - 5 底层控制系统结构图 主d s p 通过s p i 口从无线通信模块接收决策系统的控制指令，然后通过s c i 转发给从d s p ，另外，由于从机的q e p 接口有限，主机还负责对两个驱动电机的 码盘信号的读取，并转发给从机。为了协调主从d s p ，用了两根i o 线作为主从 d s p 之间的握手信号。通过这两根i o 线，主d s p 便知道什么时候可以发送控制 指令，什么时候可以发送码盘读数。 从d s p 在接收到控制命令后，需要对命令进行解析，对相关参数进行转化。 然后，将机器人的整体速度值经过速度矢量分解环节分解到各组驱动轮上，作 1 0 中嗣科学技术大学硕士学位论文 为各驱动轮的转速控制量。 如果控制指令中有击球指令或者挑球指令，从d s p 还需要通过1 0 控制升压 模块，来打开击球或者挑球电磁铁，为了安全起见，加入了互锁电路，达到不 能同时开击球和挑球电磁铁的目的。 球检测模块的作用是对机器人当前是否在带球进行检测，其他一些辅助电 路在这里就不在赘述。 2 7 机械结构介绍 1 、机器入总体结构( 除去外壳) 图2 _ 6 足球机器人总体结构图 图2 - 6 是我们现在所采用四轮全向足球机器底盘结构。它具有特殊的驱动 轮设计及其布置方式，具备平面上的全自由度运动能力。机器人总体结构从上 往下分为三部分：最上部分是上色标板，用于机器人视觉系统的识别机器人位 置、方向及编号；中间安装的是控制电路板；最下面是机器人的机构部分，其 主要由车体底盘、驱动机构、带球机构、击挑球机构组成。 足球机器人之所以能全向运动在于它特殊的驱动轮布置方式和驱动轮机 构。足球机器人的驱动轮机构是圆形大轮的圆周上密布小滚动轮子构成，整个 驱动轮可以沿周向与轴向两个方向做滚动，通过各驱动轮的速度矢量合成，机 器人可以在平面上实现全自由度运动。 比赛规则规定，带球机构与球面的接触面积不得超过球面面积的1 3 。顺时 针高速旋转的带球棍依靠摩擦力带动小球做逆时针旋转，小球受到的地面的摩 l l 中翻科学技术大学硕士学位论文 擦力与带球棍的摩擦力的合力指向机器人本体，当足球机器人前进、后退、转 弯时，小球始终在带球滚轮的带动下跟着足球机器人运动，图2 - 7 为带球机构 简图。 图2 7 带球机构简图 带球一直是机械部分的一个问题，滚轮的材料( 粘性、硬度) ，滚轮的转速 很大程度上影响的带球的能力，由于带球机构的体积限制，电机的尺寸受到了 限。转速的提升和电机的输出的力矩的增大都对带球有利，但不幸的是在电机 尺寸受到限制的情况下，这两点往往是矛盾的。在我们的设计中，采用了悬挂 可调的带球机构，带球机构的位置可以上下调整，在不同的场地比赛时根据地 面摩擦力不同来调整带球杆的位置以达到最佳的带球效果。 击挑球结构在足球机器人比赛中的重要性是不言而喻的，击挑球机构是完成 射门和传球的关键机构。目前的击球方式大致有以下几种：弹簧储能击球、齿 轮齿条击球、气动击球、弓弩式击球、电磁铁击球。 现在我们采用的是电磁铁击球机构，它的优点是力量大，动作频率高，反 应速度快，机械机构相对简单可靠。设计中采用2 0 0 v 左右的电压驱动电磁铁来 击球，利用电磁铁将存储在电容中巨大的能量释放出来传递给球，可以使球的 速度达到1 0 m s 左右，并且能通过控制放电时间来控制出球的速度和距离。因 此，可以使用电磁铁击挑球机构来实现不同力度的“传球”或“射门”。 相比电磁铁击球机构而言，其他机构都有明显的缺点：弹簧储能击球在击 球之前需通过电机将弹簧压缩储能，击球时弹簧瞬间释放能量，其缺点是机构 繁琐，占用空间较大，动作频率比较低；而气动或弓弩式击球机构设计制造复 杂，体积也很大，稳定性不好。 2 8 小结 本章简要介绍了足球机器人系统的各个子系统的功能，各个子系统的有机 结合组成了足球机器人这个多智能体平台。虽然这几个系统缺一不可，但通信， 小车子系统的技术相对比较成熟，因此决策和图像也就成为了r o b o c u p 小型组 机器人技术的组研究重点，尤其是决策系统，是人工智能的具体体现，本文的 后续部分对其中的部分相关技术进行研究。 中国科学技术大学硕士学位论文 第三章常用路径规划算法介绍 3 1 机器人路径规划算法研究综述 路径规划就是在一定的环境中给定初始位置和目标位置，按一定的策略使运 动物体从初始位置无碰撞地到达目标位置，并满足一些约束条件。路径规划技 术的应用非常广泛，不管是关节型机器人还是移动型机器入，采用路径规划技 术可以使机器人更快更安全的完成任务，这对节约工时，降低成本，提高系统 的安全性都有重要意义，同时也是机器人具有智能的体现。足球机器人作为多 智能体的典型平台，其各项技术在机器人领域都具有典型的代表型，基于此， 本文对足球机器人的路径规划方法进行了研究。 路径规划是足球机器人系统中研究的一个重要课题，其重要性主要体现在： a 在足球机器人比赛中，实时性要求十分高，在决策系统分配任务后，机 器人如何在最短时间内到达目标地将对系统的实时性产生很大的影响。 b 比赛过程中，场上的环境是时刻变化的，其路径规划属于高动态未知环 境下的路径规划及轨迹控制，在这样的平台上研究的路径规划方法可以应用到 其他机器人应用环境中，完成有实际意义的任务。另外，如何在这样一个高度 实时性和竞争性平台上研究路径规划，规划出每个机器人的运动路线，让每个 队员很有策略地行动、配合，完成系统制定任务是足球机器人研究中非常有挑 战性的方向之一。 c 在比赛规则中，已经严格限制了与对方机器入的接触，如果机器入在比 赛上随意冲撞对方的机器人，将会被视为犯规，就比赛本身来讲，也凸现出了 路径规划的重要性。 随着科技的发展和人类探索领域的不断拓宽，机器入的应用范围将不断扩 大，因此对机器人的性能要求也不断地提高，自主自治将是未来机器人的主要 特点，另外，在动态、实时性要求较高、未知的环境中对机器人路径进行规划 是目前机器人路径规划研究的主要方向。足球机器入系统环境是一个很典型的 具有动态性、不确定性、实时性的环境，机器人足球的环境正好符合当前机器 人路径规划的研究方向。这也是本文选择足球机器人路径规划问题的意义所在。 目前研究的机器人路径规划方法主要有：基于格点的算法，人工势场法， d e l a u n a y 三角法，几何方法，随机扩展搜索算法等。本文在足球机器人这一多 智能体系统的典型平台上对路径规划问题进行了的研究和分析，比较了各种算 法在实时坏境中的效果。在这些算法中寻找行之有效的算法是研究的最终目标。 本章将介绍几种常用的路径规划方法，为后续章节的研究奠定了一定的基 中国科学技术大学硕士学位论文 础，并分析了各方法的优缺点。 3 2 栅格法路径规划 栅格法是由w eh o w d e n 在1 9 6 8 年提出的。他在进行路径规划时采用了栅 格( g r i d ) 表示地图，在处理障碍物的边界时，避免了复杂的计算。h o w d e n 在 其算法中对路径规划问题做了很多简化，其思想和算法是后来诸多规划问题算 法的基本思想，它给出了全局路径规划问题的一般步骤： 第一步：划分空间 第二步：形成包含划分信息的网络 第三步：在网络上进行搜索 栅格法( g r i d s ) 是一种将工作环境离散化的方法，目前研究较广泛的路径规划 方法。该方法将机器人的工作空间解耦为多个简单的区域，一般称为栅格。若 某一个栅格范围内不包含任何障碍物，则称此栅格为自由栅格；反之，称为障 碍栅格。由这些栅格构成了一个连通图，在这个连通图上搜索一条从起始栅格 到目标栅格的路径，该路径均由自由栅格构成，用栅格的序号来表示。最后把 栅格序号转换成机器人空间的实际坐标，便构成了一条机器人运动的可行路径。 3 2 1 利用栅格法进行路径规划 采用栅格法进行机器人路径规划可以分为以下三个主要步骤： 1 建立模型 首先根据机器人和目标点的位置划定规划区域，然后将该区域用网格表示， 每个网格就是一个栅格。在机器人移动过程中，栅格的大小和位置不变。栅格 的大小是个关键因素，栅格选得小，环境分辨率较大，但抗干扰能力弱，需要 的存储量大，决策速度慢；栅格选得大，抗干扰能力强，需要的存储量小，决 策速度快，但分辨率下降，在密集障碍物环境中发现路径的能力减弱。一般栅 格大小的选取和机器人的基本移动步长相适应，机器人移动转化成从一个自由 栅格移动到另一个自由栅格，机器人移动的路径长对应于机器人经过的栅格数。 最后对划分好的栅格编序号，栅格序号将代表栅格所在的位置，并给每个栅格 赋以一定的初值，通常为了计算方便，将栅格的值二值化。从模型的建立可以 看出，栅格法直观而且建模十分容易，这也是栅格法使用广泛的原因。 2 生成障碍物地图 模型建立以后，开始检测障碍物的位置，并根据障碍物位置找到对应栅格地 图中的序号值，并对对应的栅格值进行修改。为了计算简单，可以将栅格的初 值进行二值化处理，即有障碍物的栅格将其赋初值为0 ，对于没有障碍物的自由 1 4 中国科学技术大学硕士学位论文 栅格赋初值为l 。对所有栅格进行初始化后，障碍物地图便形成了。 3 搜索无碰路径 机器人路径规划就是寻找一条从出发点到目标点的连续自由栅格序列，实际 上这个问题类似于迷宫问题的求解，只不过传统的迷宫求解只关心是否能找到 一条通路，而并不关心通路的长短，但在机器人路径规划中，除了关心能否获 得解外，如何获得最优路径是最关心的问题。在栅格序列中，搜所出一条最优 路径的方法有很多，常用的搜索算法如：基于势场法的栅格路径搜索方法，基 于动态二又树的a 算法等等。 图3 1 用栅格法进行路径规划 3 2 2 栅格法基本流程 下面给出一种基于栅格法路径规划的基本流程： 1 ) 初始化。设置计数变量n u m l = o , n u m 2 = 0 ，定义初始障碍物地图矩阵 m a p ，( ，v ) n e x t p o t n u m l ，研孔8 i 】；系统相关参数和循环次数n ，m 。 2 ) 从起始点开始，按照路径选择概率p 决定下一个结点。 3 ) 若当前点p o t c u r r e n t 为目标点，则转至第( 4 ) 步；否则计算下一个可 行点的集合中某个节点的概率，据此选择p o tc u r r e n t 的下一个可行结 点。此步骤循环执行，直到选出目标结点。 4 ) n u m l = n u m 2 + 1 ，保存找到的可行路径。如果n u m l m ，则转至第( 2 ) 步；否则，从保存的路径中选择最优路径，依此，按照栅格的关联程度 修改障碍物地图中两个相邻结点之间的关联程度，n u m 2 ：n u m 2 + 1 5 ) 如果n u m 2 “ 其中；以，p 。的大小取决于机器人的尺寸、速度及环境中障碍物的稀疏程度等 因素。 以上考虑的是单个障碍物时机器人受到的控制力，对于多个障碍物可以采用 势场的叠加性质得到总的斥力场。 3 4 3 算法描述 可将势场法的动态路径分成以下几个步骤。 1 首先将起点到最终目标点连线上的点作为规划的子目标的予目标集( 子 目标集中的点把起点和终点的连线若干等分，每个点都是一个子目标) 。 2 将第一点作为子目标。在搜索路径的时候以一定的距离，作为半径。根据 势场的定义，如果障碍物距离机器人较远( 可以根据需要设定一个阙值) ，它对机 器人的影响可以忽略不记的。可以认为半径r 以外的障碍物对机器人的影响是非 常小的。如果当前的子目标的点在某个障碍物的内部。则子目标应该重新选取。 3 计算斥力场和引力场。 4 参考位姿的生成 5 重复第二步直至达到最后的终点。 3 4 4 势场法的优缺点 ( 1 ) 优点 a 结构简单，使用方便，需要的环境信息较少，计算量小，便于底层的实 时控制，这是势场法的一个最突出的特点 b 在进行运动规划时不仅考虑机器人的避障和轨迹规划，而且也考虑了机 器人的动态运动性能，规划出来的路径一般比较平滑并且安全。 ( 2 ) 缺点 a 是一种局部寻优方法，只着眼于得到一条能够避障的可行路径，对路径 是否最优并未加以考察。 2 l 中国科学技术大学硕士学位论文 b 对简单环境很有效，但对于复杂的多障碍物环境，不合理的势场数学方 程容易产生局部极值点，即在某点的势场合力为零，常出现的现象是在某点停 止而不能到达目标点，或者是在相近的障碍物群中不能识别路径。局部最小值 是人工势场法的最大缺陷 3 5 本章总结 本章介绍了几种常用的路径规划算法，当然还有很多路径规划算法，如： d e l a u l a y 三角形法、拓扑法等，也有两种甚至三种算法结合形成的算法。各种 算法都有自己的特点，这就需要我们针对具体问题选择合适的方法。在本文的 下两章，将介绍a 算法和遗传算法在足球机器人路径规划中的具体应用。 中国科学技术大学硕士学位论文 第四章基于遗传算法的足球机器人路径规划 4 1 遗传算法起源 2 0 世纪4 0 年代以来，科学家们不断努力从生物学中寻求用于计算机科学和 人工智能系统的新思想、新方法。6 0 年代末到7 0 年代初期，美国m i c h i g a n 大 学教授j o h nh h o l l a n d 与其同事、学生们研究形成的一个较完整的理论和方法， 从试图解释自然系统中生物的复杂适应过程入手，模拟生物进化的机制来构造 人工系统的模型。经过近3 0 年的发展，取得了事硕的应用成果和理论研究进展， 这个方法被称之为遗传算法( g e n e f i c a l g o f i t h m s 。g a ) ，是人工智能研究的一个 重要方向。 4 2 遗传算法的基本思想 遗传算法是一种基于自然选择和遗传变异等生物进化机制的全局性概率搜 索算法，与基于倒数的解析方法和其他启发式搜索方法( 如爬山方法，模拟退 火方法，m o n t ec a r l o 方法) 一样，其形式上也是一种迭代方法，它既是一种自 然进化系统的计算模型，也是一种通用的求解优化问题的适应性搜索方法。它 从选定的初始解出发，通过不断迭代逐步改进当前解，直至最后搜索到最优解 或满意解，迭代过程类似生物体的进化机制，从一组解( 群体) 出发，采用类 似于自然选择和有性繁殖的方式，在继承原有优良解的基础上，生成更好性能 指标的下一代解的群体。在每一代，根据问题域中个体的适应度( f i t n e s s ) 大小挑 选( s e l e c t ) 个体，并借助于自然遗传学的遗传算子( g e n e t i co p e r a t o r s ) 进行组合交叉 ( c r o s s o v e r ) 和变异( m u t a t i o n ) ，产生出代表新种群。这个过程将使后生代种群比前 代更加适应于环境，末代种群中的最优个体经过解码( d e c o d i n g ) ，可以作为问题 近似最优解。 遗传算法在进化过程中的遗传操作是随机性的，但它所表现出的特性不是完 全随机的，它能有效的利用历史信息来推测下一代期望性能有所提高的寻优点 集。一代一代的不断进化，最有收敛到一个最适应环境的个体上求的问题的最 有解或满意解，遗传算法涉及五大要素：参数编码、初始种群的产生、适应函 数的选取、遗传策略的设计和控制参数的选定。 4 3 基于遗传算法的足球机器人路径规划 利用遗传算法进行路径规划，主要包括以下四个主要问题： 1 路径个体的编码方式选择，即目标问题的实际表示与遗传算法的染色体 位串机构之间的关系确立。选择了合适的编码方式，才能将问题准确的有效的 2 3 中国科学技术大学硕士学位论文 用遗传算法的染色体来表示。虽然遗传算法具有很强的鲁棒性，对编码的要求 并不苛刻，但是，编码的策略或方法对遗传算子的功能和设计有很大的影响。 2 种群规模的选择：它直接影响的算法的效率和效果，种群规模大，收敛 全局解的可能性大，但是影响了收敛速度；种群规模小，收敛速度加快，但是 有可能不是全局最有解，而是局部的最有解，因此种群的规模选择必须适当。 3 ：遗传算子的选择：遗传算子的选择是否合理，将直接影响进化效果，因 此，如何设计高效的遗传算子是遗传成功应用的关键。 4 适应度函数选取：适应度函数是遗传算法进化的推导准则，适应度函数 越复杂，g a 进化到编码空间的最优解位串的过程就越缓慢，或者容易收敛到局 部最优位串，甚至成为模式欺骗问题。因此，如何选择适合问题求解的评价准 则，也是g a 的一个重要方面。 上面介绍了遗传算法中的四个重要方面，下面将详细介绍在利用遗传算法进 行足球机器人路径规划时这四个方面的具体考虑。 4 3 1 路径编码方法 在现实运动中，路径点是二维的，如何将问题的解转换为编