足球机器人路径规划的研究与实现-足球机器人毕业论文.doc

足球机器人毕业论文足球机器人毕业论文题 目：足球机器人路径规划的研究与实现专 业：自动化56摘要足球机器人系统是一个典型的多智能体系统，是一个实时动态的对抗性的复杂环境，它为人工智能技术的理论研究和模型测试提供了一个标准的实验平台。路径规划是智能机器人的一个重要研究课题，在这样一个具有高度实时性和竞争性的平台上研究路径规划是一个极具挑战性的课题。目前用于路径规划的方法很多，如人工势场法、中垂线法、栅格法、贝塞尔曲线法、可视图法及各种人工智能方法如遗传算法，神经网络等等。但这些方法在高度动态性和实时性环境中的研究还都存在些问题，有待进一步完善。本课题从静态环境中研究足球机器人的路径规划问题，全文主要包括如下内容：第一章 介绍了足球机器人的研究背景并在此基础上简单的介绍了足球机器人路径规划。第二章 具体分析了足球机器人系统、路径规划策略以及足球机器人环境模型等问题。第三章 分析了现今采用的路径规划典型算法：人工势场法、栅格法、中垂线法和遗传算法。第四章 在对各种算法进行综合分析的基础上，将遗传算法基于前人的基础上加入种群间的迁移并应用在本文的路径规划中。用matlab对遗传算法和人工势场法进行编程和仿真。最后，我们对全文内容进行总结。关键词：路径规划；足球机器人；遗传算法；人工势场；中垂线法AbstractSoccer robot system is a typical multi-agent system and real-time dynamic competitive environment, which provides a standard of experimental platform for the theoretical research of artificial intelligence technology and model test. Path planning is one of the most important research subjects in intelligent robot, and the research of path planning is a challenging task on the platform with highly real-time and competitive. Recently many methods are used in path-planning, such as artificial potential field, the perpendicular bisector method, the grid, Bessel method and view method and various artificial intelligence method such as genetic algorithms, neural networks, etc. But these methods have some problems in the height and the research dynamic real-time environment, they should be further improved. This subject mainly research soccer robot path planning problem from the static environment. The text mainly includes the following contents: The first chapter introduces the research background of the soccer robot, and on the basis of it brief introduction the soccer robot path planning. The second chapter analysis the problem such as the soccer robot system, the path planning strategy and the environmental model of soccer robot in detailed. The third chapter analysis the typical path planning algorithm used currently such as the artificial potential field method, grid method, the perpendicular bisector method and genetic algorithms.The fourth chapter, based on the analysis of the various algorithm, join the population migration in the genetic algorithm which is based on the basis of former in this path planning. the genetic algorithm and artificial potential field method are simulated and programmed by the MATLAB.Finally, we summarize the content of the whole text.Keywords: path-planning; soccer robot; genetic algorithm; the artificial potential field; perpendicular bisector method目 录摘要IAbstractII第一章 绪言11.1 研究背景11.1.1 机器人足球概述11.1.2 课题国内外研究现状21.1.3 足球机器人比赛的发展31.2 机器人足球路径规划概述41.2.1 足球机器人路径规划的描述41.2.2 足球机器人路径规划的41.2.3 足球机器人路径规划的特点41.2.4足球机器人路径规划的分类及现状5第二章 足球机器人系统62.1 足球机器人系统62.1.1 足球机器人体系结构62.1.2 视觉子系统62.1.3 决策子系统72.1.4 决策子系统模型72.1.5 通讯子系统92.1.6 小车子系统92.2 路径规划92.2.1 路径规划(底层决策)92.2.2 路径策略92.2.3 最优运动规划112.3 足球机器人系统环境模型122.3.1 球场模型122.3.2 机器人小车模型122.3.3球的运动学方程14第三章 足球机器人路径规划方法153.1 栅格法153.1.1 栅格法简介153.1.2栅格法进行路径规划163.2 人工势场法173.2.1 人工势场法简介173.3中垂线法183.4 遗传算法法193.4.1 遗传算法的简介193.4.2 遗传算法的特点203.4.3 遗传算法的基本原理213.5 对各种方法的综合评价28第四章 matlab 实现人工势场、遗传算法的仿真304.1 环境建模304.2 运动方程的建立314.3遗传算法的仿真实现324.3.1 初始种群设置324.3.2 障碍物的检测334.3.3 初始参数设置354.3.4适应度函数的选取364.3.5遗传操作的过程394.3.6遗传算法路径规划仿真与实现434.4人工势场法路径规划仿真与实现46第五章 总结53参考文献54致 谢56第一章 绪言1.1 研究背景1.1.1 机器人足球概述足球机器人属于第三代智能机器人。机器人足球比赛，是近年来在国际上迅速开展起来的高技术对抗活动，它是体育与高科技结合的产物，比赛融入了机器人学、机电一体化技术、通讯与计算机技术、机器人视觉与传感融合技术、决策与对策、智能控制等多学科高新技术。1992年加拿大哥伦比亚大学教授AlnaMacwkortnl在一次国际人工智能会议上首次提出机器人足球的思想，旨在推动人工智能学科的发展，为智能机器人提出了一个新的具有标志性和挑战性的课题。同时，机器人足球的倡导者则提出了他们新的梦想：在2050年，一个全自主的类人型机器人足球队，按照国际足联的规则，战胜当时的人类足球世界杯冠军队。这个梦想被看作是继1997年IBM公司研制的计算机深蓝（Deep Blue）战胜了国际象棋大师卡斯帕洛夫（Kasparov）之后的人工智能历史上又一个里程碑项目。目前国际上有组织的机器人足球比赛有两大系列FIRA和Robocup。FIRA是国际机器人足球协会联合会（FIRA-Federation of International Robot soccer），简称国际机器人足联，成立于1997年6月5日，总部设在韩国大田的韩国科学（技术）院（KAIST）。目前已有30余个国家的近百个学校与科研院所为其成员单位，主要分布在亚洲、澳洲、北美和南美洲等地。FIRA的比赛项目主要有：超微机器人足球比赛Narosot，微型机器人足球比赛Mirosot，仿真机器人足球比赛Simurosot，小型机器人足球比赛Rboosot，自主式机器人足球比赛Kheperasot，类人机器人足球比赛Hurosot和机器人标准动作比赛Benchmark。从1995年至今，FIRA机器人足球比赛己经经历了10年的发展，而且在中国，越来越多的科研院所、高等学府把FIRA机器人足球研究工作当成是提高领域研究的手段。 另一国际组织Robocup（The Robot world Cup Initiative）是国际人工智能学会组织的国际机器人足球协会。成立于1996年，总部设在日本名古屋，主席是SONY公司计算机科学研究院的北野宏明教授。每年举办一次，吸引了众多的大学和科研机构的参加。1998年，我国成立了FIRA中国分会，并组织了相应的机器人足球队参加世界杯比赛，取得了较好的成绩。我国于2001年在北京举办了第六届机器人足球世界杯比赛。可以说，在国家有关机构和学术界的支持和努力下，中国的和器人足球事业已经迈步走向国际舞台。1.1.2 课题国内外研究现状 机器人的研究发展迅速，应用的范围十分广泛。就目前来看，机器人的发展仍然处于初级的阶段，需要去完成的工作仍然很多，特别是在许多具体的环境中仍要具体问题具体分析。在机器人中有一类机器人叫做进化机器人，它用进化算法来实现机器人控制、机构等方面的优化，在路径规划运用中，主要是能够进化出合适的运动轨迹。D.F10reano和F.Mondada成功地用Khepera机器人实现了一个进化系统。自从John.R.Koza提出遗传规划（Genetic Programming，GP）以来，遗传规划已经在许多方面得到了应用，如缠绕的螺旋线的分辨（Spiral Classification），图像压缩（Image compression），符号回归（Symbolic regression）等问题。遗传规划在机器人路径规划中的应用也是国外许多学者研究的目标，并且己经出现了许多令人兴奋的成果。其中，比较早、影响也比较大的是人工蚂蚁的问题，这些应用遗传规划来规划路径的蚂蚁能够自主地寻找食物并吃掉食物，而且能够避开障碍。除了人工蚂蚁问题外还有割草机问题，在割草机问题中，割草机必须要在执行一次程序后割草机能够到达正方形草坪的每一个部分。其环境及任务与人工蚂蚁问题的环境基本相似，但也有不同。其行为包括：MOW，TURNLETF，JUMP；没有传感器来感知环境；所有动作在程序的一次执行中完成。另一个问题是函数的返回值不同，在割草机问题中各数的返回值不同，造成了实现的复杂性。在机器人沿墙运动方面也有研究，Dain.R.A己经开发了一种基于测距仪的仿真移动机器人，导航策略在不同的环境中测试以获得稳定的解决方案，仿真实验也证明了这一点。国内外对自主移动机器人的导航和避障问题己经做了大量的研究工作，比如哈尔滨工业大学机器人研究所在1996年11月研制成功一个“导游小姐”，该机器人能够实现避障和自主路径规划，识别障碍物的类型，具有一定的语音功能，具有极强的遥控功能。这个机器人能够根据传感器信息自主规划路径。由行走部分、行使控制器、显示器、语音识别系统和大量的传感器组成。行走部分采用差速驱动的方式。既可以在线仿真，也可以显示机器人行走的路径和某个时刻导游机器人所在的位置。大面积宽阔地面的清扫工作一直是一项繁重的体力劳动，人工清扫费时、费力且工作效率低，将机器人用于清扫服务，具有广阔的应用前景。为实现适合我国国情的宽阔地面自动清扫，清华大学与香港中文大学合作，联合研制开发出一种全方位移动清扫机器人。国内在遗传规划方面研究主要是西安建筑科技大学，云庆夏教授编写的进化算法比较详细介绍了遗传规划相关内容。另外，上海交通大学自动化所利用C+语言也对该算法在机器人沿墙移动问题进行了仿真实验，通过对移动机器人的行为策略进行符号型编码，然后对这些策略的组合（GP算法个体）进行自然选择、优胜劣汰，最后进化出满足任务需要的优良个体。这些个体实际上就是机器人沿墙移动的一系列指令有序组合。最后的仿真结果说明了应用GP算法来演化移动机器人沿墙走行为的有效性。近年来，自主式水下机器人由于其在海底资源探测上的优势而受到各国的关注，但因为水下环境十分复杂导致一般的规划方法都难以奏效，而水下环境的拥挤程度相对较低，机器人工作在同一区域的可能性较大，这一特征恰好有利于基于事例的规划方法的应用，因此该方法被广泛的用于解决水下机器人的路径规划问题。1.1.3 足球机器人比赛的发展从最近几年的机器人足球赛来看，主要有如下几个特点：1）发展迅速，比赛规模逐年扩大。2004年6月27日至7月3日，在葡萄牙里斯本举行的第七届RoboCup机器人足球世界杯，有30多个国家的200支队伍参加，而成立之初，仅有37支队伍；FIRA经过这些年的发展，比赛参赛队伍也超过百支。由此可见，机器人足球的发展非常迅速。2）竞争激烈，比赛水平提高很快。由于参赛队伍多，好多球队实力很接近，因此竞争非常激烈。每一次世界杯球队排名都会与上一届有很大的变化，这表明机器人足球已经受到各国的高度重视，每次比赛各队的水平都有明显的提高，也会出现一些新颖的软、硬件设计和巧妙的战术配合。3）研究不断深入，比赛类型不断升级。各队都在不断探索新方法、新思路，以求进一步提高队伍的水平，也出现了一些新的足球机器人类型，如1999年增加了SONY公司四足机器狗足球赛，2000年出现了拟人双足机器人踢球表演等。为了提高机器人足球的水平，世界各国不仅加大了人力、物力和财力上的投入，而且在研究上也不断深入，所有这些都成为推动足球机器人发展的重要因素。1.2 机器人足球路径规划概述1.2.1 足球机器人路径规划的描述机器人的最优路径规划问题，就是依据某个或某些优化准则（如工作代价最小、行走路线最短、行走时间最短等），在其工作空间中找到一条从起始状态到目标状态的能避开障碍物的最优路径。机器人路径规划是智能机器人的一个重要的课题，是机器人智能性的一个重要体现。在静态环境和动态环境下进行路径规划与实时避障是解决机器人应用的一个非常重要的问题，而动态不确定环境下的机器人路径规划则是实际研究与应用的一个重点和难点。 1.2.2 足球机器人路径规划的在足球机器人中，路径规划的目的主要有两个：一是为了完成某项动作，二是为了避障实现安全的运行。在现在的足球机器人系统中主要还是采用双轮差驱动的轮式机器人，这种机器人的运动模型是一种典型的非完整性约束系统，机器人为了完成某项动作，比如射门，就必须沿着一定的路径运动才能完成规定动作，这类路径规划可归结为由初始势态（位置和方向）到目标势态（位置和方向）的路径规划，路径规划的好坏直接影响到动作执行的速度和准确性。在充满对抗的机器人足球系统中，机器人之间的碰撞是不可避免的，为了在比赛中取得先机在决策系统中就必须要考虑到避障问题。因此，路径规划在是研究足球机器人系统中的重要的一部分，要想使一个足球机器人系统在比赛中获得优势必须在决策层中把路径规划问题放在首要问题，不管是在运动过程中还是在射门中，都需要用到路径规划的问题。1.2.3 足球机器人路径规划的特点足球机器人系统是一个实时动态的不确定的复杂环境，其路径规划具有如下特点：1）复杂性：机器人足球系统是一个实时的、动态的复杂多机器人系统。在这种动态时变环境中，机器人路径规划非常复杂，且需要很大的计算量。2）随机性：机器人足球是一个充满对抗的复杂环境，对方机器人的运动是难以预测的，动态障碍物的出现也带有随机性。机器人足球系统还有噪声因素：包括感知噪声和动作实现噪声。从视觉部分得到的信息必定是有一定延时的。同时，由于电机的物理性质，也无法保证小车一定会根据所得到的命令准确无误的运动，往往存在很多随机性和不确定因素。3）多约束：机器人的运动存在几何约束和物理约束。几何约束是指机器人的形状制约，而物理约束是指机器人的速度和加速度。4）多目标：机器人运动过程中路径性能要求存在多种目标，如路径最短，时间最优，安全性能最好，能源消耗最小。但它们之间往往存在冲突。实现起来比较困难了。1.2.4足球机器人路径规划的分类及现状人们应用人工智能技术在路径规划领域做了大量研究工作，探索出了很多有效的求解方法。其中一些应用范围很广，另外一些应用范围则极为有限。它们之间也不是互相排斥的，各有优缺点，因而常常结合起来共同地实现路径规划。路径规划问题已有的研究方法可以分为全局型方法、局部型方法以及混合型方法三种。全局规划方法，依照已获取的环境信息给机器人规划出一条路径。规划路径的精确程度取决于获取环境信息的准确程度。全局方法通常可以寻找最优解，但是需要预先知道环境的准确信息，并且计算量很大。局部规划方法，侧重于考虑机器人当前的局部环境信息，让机器人具有良好的避碰能力。很多机器人导航方法通常是局部的方法，因为它的信息获取仅仅依靠传感器系统获取的信息，并且随着环境的变化实时的发生变化。和全局规划方法相比较，局部规划方法更具有实时性和实用性。缺陷是仅仅依靠局部信息，有时会产生局部极点，无法保证机器人能顺利到达目的地。混合型方法试图结合全局和局部的优点，将全局规划的“粗”路径作为局部规划的子目标，从而引导机器人最终找到目标点。从机器人工作环境的角度区分规划方法，可以分为静态确定环境规划方法和动态时变环境规划方法。目前许多研究工作集中在静态环境下，如装配机器人；在动态环境下的规划问题己经引起了人们的重视，并且己经取得了一些成果，这将是今后的一个发展方向。从机器人路径规划发展历史来分，可分传统方法和智能方法。传统路径规划方法主要有自由空间法、图搜索法、栅格法和人工势场法。智能方法主要有模糊方法、神经网络和遗传算法等。第二章 足球机器人系统2.1 足球机器人系统2.1.1 足球机器人体系结构图2.1从硬件角度划分足球机器人系统由以下四个部分组成：三个机器人小车构成的机器人小车子系统；一个位于球场正上方约2米的摄像机、图像识别系统组成的视觉子系统；由一个至少2个频道的无线电发射板组成的通讯子系统；为各个机器人提供各种动作的决策子系统。其相互联系如图2.1所示，决策子系统处理来自视觉子系统的识别场景数据，做出决策，通过通讯子系统发出命令，由机器人小车完成一定的动作。2.1.2 视觉子系统 由置于球场上方的摄像头及相关软硬件构成。主要任务是以一定周期、快速地采集、处理赛场上的彩色图像，然后将处理结果送给决策子系统。图2.2 各子系统之间的关系2.1.3 决策子系统决策子系统在比赛进行过程中担当“教练”的角色。对于采用共轴平行的两轮独立驱动的移动机器人，决策子系统的输入信息是视觉系统获取的环境信息，包括球的位置，己方和对方机器人的位置及方向等，输出信息是本方5个机器人的左右轮轮速和击球控球命令。决策子系统是机器人足球比赛的核心，是人工智能等相关理论在机器人足球系统中的集中体现。2.1.4 决策子系统模型决策子系统处理来自视觉的实时场景辨识数据，做出决策、发出命令，通过无线通讯给机器人小车，决策子系统相当于机器人的“大脑”，视觉子系统相当于机器人的“眼睛”，机器人小车相当于机器人的“手脚”。决策子系统是本论文研究的一个重点，决策子系统主要解决足球机器人多智能体协作和运动控制的问题。决策子系统的任务是根据视觉子系统送到的目标信息，经过决策后产生机器人运动控制指令。决策子系统的输入是目标信息，输出是机器人运动控制指令，它是一个非结构化的知识型系统。一般认为，决策子系统由决策模型和机器人行为控制两部分组成。决策模型主要完成攻防态势判断、队形确定、角色和任务分配；机器人行为控制则包括动态避碰和运动控制，如图2.3所示决策。决策子系统要求具有较高的实时性和灵活性，其灵活性指灵活地实现攻防策略、阵型变化、战术配合及足球机器人运动。图2.3机器人控制决策子系统是一个知识型输入输出系统，它是一个软件，所以决策子系统的结构和机制不是唯一的，但决策子系统应该能够满足下列要求：1、实时性这个要求与视觉子系统的要求类似，系统的工作频率确定后，决策子系统的工作频率与之相同。因此，决策子系统的结构和算法应当尽量简化。2、灵活性足球比赛是一种竞争性、对抗性很强的运动，机器人足球比赛也不例外。比赛场上的形势瞬息万变，决策子系统必须能够准确判断攻防态势，灵活实现比赛阵型变化和战术配合，同时机器人的运动必须流畅。如何实现决策子系统要求的实时性和灵活性，也就是说如何更好的规划足球机器人的路径，使其更好的达到时间最优和路径最优，是本子系统研究重点解决的问题。本节根据robocup系统多智能体协作的特点，提出适用于机器人足球比赛的底层决策及其最优路径规划的思路。2.1.5 通讯子系统在机器人足球比赛中，计算机根据视觉系统采集的信息做出辨识和决策，通过无线通讯装置指挥场上机器人完成相应的战术动作。因此无线通讯系统就成为在机器人闭环控制系统成为决策子系统和机器人小车子系统的桥梁，其主要任务就是要将计算机的命令准确无误的传送给机器人，使机器人能准确接受和完成命令。2.1.6 小车子系统在整个足球机器人系统这个闭环控制系统中，机器人小车充当执行机构的角色。所以，小车性能在赛场上表现的好坏直接反映了整个足球机器人系统的优劣。小车子系统相当于我们的执行机构，所有的算法和要完成的动作都是靠它来执行，进而小车须在实际操作中完善和改进，使其能够完成其他子系统对它的控制。2.2 路径规划2.2.1 路径规划（底层决策）路径规划问题就是找到一条从当前点到目标点的无碰且时间最优的路径。由于足球机器人竞赛具有高度对抗、高速运动、动态环境和实时决策等特点，所以，路径规划的成功与否直接关系到比赛结果的成败。因此，路径规划任务在足球机器人系统中占有很重要的地位。 与一般的运动规划问题相比，足球机器人规划问题具有一个明显的特点；碰撞问题涉及规划的策略、路径和轨迹三个层次，贯穿规划的设计、执行和监督过程，任务、路径和轨迹都成为受事件驱动的短时规划行为。这样，原来层次化的规划模型就难以奏效了。足球机器人规划问题的复杂性还在于：多个智能体的高速运动、运动速度与方向的复杂变化、复杂的碰撞行为和高度实时性要求。很多传统的规划方法是针对一个静态的封闭环境设计的，并且具有较高的时间复杂度。如采用位姿空间描述和图搜索的求解方法等，很难满足实时性能的要求。探索适合于足球机器人在动态环境下的多智能体规划方法，已经引起研究人员的关注。2.2.2 路径策略路径规划的策略具体可以分为：全局路径规划的方法和局部路径规划，全局路径规划的方法有：拓扑法、可视图法和栅格法等。拓扑法是将规划空间分割成具有拓扑特征子空间，并建立拓扑网络，在拓扑网络上寻找起始点到目标点的拓扑路径,最终由拓扑路径求出几何路径。其缺点是建立拓扑网络的过程相当复杂，特别在增加障碍物时如何有效地修正已经存在的拓扑网络及如何提高图形速度是有待解决的问题。可视图法视机器人为一点，将机器人、目标点和多边形障碍物的各顶点进行组合连接，要求机器人和障碍物各顶点之间、目标点和障碍物各顶点之间以及各障碍物顶点与顶点之间的连线，均不能穿越障碍物，即直线是可视的。搜索最优路径的问题就转化为从起始点到目标点经过这些可视直线的最短距离问题。运用优化算法，可删除一些不必要的连线以简化视图，缩短搜索时间。该法能够求得最短路径，但假设机器人的尺寸大小忽略不计，使得机器人通过障碍物定点时离障碍物太近甚至接触并且搜索时间长。栅格法是由W.E.Howde在1968年提出的。栅格法将机器人工作环境分解成一系列具有二值信息的网格单元，工作空间中障碍物的位置和大小一致，并且在机器人运动过程中，障碍物的位置和大小不发生变化。用尺寸相同的栅格对机器人的二维工作空间进行划分，栅格的大小以机器人自身的尺寸为准。若某个栅格范围内不含任何障碍物，则称此栅格为自由栅格；反之，称为障碍栅格。自由空间和障碍物均可表示为栅格块的集成。栅格的标识方法有两种：直角坐标法和序号法多采用四叉树或八叉树表示工作环境，并通过优化算法完成路径搜索。该方法以栅格为单位记录环境信息，栅格粒度越小，障碍物的表示会越精确，但同时会占用大量的存储空间，算法的搜索范围将按指数增加。栅格的粒度太大，规划的路径会很不精确。所以栅格粒度的大小的确定，是栅格法的主要问题。局部路径规划的主要方法有：人工势场法、遗传算法和模糊逻辑算法。人工势场法是由Khatib提出的一种虚拟力法。人工势场法是传统算法中较成熟且高产的规划方法。这种方法的基本思想是把机器人在环境中的运动视为一种在抽象的人造受力场中的运动，即在环境中建立人工势场的负梯度方向指向系统的运动控制方向。目标点对移动机器人产生引力，障碍物对机器人产生斥力，其结果是使机器人沿“势峰”间的“势谷”前进。引力和斥力的合力作为机器人的加速力来控制机器人的运动方向和计算机器人的位置。这类方法突出的优点是系统的路径生成与控制直接与环境实现了闭环，从而大大加强了系统的适应性与避障性能。但是人工势场法也存在几个主要的缺陷：（1）陷阱区域。（2）在相近的障碍物之间不能发现路径。（3）在障碍物前振荡。（4）在狭窄通道中摆动。遗传算法（GA）是一种基于自然选择和自然遗传的全局优化算法，他采用从自然界选择、遗传操作中抽象出来的几个算子，对参数编码的字符串进行遗传操作，每一字符串对应于一个可行解，这种遗传操作是对多个可行解组成的群体进行的，故在进化过程中可以并行地对解空间的不同区域进行搜索，可使搜索趋于全局最优解而不会陷于局部极小解。正是由于这种内在的优良特性，GA可广泛应用于各种优化问题。遗传算法的操作算法有：（1） 复制或选择算子。（2）交叉算子。（3）变异算子。可见GA的主要优点是：采用群体方式对目标函数空间进行多线索的并行搜索，可同时对多个可行解进行检查，交叉算子、变异算子可以使可行解之间交换信息从而产生新的可行解，不会陷入局部极小点；GA只需要可行解目标函数的值，而不需要其他信息,对目标函数的连续性、可微性没有要求，因此使用方便；解的选择和产生采用概率方式，因此具有较强的适应能力和鲁棒性。他通过对随机产生的多条路径进行选择、交叉、变异、优化组合，利用遗传算法的优胜劣汰、适者生存的自然选择原理，选择出适应值达到一定标准的一条优化路径。利用遗传算法解决机器人动态环境中路径规划问题，可以避免困难的理论推导，直接获得问题的最优解。但遗传算法运算速度不快，进化众多的规划要占用较大的存储空间和运算时间。基于实时传感信息的模糊逻辑算法参考人的驾驶经验，通过查表得到规划信息,实现局部路径规划，计算量不大，易做到边规划边跟踪,能满足实时性要求。该方法克服了势场法易产生的局部极小问题，适用于时变未知环境下的路径规划，实时性较好。2.2.3 最优运动规划在保证运动规划算法具有足够的安全性（避免碰撞）的前提下，寻找一条长度最短的路径，或者时间最短的运动轨迹，是运动规划算法追求的目标。在最优规划的理论研究方面取得的重要研究成果包括：Fillipoy的存在性理论，Pontryagin最大值原理(PMP)Boltianskii的充分优化条件。其中PMP给出了最优路径的必要条件，因此是衡量最优路径的重要指标。分布式的思想同样也被用来研究近似优化的解法。Shiller等人提出了一种局部时间最优的轨迹规划方法。这种方法分为两个步骤：首先规划出一条路径，然后将沿路径的最优运动时间作为价值函数，进行局部最优化。考虑到精确求解的巨大困难，研究人员在许多实际问题中提出了近似的算法，这些算法的基本思想是通过搜索预先定义在工作空间、姿态空间或者状态空间的栅格，来寻找一条近似最优的路径。2.3 足球机器人系统环境模型2.3.1 球场模型 在足球机器人系统中，其运行环境是部分己知、部分未知，含有静态和动态障碍物的环境，且是个时刻变化的竞争性动态环境。图2.4球场模型如上图2.4所示，其中足球机器人球场边界是已知的静态障碍物，另外球场大小禁区有时也属于己知的静态障碍物，比赛规则中对大小禁区内双方机器人的数量均有严格的限制，所以决策系统应该机器人小车模型根据场上形势，规定禁区附近每个机器人是否可以进入禁区。机器人和小球都属于不确定性障碍物，它们的形状确定，但位置不确定，而且可能是静态的或者是动态的，对这些障碍物的避障是研究的重点和难点。2.3.2 机器人小车模型(1)机器人小车动力模型目前，足球机器人普遍采用的是两轮差动式移动机器人，其两个轮子共轴并且独立驱动。设机器人目前的位姿 速度为，和分别为左右轮的速度。机器人的位姿(位置、方向)与速度(线速度、角速度)之间存在如下关系： 由机器人小车的运动学模型可以看出，其状态空间有三个分量：，和。，而控制分量却只有两个：线速度和角速度，也可以是左右轮的速度和。因此，这是一个非完整性约束问题，必须增加一个约束方程： (2.4)根据机器人小车纯滚动、无侧滑的假定，在运动过程中上面的等式始终满足，其物理意义是，小车在轮轴方向上的速度始终为零。这个等式意味着，小车运动的瞬时速度的方向始终与小车的朝向相同，小车方向的改变只能通过两个轮子的差速来实现。足球机器人的这种典型的非完整性约束的运动模型，我们在运动规划时必须加以考虑，这样规划出来的路径才能被足球机器人加以跟踪和执行。(2)机器人小车的运动学模型 由上面的机器人小车动学力模型可知，机器人小车可作直线或曲线运动，根据机器人当前位姿和左右轮的速度可计算其曲率半径，角速度，线速度，以及下个周期的位姿，其运动学模型由式（2.5）、（2.6）确定。 (2.5) (2.6)其中，为机器人小车的边长，、分别为较大的轮速和较小的轮速，、。分别机器人当前的坐标和方向角。2.3.3球的运动学方程对球而言，它只能作直线运动，在没有外力的作用下，它的运动是匀减速直线运动。如下式表示： （2.7）其中，、表示t时刻球的运动状态，表示t-1时刻球的运动状态，a表示摩擦力产生的加速度，表示时间间隔，表示t-1时刻球的运动方向。第三章 足球机器人路径规划方法路径规划是实现机器人智能的一个关键技术。它的任务是在具有障碍物的环境中，按照一定的评价标准，寻找一条从起始状态（包括位置及姿态）到达目标状态（包括位置及姿态）的无碰路径。在足球机器人中，路径规划的目的主要是为了在充满对抗的赛场上规划出一条满足某项评价指标的无碰路径。路径规划主要应用于机器人底层策略中，作为足球机器人基本动作实现的基础，他的优劣将直接影响动作的实时性和准确性。因此，每个足球机器人研究人员都把他作为一个研究重点，探索出了很多有效的求解方法。其中一些应用范围很广，另外一些应用范围则极为有限。它们之间也不是互相排斥的，各有优缺点，因而常常结合起来共同地实现路径规划。下面对足球机器人的一些传统路径规划方法作个介绍。3.1 栅格法3.1.1 栅格法简介栅格法（Grid）是在静态路径规划中避障过程搜索最优路径的常见方法。该方法将机器人的工作空间分解为多个简单的区域，一般称为栅格。每个栅格的面积比一个机器人所占的面积略大。若某一个栅格范围内不包含任何障碍物，则称此栅格为自由栅格；如某一个栅格内含有障碍物，则称为障碍栅格。由这些栅格构成了一个连通图，在这个连通图上搜索一条从起始栅格到目标栅格的路径，该路径均由自由栅格构成，用栅格的序号来表示。最后把栅格序号转换成机器人空间实际坐标，令机器人按此路径运动，达到无碰撞的路径。目前有许多学者用栅格法对环境空间建模来解决问题并取得了较好的效果J.Borensteinf曾采用Grids表示环境，用势场法决策出VFF算法和VFH算法，并由此将栅格法的良好性能向人们展现出来。任世军和洪炳熔等人在机器人的位姿空间中采用基于栅格扩展的策略解决了机器人路径规划问题。薄喜柱等人用栅格法对机器人空间建模，参照人类在人群中行走的经验对栅格地图进行进一步规划，成功的实现了足球机器人路径规划问题。栅格法的运用方便，易于规划出正确的路径，因而对它的研究比较多。在栅格法表示的机器人路径规划问题研究中，定义出路径记忆量、路径方位的重要性等概念，通过可行路径中两两结点之间关联程度的改变，按照比例选择概率确定下一结点，由此得到一条新的可行路径。路径和关联程度之间形成一种正反馈机制，二者相互激励，从而简化了路径搜索方法，提高了路径搜索的效率。用栅格法建模进行机器人路径规划是研究比较多的一种方法。该方法将机器人的工作空间解耦为多个简单的区域，一般称为栅格，由这些栅格构成了一个连通图，在这个连通图上搜索一条从起始栅格到目标栅格的路径。哈尔滨工业大学用栅格法对机器人空间建模，参照人类在人群中行走的经验对栅格地图进行进一步规划，成功的实现了足球机器人路径规划问题。3.1.2栅格法进行路径规划使用栅格法进行路径规划的步骤有3个步骤：(1) 建立模型区域用栅格法建模进行机器人路径规划是研究比较多的一种方法。该方法将机器人的工作空间解耦为多个简单的区域，一般称为栅格，由这些栅格构成了一个连通图，在这个连通图上搜索一条从起始栅格到目标栅格的路径。哈尔滨工业大学用栅格法对机器人空间建模，参照人类在人群中行走的经验对栅格地图进行进一步规划，成功的实现了足球机器人路径规划问题。根据机器人和目标点的位置划定规划区域，然后将该区域用网格表示，每个网格就是一个栅格。栅格的