机器人路径规划演示平台设计

本科毕业论文题目机器人路径规划演示平台设计院（部）信息与电气工程学院专业班级学生姓名学生学号指导教师完成日期2013年6月14日目录摘要IIIABSTRACTIV1绪论111机器人路径规划演示平台设计的产生及背景112选题背景和意义213机器人路径规划演示平台设计的研究现状214课题应用与前景42机器人路径规划演示平台设计的理论基础621机器人路径规划问题的表达、分类和特点622机器人路径规划理论723栅格法8231栅格法简介8232栅格法算法原理简介9233路径选择概率11234栅格法优缺点分析1124人工势场法11241人工势场法原理11242势函数的确定13243人工势场法的优缺点分析1425人工神经网络算法15251人工神经网络算法概念15252人工神经网络算法理论基础1626蚁群算法18261蚁群算法概述18262蚁群算法理论基础1827本章小结203机器人路径规划演示平台设计系统的VC实现2131软件介绍21311VC简介21312VC安装使用21313VC功能优势2132机器人路径规划演示平台系统的总体设计22321设计名称22322设计说明22323设计目的22324设计内容2233算法论述23331界面的设计运行23332机器人路径规划的VC实现31333程序仿真结果3934小结404结论41致谢42参考文献43摘要机器人路径规划就是在具有障碍物的环境中，按照一定的评价标准，寻找一条从起始状态到达目标状态的无碰路径。因此在一些危险或人类不能直接到达的探测领域，路径规划可以帮助机器人在复杂地形中行进时自动避障，安全准确的到达目的位置。本文介绍了基于VC实现机器人路径规划仿真平台的设计和基于栅格算法的机器人路径规划方法。栅格法是在粗略划分整个工作环境的情况下，采取概率搜索的办法，先获得一条次优的最短路径，然后在此基础上，将不完全可行栅格回归原工作环境，最终获得一条最短的无碰撞路径。仿真结果显示移动机器人完全可以安全的到达目的地，并且可以寻找到一条平滑的路径轨迹。经过第二步的处理，精度越小搜索到的路径会更加平滑，实验表明基于栅格法的路径规划算法有效并易于实现。关键词VC仿真平台；栅格法；路径规划THEDESIGNOFROBOTPATHPLANNINGDEMONSTRATIONPLATFORMABSTRACTROBOTPATHPLANNINGISTOFINDACOLLISIONFREEPATHFROMTHEINITIALSTATETOTHETARGETSTATEACCORDINGTOACERTAINEVALUATIONSTANDARD,WHICHISINANENVIRONMENTTHATPOSSESSESANOBSTACLETHESIGNIFICANCEOFTHERESEARCHISMAINLYDETECTEDINTHEFIELDTHATISDANGEROUSANDHUMANSCANNOTREACHINDIRECTLYROBOTPATHPLANNINGCANHELPTHEROBOTBRINGABOUTAUTOMATICOBSTACLEAVOIDANCEANDARRIVEINTHEDESTINATIONSAFELYANDACCURATELYINTHECOMPLEXTERRAINTHISPAPERINTRODUCESTHATWEACHIEVETHEDESIGNOFPATHPLANNINGROBOTSIMULATIONPLATFORMANDROBOTPATHPLANNINGWHICHISBASEDONGRIDALGORITHMUSINGTHEVCGRIDMETHODDIVIDEDTHEWHOLEWORKINGCIRCUMSTANCEROUGHLY,ADOPTINGPROBABILITYSEARCHMETHODTOOBTAINASUBOPTIMALSHORTESTPATHTHENONTHISBASIS,GRIDTHATISNOTFEASIBLEWILLRETURNTOTHEORIGINALWORKENVIRONMENT,ANDFINALLYWEGETTHESHORTESTCOLLISIONFREEPATHAFTERPROCESSINGOFTHESECONDSTEP,THESMALLERTHEACCURACY,THESMOOTHERTHEPATHWECANSEARCHWILLBETHESIMULATIONRESULTSSHOWTHATTHEPATHPLANNINGALGORITHMBASEDONGRIDMETHODISEFFECTIVEANDEASYTOIMPLEMENTKEYWORDSSIMULATIONPLATFORM；GRIDALGORITHM；PATHPLANNING1绪论11机器人路径规划演示平台设计的产生及背景随着科学的发展和人类的进步，人们对未知世界的探索和自然资源的勘探也在不断的深入，但在科学探索和紧急抢险的环境中经常会遇到一些危险或人类不能直接到达的地域的探测，这些就需要用机器人来完成。而机器人在复杂地形中行进时自动避障,则是一项必不可少也是最基本的功能。因此，机器人的自动避障有了重大的意义。机器人避障的先决条件是机器人的路径规划设计，而机器人路径规划技术是智能移动机器人研究的核心内容之一。自20世纪40年代后期，美国橡树岭和阿尔贡1国家实验室制造出世界上第一台“主从型”机械手开始，机器人的研发和应用在欧美和日本等国家中以惊人的速度发展起来，我国关于这方面的研究起步相对较晚一些。但随着改革开放的不断深入，我国在机器人路径规划研究领域突飞猛进，并取得了一定的成果，例如地面自动导航车、水下自主机器人、飞行机器人的相继诞生证明了我国在机器人路径规划方面，无论是理论还是实践都取得了长足的进步，很好的激励我们能够不断完善进取。相应地，机器人的路径规划及相关算法的研究领域也因此而快速兴起。伴随着科学技术尤其是计算机领域的飞速发展，验证一种新的算法对于机器人路径规划是否成立将不必再耗费大量的人力物力进行实际操作，机器人路径规划演示平台设计应运而生。机器人路径规划演示平台设计是利用现代科技对机器人工作场地进行避障模拟的一种技术。它的任务是在具有障碍物的环境中，按照一定的评价标准，寻找一条从起始状态包括位置及姿态到达目标状态包括位置及姿态的无碰路径。目前常用到的路径规划方法主要有人工势场法、栅格法、神经网络等。在长期发展的过程中，智能避障已逐步演化为一门独立的学科，其中主要包含了超声波测距原理的研究和避障算法的研究。由于避障过程解决的不只是机器人避开障碍物，还为机器人提供了轨迹的规划走向。机器人路径规划演示平台的设计有效的为机器人的实际操作进行实况模拟，为机器人更好地完成任务奠定基础。随着科学技术的发展，各种不同的算法相继产生，为机器人路径规划的改善和深入奠定了良好的基础，它要求机器人根据给予的指令及环境信息自主地决定路径，避开障碍物，完成任务和目标。路径规划是移动机器人完成任务的安全保障，是机器人智能化程度的标志之一，同时也是人工智能与机械机器人的一个完美结合点。各类软件和程序语言的产生可以有效的帮助我们去建立一个机器人路径规划演示平台，实现机器人路径设置和壁障功能显示，为实际操作奠定了良好的理论基础。12选题背景和意义随着科学的发展和人类的进步，人们对未知世界的探索和自然资源的勘探也在不断的深入，但在科学探索和紧急抢险的环境中经常会遇到一些危险或人类不能直接到达的地域的探测，这些就需要用机器人来完成。而机器人在复杂地形中行进时自动避障则是一项必不可少也是最基本的功能。因此，机器人的自动避障有了重大的意义，同时伴随着高科技技术的进步，使得这一构想具备了实现的基础条件。目前人类在机器人路径规划算法方面已取得了骄人的成绩，传统路径规划方法主要包含自由空间法，图搜索法，栅格法等，智能路径规划算法则主要包含基于模糊逻辑的路径规划，基于神经网络的路径规划，基于遗传算法的路径规划，人工势场法以及信息融合方法等。但在高新科技的促使下，人类逐渐更倾向于涉足于深海和深空领域的探索，这也逐渐成为提高国家竞争力和综合国力的标志，这就对机器人路径规划产生了更高层次的要求，以适应更复杂的环境。同时伴随着机器人应用的日益广泛，结合路径规划问题所具有的复杂性、随机性、多约束性、多目标性特点，如何在各种具体环境中具体问题具体分析，合理有效地选择路径规划方法或策略等问题有待进一步深入。鉴于机器人路径规划演示平台设计具有重要意义和重大的社会经济效益和广阔的应用前景以及目前所面临的问题，说明了本课题的亟待研究和应用开发的紧迫性。13机器人路径规划演示平台设计的研究现状机器人路径规划演示平台技术是智能移动机器人研究的核心内容之一，它起始于20世纪70年代，迄今为止，己有大量的研究成果报道。路径规划方法的分类也呈现多样化，可以分为基于地图的全局路径规划方法和基于传感器的局部路径规划方法两种，也可以分为传统路径规划方法和智能路径规划方法。传统路径规划方法主要包含图搜索法，自由空间法，栅格法等，智能路径规划算法则主要包含基于遗传算法的路径规划，基于模糊逻辑的路径规划，基于神经网络的路径规划，以及人工势场法等等。在机器人路径规划发展的历程中，取得的重大成就主要有（1）1966年，JEDORAN和DMICHIE将图论的原理应用于路径规划之中，开始了这一领域的研究。（2）1968年，WEHOWDEN提出了著名的“搬沙发问题”，用来处理机器人路径规划中的几个问题。（3）1968年，PHART、NNILSSON和BRAFAEL针对遍历型经典DIJKSTRA算法运算速度慢的缺点，提出了优化性的A算法，这一成果成为机器人学规划研究的经典性基础。（4）1971年，REFIKES、PHART和NNILSSION提出了STRIPS方法。（5）1979年，TLOZANOPEREZ和MAWESLEY提出了路径搜索的概念，用来处理存在障碍物空间的路径规划问题。同年，JALBUS提出了任务分解的方法，这一方法后来总结成为NISTRCS方法的核心，用来处理包含有嵌套多步路径规划的问题。（6）1981年，TLOZANOPEREZ提出了机器人位置空间的概念，将机器人缩小为点，同时将障碍物按比例相应的扩张，使得机器人能够在这个新的空间中自由移动，这样可以大大简化机器人规划中碰壁问题的处理。（7）1983年，MJULLIERE、LMARCE和HPLACE提出了近似于栅格法的环境建模思想。（8）1985年，经典的人工势场法被提出。（9）20世纪90年代，人工神经网络、遗传算法等被成功的应用于机器人的路径规划中，取得了很多成果。近年来，随着高新技术机器人的出现及全方位制造系统的应用，研究人员对由适应极端环境的机器人组成的系统越来越感兴趣，自主避障机器人系统已经成为一个典型的、具有挑战性的研究领域。在这种尖端机器人系统的研究和开发过程中，实验是一个非常重要的环节。但是，直接构造实体的这种机器人系统并反复实验不仅价格昂贵，所需的时间周期较长，而且不成熟的算法在实验中可能会对机器人造成破坏。于是，机器人路径规划演示平台便得到研究人员的关注和青睐。现在，在机器人控制算法的研究和测试中，仿真已经成为实体实验前一个必要的验证手段。在机器人系统应用中，路径规划是必须解决的重要问题。机器人路径规划问题是指在有障碍物的工作环境中寻找一条恰当的从给定起点到终点的运动路径，使机器人在运动过程中能安全、无碰撞地绕过所有的障碍物。仿真系统对于机器人路径规划的研究具有重要的作用。机器人路径规划仿真系统是面向多移动机器人路径规划算法仿真的专用软件。当前，随着计算机技术、通信技术、网络技术、可视化技术等现代信息技术的高速发展，自主避障机器人系统的技术水平有了很大的提高。因此，机器人路径规划仿真系统必须采用适当的软件工程方面的技术，以更好地模拟由各自独立的机器人组成的机器人物理系统。综上所述，采用一种合理有效、能够实现上述目标的软件结构来建立一个通用的避障机器人路径规划仿真平台，对于当前多移动机器人系统路径规划问题的研究是很有意义也很必要的。PIEPER于1968年提出基于直角坐标空间的假设和检验方法，也是最早的机器人避障方法。20世纪80年代初，来自麻省理工学院人工智能实验室的PEREZ和LOZANO提出了基于C空间的自由空间法，并得到国内外很多学者的青睐，与之相关的各种几何法和拓扑法也应运而生。国内学者席裕庚等借鉴预测控制中的滚动优化原理，提出了动态不确定环境下基于滚动窗口的移动机器人路径规划法，该法利用机器人实时测得的局部环境信息，以滚动方式进行在线规划，实现了优化与反馈的合理结合，具有良好的避碰能力。14课题应用与前景在科学探索和紧急抢险的环境中经常会遇到一些危险或人类不能直接到达的地域的探测，这些就需要用机器人来完成实现任务的智能避障功能机器人避障已经广泛的用于地震之后的危险区域的搜救工作；机器人避障同时也在战争中得到应用，广泛的用于敌后侦查活动；考古人员将机器人避障应用于未知墓葬或洞穴的发掘工作。随着计算机、传感器技术以及人工智能技术的发展,路径规划技术已取得大量的成果。从目前的研究动向来看,路径规划技术有以下发展趋势1路径规划的性能指标要求的提高。这些性能指标包括可达性、实时性、安全性等。一种好的路径规划方法既要能规划出好的路径,又要能达到移动机器人系统实时性的要求,还要保证由于动态环境的不确定性、传感器采集信息的不完整性或者移动机器人自身结构的限制和缺陷等因素所带来的干扰下的安全性。因此,如何使路径规划的性能指标达到更好是目前算法研究的一个重要课题。2多移动机器人路径规划。随着机器人工作范围的不断扩大和工作任务越来越复杂，单个机器人很难完成人们所规定的任务,这就需要多个机器人之间进行合作和协调,既提高了机器人工作的效率,又可以解决因工作环境发生变化或机器人系统局部出现故障时所造成的工作停滞,这些都显示了开展多机器人系统以及多机器人路径规划研究工作的必要性。多机器人路径规划比单个机器人路径规划要复杂的多,从目前国内外研究的现状来看,规划多机器人路径需要更多考虑机器人之间的协调和合作式的路径规划。3传统的路径规划方法与智能算法的交叉融合。新的智能算法如遗传算法、神经网络算法逐渐引入到路径规划中来,促使了各种方法的融合发展,各种方法取长补短,催生一些更优秀的算法。因此如何把各种方法的优点融合到一起以达到更好的效果亦是一个有待探讨的问题。4传感器集成与信息融合技术2。由于单个传感器采样精度和范围有限,难以保证检测信息的完整、可靠,不足以决策其行为,于是多传感器集成和信息融合技术在移动机器人路径规划上得了广泛的应用，多传感器所获得的信息具有冗余性、互补性、实时性和低代价性,可以快速并行分析现场环境，信息融合技术通过一定的技术手段,总结融合了多传感器数据资源,使决策系统得到更全面的信息,获得对环境的正确理解。多传感器集成与信息融合技术的发展和应用大大提高了机器人对环境的理解程度,增强了移动机器人路径规划的可靠性和鲁棒性。2机器人路径规划演示平台设计的理论基础21机器人路径规划问题的表达、分类和特点机器人路径规划就是移动机器人在具有障碍物的环境中按照一定的评价标准如行走路径最短,行走时间最短,工作代价最小等,寻找一条从给定起点到达目标终点的无碰路径。机器人路径规划问题源于计算机几何学的传统研究课题。七十年代中期，智能机器人研究的诞生，促进了规划问题的研究。因为装配机器人和移动机器人都涉及到路径规划技术。八十年代初，SCHWARTZ搬钢琴问题，TLOZANOPEREZ位姿空间法，RABROOKS广义锥法使规划问题的研究得到了进一步的发展。KHATIB提出的人工势场法考虑到了机器人的动态性能及直接控制。随着研究的深入，位姿空间法及人工势场法得到了广泛的应用并发展成为两种较为成熟的规划方法，并在此基础上产生了许多类似的方法。由于路径规划问题的复杂性，不同的研究者从不同的角度研究某一方面的问题，对具体问题的提法也不完全相同。典型的路径规划问题的提法是指在有障碍物的工作环境中，如何为机器人寻找从起点到终点的运动路径，让机器人在运动过程中能安全、无碰撞的通过所有的障碍物。路径规划问题的研究涉及到环境表达、规划方法、路径执行。环境表达有两层含义，其一是有效的获取环境信息，这与视觉传感器相关；其二是如何将环境信息有效的表达出来。规划方法关心的是在环境表达的基础上，采用有效的方法规划路径并且进行优化。路径的执行与底层控制密切相关，并且考虑机器人的动力学特性，控制机器人按照设定的路径行走。路径规划问题已有的研究方法可以分为全局型方法、局部型方法以及混合型方法三种。全局规划方法依照己获取的环境信息，给机器人规划出一条路径。规划路径的精确程度取决于获取环境信息的准确程度。全局方法通常可以寻找最优解，但是需要预先知道环境的准确信息，并且计算量很大。局部规划方法侧重于考虑机器人当前的局部环境信息，让机器人具有良好的避碰能力。很多机器人导航方法通常是局部的方法，因为它的信息获取仅仅依靠传感器系统获取的信息，并且随着环境的变化实时的发生变化。和全局规划方法向比较，局部规划方法更具有实时性和实用性。缺陷是仅仅依靠局部信息，有时会产生局部极点，无法保证机器人能顺利到达目的地。混合型方法试图结合全局和局部的优点，将全局规划的“粗”路径作为局部规划的子目标。从而引导机器人最终找到目标点。从机器人工作环境的角度区分规划方法，可以分为静态确定环境规划方法和动态时变环境规划方法。目前许多研究工作集中在静态环境下，如装配机器人；在动态环境下的规划问题已经引起了人们的重视，并且已经取得了一些成果，这将是今后的一个发展方向。路径规划问题具有如下特点1复杂性在复杂环境尤其是动态时变环境中，机器人路径规划非常复杂，且需要很大的计算量。2随机性复杂环境的变化往往存在很多随机性和不确定因素。动态障碍物的出现也带有随机性3多约束人的形状制约，机器人的运动存在几何约束和物理约束。几何约束是指机器而物理约束是指机器人的速度和加速度。4多目标机器人运动过程中路径性能要求存在多种目标，如路径最短，时间最优，安全性能最好，能源消耗最小。但它们之间往往存在冲突。机器人路径规划的方法可以按照两种标准进行分类一种标准是根据算法的不同,分为传统路径规划和智能路径规划。传统路径规划大多基于图论的思想,通过一定的方法建立几何模型,进行空间路径的搜索,包括自由空间法、图搜索法、栅格解耦法、动态规划算法等；智能路径规划是随着近年来人工智能的深入研究而发展起来的优化方法,其中有模糊逻辑法、神经网络法、遗传算法以及现在非常热门的仿生算法如蚁群算法、免疫算法、粒子群算法、蜂群算法等,智能算法能够模仿人或者动物的经验和习性,具有良好的非线性逼近能力和自组织学习能力；第二种分类标准是根据规划体对环境信息的认知程度,分为基于已知环境模型的全局路径规划和基于传感器信息的局部路径规划。22机器人路径规划理论机器人路径规划就是依据某种最优准则，在工作空间中寻找一条从起始状态到目标状态的避开障碍物的最优路径。路径规划是移动机器人领域的一个重要组成部分。它的任务是在具有障碍物的环境中，按照一定的评价标准，寻找一条从起始状态包括位置及姿态到达目标状态包括位置及姿态的无碰路径。在长期发展的过程中，智能避障3已逐步演化为一门独立的学科，其中主要包含了超声波测距原理的研究和避障算法的研究。由于避障过程解决的不只是机器人避开障碍物，还为机器人提供了轨迹的规划走向，所以，智能避障过程又被称为机器人轨迹规划。目前常用到的路径规划方法主要有人工势场法、栅格法、神经网络等。23栅格法231栅格法简介栅格法是由WEHOWDEN4在1968年提出来的，他在进行路径规划时采用了栅格来表示地图。栅格法属于环境建模技术方面的研究，也称作是单元分解建模。已经在许多机器人系统中得到应用，是使用上较为成功的一种方法，这属于一种近似的描述建模，当然它的离散特性也有利于栅格地图的创建和维护。该方法的特点是简单和易于实现，易于扩展到三维环境。但它对工作区域的大小有一定的要求，如果区域太大，将使栅格的数量急剧增加，使搜索存在组合爆炸的问题。栅格法是后来许多方法的一个基础，而且随着激光、摄像头对三维环境重建的发展来看，这种方法也将一直不断地发展下去。进行路径规划时我们用栅格表示地图，假设环境的最大长度为L，宽度为W，栅格的尺度可以根据需要确定值，在本论文里假设长和宽均为B，也就是假设每个栅格为一个正方形，那么栅格数就为（L/B）（W/B），环境MAP由栅格构成IMAPM0引1为整数其中表示该栅格为自由区域（即此栅格机器人可安全通过），表示该栅格为IMAPIMAP障碍区域（即此栅格机器人无法安全通过或者此栅格某部分机器人无法安全通过）。栅格法将机器人规划空间分解成一系列的具有二值信息的网络单元，工作空间分解成单元后则使用启发式算法在单元中搜索安全路径。搜索过程多采用四叉树或八叉树表示工作空间。基于四叉树的环境表示方法实质上是一种层次化的表达方式，是基于环境中非相似区域的不断递归分解。本论文采用的是八叉树的方式，栅格的一致性和规范性使得栅格空间中邻接关系的简单化。赋予每个栅格一个通行因子后，路径规划问题就变成在栅格网寻求两个栅格节点间的最优路径问题。栅格法以基本元素为最小栅格粒度，将地图进行栅格划分，基本元素位于自由区取值为0，处在障碍物区或包含障碍物区为1，这样在计算机中建立一幅可用于路径规划的地图。用尺寸相同的栅格对机器人的二维工作空间进行划分，栅格的大小以机器人自身的尺寸为准。若某个栅格范围内不含任何障碍物，则称此栅格为自由栅格；反之，称为障碍栅格。自由空间和障碍物均可表示为栅格块的集成。栅格法通过优化算法完成路径搜索，该法以栅格为单位记录环境信息，环境被量化成具有一定分辨率的栅格，栅格的大小直接影响着环境信息存储量的大小和规划时间的长短，栅格划分大了，环境信息存储量小，规划时间短，但分辨率下降。在密集环境下发现路径的能力减弱，栅格划分小了，环境分辨率高。在密集环境下发现路径的能力强，但环境信息存储量大，规划时间长，可以采用改进的栅格法弥补原栅格法的不足。这些方法虽然计算的实时性很强，便于机器人的动力学优化控制和实时路径规划，但却保证不了能够寻求到全局最优的路径。栅格法是将机器人工作环境分解为一系列具有二值信息的网格单元，采用均匀的栅格覆盖整个工作空间，从而将其分成被障碍物占据的栅格和自由的栅格，障碍物栅格和非障碍物栅格具有不同的识别值，然后用启发式算法在栅格中搜索一条无碰撞路径，即要求路经的栅格都必须是自由的。该方法以栅格为单位记录环境信息，环境被量化成具有一定分辨率的栅格，栅格的大小直接影响着环境信息存储量的大小和规划时间的长短。232栅格法算法原理简介移动机器人在二维平面上的有限运动区域（环境地图）上运动，其内部分布着有限多个静态障碍区，障碍物的坐标位置有栅格的编码表示。为了简单起见将移动机器人的模型可以转换为点状机器人，这样机器人就可以忽略不计，可以将静态障碍物的尺寸以障碍物的边缘分别向外扩展到机器人本体长、宽方向上最大尺寸的一半，经过这样的处理之后，可以使得障碍物的边缘为安全区域，并且各障碍物之间及障碍物与区域边界不想交。环境信息的描述要考虑三个重要的因素1如何将环境信息存储与计算机当中；2要求环境信息方便使用；3问题的求解要求有实时性和高效率性。才用栅格法表示环境，每个栅格中都有一个概率，概率为1表示这个栅格中存在障碍物或部分被障碍物占有，概率为0表示此栅格为自由区域，移动机器人可以自由通过。栅格大小的选取直接影响到算法的性能，栅格选的小，环境分辨率高，但抗干扰能力弱，环境信息存储量小，决策速度快，但分辨率下降，在密集障碍物环境中发现路径的能力减弱。在一般情况下，栅格的大小与机器人的移动步长相适应，即机器人的移动就可以转化为从一个完全可行栅格移动到另外一个完全可行栅格。则路径规划问题的一般表述如下设起始点的位置即为机器人的位置（假设用A表示），在整个栅格环境中运动，机器人的位置可以用起始位置的编号来表示。整个网络环境假设用MAP表示，即把MAP划分为一个个大小相同的66的方格，整个运动环境中的静止障碍物栅格区用（I1,2,3，N）表示，表示第I个障碍物区在整个环境为位IBIB置MAP中所占的区域的号码编号。依照不同的环境情况，障碍区域的信息可能已知，也可能未知。在机器人运动的每个时刻，将障碍物区映射入位置环境MAP，则在位置环境IMAP中的避障空间表示为其中Q为位置空间的某一个栅格位BIMAPQ,AB,置，表示机器人处于Q点。路径规划就是寻找从A的初始位置到目标位置（假设用AQB表示）的避障路径。运动空间中的每个栅格表示一个自由区域或者障碍区域，这些区域用如下函数来描述MAP（I）1表示I为障碍物区域，MAP（I）0表示I是自由区域。因此，整个运动环境转换为一个二进制方阵，即等价成一个二维数组，记为，这样BMAP障碍区域在中被划分为一个MAP（I）1的区域。BMAP根据栅格位置的不同，可以将栅分为中间栅格和边界栅格。面对中间栅格，下一步可有八个方位进行搜索，即东、南、西、北、东北、东南、西北、西南；面对边界栅格，则要去掉不可行的方位，顶角栅格只有三个方向可用，图21显示栅格为左下角栅格时，只有北，东北和东三个方向的栅格。北东北东图21左下角栅格若栅格为边界栅格时则有五个方向，如图22所示，在栅格为最左边界栅格时，则存在北，东北，东，东南，南，五个方向的栅格。北东北东南东南图22最左边界栅格233路径选择概率设在第I条路径的搜索中,当前的位置位于栅格U处,设与U相邻的完全可行方位的集合为V,V是V中的任一完全可行方位,在这里U和V均表示它们在环境地图中的栅格序号,那么集合V中任一完全可行方位被选择的概率公式为（21）VVUVKKV0IIP栅格U，V之间完全不可行栅格，之间完全可行越大,也就表明第I条路径从U到V的几率也就越大。P234栅格法优缺点分析优点简单、易于实现，易于扩展到三维环境。缺点对工作区域的大小有一定的要求，如果区域太大，将使栅格的数量急剧增加，使搜索存在组合爆炸的问题。24人工势场法241人工势场法原理人工势场法是由KHATIB于1985年提出的一种虚拟力法，实现了机械臂的实时避障，其基本思想是将机器人在环境中的运动视为一种虚拟的人工受力场中的运动，障碍物对机器人产生斥力，目标点对机器人产生引力，引力和斥力合力作为机器人的加速力，来控制机器人的运动方向，在合力的作用下机器人向目标点做安全无碰撞的运动。目标点对机器人产生的引力设为，矢量的方向是从机器人指向目标点，障碍物对机器人产生斥力F引引，方向是从障碍物指向机器人。引力和斥力产生的合力我们设为，则合力即为F引F机器人的加速力，受力状况如图23所示图23受力状况人工势场法简单，便于低层的实时控制，在实时避障和平滑的轨迹控制方面得到了广泛的应用，但是在很多环境下势场中存在大量势能为零的点，机器人一旦入这种点周围的“谷”区域，将被陷住，因而可能使机器人在到达目标点之前就停留在局部最优点。因而存在局部最优解的问题，容易产生死锁现象。为此，提出了许多新势场函数和局部极小逃逸等方法，但当环境变得更复杂时这个问题还是难以得到解决。人工势场法是迄今为止应用最广泛的移动机器人路径规划方法之一。该方法的特点是计算简洁、实时性强，便于数学描述，主要用于解决局部路径的避障规划问题。其基本思想是将机器人在环境中的运动视为一种在虚拟的人工受力场的运动。障碍物对机器人产生斥力，目标点产生引力。引力和斥力的合力控制机器人的运动方向，确定机器人的位置。经常使用的人工势场函数如公式22一255机器人在整个区域内所受的引力场定义为22MANGOAL1UQQ,2其中是正比例系数；是机器人Q口到目标的距离，由该引力场GOLGOL,GOALQ所生成的对机器人的引力为引力势能的负梯度公式23ANANGOALFQ该引力随机器人趋近于目标而成线性趋近于零。斥力场公式如24所示242OBSOBSREP11Q,2Q,U0其中，为正比例系数，为机器人到障碍物的最小距离，为机器人到障碍物OBSOBSQ的最近点，P。表示障碍物影响范围的正常数。所以该斥力场所对应的斥力为25REPREP2OBSOBSFQ11Q,2,0机器人所受的合力为引力和斥力的和为26TOALNREPF242势函数的确定KHATIB6首先提出了势场的概念，提出了一种只与系统位置有关的建立方法，并将之应用于机械臂的避碰问题。势场源有两类引力极和斥力极。系统不希望进入的区域或者障碍物属于斥力极，目标为引力极，对于目标引力极，定义抽象力为以该目标为参考位置的比例控制，对于斥力极，建立等势线与障碍物边缘形状相似的斥力场。系统所在的位势的势为有势极在该点产生的势之和，即障碍物的斥力势与目标的引力势迭加和,它的负梯度方向表达了机器人系统所受抽象力的方向，正是这种抽象力使系统绕开障碍物，朝向目标前进，如图24所示。图24势场受力机器人的工作空间为,空间中每一处X的势场值如公式27所示TXY27GOUUX其中和分别为相对于目标的引力场和相对于某个障碍物的斥力场。于是作用GUXO于机器人上的控制力公式为28GOF其中。势函数的选取应当满足连续可导等性质。通常GGOOFGRADX,FGRADUX的目标势函数为292GPG1KX则吸引力为目标势函数的负梯度210GGPGFGRADU所有的吸引力相当于空间位置闭环的比例控制,其中为比例因子，为机器人当前位置,K为目标位置矢量。GX243人工势场法的优缺点分析人工势场法相对自由空间法而言更适合于动态环境，以及多关节机械手的路径规划该法结构简单，便于低层的实时控制，在实时避障和平滑的轨迹控制方面，得到了广泛的应用。而其存在的主要问题是1缺乏全局信息。因而存在局部极值点的问题。当机器人处于局部极值点的时候，容易产生“锁死”现象，使机器人在到达目标点之前就停留在局部极值点。所谓局部极值点，是由于吸引势函数和排斥势函数分布在空间内，在某些区域，受多个势函数的作用，造成了局部极值点。障碍越密集，共同作用的势函数也越多，因而产生局部极值点的几率也就越大，因此人工势场法适用于障碍分散的情况。2N试点的选择。局部方法只考虑末端和控制点离障碍最近点，而控制点在移动机器人刚体姿态变化或关节式机械手运动时是变化的。3障碍物的近似描述。为了简化距离求解，用规则的几何体来近似描述连杆和障碍物，因此，需要对多面体进行合理的分解和组合，并保证尽可能少地浪费自由空间。4局部最优问题的解决当目标点对机器人产生的斥力与目标点对机器人产生的引力之和为零时,机器人就会出现局部最优点的问题,而无法达到最终的目标点,这时,通过在引力函数当中引入机器人的不断更新位置与目标位置的距离,而得以解决这个问题。25人工神经网络算法251人工神经网络算法概念神经网络7引的研究始于20世纪40年代，是在现代生物学研究人脑结构和功能成果的基础上提出来的。它作为一个高度并行的分布式系统，能较好地模拟人的形象思维，具有大规模并行协同处理能力、较强的容错能力、联想能力和较强的学习能力。该方法具有鲁棒性强等优点，在智能自主移动机器人路径规划中的应用已显示出其优越性，但神经网络中的权值设定比较困难。针对权值设定难的问题，国内外研究人员提出了很多改进算法，使神经网络与其他方法相结合来解决这一难题。如利用神经网络与遗传算法相结合实现具有学习能力的避障控制；利用神经网络与模糊逻辑相结合实现具有模糊推理功能的局部规划器；同样，利用神经网络与基于行为的算法相结合实现具有学习能力的行为融合和行为仲裁，使得系统的灵活性加强。神经网络作为人工智能的重要内容,在移动机器人路径规划研究中得到了广泛关注,如GHATEE等将HOPFIELD神经网络应用到路径距离的优化中，近年来加拿大学者SIMON提出一种新的生物启发动态神经网络模型,将神经网络的神经元与二维规划空间的离散坐标对应起来,通过规定障碍物和非障碍物对神经元输入激励和抑制的不同,直接计算相关神经元的输出,由此判定机器人的运行方向。由于该神经网络不需要学习训练过程,路径规划实时性好,同时利用神经网络本身的快速衰减特性,较好地解决了机器人路径规划的死区问题。神经网络算法的研究始于20世纪40年代，是在现代生物学研究人脑结构和功能成果的基础上提出来的。它作为一个高度并行的分布式系统，能较好地模拟人的形象思维，具有大规模并行协同处理能力、较强的容错能力、联想能力和较强的学习能力。该方法具有鲁棒性强等优点，在智能自主移动机器人路径规划中的应用已显示出其优越性，但神经网络中的权值设定比较困难。针对权值设定难的问题，国内外研究人员提出了很多改进算法，使神经网络与其他方法相结合来解决这一难题。如利用神经网络与遗传算法相结合实现具有学习能力的避障控制；利用神经网络与模糊逻辑相结合实现具有模糊推理功能的局部规划器；同样，利用神经网络与基于行为的算法相结合实现具有学习能力的行为融合和行为仲裁，使得系统的灵活性加强。人工神经网络也被称为神经网络连接模式，它的行为特征是分布式并行处理算法的数学模型。网络依赖于复杂的系统，通过调整内部之间的联系，以实现节能的目的和完成信息处理。优点人工神经网络算法研究始于20世纪40年代，是在现代生物学研究人脑结构和功能成果的基础上提出来的。它作为一个高度并行的分布式系统，能较好地模拟人的形象思维，具有大规模并行协同处理能力、较强的容错能力、联想能力和较强的学习能力。该方法具有鲁棒性强等优点，在智能自主移动机器人路径规划中的应用已显示出其优越性。缺点神经网络中的权值设定比较困难。252人工神经网络算法理论基础在人工神经网络路径规划算法中设计了一个检测器，它实际上是一个神经网络分类器。利用检测器在路径规划的过程中始终检测着路径点的位置，由神经网络分类器判断X,Y该点是否在障碍物内即是否与障碍物相碰并将检测结果返回系统神经网络分类器就是在路径点到一个障碍物的罚函数的神经网络中间层和顶层结点的激发函数取为阶跃函数8则中间层的每个结点是决定该结点是否满足它的限定条件，若满足，则输出1，否则输出为0，若所有中间点均满足则顶层输出为1，它表示该点在障碍物内8若中间点检测出其中至少有一个不满足限制条件，顶层输出便为0，它表示该点在障碍物外。系统根据检测器返回的信息选择路径点的动态运动方程，若路径点在障碍物内则按动态运动方程（211）、（212）移动。若路径点在障碍物之外，则按动态方程（213）移动。即若路径点在障碍物外或障碍物内的路径点一旦移出了障碍物就仅按减少路径长的方向移动，不再向远离障碍物的方向移动，从而使路径能快速收敛到无碰的最短路径。下面给出改进的快速神经网络最短路径规划算法，在此作了3点假设障碍物是多边形围成的平面图形或者是圆形的平面图形；机器人为圆形点机器人，计算时障碍物的尺寸按机器人的半径作了适当拓展；障碍物为静止的。步骤1输入出发点，及目标点的坐标，对于，初始路径一般12PX,YNPX,YT0取为出发点到目标点的直线上均匀分布的点列,当时有公式2111I1NXIX（211）INI11YY2,3步骤2对于路径点用检测器检测是否在障碍物内。IPX,Y2,3N1步骤3若在障碍物内8则按下列运动方程移动。I方程212为212I1LI1IKMKKCOIHMIXMKI1LI1IKKKCOIHMIYMKX2XFIFIYYFIFI方程213为（213）I1LI1ICOIHI1LI1ICIIX2XFIFIPXYYFIFIQY其中方程212用于位于多边形的障碍物内的情况，方程213用于位于IPX,IPX,Y圆心在P,Q的圆形障碍物内的情况。若在障碍物之外，则按运动方程214移动IPX,Y214I2I1IIIIXXYY步骤4重复执行步骤2，步骤3直到路径收敛。这里，整条路径总能量函数的定义与原算法相同，一个点到一个障碍物的罚函数的神经网络结构的中间层第M个结点的输出改为215HMOFI中间层第M个结点的激发函数改为216HMHMXT1FETTLOGT其中是相应于障碍物每一条边的初始温度，即可以根据障碍物的形状设定各边的不同M的初始温度，这样对于一些不对称图形可避免其罚函数曲面形成一边倒的情况，从而避免路径规划收敛到局部极小值。当障碍物是圆形的平面图形时不等式的个数取为一，即中间层只有一个结点，且输入为217222HIIIRXOYQ其中R为圆形障碍物的半径，（P,Q）为圆形障碍物的圆心。26蚁群算法261蚁群算法概述目标机器人在有障碍物的工作环境中工作时，通过两组蚂蚁相向搜索，优化寻找出一条从给定起始点到终止点的较优的运动路径，使机器人在运动过程中能安全、无碰撞地绕过所有的障碍物，且所走路径最短。方法用两组蚂蚁分别以机器人出发点和目标点为出发点，按照一定的概率搜索算法相向搜索。本课题要研究这一概率搜索算法及其编程实现，并用C语言给出仿真结果。原理生物学的研究表明虽然单个蚂蚁的能力非常有限，但多个蚂蚁构成的群体具有找到蚁穴与食物之间最短路径的能力。这种能力是靠其在所经过的路径上留下的一种挥发性分泌物，即信息素PHEROMONE来实现的。蚂蚁在路径上前进时会根据前边走过的蚂蚁所留下的信息素选择其要走的路径，其选择一条路径的概率与该路经上分泌物的强度成正比。因此，由大量蚂蚁组成的群体的集体行为实际上构成一种学习信息的正反馈现象某一条路径走过的蚂蚁越多，后面的蚂蚁选择该路径的可能性就越大。蚂蚁的个体之间通过这种信息的交流寻求通向食物的最短路径。262蚁群算法理论基础算法分析步骤1在屏幕上画一个1010的栅格，格子的号码从1到100，栅格障碍物的号码随机生成（设有20个障碍物），并按照生成的号码在图中用阴影表示。步骤2设定起点和终点的位置BEGIN5,END99。因为障碍物是随机生成的，所以设定的起点和终点有可能与障碍物的号码冲突。为了避免出现这样的情况，需用另外的函数来检测，如果设定的起点或者终点恰好就是随机生成的障碍物时，就要再重新设定起点和终点的方格号码。为了便于后续距离的计算，将终点END转换为横纵坐标横坐标ENDXEND1/Y1；纵坐标ENDYEND1Y1。步骤3初始化。将每两个方格之间的信息素初始化为一个很小的常数值HORMONEIJHORMONEJI05起点和终点处均放置一定数量的蚂蚁（本程序中分别放两只），并将它们固定地分配到起点和终点地四周（一个方格放一只）。对于每一只蚂蚁，将它们所在的方格号码加到禁忌表中。步骤4下一步要走的方格的选择。每只蚂蚁在自己领接的（8个）非障碍物的格子中（CIK0）选择下一步要走的方格。同样运用ACS算法中选择结点的方法218KKIJ20JTABUIJKIJKIK2TABURGMXHORNETF,TEMP1QP,JTABU,RTF如果否则也是初始设定的参数，TEMP1是一个0到1之间的随机数。如果TEMP1按照最大信息素选择QJ，否则计算转移概率，按赌轮盘规则选择J，同时将J加入到禁忌表中。是当前点转移到方格J的启发函数。如果是起点的蚂蚁，它的启发函数就是它领接的2F各点到终点的距离的倒数，。终点的蚂蚁就恰好相反。2IJF1/D设X,Y分别表示将要走的点的横纵坐标，距离21922IJXENYEND步骤5信息素局部更新。每只蚂蚁走完一步后，用下式更新该边上的信息素。220KQ1KI,JSUMTAOL0，当蚂蚁走过方格时，否则LK是蚂蚁K从起点到当前方格所走过的路径长度。步骤6计算距离看是否有两只蚂蚁可以相遇。当有从起点和终点出发的两只蚂蚁相遇时，一次搜索过程结束，将这两只蚂蚁所走过的路径相加，就得到了一次循环中从起点到终点得最佳路径。对每两只蚂蚁I，J用记录蚂蚁I在T时刻所在方格的横坐标和纵坐标，有0X,Y2210XTABUIT1/Y2220YTABUIT1Y同样，用，记录蚂蚁J在T时刻所在方格的横坐标和纵坐标，有1XY2231XTJT/224YABU1Y如果（或者为1，）则说明蚂蚁I,J此刻相遇了。22010XY2步骤7信息素全局更新。一次循环搜索完毕之后，要对最佳路径上的信息素进行更新。方法同ACS算法225NEWOLDIJIJKHORM1ALFHRMNEAFHSUTOQ,KIJSUTABSTD0当蚂蚁走过的方格属于最佳路径时，否则27本章小结本章从机器人路径规划演示平台的历史和现状出发，对比了国内外的不同发展状况，并且对机器人路径规划领域的研究方向进行了综述。着重介绍了机器人在避障与路径规划中常用的算法，对其中的栅格法，人工势场算法，和神经网络算法进行了逐一的分析和详细阐述。此外，本章还着重分析了栅格法的实现原理和人工势场法的建模实现原理。3机器人路径规划演示平台设计系统的VC实现31软件介绍311VC简介VISUALC60，简称VC或者VC60，是由微软公司推出的一款C编译器，是将“高级语言”翻译为“机器语言”的程序。VISUALC60是一个功能强大的可视化软件开发工具，因此它不仅是一个C编译器，而且是一个基于WINDOWS操作系统的可视化集成开发环境（INTEGRATEDDEVELOPMENTENVIRONMENT，IDE）。VISUALC60由许多组件组成，包括编辑器、调试器以及程序向导APPWIZARD、类向导CLASSWIZARD等开发工具，这些组件通过一个名为DEVELOPERSTUDIO的组件集成为和谐的开发环境，是MICROSOFT的主力软件产品，也是日常应用非常广泛的一个软件。312VC安装使用VC的安装相对比较简单，将下载的VC软件按照提示，顺序安装即可。VC的安装步骤如下所示（1）双击VC的桌面图标VC60。（2）在菜单文件中点击新建按钮，然后在PROJECTS里点击工程MFCAPPWIZARD，下一步选择单文档，其余设置选择默认即可。（3）然后再次点击文件的新建，然后在FILES里选择CSOURCEFILE。（4）一直默认下一步即可，然后就可以在出现的编辑区域中编写代码。（5）写好代码后，点击工具栏中的COMPILE按钮，编译源代码看是否报错，若无错误，点击BUILD按钮运行；若报错，则在编辑区下方有提示问题的所在，双击报错的代码行，会在程序中显示出错的位置，在提示的位置中做修改后重复上面的工作，也可以点击工具栏中的感叹号或者直接点击快捷键F9运行。313VC功能优势VISUALC是一个功能强大的可视化软件开发工具。VISUALC已成为专业程序员进行软件开发的首选工具。VISUALC60以拥有“语法高亮”，自动编译功能以及高级除错功能而著称。比如，它允许用户进行远程调试，单步执行等。还有允许用户在调试期间重新编译被修改的代码，而不必重新启动正在调试的程序。其编译及创建预编译头文件STDAFXH、最小重建功能及累加连结LINK著称。这些特征明显缩短程序编辑、编译及连结的时间花费，在大型软件计划上尤其显著。这也是选用VC实现机器人路径规划演示平台设计的重要原因。32机器人路径规划演示平台系统的总体设计321设计名称机器人路径规划演示平台设