学校代号学密号级湖南大学硕士学位论文静态场景中机器人避障规划问题的模型和算法研究万方数据，万方数据湖南大学学位论文原创性声明本人郑重声明所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本论文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名凌窃臼中日期们肄斗月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于．保密口，在年解密后适用本授权书。．不保密口请在以上相应方框内打””作者签名期和罗年月日导师签名歹孝荔雾墨日期缈年≯月乡日万方数据静态场景中机器人避障规划问题的模型和算法研究摘要机器人避障与路径规划是移动机器人研究的重要方向之，也是移动机器人导航技术中不可缺少的重要组成部分。静态场景中机器人避障与路径规划是机器人全局路径规划的核心内容，也是局部路径规划的基础。本论文深入研究静态场景中机器人避障规划的数学模型和计算算法，试图提供此类问题的完整解决方案，具有定的理论意义和实际价值。本论文具体研究了如下两个方面的问题本论文采用可视图法完整地建立了静态场景中机器人避障全局路径规划的数学模型。首先建立了机器人避障问题的环境模型，构建了机器人避障问题的可视网络图其次，针对四种不同情形建立了机器人全局路径规划的非线性整数规划模型，分别为单目标点下机器人避障最短路程路径模型多目标点下机器人避障最短路程路径模型单目标点下机器人避障最短时间路径模型多目标点下机器人避障最短时间路径模型。本论文针对静态场景中机器人避障全局路径规划的不同情形，在最短路的算法基础上，分别构建了相应的计算算法。主要包括单目标点下机器人避障最短路程路径的求解算法多目标点下机器人避障最短路程路径求解算法单目标点下机器人避障最短时间路径求解算法多目标点下机器人避障最短时间路径求解算法。为验证算法的有效性，本论文还针对个具体的机器人避障实例进行实证研究，利用编程求解，分别求解出机器人避障最短路程路径和最短时间路径，实证结果表明算法有效。本论文最后还选取部分障碍物和目标点，考察障碍物移动和目标点移动时最短路径的变化情况，以此检验模型和进行敏感性分析。关键词避障路径规划机器人导航技术数学模型算法万方数据硕士学位论文，．，．．，．，．，万方数据静态场景中机器人避障规划问题的模型和算法研究，万方数据硕士学位论文目录学位论文原创性声明和学位论文版权使用授权书摘要Ⅲ第章绪论．引言．机器人避障规划问题的研究目的与意义．机器人避障规划问题国内外研究现状．本论文研究的主要内容与创新点问题的提出研究的主要内容研究的目标拟解决的关键问题本论文的创新点．本论文的章节安排第二章预备知识．两圆的内外公切线点到圆的切线两圆的外公切线两圆的内公切线最短路问题及算法算法．避障问题的预备事项禁入区的构造最优路径的预备证明第三章静态场景中机器人避障路径规划问题的数学模型万方数据静态场景中机器人避障规划问题的模型和算法研究．环境模型障碍物区域模型扩充障碍物区域的数学模型可视图的构建模型．单目标点最短路径模型．多目标点最短路径模型．单目标点最速路径模型．多目标点最速路径模型．固定路径的最优圆弧模型第四章静态场景中机器人避障路径规划问题的求解算法．单目标点最短路径的求解算法．有中间目标点最短路径的求解算法．单目标点最速路径的求解算法．多目标点最速路径的求解算法第五章实证结果与分析．实证结果环境模型单目标点的最短路径多目标点最短路径的计算结果单目标点最速路径的计算结果．模型检验和敏感性分析考察障碍物移动时最短路径的变化考察目标点移动时最短路径的变化结论参考文献致谢万方数据硕士学位论文第章绪论引言作为世纪影响最大的发明之，机器人历经五十余年的发展己取得了长足进步。现阶段，由于机器人技术越来越先进，机器人学科也彰显出非常强大的生命力，从个角度来讲，它能够反映出目前的自动化与信息科技以及系统控制和集成科技的发展水平。构成机器人学科的个核心部分就是移动机器人的相关研究，而移动机器人探究的核心方向之就是机器人避障路径规划心。构成移动机器人导航技术的个关键部分就是机器人避障路径规划，同时它也是移动机器人必不可少的个环节，它体现出了在运动期间，机器人和周边环境的交互能力，是移动机器人顺利做完任务的基础№。所以，机器人应用中的项核心技术就是机器人避障路径规划，采用合适的避障路径方面能减少机器人的作业时间，同时也可以减少资源投入。避障路径规划问题的典型描述是在具有障碍物的场景中，寻找出机器人从起始点到目标点的运动路径且无碰撞地通过所有障碍物．路径规划属于组合优化的范畴．路径规划的核心模型是组合优化模型，该模型是类非线性规划模型。而路径规划的核心算法是最短路径算法。最短路径算法有很多，包括图论方法中的算法与算法以启发式搜索方法为主要方法的木算法以动态规划方法为主要方法的木算法神经网络方法等。本论文的研究目的在于在有障碍物的平面场景中，从起始点到目标点之间规划出条绕过障碍物的路程最短路径或时间最少路径。其中任何个障碍物的面积位置以及形状都是已经知晓的，同时保持静止状态，这种场景就被叫做静态场景。在很早之前，就有专家探究机器人避障规划的算法以及相关的数学模型，不过在各个国家学者们所获得的探究成果上，深层次探究其具体应用以及理论创新依然有很重要的意义。本章先是对探究机器人避障问题的算法以及数学模型的意义进行了详细说明，之后介绍国内外学者在此领域所取得的成果，最后明确本论文的探究内容以及论文框架。．机器人避障规划问置的研究目的与意义作为知识经济时代最热门的高科技领域之，机器人科学研究和技术开发极具战略以及创新性，在很大程度上影响着社会经济的发展信息化水平以及国家万方数据静态场景中机器人避障规划问题的模型和算法研究安全哺。从年出现之后，机器人技术历经了五十余年的发展，其理论研究技术开发及工程应用都获得了很好的发展。机器人技术属于门交叉技术，其中对不同高新技术领域以及学科进行了综合。它融合了互联网技术控制论以及信息传感技术机械学人工智能电子学仿生学等多学科而形成的综合技术，是当今世界科学技术研究最活跃应用最广泛的领域之，也是个国家工业自动化水平的主要标志之瞄。机器人技术开发能力和工程应用水平是个国家高科技的象征之，也是个国家经济实力的体现，因此，不少国家都将机器人技术当成世纪最优先发展的方向之。现阶段，在工业农业航空航天医学等领域，移动机器人都发挥了重要的作用，并且应用越来越广泛，几乎渗透到所有的领域。社会对移动机器人的智能化和自动化需求也越来越大，将环境场景感知掌控与实施策划以及决策等功能进行融合的智能化机器人也获得了很好而快速的发展。智能机器人可以自动获取外部环境信息，同时对信息数据进行处理以及智能辨别，进而就产生了可以让机器人感知的符号化环境模型，之后按照该模型完成相关的决策规划以及控制任务。在规划决策的任务系统中，个重要的任务就是按照采集的障碍物信息对避开障碍物的路径进行规划，这就是所谓的避障规划随，。始于二十世纪七十年代的机器人避障路径规划是移动智能机器人学中的个重要分支，直以来都是机器人探究领域的核心内容，目前各个国家的专家依然将探究重心放在这个领域上。在存在障碍物的场景中，按照机器人已有的行进标准，让机器人从最初位置避开障碍物到达目的位置，这就是避障路径规划的任务。根据障碍物的各种情形以及机器人了解环境数据情况，将避障路径规划划分成种类型，分别是未知环境信息动态与静态障碍物的避障规划，己知环境信息动态与静态障碍物的避障规划№。已知了障碍物的形状等数据，但并非工作区域里的每条路径都是无障碍的空路径，在无障碍的空路径中也并非就是最佳的条路径，这就是已知环境信息的避障路径规划。所以，避障路径规划在已知的环境信息中，仍要处理很多问题。如果机器人对环境信息数据已经非常了解，通过全局路径规划确定条能从最初位置顺利到达目的位置的路径，另外能对有关行进时的信息展开优化，有关这个方向各国专家都获得了定的研究成果。但在真实环境中，障碍物的复杂情形下，往往不能完成整体上的全局避障路径规划，更多的办法是经过各种局部避障路径规划进而得到相似的无碰撞的全局路径。所以，目前还是缺少完善有效的避障方式和全局路径规划。而对未知环境信息静态障碍物避障路径规划问题进行探究的基础就是对己知环境信息静态障碍物避障路径规划问题进行的探究。总而言之，对移动机器人在外界静态已知障碍物环境下的避障路径规划方式进行深层次地探究具有非常关键的意义，同时也有定的理论价值。万方数据硕士学位论文．机器人避障规划问题国内外研究现状机器人探究领域的个核心问题就是机器人路径规划问题，也就是按照种优化原则时间最短路径最小，在其工作范围内明确条可以避开障碍物的最佳路径№。按照机器人了解环境信息的具体情况，我们将其划分成种类型，分别是环境信息些或全部未知的局部路径规划环境信息全部已知的全局路径规划口。前者经常使用的方法包括遗传与人工势场法以及模糊逻辑算法错误未定义书签．。本论文主要研究的是静态场景已知的全局路径规划，为此，对局部路径规划不再赘述。对于环境信息完全已知的静态场景情形下的避障规划问题，截止到现在已有非常多的处理方法。全局路径规划共涉及到个子问题，分别是路径搜索方式以及环境建模。其中后者经常采取的方法包括自由空间法可视图法以及栅格法。前者使用的方法包括术最优算法以最短路算法为基础的改进算法木算法。顺利实现机器人无碰撞路径规划就是环境信息已知的全局路径规划的目标，国内外现有的主要方法有以下几种可视图法。年，提出了该方法。该方法视机器人为单独的点，将其他各项点，比如目标点机器人以及多边形障碍物进行连接，要求任何个连接都不可以跨过障碍物，也就是说，直线必须是能够看到的。因此，最优路径问题就转变成从起始位置到终点位置经过这些可视直线的最小距离问题。这个算法简单并能找到最短路径，不过如果将机器人看成点，那么就会让机器人跨过障碍物顶点时和它的距离太小。这个算法会花费很长的搜索时间，而且其时间复杂度为胛，其中玎表示障碍物顶点的个数。由此，法以及法都进步完善了可视图法。法用障碍物的切线表示弧，解决了可视图法中障碍物不能是圆形的问题。法在防止机器人接触到障碍物的同时也拉长了路径长度。杨淮清和其他专家№共同建立了种以可视图法为基础的移动机器人路径规划算法。这个算法