[硕士论文精品]移动机器人导航中的路径规划与运动控制技术研究

武汉科技大学硕士学位论文第1页摘要路径规划和运动控制是自主轮式移动机器人领域的重要研究方向，也是机器人实现自主导航、完成复杂智能任务的关键，集中体现了机器人的感知能力和智能水平。本文针对栅格环境地图模型下，移动机器人上位机的路径规划控制器执行周期短这一特点，采用基于启发式搜索理论的搜索算法设计路径规划控制器。同时针对轮式移动机器人非完整运动学模型，设计出轨迹跟踪控制器和路径跟踪控制器，从而完成了移动机器人自主导航目标。本文主要工作如下首先，介绍了移动机器人导航技术的发展情况。并且阐述了移动机器入导航研究中的关键技术，包括路径规划和运动控制。以及这两项关键技术在移动机器人导航中的应用范围和应用中需解决关键问题。其次，详细阐述了人工智能领域的启发式搜索理论，包括启发式信息和估价函数以及搜索算法的可采纳性。在充分考虑搜索的实时性、最优性需求以及估价函数死区问题的基础上设计了基于图搜索策略ASTAR算法的路径规划控制器。该控制器能够在全局占有栅格地图中高效地寻求最优路径。再次，详尽分析了轮式移动机器人非完整运动学模型。针对带时间参数的行走轨迹，通过构造一种简单的虚拟反馈变量，结合LYAPUNOV直接法设计了基于BACKSTEPPING的时变反馈轨迹跟踪控制器。针对由离散路径点组成的行走路径，采用LYAPUNOV直接法设计出基于点镇定原理的路径跟踪控制器。并且通过设计仿真实验对上述控制器进行了验证。最后，介绍了实验室JPOT轮式移动机器人的系统架构。通过对路径规划控制器和路径跟踪控制器进行算法的移植来设计移动机器人自主导航实验。利用采集到的实验数据详尽分析了控制器的执行性能，同时证明由于采用合理的设计思路和简化策略，不仅增强了控制器算法移植的可操作性，而且能够让控制器运行更加稳定。关键词移动机器人；导航；路径规划；轨迹跟踪；路径跟踪第1I页武汉科技大学硕士学位论文ABSTRACTPATHPLANANDMOTIONCONTROLPROBLEMSARETHEKEYISSUESFORAUTONOMOUSWHEELEDMOBILEROBOTSTHESEPROBLEMSALENOTONLYVERYIMPORTANTTOACCOMPLISHAUTONOMOUSNAVIGATIONANDOTHERCOMPLEXINTELLIGENTTASKS，BUTALSOEMBODYPERCEPTIONABILITYANDINTELLIGENCEOFROBOTSTHEMODELOFTHEENVIRONMENTIS鲥DM印INWHICHTHEROBOTNEEDSTORUNTHECONTROLLEROFPATHPLANFREQUENTLY,SOHEURISTICSEARCHALGORITHMISUSEDTODESIGNTHECONTROLLEROFPATHPLANTHISPAPERDESIGNSTHECONTROLLEROFTRAJECTORYTRACKINGANDPATHFOLLOWINGBASEDONNONHOLONOMICKINEMATICMODELOFWHEELEDMOBILEROBOT，ANDCOMPLETESTHEGOALOFAUTONOMOUSNAVIGATIONFORTHEMOBILEROBOTTHEMAINRESEARCHACHIEVEMENTSAREASFOLLOWINGSFIRSTLY,DEVELOPMENTOFNAVIGATIONTECHNOLOGYISINTRODUCEDTHEKEYTECHNOLOGIESOFPATHPLANANDMOTIONCONTROLALEANALYZEDTHEMETHODSAREPROPOSEDTOSOLVETHEPROBLEMSINTHEAPPLICATIONOFPATHPLANANDMOTIONCONTR01SECONDLY,HEURISTICSEARCHTHEORYINARTIFICIALINTELLIGENCEISINTRODUCED，INCLUDINGHEURISTICINFORMATION，EVALUATIONFUNCTIONANDADMISSIBILITYOFSEARCHALGORITHMTHECONTROLLEROFPATHPLANBASEDONGRAPHSEARCHALGORITHMASTARALGORITHMISDESIGNEDBYCONSIDERINGREALTIMEPROPERTY,OPTIMALITYABOUTTHESEARCHALGORITHMANDTHEPROBLEMOFDEADZONETHECONTROLLERCANCOMPUTETHEPATHEFFICIENTLYANDFINDTHEOPTIMALPATHINTHEGLOBALOCCUPANCY鲥DMAPTHIRDLY,NONHOLONOMICKINEMATICMODELOFWHEELEDMOBILEROBOTISANALYZEDUSINGTHEIDEAOFINTEGRALBACKSTEPPING，ASIMPLEVIRTUALFEEDBACKVARIABLEISPROPOSEDANDATIMEVARYINGFEEDBACKCONTROLLEROFTRAJECTORYTRACKINGISDESIGNEDVIALYAPUNOVDIRECTMETHODTHEWAYOFFOLLOWINGTHEPATHWHICHISCOMBINEDBYTHEDISCRETEWAYPOINTSISBYUSINGTHECONTROLLEROFPATHFOLLOWINGTHISCONTROLLERISDESIGNEDVIALYAPUNOVDIRECTMETHODANDTHETHEORYOFPOINTSTABILIZATIONSIMULATIONEXPERIMENTSVERIFYTHECORRECTNESSANDEFFECTIVENESSOFTHECONTROLLERSOFTRAJECTORYTRACKINGANDPATHFOLLOWINGFINALLY,SYSTEMSTRUCTUREOFTHEJPOTROBOTISINTRODUCEDTHEAUTONOMOUSNAVIGATIONEXPERIMENTSFORTHEMOBILEROBOTARODESIGNEDBYUSINGTHEPROGRAMSOFTHECONTROLLERSOFTRAJECTORYTRACKINGANDPATHFOLLOWINGTHEPROGRAMSWHICHCANBERUNINTHEUPPERCOMPUTEROFTHEROBOTALEWRITTENINCLANGUAGETHEEXPERIMENTALRESULTSINDICATETHEPERFORMANCEEVALUATIONFORTHECONTROLLERSBECAUSEOFSIMPLIFYINGALGORITHMSFORTHECONTROLLERS，THEPROGRAMSFORTHECONTROLLERSCANBEEASILYWRITTENANDTHECONTROLLERSARESTABLEKEYWORDSMOBILEROBOT；NAVIGATION；PATHPLAN；TRAJECTORYTRACKING；PATHFOLLOWING武汉科技大学研究生学位论文创新性声明本人郑重声明所呈交的学位论文是本人在导师指导下，独立进行夥究所取得的成果。除了文中已经注明引用的内容或属合作研究共同完成醮工作外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。申请学位论文与资料若有不实之处，本人承担一切相关责任。论文作者签名薹L。日期翌望研究生学位论文版权使用授权声明本论文的研究成果归武汉科技大学所有，其研究内容不得以其它单位的名义发表。本人完全了解武汉科技大学有关保留、使用学位论文的规定，同意学校保留并向有关部门按照武汉科技大学关于研究生学位论文收录工作的规定执行送交论文的复印件和电子版本，允许论文被查阅和借阅，同意学校将本论文的全部或部分内容编入学校认可的国家相关数据库进行检索和对外服务。论文作者签名垂一指导教师签名，魉习期圣竺2兰兰堡武汉科技大学硕士学位论文第L页第一章绪论在人类发展的历史长河中，许多阶段都出现了一些足以促使人类文明产生巨大进步的发明创造。比如原始社会，人类学会利用火来烘烤食物，学会制作石器工具用来耕作和捕猎。到了奴隶社会，出现了青铜器和传递文明的文字。发展到了封建社会，出现了铁器及具有那个阶段代表意义的中国古代四大发明。然而真正使得人类社会发展出现巨大飞跃的是以英国人瓦特改良蒸汽机为代表的，一系列技术革命引起的从手工劳动向动力机器生产的转变。这种转变成为欧洲工业革命的开端，此后短短的二、三百年间，人类便完成了蒸汽时代电气时代信息时代的过渡。直到今天，我们仍旧在孜孜不倦地研究和发展更先进、更智能化的机器人，为的是不仅仅在工业生产上代替人力，而是让机器人在日常生活中为我们服务，乃至帮助我们去探索更多未知的领域。机器人的英文单词来源于捷克语“ROBOTA，意思是“劳役、苦工“。1983年1月，美国机器人学会对工业机器人给出了定义“机器人是一种可编程和多功能的，用来搬运材料、零件、工具的操作机；或是为了执行不同的任务而具有可改变和可编程动作的专门系统“。现如今，机器人不再是工业上具有单一职能的生产机器，其工作环境也从单纯的室内环境变成了各种复杂的环境，包括水下、地面、空中甚至外太空等。其中地面作为人类活动最密集的场所，同时也是移动机器人应用最广泛的领域。专家、学者们针对智能移动机器人更是展开了深入的研究。移动机器人导航问题一直以来都是移动机器人研究方向上的热点。移动机器人的导航包括环境地图创建，机器人定位，路径规划，运动控制等关键问题。其中路径规划与运动控制二者紧密联系，互相影响，这两方面的内容直接决定移动机器人导航执行效果的好坏。本文旨在实现移动机器人导航功能的目的下对这两方面的内容进行研究和设计实现。11课题研究的意义移动机器人按其运动机构来分类，一般分为腿式移动机器人和轮式移动机器人WHEELCDMOBILEROBOT。轮式移动机器人相对于腿式移动机器人来说机械构造更简单，运行更稳定，执行效率更高。所以这些因素都促成了轮式移动机器人在移动机器人种类中的主流地位。智能化的轮式移动机器人具有高度自识别、自规划、自适应的能力，适合在复杂的非结构化的环境中工作。其目标是在无人干预、无需对环境做任何规定和改变的前提下有目的地移动和完成相应任务。因此，轮式移动机器人的自主导航便是这一系列应用的必要条件。在此基础上，轮式移动机器人可以完成诸如大型博物馆的导游，家庭打扫地面卫生的保姆，探索外星球或者危险环境的探索车，医院里传送食物和药品的服务机器人，工厂里运送大型部件的自主导向车，物流码头集装箱自主运输车等各种工作。路径规划和运动控制作为轮式移动机器人导航的重要组成部分，涉及到基于占有栅格地图的路径规划，和直接决定移动机器人执行效果的路径跟踪和自主避障等问题。目第2页武汉科技大学硕士学位论文前已存在许多优化算法用来研究移动机器人路径规划和运动控制，但不少算法都存在一定的局限性，比如反应时间慢，可移植性不佳。为了使移动机器人在实时动态环境中，充分利用已有的运动学模型，迅速高效的执行导航工作，选择合适的路径规划和运动控制算法是非常重要的研究课题。本文根据机器人导航过程中对程序执行实时性的要求，分别针对路径规划和运动控制这两个问题进行算法的研究和设计。12移动机器人导航技术研究现状与进展轮式移动机器人导航是指移动机器人通过传感器感知环境和自身状态，实现在有障碍物的环境中面向目标的自主运动。导航主要解决四方面的问题1用一定的算法对所获传感器的信息进行处理并建立全局环境地图模型；2通过一定的检测手段获取移动机器人在空间中的位置、方向以及所处局部环境的信息；3寻找一条最优或近似最优的无碰路径，实现移动机器人安全移动的路径规划；4控制算法使得机器人按照规划出的路径进行移动，同时针对路径上出现的障碍物进行实时路径修正及避碰。移动机器人常见的导航方式有磁导航、激光导航、视觉导航、卫星导航等。1电磁导航电磁导航也称为地下埋线导航，是20世纪50年代美国开发的，到20世纪70年代这种导航方式迅速发展并应用于柔性生产。其原理是在路径上连续埋设多条引导电缆，分别流过不同频率的电流，通过感应线圈对电流的检测来感知路径信息，并进行有效跟踪。中国科学院沈阳自动化研究所已生产出基于电磁导航的多代移动机器人产品。国外SWISSLOG公司，针对大型工厂、物流仓库和分配中心，设计了多款高效AGVAUTONOMOUSGUIDEDVEHICLE。电磁导航技术简单实用，但其成本高，改造和维护困难。2激光导航激光导航是准确的说是一种多传感器信息融合导航，需要利用装配在机器人上的里程计和激光测距仪。将里程计采集的数据进行航迹推算结合激光测距仪实时扫描的数据与环境地图的匹配，来获得机器人在环境中的精确位姿。依照位姿信息，机器人就可以完成现有路径的跟踪。美国卡耐基梅隆大学机器人实验室和德国波恩大学计算机科学学院联合开发的导游机器人MINERVA一直在美国国家历史博物馆工作，MINERVA能够在拥挤的人群中自由移动并且精确的定位，完成各项导游任务。3视觉导航视觉导航方式探测信号范围宽、获取信息完整，且作为视觉传感器的双目或者单目摄像头价格成本较低。在视觉导航系统中，目前国内外应用最多的是采用在移动机器人上安装车载摄像机的基于局部视觉的导航方式。BOLEY等川研制的移动机器人利用车载摄像机和较少的传感器通过识别路标进行导航，比直接采用卡尔曼滤波器获得了更小的延迟，并有效抑制了噪声。视觉导航中图像处理计算量大、实时性差始终是阻碍其发展的瓶颈，为了提高导航系统的实时性和导航精度，仍需研究更加合理的图像处理方法。4卫星导航GPS全球定位系统是以距离作为基本的观测量，通过对四颗GPS卫星同时进行伪距武汉科技大学硕士学位论文第3页离测量计算出接收机的位置。机器人通过安装卫星信号接收装置，可以实现自身定位，无论其在室内还是室外。“等【6】先利用GPS信号对野外环境中的机器人进行粗定位，然后利用全景图像数据精确定位机器人。仿照卫星定位原理，HADA等【7】利用分布在室内各处的摄像机，研制了一个室内GPS系统IGPS。同样仿照卫星定位原理，可以在AGV上装配360度激光测距仪，同时在引导区域四周布置足够的激光反射板，用来确定AGV当前位姿。国内昆船公司已经将这种导航方式进行了成熟的应用，针对工业室内环境生产出多种型号的仿GPS激光定位AGV。13移动机器人导航研究中的关键技术131移动机器人路径规划移动机器人的路径规划问题可以描述为移动机器人依据某个或某些优化准则如工作代价最小、行走路线最短、行走时间最短等，在运动空间中找到一条从初始状态到目标状态、可以避开障碍物的最优或者接近最优的路径。自20世纪70年代开始研究以来，已相继提出了多种路径规划的方法。对这些路径规划方法分类的方法有很多种，但比较常见的是按功能分为两类一类是基于环境先验完全信息的全局路径规划，另一种是基于传感器信息的局部路径规划。后者需要通过传感器来获取局部障碍物的尺寸、形状和位置信息。实际上，这两类路径规划的方法在机器人导航中缺一不可。前一类是在战略上整体规划出机器人所行走的完整最优路径，后一类是指当机器人在局部环境遇到障碍时，战术上调整路径，以达到避障的效果。一个好的路径规划方法需要满足如下指标1合理性返回的任何路径都是合理的，或者说任何路径对控制机器人运动都是可执行的。2完备性如果客观上存在一条从起点到达终点的无碰路径，该算法一定能找到。如果环境中没有路径可通行，会报告规划失败。3最优性算法规则的复杂度时间需求、存储需求等能满足机器人运动的需要。4环境变化的适应性算法具有适应环境动态改变的能力，随着环境改变，不必全部重新计算。4满足约束支持移动机器人运动时的完整性和非完整性运动约束。目前已经有多种路径规划的方法被学者们提出并进行研究，比如可视图法、自由空间法、拓扑法、人工势场法、遗传算法、神经网络算法等多种算法。这其中，基于启发式搜索理论的图搜索算法ASTAR算法在如上所述的性能指标上要优于其它算法，在目前机器人路径规划程序设计中得到了广泛的应用。132移动机器人运动控制移动机器人运动控制问题是机器人研究中最基本的问题，也是机器人学中只有依靠控制理论才能予以解决的问题。从控制理论的角度出发，对于一个包括受控系统即控制对象在内的控制系统而言，控制问题的理论研究包括两方面内容，一是控制系统分析问题，一是控制系统综合问题，研究的前提是已知控制对象模型的结构和参数。获得控制对象模型的方法有机理建模和统计建模，机理建模是利用已知的物理原理建立对象的数第4页武汉科技大学硕士学位论文学模型，统计建模是采用参数估计和系统辨识的方法获得对象模型。在分析问题中，根据已知的控制输入作用，来确定控制系统的定性行为如能控性、能观测性、稳定性等以及定量的变化规律。在综合问题中，恰好与分析问题相反，根据所期望的受控系统运动形式或某些性能指标，来确定需要施加于控制对象的控制输入作用，即控制律。移动机器人运动控制问题的提出，最早是出于生产实践的需要，目标是通过寻求某种控制输入作用，使机器人精确快速平稳地自动到达运动空间的某一位置或跟踪空间中的某条曲线。由此，在历史上开成了点镇定POINTSTABILIZATION、路径跟随PATHFOLLOWING和轨迹跟踪TRAJECTORYTRACKING三种移动机器人运动控制的基本问题，示意图分别如图11、图12和图13所示。期望位姿图11移动机器人期望位姿镇定图12移动机器人路径跟踪图13移动机器人轨迹跟踪O口一武汉科技大学硕士学位论文第5页严格来讲，根据控制目的来区分的点镇定、路径跟随和轨迹跟踪三种移动机器人运动控制基本问题，即便在名称上，不同的文献之间也并不完全一致，统一严谨的数学定义更是从未出现过，尽管各自的基本意义已经得到了广泛的认可。移动机器人运动控制的三种基本控制问题从控制结构上看都是闭环控制，需要测量环节才能构成闭环回路。对于轮式移动机器人而言，运动控制用到的测量值通常来自机器人内部传感器中的里程计ODOMETER。里程计作为相对定位的有效传感器已经成为轮式移动机器人的缺省配置，它的主要原理是通过装在机器人驱动轮上的光电编码器对其进行计数，检测出两个驱动轮转过的圈数，然后应用航迹推算估计出机器人的相对位姿。对于移动机器人运动控制这种闭环控制系统而言，如何设计有效的点、路径和轨迹跟踪控制律成为机器人运动性能好坏的关键。14本课题的研究任务和拟解决的关键问题141本课题的研究任务移动机器人导航中的路径规划和运动控制具有学科交叉密切、关键技术突出、涉及面广和应用前景广阔等主要特点。它涉及到机器人学中的许多分支，包括环境模型的选取、机器人运动学模型的分析、传感器技术等，还涉及到非线性系统和离散数据采集和处理等许多领域，因此，它是需要多种专业知识共同支持的研究项目。基于上述原因，本课题根据移动机器人导航中对路径规划和运动控制的要求，拟从理论和实验两方面，对其各个步骤进行系统的分析和研究。主要研究内容包括1采用基于启发式搜索理论的图搜索算法ASTAR算法设计路径规划控制器。2针对两论差动机器人的运动学模型，采用基于BACKSTEPPING的设计思想结合LYAPUNOV直接法设计轨迹跟踪控制律，带时间参数的连续轨迹的跟踪控制。3针对非完整移动机器人这种非线性系统，采用LYAPUNOV直接法设计出点镇定控制器，用来对路径规划控制器在导航过程中规划出的路径中的离散路径点进行跟踪控制。4将路径规划和运动控制技术结合起来对差动驱动的轮式移动机器人设计导航实验，包括算法的移植，传感器数据的采集和处理，验证算法的有效性和将算法转换为程序后运行的实时性和稳定性。142研究计划与拟解决的关键问题本课题的研究任务主要分三个阶段完成。第一阶段主要是分别针对移动机器人路径规划和运动控制两部分内容，进行算法的分析和控制器设计；第二阶段主要将所设计的启发式路径规划控制器和运动控制器进行仿真实验，以验证其正确性和仿真效果。第三阶段主要将上述两部分所设计的控制器移植到轮式移动机器人平台，完成机器人自主导航目标。本课题拟解决的关键问题1针对特定的全局栅格地图，充分利用启发式搜索算法的计算高效性来设计路径规划控制器寻求最小耗费路径。2设计移动机器人的轨迹跟踪控制律时，构造一种简单的虚拟反馈变量以加强控制律的执行效率和算法转换为程序的第6页武汉科技大学硕士学位论文可移植性。3使得移动机器人在极坐标系下的两个控制量P和口能够同时镇定，并且机器人对离散路径点的跟踪控制律能够达到全局稳定。4机器人导航过程中，行走路径平滑、准确。143论文各部分的主要内容第二章详细介绍了人工智能领域的启发式搜索理论，包括启发式信息和估价函数以及搜索算法的可采纳性。采用基于图搜索策略的ASTAR算法设计出路径规划控制器，同时通过设计MATLAB平台上的仿真实验验证了路径规划控制器的有效性。论文的第三章详细介绍了轮式非完整移动机器人的运动学模型，针对机器人不同性质的移动轨迹，分别设计了基于BAEKSTEPPING的轨迹跟踪控制器和基于点镇定原理的路径跟踪控制器，同时通过设计MATLAB平台上的仿真实验验证了轨迹跟踪控制器和路径跟踪控制器的有效性。第四章介绍了实验室JPOT轮式移动机器人的系统架构，通过对路径规划控制器和路径跟踪控制器进行算法的移植来设计移动机器人自主导航实验，并详尽分析和归纳了实验结果。第六章总结了本论文的主要工作、论文的创新点以及进一步的研究工作。15资助本课题的专项研究基金本论文先后得到以下专项研究基金的共同资助，特此致谢。1国家自然科学基金“低雷诺数气动特性与微机电系统控制的多学科优化设计研究，项目号50675161；2教育部重点研究基金“多学科优化设计在微小智能服务机器人中的应用研究“，项目号2050983湖北省国际科技合作重点研究基金“基于网络化智能体架构的微小型光机电系统“，项目号2006CA025；4湖北省教育厅重大研究基金“微小型服务机器人集成优化设计研究，项目号Z200511001武汉科技大学硕士学位论文第7页第二章基于启发式搜索理论的路径规划移动机器人的路径规划研究方法有很多种，比如人工势场法、遗传算法、粒子群算法等。但这些算法在机器人实际的应用中都无一例外暴露出实时性差，占用过多系统资源、算法可移植性不佳等弱点。因此在选取机器人路径规划的方法时，采用了人工智能领域的启发式搜索理论来设计移动机器人的路径规划控制器。而同样属于人工智能领域的搜索算法，比如宽度优先搜索、深度优先搜索等，它们均属于盲目搜索方法，又叫做无信息搜索，一般适用于求解比较简单的问题。盲目搜索是按规定的搜索策略进行搜索，在搜索过程中获得的中间信息并不能改进搜索策略。由于搜索总是按照规定的路线进行，没有考虑搜索对象本身的特性，所以具有盲目性，对于复杂问题求解效率低下。相比无信息搜索，启发式搜索HEURISTICSEARCH又叫有信息搜索INFORMEDSEARCH不仅可以简化搜索，提高问题的求解效率，更重要的是能够实时找到全局最优解。21启发式搜索理论用盲目搜索理论来求解，对于大多数搜索对象而言，其扩展的节点数目可能很大。因为这些节点扩展顺序具有随意性，没有将搜索过程中所获得的中间信息用来修正某些局部的搜索策略。启发式搜索在搜索过程中加入了与搜索对象相关的启发式信息，用来指导搜索沿着寻求最优解的方向进行。这种搜索针对性强，因而在原则上只需要搜索问题的部分状态空间，效率高。211启发式信息和估价函数用于指导搜索过程，且与具体求解对象有关的搜索策略信息称为启发式信息。在启发式搜索技术中，启发式信息按其用途可以分为下列3种1用于决定要扩展的下一个节点，以免出现宽度优先或深度优先搜索中的盲目地扩展现象。2在扩展一个节点的过程中，用于决定要生成哪一个或哪几个后继节点，以免盲目地同时生成所有可能的节点。3用于决定某些应该从搜索树中抛弃或修正的节点。在启发式搜索过程中，如何确定下一个要考察的节点是搜索的重要一环，确定的方法不同就形成了不同的搜索策略。如果在确定节点时能充分利用与问题求解有关的特性信息，估计出节点的重要性，就能在搜索时有目的选择重要性较高的节点，以利于求得最优解。用于估价节点重要性的函数称为估价函数，其一般形式为厂，1GN刀，其中G刀为从初始节点到节点聆已经实际耗费，五0是从节点刀到目标节点的最优路径的估计耗费，它体现了问题的启发式信息，其形式要根据问题的特性确定。例如，它可以是节点N到目标节点的距离，也可以是节点甩处于最优路径上的概率等。JIL甩称为启发式函数。第8页武汉科技大学硕士学位论文设计估价函数是使用搜索技术的关键。因此需要充分利用启发式知识，设计比较优秀的估价函数，尽可能的减少搜索代价，找出最优解最小路径耗费。如果不容易找到优秀的估价函数，那么就会影响到问题的求解，为了弥补这个不足，不妨试一下盲目搜索算法，只要能解决问题，即使是多费点代价也是可行的。但是不是所有的难题都能够通过这种无信息式搜索来解决的，因为这些难题的状态空间所包含节点的个数，可能数量巨大，就当前计算机的存储能力和运算能力是不可能解决的。所以，当盲目搜索的方法被排除时，就必须设计估价函数。当设计估价函数的代价有可能超过搜索本身的代价时，可以有针对性的采用性能差一些的估价函数，牺牲一些搜索代价，来减少设计估价函数的代价，最终行成一个综合代价较小的搜索。在实际操作中可以这样解决，给估价函数加上一个可控制的大于零的系数因子W，使估价函数FNG，1WHN。同时可以通过调节控制因子值的大小，来控制搜索是向纵深方向还是向宽度水平方向进行。当W专0时，启发函数部分WHN一0，从而启发函数对估价函数影响变弱，使搜索向宽度水平方向进行。当把W的值调大时，WHN的值就会变大，从而启发函数对估价函数影响变强，使搜索向纵深方向进行。这样就可以根据需要来调整估价函数，寻找搜索和估价函数设计之间的代价平衡点，争取综合代价最小。对于一般的搜索过程，可以这样控制刚开始搜索时，即搜索的前一个阶段，调大W值，使搜索向纵深方向进行，目的是尽快接近目标节点。因为该阶段距离目标节点尚远，不会错过要找的目标节点。当搜索到达一定深度时，应及时把W的值调小，使搜索向宽度水平方向进行，目的是不要错过了目标节点。随着搜索的不断深入，应逐渐调小W的值，成功的完成搜索，并找到最小耗费路径。212搜索算法的可采纳性可采纳性是衡量一个启发式算法的重要指标，而算法被采纳的关键则是采用该算法能否达到预期的搜索目的。比如在图搜索中，如果客观存在从初始节点到目标节点的可搜寻路径，同时启发式搜索算法能够找到最小耗费路径，则称该算法具有可采纳性。如果该算法不具有采纳性的话，就搜寻不到目标节点，或者找到的不是移动耗费最小的路径。设有估价函数厂咒G。万JIL以，其中刀为从初始节点经节点玎到目标节点的实际最小移动耗费，G刀为初始节点到节点N的实际最小移动耗费，矗刀为节点RT到目标节点的实际最小移动耗费。而实际搜索问题的求解过程中，并不知道厂的值，在搜索中所采用的启发式估价函数是只能算厂刀的近似值。如果能保证FN厂以，即G刀G刀，JIL，1JIL聍，那么在选取后继节点时，每次都能正确地选取相关的后继节点，不会扩展无关节点，直到顺利找到最小耗费路径。但实际上在求解复杂的路径寻优问题时，能找到近似于G刀和五刀的GN和HN是非常困难的。一般而言，G疗的值可以从已生成的搜索树中计算出来，是已经耗费的代价，不必专门定义计算函数。然而，对0设计，则依赖于启发式信息的应用，并影响估价函数。可以证明，如果对于任意武汉科技大学硕士学位论文第9页节点刀的启发函数总有而刀矿阼，则该启发式搜索算法具有可采纳性。22ASTAR路径规划算法221图搜索策略图搜索GRAPHSEARCH策略是一种在图中寻找路径的方法。在有关图的表示方法中，节点对应于状态，而连线对应于操作符。图搜索算法中包括两个表开启列表和关闭列表。其结构如下所示。开启列表关闭列表堕工圈臣亘工蔓丑至至口图搜索的一般过程可分为9个步骤1建立一个只含有初始节点的搜索图，把初始节点放到一个叫做开启列表的未扩展节点表中。2建立一个叫做关闭列表的已扩展节点表，其初始为空表。3若开启列表是空表，则失败退出。4选择开启列表上的第一个节点，把它从开启列表移出并放进关闭列表中。称此节点为节点N，它是关闭列表中节点的编号。5若节点刀为个目标节点，则有解并成功地退出，此解便是搜索图中从节点N开始沿着指针一直到回溯到初始节点的这条路径。6扩展节点靠，同时生成不是节点万的父辈节点的那些后继节点的集合膨。把M的这些成员作为N的后继节点添加到搜索图中。7对那些未曾在搜索图中出现过的未曾在开启列表上或关闭列表上出现过的M成员设置一个通向N的指针。把M的这些成员加进开启列表。对已经在开启列表或关闭列表上的每一个M成员，确定是否需要更改通到N的指针方向。对已在关闭列表上的每个M成员，确定是否需要更改搜索图中通向它的每个后继节点的指针方向。8按某一方式或按某个试探值，重新排列开启列表。9返回步骤3。图搜索过程生成一个明确的搜索图和一个搜索图的子集，称为搜索树，搜索树上的每个节点也在搜索图中。搜索树是由第7步中设置的指针来确定的。搜索图中的每个节点除初始节点外都有一个只指向搜索图中一个父辈节点的指针，该父辈节点就定为树中那个节点的唯一父辈节点。一般的图搜索过程可用图21来表示101。第10页武汉科技大学硕士学位论文丌始把初始节点放入开启列表丌启列表为空表否把第一个节点N从开启列表移至关闭列表N为目标节点否把N的后继节点放入开启列表的末端，提供返回节点N的指针修改指针方向重排丌启列表图21图搜索过程框图图搜索过程的步骤8对开启列表上的节点进行重排序，以便能够让步骤4选出一个最佳节点。这种排序可以任意的，即属于盲目搜索，也可以用各种启发式思想或其他准则作为依据，即属于启发式搜索。每当被放入关闭列表中的节点为目标节点时，这一过程就宣告成功结束。这时，重现从初始节点到目标节点的最优路径，其办法是从目标节点按指针方向进行回溯。当搜索树不存在时，过程就以失败告终。在搜索失败的情况下，从初始节点出发，一定达不到目标节点。222ASTAR算法估价函数通常ASTAR算法的估价函数可描述为估价函数厂使得任意节点上的函数值FN能近似代表从初始节点到节点N的最小移动耗费与从节点以到目标节点的最小移动耗费的和，也就是说厂，1是约束通过节点以到目标节点的最小移动耗费的一个估计。因此，开启列表上具有最小厂值的那个节点就是所估计的严格约束条件附加得最少的节点，而且下一步对这个节点进行扩展是合适的。令七珥，N，表示任意两个节点NL和，L，之间最小耗费路径的实际耗费，因此对于两节点问没有通路的节点，函数K没有定义。于是，从节点甩到某个具体的目标节点T，某一条路径的移动耗费可由KN，给出。令一表示目标节点上所有KN，中最小的一个，武汉科技大学硕士学位论文第11页因此，矿行就是从节点拧到目标节点最小耗费路径的移动耗费，而且从节点以到目标节点能够获得JIL刀的任一路径就是一条从N到这个目标节点的最优路径。对于那些不能到达目标节点的节点以，函数H没有定义。引进一个新函数G，使得从初始节点到任一节点N的一条最优路径的移动耗费KS，刀得到简化。对于所有从初始节点开始可到达节点刀的路径来说，函数G定义为G刀KS，玎。其次，定义函数厂，使得在任一节点刀上其函数值厂刀就是从初始节点到节点以的一条最优路径的实际移动耗费加上从节点N到目标节点的一条最优路径的实际移动耗费之和，即厂0G，1刀。因而厂0值就是从初始节点开始约束通过节点N并到达目标节点的一条最优路径移动耗费，而厂S|ILS是初始节点与目标节点之间一条无约束的最优路径的移动耗费。估价函数厂是厂的一个估计，有FNG，1JJL行。其中，G是G的估计，H是H。的估计。G疗代表搜索树中从初始节点到节点刀这段路径的移动耗费，该耗费可以由从节点以到初始节点进行指针回溯时，把所遇到的各段弧线的移动耗费加起来得到。这个定义包含了GNG。，1。对于矿万的估计矗栉，它依赖于有关问题领域中的启发式信息。223ASTAR算法结构ASTAR算法是一种有序搜索算法。对于一般的有序搜索，总是选择厂值最小的节点作为路径节点。因此，厂是依据需要找到一条最小移动耗费路径的思路来估算节点的，所以，可考虑每个节点N的估价函数值为两个分量，从初始节点到节点栉的移动耗费以及节点N到目标节点的移动耗费。ASTAR算法的执行过程可以描述如下。1把初始节点放入开启列表，记FH，令关闭列表为空表。2重复下列过程，直至找到目标节点止。若开启列表为空表，则宣告失败。3选取开启列表中未设置过的具有最小厂值的节点为最佳节点，并把它放入关闭列表。4若最佳节点为目标节点，则成功求解。5若最佳节点不是目标节点，则把它的后继节点进行扩展。6对每个扩展的后继节点进行下列过程建立从后继节点返回最佳节点的指针。计算GSUCGBESGBES，UC，式中SUE代表后继节点，BES代表最佳节点。如果后继节点已经在开启列表中，则称此节点为OLD。比较新旧路径的移动耗费。如果GSUCC。标节小L6目口韧始节点|O一一一LJ一一一_L|一|JL_|一L|II叫|_初始，R点口Q目标1，点。I第20页武汉科技大学硕士学位论文第三章移动机器人运动控制31移动机器人运动学模型本文研究的移动机器人的结构模型如图31所示。图31移动机器人底盘结构机器人驱动方式采用两轮差动驱动DIFFERENTIALDRIVE方式。前轮为驱动轮，属于固定标准轮FIXEDSTANDARDWHEEL，分别由独立电机进行驱动。后轮为仅起支撑作用的万向小脚轮CONVENTIONALOFFCENTEREDORIENTABLEWHEEL，小脚轮并不影响机器人的运动学模型【291。机器人两个驱动轮之间的距离为26，设左驱动轮的线速度为VJ，右驱动轮的线速度为咋，则机器人的线速度Y旦，角速度缈兰。这里定义的线速度1，为机器人ZZD在全局坐标系下的线速度，当机器人前进时，1，取正值，当机器人后退时，1，取负值。同样，当机器人在全局坐标系下逆时针旋转时，国取正值，顺时针旋转则取负。如图32所示，移动机器人的运动可以等效看成一个质点的运动，机器人所等效的运动质点为两驱动前轮的中心点。LCR图32机器人旋转示意图在不考虑驱动轮的任何横向滑动的情况下，机器人的瞬时旋转中心INSTANTANEOUS武汉科技大学硕士学位论文第21页CENTEROFROTATION,，ICR始终都在两个驱动轮的共享公共水平轴向上。机器人旋转半径可表示为杉手杉，兰2垒业塑国兰二旦V，一26这种结构的移动机器人的活动性程度DEGREEOFMOBILITY瓯2，可操作度DEGREEOFSTEERABILITYT0，机动程度DEGREEOFMANEUVERABILITY毛吒正2，即可操纵的总自由度为二，它受到如下非完整约束圣SIN05,EOS0031如图33所示，机器人在二维全局坐标系置D，匕下的位姿用它的三个空间定位自由度组成的广义坐标向量PX，Y，口R来表示，其中秒以逆时针方向为正。图33机器人位姿示意图机器人的运动状态由它的线速度Y及角速度国来决定，表示为向量形式Q，COR。机器人的运动学模型为【30】HCOSL901I夕L户砌ISIN90IQ32例L0LJ其中，为雅可比矩阵，文是移动机器人在全局坐标系下X轴方向的线速度，当机器人朝X轴正方向运动时J取正值，机器人朝X轴负方向运动时J取负值。夕是移动机器人在全局坐标系下Y轴方向的线速度，机器人朝】，轴正方向运动时夕取正值，机器入朝】，轴负方向运动时夕取负值。痧是移动机器人在全局坐标系下的角速度，逆时针转动时P取正值，顺时针转动时痧取负值。这里，痧缈，两者在数量关系上完全等价。对于差动驱动的移动机器人，其位姿状态可以通过航迹推算来予以估计，即从一个已知位置开始，将运动进行积分行走距离的增量求和。对于具有固定采样时间间隔垃第22页武汉科技大学硕士学位论文的离散系统，行走距离的增量缸，每，AO7为AXASCOSOA012缈ASSINOAB2AOASAST26ASASAST2上式中，缸，AY，AO7为机器人在一次采样周期内走过的路径，厶，和每分别为左右驱动轮行走的距离，26为差动驱动机器人两个驱动轮之间的距离。由此，得到更新后的当前时刻机器人的位姿P由前一时刻位姿经过一次采样周期获得当前时刻机器人的位姿半COSP气产，半STNP学，缸R一心L2B32基于BACKSTEPPING的轨迹跟踪控制器设计通过差动驱动DIFFERENTIAL衄VE的轮式移动机器人属于典型的非完整系统【”】，近年来依据非完整系统运动学模型和动力学模型【32】来对它进行有效的反馈控制一直是研究的热点。由于移动机器人并不满足BROCKETT光滑反馈镇定必要条件【331，这使得它的轨迹跟踪系统比一般的非线性系统更难控制。文献30针对移动机器人运动学误差模型采用泰勒线性化的思想完成了轨迹跟踪反馈镇定控制器的设计，这种方法只能得到局部的稳定性。文献34，35，36利用积分BACKSTEPPING思想结合LYAPUNOV直接法设计了轨迹跟踪控制器，并且对满足特定条件轨迹的跟踪可以达到全局稳定。根据二自由度轮式移动机器人的运动学模型，在文献36】的基础上利用积分BACKSTEPPING设计思想构造出更加简单的虚拟反馈变量，同时结合LYAPUNOV直接法设计出时变反馈轨迹跟踪控制律，并证明其控制效果能够达到全局渐近稳定。仿真结果表明机器人在控制律的作用下，能够迅速且有效地跟踪期望轨迹。321轨迹跟踪问题设机器人当前位姿表示为P毛Y，秒7R3，而期望轨迹上的参考位姿表示为PRXR，”，PR，砟R3为时间的函数、具有一阶连续可微的性质，并且满足非完整移动机器人非完整约束方程即公式33所示的关系。毫SINE,一剪COSE,033设机器人沿期望轨迹运动时参考速度的控制输入为GRV，COR，咋0，CORR1，G，动动9妒咿0UOS厶厶武汉科技大学硕士学位论文第23页为进间的函数，同时机器入当前速度表示为GK彩R。B与毋之间满足非完整移动机器人运动学模型即公式34所示关系。妻办以G，孑毒习I。定义非完整移动机器人全局坐标系一Q巧下所描述的位姿误差为如公式35所示。R吒RT吖P尼2L虼L只一P1“一YI35【锟J【P一秒J在公式35的基础上，可以得到如公式36所示的在机器人局部坐标系Q匕下所描述的位姿误差见。见料吊铷0驴加料啪X二习XN6，其中乃为正交旋转矩阵，段与靠之间的关系如图34所示。图34局部坐标系下的位姿误差示意图由公式31至公式36NN推导以下公式毫毫一ICOSO夕，一允SIN9一_XOSINOY，一YOCDSOYC国一V支RCOSO多RSINO2只缈一V毒COSAE允SINO，一22儿国一1，毫COS包COS幺SING,SIN2以COS2SINO，SINO，COSOA2YRO一，毫COSG见SINOJCOSO。毫SINO,一只COSESIN见YOYCOS统第24页武汉科技大学硕士学位论文虎斟鼍引B7，Q1，COR，使得它和方程37组成的闭环系统位姿误差全局一致有界，并且当T寸OO，咋和Q不同时收敛于零时，系统在任意初始跟踪误差下有脚LITF，以F，见F7IO。图35轨迹跟踪控制系统结构框图设计全局跟踪控制律时引入积分BACKSTEPPING思想，在公式36QA，针对误差分量，构造虚拟反馈变量元艺一向SINARCTANCOY。38其中KL为大于零的常数，显然当缈0时，毛SINARCTANROY，0，且KLSINARCTANRO关于缈的一阶导数有界。由公式37中见分量的方程可知，如果控制作用使得误差分量L，一IMT2毛SINARCTANROY。，并且脚吧0，那么烩见一KLROSINARCTANCOY，。同时对部分LYAPUNOV函数去求时间导数，得哆只见。又因为ROSINARCTANRA0，当且仅二当缈0时等号成立，所以根据BARBALAT引理【3刀得到，当T专00时，Y，收敛于零，由此可以看出误差分量Y是间接受控量。综上所述，设计控制律的实质就是寻求输入控制量武汉科技大学硕士学位论文第25页G2“功R使得1ITMAOTK,SINARCTANCCOY,，IM。OO。按照上述思路构造LYAPUNOV纯量函数Y三三一吾一COS譬39其中恕为大于零的常数。考虑到包为实际角度误差，即可以忽略角度的周期性，定义吃【O，2刀。很明显，函数矿O，当且仅当墨，咒，色RO时，VO。将虚拟反馈变量乏的方程38转化为意毫一K,COSARCTALL彩再咄一毛SINARCTANRO5,31O将LYAPUNOV函数对时间求导数，并确定闭环系统的控制律矿魂以见I1SIN和2元毫一毛COSARCTANR麦RBY,一毛SINARCTANROD,咒一缈T咋SIN吧1厩SIN臼ZCRN一功2乏够儿V匕COS包一岛COSARCTAN国RI西以一向SINARCTANRO夕,311YA叫茏毛SILLARCTAN国舰V,SIN包I1SILL拿Q一缈2乏一，哆COS秒,一向COSARCTANRO。了痧圪一毛SINARCTANCCAAX,SIN0，L。一墨Z国SINARCTAN缈”I1SIN鲁一彩Q2乜以VRCOS鲁”I发VTE0，佃，咋，婢，也，4有界且V，和CO,不同时收敛于零，取系统的控制律为J；COSAQSINARCTANROROX，一考髟SINARCTANROSIN见一毛COSARCTAN力丽1咄红一毛SINARCTAN缈以312缈Q2毛此一COS鲁屯SIN导_兵甲心，心为大于零的常数，且有如F万程。西匆2包允咋儿嘭C。S拿一毛V以SIN鲁晓互1缸COS譬晓见一鳞2毛只哆COS冬屯SIN鲁艺Y，SIN包晓2殳，Y以S导一毛SIN导第26页武汉科技大学硕士学位论文将控制律公式312以下简称控制律312代入公式311并整理得LA矿一屯_KLY；COSINARCTANCOK4一SIN2专313Z因为VT【O，400，_，Q，也，喀有界，所以VT【O，TOO，T，Y。，包一致有界。由于KL，岛，屯，K4均为大于零的常数，并且COSINARCTANRO之0，所以矿0。可以看到Y为正定连续可微函数且有界，矿为半负定一致连续函数，那么根据BARBALAT引理【37】口可知，T00时，矿一0，从而得到霹，Y；ROSINARCTANCO，SIN2睾分别收敛于零。进一Z步，由LIM乏O得到LIMT毛SINARCTANCOY,。由TOO时，V，Q不同时收敛于零推得力不收敛于零，结合LIMY；COSINARCTANCO0可知，LIM儿0