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

PAGE足球机器人毕业论文PAGEPAGE57足球机器人毕业论文题目：足球机器人路径规划的研究与实现专业：自动化摘要足球机器人系统是一个典型的多智能体系统，是一个实时动态的对抗性的复杂环境，它为人工智能技术的理论研究和模型测试提供了一个标准的实验平台。路径规划是智能机器人的一个重要研究课题，在这样一个具有高度实时性和竞争性的平台上研究路径规划是一个极具挑战性的课题。目前用于路径规划的方法很多，如人工势场法、中垂线法、栅格法、贝塞尔曲线法、可视图法及各种人工智能方法如遗传算法，神经网络等等。但这些方法在高度动态性和实时性环境中的研究还都存在些问题，有待进一步完善。本课题从静态环境中研究足球机器人的路径规划问题，全文主要包括如下内容：第一章介绍了足球机器人的研究背景并在此基础上简单的介绍了足球机器人路径规划。第二章具体分析了足球机器人系统、路径规划策略以及足球机器人环境模型等问题。第三章分析了现今采用的路径规划典型算法：人工势场法、栅格法、中垂线法和遗传算法。第四章在对各种算法进行综合分析的基础上，将遗传算法基于前人的基础上加入种群间的迁移并应用在本文的路径规划中。用matlab对遗传算法和人工势场法进行编程和仿真。最后，我们对全文内容进行总结。关键词：路径规划；足球机器人；遗传算法；人工势场；中垂线法AbstractSoccerrobotsystemisatypicalmulti-agentsystemandreal-timedynamiccompetitiveenvironment,whichprovidesastandardofexperimentalplatformforthetheoreticalresearchofartificialintelligencetechnologyandmodeltest.Pathplanningisoneofthemostimportantresearchsubjectsinintelligentrobot,andtheresearchofpathplanningisachallengingtaskontheplatformwithhighlyreal-timeandcompetitive.Recentlymanymethodsareusedinpath-planning,suchasartificialpotentialfield,theperpendicularbisectormethod,thegrid,Besselmethodandviewmethodandvariousartificialintelligencemethodsuchasgeneticalgorithms,neuralnetworks,etc.Butthesemethodshavesomeproblemsintheheightandtheresearchdynamicreal-timeenvironment,theyshouldbefurtherimproved.Thissubjectmainlyresearchsoccerrobotpathplanningproblemfromthestaticenvironment.Thetextmainlyincludesthefollowingcontents:Thefirstchapterintroducestheresearchbackgroundofthesoccerrobot,andonthebasisofitbriefintroductionthesoccerrobotpathplanning.Thesecondchapteranalysistheproblemsuchasthesoccerrobotsystem,thepathplanningstrategyandtheenvironmentalmodelofsoccerrobotindetailed.Thethirdchapteranalysisthetypicalpathplanningalgorithmusedcurrentlysuchastheartificialpotentialfieldmethod,gridmethod,theperpendicularbisectormethodandgeneticalgorithms.Thefourthchapter,basedontheanalysisofthevariousalgorithm,jointhepopulationmigrationinthegeneticalgorithmwhichisbasedonthebasisofformerinthispathplanning.thegeneticalgorithmandartificialpotentialfieldmethodaresimulatedandprogrammedbytheMATLAB.Finally,wesummarizethecontentofthewholetext.Keywords:path-planning;soccerrobot;geneticalgorithm;theartificialpotentialfield;perpendicularbisectormethod目录摘要 IAbstract II第一章绪言 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公司研制的计算机深蓝（DeepBlue）战胜了国际象棋大师卡斯帕洛夫（Kasparov）之后的人工智能历史上又一个里程碑项目。目前国际上有组织的机器人足球比赛有两大系列FIRA和Robocup。FIRA是国际机器人足球协会联合会（FIRA-FederationofInternationalRobotsoccer），简称国际机器人足联，成立于1997年6月5日，总部设在韩国大田的韩国科学（技术）院（KAIST）。目前已有30余个国家的近百个学校与科研院所为其成员单位，主要分布在亚洲、澳洲、北美和南美洲等地。FIRA的比赛项目主要有：超微机器人足球比赛Narosot，微型机器人足球比赛Mirosot，仿真机器人足球比赛Simurosot，小型机器人足球比赛Rboosot，自主式机器人足球比赛Kheperasot，类人机器人足球比赛Hurosot和机器人标准动作比赛Benchmark。从1995年至今，FIRA机器人足球比赛己经经历了10年的发展，而且在中国，越来越多的科研院所、高等学府把FIRA机器人足球研究工作当成是提高领域研究的手段。另一国际组织Robocup（TheRobotworldCupInitiative）是国际人工智能学会组织的国际机器人足球协会。成立于1996年，总部设在日本名古屋，主席是SONY公司计算机科学研究院的北野宏明教授。每年举办一次，吸引了众多的大学和科研机构的参加。1998年，我国成立了FIRA中国分会，并组织了相应的机器人足球队参加世界杯比赛，取得了较好的成绩。我国于2001年在北京举办了第六届机器人足球世界杯比赛。可以说，在国家有关机构和学术界的支持和努力下，中国的和器人足球事业已经迈步走向国际舞台。1.1.2课题国内外研究现状机器人的研究发展迅速，应用的范围十分广泛。就目前来看，机器人的发展仍然处于初级的阶段，需要去完成的工作仍然很多，特别是在许多具体的环境中仍要具体问题具体分析。在机器人中有一类机器人叫做进化机器人，它用进化算法来实现机器人控制、机构等方面的优化，在路径规划运用中，主要是能够进化出合适的运动轨迹。D.F10reano和F.Mondada成功地用Khepera机器人实现了一个进化系统。自从John.R.Koza提出遗传规划（GeneticProgramming，GP）以来，遗传规划已经在许多方面得到了应用，如缠绕的螺旋线的分辨（SpiralClassification），图像压缩（Imagecompression），符号回归（Symbolicregression）等问题。遗传规划在机器人路径规划中的应用也是国外许多学者研究的目标，并且己经出现了许多令人兴奋的成果。其中，比较早、影响也比较大的是人工蚂蚁的问题，这些应用遗传规划来规划路径的蚂蚁能够自主地寻找食物并吃掉食物，而且能够避开障碍。除了人工蚂蚁问题外还有割草机问题，在割草机问题中，割草机必须要在执行一次程序后割草机能够到达正方形草坪的每一个部分。其环境及任务与人工蚂蚁问题的环境基本相似，但也有不同。其行为包括：MOW，TURNLETF，JUMP；没有传感器来感知环境；所有动作在程序的一次执行中完成。另一个问题是函数的返回值不同，在割草机问题中各数的返回值不同，造成了实现的复杂性。在机器人沿墙运动方面也有研究，Dain.R.A己经开发了一种基于测距仪的仿真移动机器人，导航策略在不同的环境中测试以获得稳定的解决方案，仿真实验也证明了这一点。国内外对自主移动机器人的导航和避障问题己经做了大量的研究工作，比如哈尔滨工业大学机器人研究所在1996年11月研制成功一个“导游小姐”，该机器人能够实现避障和自主路径规划，识别障碍物的类型，具有一定的语音功能，具有极强的遥控功能。这个机器人能够根据传感器信息自主规划路径。由行走部分、行使控制器、显示器、语音识别系统和大量的传感器组成。行走部分采用差速驱动的方式。既可以在线仿真，也可以显示机器人行走的路径和某个时刻导游机器人所在的位置。大面积宽阔地面的清扫工作一直是一项繁重的体力劳动，人工清扫费时、费力且工作效率低，将机器人用于清扫服务，具有广阔的应用前景。为实现适合我国国情的宽阔地面自动清扫，清华大学与香港中文大学合作，联合研制开发出一种全方位移动清扫机器人。国内在遗传规划方面研究主要是西安建筑科技大学，云庆夏教授编写的《进化算法》比较详细介绍了遗传规划相关内容。另外，上海交通大学自动化所利用C++语言也对该算法在机器人沿墙移动问题进行了仿真实验，通过对移动机器人的行为策略进行符号型编码，然后对这些策略的组合（GP算法个体）进行自然选择、优胜劣汰，最后进化出满足任务需要的优良个体。这些个体实际上就是机器人沿墙移动的一系列指令有序组合。最后的仿真结果说明了应用GP算法来演化移动机器人沿墙走行为的有效性。近年来，自主式水下机器人由于其在海底资源探测上的优势而受到各国的关注，但因为水下环境十分复杂导致一般的规划方法都难以奏效，而水下环境的拥挤程度相对较低，机器人工作在同一区域的可能性较大，这一特征恰好有利于基于事例的规划方法的应用，因此该方法被广泛的用于解决水下机器人的路径规划问题。1.1.3足球机器人比赛的发展从最近几年的机器人足球赛来看，主要有如下几个特点：1）发展迅速，比赛规模逐年扩大。2004年6月27日至7月3日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)建立模型区域用栅格法建模进行机器人路径规划是研究比较多的一种方法。该方法将机器人的工作空间解耦为多个简单的区域，一般称为栅格，由这些栅格构成了一个连通图，在这个连通图上搜索一条从起始栅格到目标栅格的路径。哈尔滨工业大学用栅格法对机器人空间建模，参照人类在人群中行走的经验对栅格地图进行进一步规划，成功的实现了足球机器人路径规划问题。根据机器人和目标点的位置划定规划区域，然后将该区域用网格表示，每个网格就是一个栅格。栅格的大小是一个关键因素：栅格选得小，环境分辨率较大，但抗干扰能力弱，环境信息存储量大，决策速度慢；栅格选得大，抗干扰能力强，环境信息存储量小，决策速度快，但分辨率下降，在密集障碍物环境下，发现路径的能力减弱。一般栅格大小的选取和机器人的大小相关。最后对划分好的栅格编序号，栅格序号将代表栅格所在的位置；并给每个栅格赋以一定的初值，栅格的值将代表有障碍物的可能性。(2)生成障碍物地图区域建好以后，开始检测障碍物的位置，并根据障碍物位置找到对应栅格地图中的序号值，并对对应的栅格值进行修改。定义不包含障碍物的栅格为自由栅格，包含障碍物的栅格为障碍物栅格。(3)在区域里搜索无障碍物的栅格足球机器人所走的路径就是在区域里寻找一条无碰撞的路径，也就是区域里联系自由栅格组成的一条路径，搜索的方法很多如基于势场法的栅格路径搜索方法，用遗传法进行的路径规划方法，以及基于动态二叉的A*算法等。3.2人工势场法3.2.1人工势场法简介人工势场法是国内外研究者研究与应用较多的方法。人工势场实际是对机器人运行环境的一种抽象描述。势场中包括斥力场和引力场，不希望机器人小车进入的区域和障碍物是斥力场，子目标及其建议机器人进入的区域为引力场。引力场和斥力场的周围有一定的抽象势能，它的负梯度方向表达了机器人小车系统所受抽象力的方向，正是这种抽象力，促使机器人小车以平滑的曲线朝向目标前进。人工势场法在避障和轨迹规划的同时也考虑了机器人小车的运动性能指标。该方法计算方法简单，计算量小，且在避障和轨迹规划的同时也考虑了机器人的运动性能，因此该方法倍受人们欢迎。传统的人工势场该方法是由khatib于1997年首次提出的一种虚拟力法，其主要思想是：构造目标位姿引力场和障碍物斥力场共同作用的人工势场，搜索势力函数的下降方向来寻找无碰撞的路径。首先，在机器人的运动空间中创建一个势场。该势场由两部分组成：一个是引力场，方向指向目标点球；另一个是斥力场，方向指向远离障碍物方向。整个势场U是其引力部分和斥力部分的叠加。机器人就是沿着合成的势场力方向运动，绕开障碍物，向目标点运动。如图3.1所示图3.1空间势场模型在足球机器人系统中，将整个比赛场地虚拟成一个有力存在的场地，把力分为引力和斥力，目标点对移动机器人产生引力，障碍物对机器人产生斥力，其结果是使机器人沿“势峰”间的“势谷”前进。引力和斥力的合力作为机器人的加速力来控制机器人的运动方向和计算机器人的位置。根据比赛的进行，场上队员会发生变化，因而整个力场中各部分的受力情况也会发生变化，因此决策系统就可以根据场上的这种变化去实时的控制足球机器人的运动情况。确定引力势场和斥力场函数如下：引力场：(3.1)这里定义为引力场系数，和分别代表目标点和机器人的位置，m=1或2。对于m=1，引力场呈现圆锥状，近似重力场，除在目标点外，其他点的吸引力为定值，为恒定的。对m=2，吸引力场呈现抛物线状。则斥力场：(3.2)当机器人接近目标点时，引力势场近似为零。此时，吸引力为零。斥力场函数为(3.3)为一正的比例因子，表示障碍物和目标点的最短距离，为影响障碍物的设定的一个正比例数，的选择影小车的避障情况，合理的选择有利与机器人走出合适的路径规划，一般选取<min(d1,d2)其中d1是各障碍物间相互距离中最小距离的一半，d2是目标点到各障碍物距离的最小者。相应的斥力为(3.4)则，作用在机器人上的合力为引力和斥力的合理F=+(3.5)机器人的最后作用力为F，通过F来控制机器人小车的运动路线，避障情况，还有射门情况等，通过调节，的值进而调节机器人的运动。3.3中垂线法中垂线法是较早在控制中大量使用的路径规划算法，如图3.5所示，分别作目标点与期望方向上一点的连BT，目标点与机器人小车的连线，再作目标点和机器人之间线段的中垂线交于BT于A1，使小车向该点运动，在下一周期，作一条新的中垂线，交BT于新的一点A2，使小车向A2运动，依此类推，最终小车将趋向目标点，同时保证其姿态为期望的方向。图中点划线表示机器人经过的路径。图3.5中垂线模型这种方法的特点是算法简单，而且算法可以保证机器人到达目标点时满足位置和方向的要求。但是这种方法使用的范围是有限的。当小车距位于球和对方球门之间的区域时，不能直接用中垂线法，而需要决策部分的相应算法来实现控制小车首先绕到球的另一面。3.4遗传算法法3.4.1遗传算法的简介遗传算法(GeneticAlgorithm)是一种人工智能方法，它基于达尔文的生物进化论的适者生存原理，是1975年左右由美国Michigan大学的JohnH.Holland教授研究出的，遗传算法模拟了生物的遗传、进化原理，并引用了随机统计理论而形成，在求解过程中，算法从一个初始变量群体开始，逐代寻找问题的最优解，直至满足收敛判据或预先设定的迭代次数为止，属于迭代式算法。遗传算法（GA）是一种基于自然选择和自然遗传的优化算法，它采用从自然界选择、遗传操作中抽象出来的几个算子，对参数编码的字符串进行遗传操作，每一字符串对应于一个可行解，这种遗传操作是对多个可行解组成的群体进行的，故在进化过程中可以并行地对解空间的不同区域进行搜索，可使搜索趋于全局最优解而不会陷于局部极小解。正是由于这种内在的优良特性，GA可广泛应用于各种优化问题。生物进化过程本质上就是生物群在器生存环境约束下通过个体的竞争（competition）、选择（selection）、杂交（crossover）、变异（mutation）等方式所进行的“优胜劣汰”的一种自然有花过程。遗传的基本思想正式体现了这一过程，随记生产初始种群，将其视为附带群体开始进行搜索，群体中的每个个体，即问题的一个解。算法通过个体的“适应值”来作为父代中个体适应环境的能力度量，进过选择杂交和变异产生新的子代染色体重新选择，如此反复金环迭代，使个体的适应能力不断提高并收敛与最好的个体，该个体就是问题的最优解。遗传算法对解决复杂系统优化问题，特别是对组合优化问题的求解有着良好的能力。近年来越来越多的中外学者致力于遗传算法的研究。遗传算法已将在旅行商问题的求解、生产调度、图形划分、函数优化图像处理、机器学习、自动控制、人工生命等总舵领域中得到了成功的应用，并取得良好的成果。3.4.2遗传算法的特点传统的搜索方法重要分为三类：=1\*GB3①基于微分的方法：包括直接法和间接法。这类方法在求解问题是，要求倒数纯在而且容易得到。=2\*GB3②枚举方法：包括动态规划法、隐枚举法和完全枚举法。该方法往往效率不高。=3\*GB3③启发式随机搜索方法：包括模拟退火和传统方法相比，遗传算法具有以下的优势。遗传算法处理的对象是参数集的代码，而不是参数本身，所以遗传算法是一种所方法，与具体问题领域无关。此编码操作使得遗传算法可直接对结构对象进行操作，所谓节后对象泛指集合，序列、矩阵、树、图、链、表等各种一维或二维甚至多维结构形式的对象。这一特点使得遗传算法具有广泛的应用领域。遗传算法是非单点搜索算法，具有全局搜索能力。它的优化过程是从点集开始对搜索空间中的多个解进行适应值评估和染色体进化，这种机制使得遗传算法易于并行话且搜索不易陷入局部极小点。特别是当算法中有保证全体多样性的措施时，可以有效保持搜索空间的多样性并使其具有较强的鲁棒性。遗传算法的搜索过程使用适应度函数（目标函数）判定解的优劣。适应值函数不受可导，可微等传统方法思路的限制，而且其定义域可以任意设定，因此算法过程简单，易于实时。上述这些优势可以看出，遗传算法有许多独特的优点。(1)全局性遗传算法在搜索过程中不易陷入局部极值点，即使在非连续、多峰以及噪声的情况下，也能以很大的概率收敛到最优解或满意解，具有惊人的容噪能力等。(2)并行性和高行型遗传算法具有大范围全局搜索的特点，与问题无关，潜入问题的前期工作量少，本身具有并行性，很适用于并行计算机，因而具有很高的执行效率。(3)鲁棒性鲁棒性强意味着遗传算法的搜索以全体为基本单元，解的节后随时间增加而趋于稳定，不受初始选择的影响，不因实例的不同而蜕变；同时也疑问者，对一个相同问题，遗传算法在不同的多此运行中得到的节后是相似的，在解的质量上没有很大的差异。遗传算法的鲁棒性已被许许多多的数值试验所证实。(4)普适性和易扩性遗传算法是一种弱方法，它采用自然进化机制来表达一类复杂现象，对函数的形态无要求，可解决多种优化搜索问题。针对不同的实例，只需适当调整算子参数等，做很小的修改即可适应新的问题，程序能够通用，然而线性的大多数优化方法都做不到折点。(5)简明性遗传算法的基本思想简单明了，实现起来通俗易懂。3.4.3遗传算法的基本原理1.遗传算法的基本术语染色体：遗传物质的主要载体，指多个遗传因子的集合。个体：指染色体呆有特征的实体称个体。种群：染色体带有特征个体的集合称为群体，该集合内的个体数称为群体的大小。编码：从表现型到遗传子型的映射称为编码。适应度：各个个体对各自适应环境的程度成为适应度。交叉：把两个染色体换组的操作称为交叉，又称为重组。变异：让遗传因子以一定的概率变化的操作称为变异。解码：让遗传子型到表现型的映射称为解码。2.遗传算法的基本原理与流程在遗传算法中，首先通过随机方式产生若干个所求解的问题的数字编码(即染色体)来形成初始群体（即种群），以此为进化起点的第一代群体，并计算每个编码的个体适应值来对每个个体进行数值评价，这里的适应度值体现并反应了木匾函数的巡游信息。接下来与自然界一样，从群体中随机挑选若干个体作为繁殖过程的样本集合，选择机制应保证适应度值较高的个体能保留较多的样本，而适应度值较低的个体则保留较少的样本或被淘汰。在繁殖过程中，利用交叉和变异两种算子，以一定的交叉概率和变异概率对挑选后的样本进行交换，从而给出新的个体。最后通过新老个体替换产生下一代群体。算法不断重复进行上述评价、选择、繁殖和替换过程，直到结束条件得到满足为止。通常进化过程的最后一代群体中适应度最高的个体，就是利用遗传算法求解最优化为题的最终结果。图3.6遗传算法的流程3.用遗传算法进行路径规划①染色体表示用十进制栅格序号表示路径节点，用栅格序列表示一条染色体。由于我们无法确定究竟要经过多少个栅格，所以我们这里的染色体用不定长染色体表示。②初始群体生成初始种群为随机生成的从出发点到目标点的任意一条可行路径集合。具体产生的方法与栅格法搜索最优路径方法类似。③适应值计算式中，Num为该个体所通过的栅格总数;D为该个体中相邻序号间直线距离之和。④遗传操作选择操作：用一定的算法从当前种群中选择同样数量的新一代群体。首先计算每个个体的适应值函数，然后用赌轮选择方法或者其它方法选出新的种群，通常在选择时要把上一代的最优个体强制保留下来。交叉操作：通常有单点交叉、多点交叉、均匀交叉等几种方法。随机选择两个个体，按照一定的交叉概率选择交叉点进行交叉，用交叉后的子代个体代替原种群中的父代个体，产生新的种群。前面提到这里的染色体是长度不相等个体，所以交叉点应该分别在要交叉的两个个体中进行选择。变异操作：根据路径规划的特点，这里的变异操作有多种设计方式，可以从个体中以一定概率选择一个起点和终点之外序号作为变异点，删除该点，或者用另一个随机产生的序号代替它，或者在个体中随机选择一个序号在变异处插入。在机器人的路径规划中，还需要增加一些特殊的算子，以保证所得的路径能够避开障碍物，并达到最短的要求，常见的有插入和删除算子。插入算子：前面由于交叉和变异操作可能产生不连续路径的情况，引入插入操作的目的就是为了把间断路径用自由栅格弥补，使之成为连续路径。具体方法是将出现断点处的两个路径点分别设为起点和终点，然后搜索着两点间的可行路径，直到所有路径位连续路径为止。删除算子：插入自由栅格的操作可能会使路径中出现重复节点，删除操作的作用就是将个体中两相同序号之间的冗余序号，连同两相同序号中的一个一并舍去，以简化路径。4.种群的初始化设定种群的初始化过程有很多种。在研究遗传算法时，常常随机产生初始群体，这样做的好处是产生方式不依赖于问题，也就是对于任何问题，我们都可以采用这种方式来生成初始群体，因此从随机初始群体出发能更清楚地考察算法的行为和性能。当然这也存在一定的问题，例如对于一个有约束的非线性规划问题，随机初始群体可能存在着不满足约束的不可行解，虽然对于一个好的算法来讲这并不会影响到最后的优化结果，算法最终得到的最优个体中关键的特性是算法的搜索和重组机制产生的，而不是由初始化过程产生的。但是，这还是可能对优化的速度产生一定的影响。如果初始群体都是可行解，我们就有可能加快收敛速度。在实际应用中，可以采用更有效的初始化方法来加快搜索，比如用贪婪算法等启发式算法的输出结果、利用人的直观解答和加权随机初始化过程等。5.遗传操作算子1）选择运算选择是从群体中挑选优良个体并淘汰劣质个体的操作过程。它建立在适应度评估的基础上，个体适应度越大，被选择中的可能性就越大，它的子代保留到配对库（matingpool）中的个体就越多。常用的选择方法有：轮盘赌方法（roulettewheelmodel）轮盘度方法是目前遗传算法中最基本也是最常用的选择方法。设群体的大小为，个体的适应度，则个体的选择概率为则累计概率为然后，根据选择概率{，=1,2,…,N}把一个圆盘分成N份，其中第扇形的中心角为2π*。在进行选择时，可以假想转动一下圆盘，若某参照点落入到第个扇形内，则选择个体。如下图所示图3.7概率分配轮盘所占的面积越大，被选中的概率也越大。表3.1个体1234567891011适应度值2.01.21.00.20.1选择概率90.070.060.030.020.0累计概率0.180.340.490.620.730.820.890.950.981.001.00排序选择法排序选择法以标准化几何分布规律随机对种群中染色体进行选择，以最佳染色体的选择概率作为基本参数，按染色体的排列序号确定其选择概率。排序法的最大优点是：排序法忽略实际染色体的适应度值，用染色体的顺序来换算出相应的生存概率，换算原则为大适应度值对高选择概率，小适应度值对地选择概率。这样既保证大适应度值染色体获得高选择概率，同时又阻止某些超级染色体过快地控制遗传过程。在该遗传过程中，首先需要根据最佳染色体选择概率计算标准分布值，如下(3.6)然后根据上式计算染色体选择概率，k=1，2，3,…,P(3.7)式中为第个染色体的适应值在种群中有达到小排列的序号。为最佳染色体选择概率，为样本数。最后计算染色体的累计选择概率值,,k=1,2,3,…,P(3.8)其后的选择方法同轮盘的赌类似。最佳个体保存法最佳个体保存法把群体中适应度最高的个体不进行配对交叉而直接复制到下一代。该方法的好处在于保证了进化过程中某一代的最优解不被交叉和变异操作所破坏。但是该方法是一些局部优化个体的遗传基因会急速增加进而达到局部有化解，器全局搜索能了差，不利于多峰值的搜索问题，所以该方法一般与其他选择方法相结合使用。2）交叉运算（crossover）交叉操作：通常有单点交叉、多点交叉、均匀交叉等几种方法。随机选择两个个体，按照一定的交叉概率选择交叉点进行交叉，用交叉后的子代个体替原种群中的父代个体，产生新的种群。前面提到这里的染色体是不等长个体，所以交叉点应该分别在要交叉的两个个体中进行选择。①离散杂交离散杂交又分为部分离散杂交和整体离散杂交。部分离散杂交即是在父代向量中选择一部分分量（如一个分量或从某分量以后的所有分量）然后交换这些分量以形成后代。例如：若选择交换第k个分量以后的所有分量。则两个后代为而整体杂交则是以0.5的概率交换所有分量，这有点像二进制编码时的均匀性杂交，这些我们也可以通过生成模板的形式来实现，若某一位是1则交换相应的分量，否则保留。显然，通过离散杂交产生的后代，其分量仍然在其定义区间之内。②算术杂交算术杂交也分为部分算术杂交和整体算术杂交。部分算术杂交也是先在父解向量中选择一部分分量，如第个分量以后的所有分量，然后生成个（0,1）间的随机数,…则两个后代定义为3）变异运算遗传算法中使用变异算子使得遗传算法具有局部的随机搜索能力，能找到更精确的值，并配合交叉操作以维持种群的多样性，防止出现过早收敛。一般来说变异算子也有两类，一类为基本的二进制变异操作，另一类为浮点数交叉。①二进制变异运算变异就是以很小的概率随机的改变群体中染色体某些基因的值。变异操作的基本过程是：在二进制编码方式中，百衲衣算子随机的将某个基因值取反，即“0”编程“1”或“1”变成“0”。例如：浮点数变异运算对于浮点数来说常用的变异手段有均匀变异、边界变异和非均匀变异等。其主要目的就是构造变异一个扩大染色体基因值的取值范围。均匀变异：设种群中有染色体，均匀变异则先在染色体中选择一个分量，然后在一个定义区间[,]中均匀地选择一个数代替，由此得到新的染色体为=（，，…，）。6.遗传算法的终止条件作为一种算法不能无限地执行下去，要在合理的时间内终止。遗传算法通常用到的终止标准有：①收敛标准。算法执行到一定程度，群体中的个体字符串结构会很相似，再执行下去难以得到更好的个体了，这时认为算法收敛了。当然，判断收敛的标准可以是不同的。②时间标准。预先给定算法的执行时间，如给定要产生的个体的总数、循环的代数或者计算的时间长度。③精度标准。当找到的个体的评价函数值的精度达到一定要求后，算法就可终止。7.遗传算法的参数设置从前面遗传算法的讨论中我们可以看出，每个部分都有许多参数，如变异概率、杂交概率、群体大小等，不同的参数取值使遗传算法体现不同的行为。有一些问题的参数取值是相互关联的，这些参数很大程度影响着解的质量。在简单遗传算法中，在演化过程中，这些参数是固定不变的，而对于不同类型的问题，往往要采用不同的参数才能得到满意的解。因此我们不得不花费很多时间来试验到底哪个参数最适合我们要解决的问题。但是由于遗传算法的各个部分是相互作用的，这些参数组合起来的情况非常多，实际上想通过手工调节来找到最佳的参数组合是很费力的一件事。如果能在演化过程中，程序自己不断的调节这些参数，就能使算法适用于更多类型的问题。参数的调节方式大致可以划分为三类：确定性调节，适应性调节，自适应性调节。确定性调节方式是指参数的调节方式是靠事先确定好的策略调节的，这种调节没有用到解的反馈信息，只用到了时间信息。例如在变异策略中，我们可以在前面若干代中使用大的步长变异，而当收敛到一定代数后使用步长较小变异。这里我们只用到了代数这一个参数，并没有其他关于群体的反馈信息。适应性调节方式是根据群体中解的反馈信息来调节参数的，这种调节方式是最为常用的，也是非常有效的方法。例如我们前面提到的变异方法大多属于这一类型。自适应调节是指将参数作为个体的一个染色体和其他需要优化的参数一起用遗传算法进行优化。参数调节本身就是一个复杂的优化过程，而遗传算法本身也是一种优化算法，既然遗传算法可以用来优化非线性规划问题，也应该可以用来优化自身的参数。这种方法己经成功的用于变异算子，杂交算子和群体大小的优化。但是这种方法并不适用于罚函数的参数调节。与杂交和变异算子的参数不同，罚函数的参数直接影响到个体的适应值，而杂交和变异算子的参数并不参与适应值的计算。适应值是我们进行个体好坏判断的标准，当我们把罚函数的参数也作为个体的一部分时，我们得到的适应值好的个体可能并不好，而只是它所在那一代的罚函数的参数使它得到了很好的适应值。3.5对各种方法的综合评价人工势场法比较容易掌握，结构简单，使用方便，便于底层的实时控制，规划出的路径比较平滑安全，使机器人运动更加自然具有柔韧性。但是人工势场法是一种局部规划算法，不一定能规划出全局最优路径。而且算法本生有着一定的局限性：①会出现机器人在没有到达目的地时停滞或者找不到路径的现象；②当障碍物与目标点的位置很近时会出现机器人在障碍物前振荡甚至被障碍物推开的现象。不过它最突出的优点就是简洁方便，便于实时控制，因此在实际应用中使用的还是很广泛的。栅格法是最容易掌握的一种方法，其简单的建模过程与灵活多变的搜索算法可以被各个领域、各个阶层的人接受和使用，而且只要问题的最优路径存在，设计合理的搜索算法一定能求出最优的路径。但是当要规划的环境比较复杂时，搜索效率会下降。另外规划的路径是一种折线路径，路线不光滑，机器人在转角处的速度会受到影响，对于高速运行的机器人，这个问题就显得更加突出了。中垂线法的特点是算法简单，而且算法可以保证机器人到达目标点时满足位置和方向的要求。但是这种方法使用的范围是有限的。当小车距位于球和对方球门之间的区域时，不能直接用中垂线法，而需要决策部分的相应算法来实现控制小车首先绕到球的另一面。遗传算法、神经网络都属于人工智能方法。遗传算法是一种全局算法，但是算法比较复杂，设计者需要花大量的精力来设计。另外该算法采用的是迭代方法，如果迭代次数太多，会影响到实时性。综上所述，可以看出没有一种方法是完美的，每一种方法都有自己的优点和不可避免的缺点。我们应该设法利用这些优点，用其他的方法来弥补其缺点。现在研究者们常用的方法就是将两个或者两个以上的方法相互结合，来解决这类问题。例如：栅格法和人工势场法的结合，栅格法和遗传算法的结合，人工神经网络和进化算法的结合等等。第四章matlab实现人工势场、遗传算法的仿真4.1环境建模实现路径规划的前提是对环境进行描述，即对环境进行建模。赛场为黑色（不反光的）木质长方形场地（图4.1），其尺寸是150cm×130cm，带有5cm高，2.5cm厚的围墙。围墙的侧面为白色，围墙顶部为黑色。在场地的四角固定四个7cm×7cm的等腰三角形以避免球进入角落。木板表面的材质与乒乓球台相同。图4.1实际2D环境中圈半径是20cm，作为门区的一部分的圆弧沿球门线长20cm，垂直于球门线5cm。主要直线、圆弧（中线、门区边界线和中圈）均为白色，3mm宽。球门宽40cm，没有横梁和网。门线是恰好位于球门前长40cm的直线。门区包括位于球门前尺寸为70cm×15cm的长方形区域以及附属的弧形区域，弧形区域平行于球门线长度为20cm，垂直于球门线高度为5cm。将球场的图像以q