室内移动机器人路径规划与定位技术研究.docx

.可编辑修改，可打印别找了你想要的都有！ 精品教育资料全册教案，试卷，教学课件，教学设计等一站式服务全力满足教学需求，真实规划教学环节最新全面教学资源，打造完美教学模式摘要本文研究对象是室内移动机器人，针对各种不同的室内环境，合理高效的路径规划算法和室内定位技术是论文研究的重点。论文的工作包括两个部分，一是路径规划算法的分析仿真和算法在硬件系统上的应用，二是室内无线定位技术及其在硬件系统上的应用。论文分析了已有路径规划技术的方法，重点研究了基于栅格地图的路径规划算法：区域覆盖路径规划算法和点到点路径规划算法。针对室内环境特点提出了环境地图的建模，具体算法设计以及基本的行进方式，用 VS.NET 软件开发平台对两种路径规划算法进行了软件仿真。本论文在研究了室内定位系统的相关技术以及常用的室内定位方法的基础上，分析了多种室内定位算法的应用特点和测距方法，重点研究了基于 ZigBee 无线网络的室内定位技术。最后，本文设计并实现了一个基于英飞凌微控制器的简单移动机器人系统及其室内定位系统。硬件控制部分主要包括主控芯片模块，电机驱动模块，传感器模块以及其定位模块等；软件设计部分主要包括 A/D 模块，PWM 模块，以及具体的覆盖算法和定位算法等。论文将仿真过的算法应用于机器人系统的路径规划和定位，验证了算法的有效性。本论文的工作对机器人路径规划及定位方面的研究，有一定的参考价值。关键字：移动机器人 路径规划ZigBee无线网络 室内定位目录目录第一章 绪论 .11.1 课题的研究背景.11.2 智能移动机器人的发展与分类.21.2.1 国内外发展动态.21.2.2 国内发展动态.41.3 论文的内容安排及主要工作.5第二章 室内移动机器人的路径规划技术.72.1 路径规划技术的核心问题.72.2 环境地图模型.82.2.1 环境地图的建立.82.2.2 环境地图的分类.82.2.3 基于栅格法的环境地图.92.3 区域覆盖路径规划 .102.3.1 区域覆盖路径规划方法.102.3.2 区域覆盖策略.122.4 点到点的路径规划 .142.4.1 点到点路径规划方法 .152.4.2 快速算法.162.4.3 距离转换算法.17第三章 室内定位方法及其关键技术.193.1 常用的室内定位方法.193.1.1 基于构造地图的定位方法.193.1.2 基于路标的定位方法 .203.2 室内无线定位技术 .213.2.1 ZigBee 技术.213.2.2 无线射频识别技术 .233.2.3 蓝牙技术.233.2.4 无载波通信技术.243.3 常用的测距算法.253.3.1 RSSI 测距算法.253.3.2 AOA 测距算法 .26划与定位技术研究3.3.3 TOA 测距算法.273.3.4 TDOA 测距算法.28第四章 机器人软硬件系统设计与实现.294.1 实验机器人硬件的总体设计.294.1.1 机器人的运动模型 .294.1.2 机器人的控制系统 .304.2 机器人的硬件平台设计.314.2.1 机器人控制芯片 .314.2.2 机器人行走驱动设计.324.2.3 障碍物探测功能设计.334.2.4 机器人定位系统设计.354.3 机器人的软件设计.384.3.1 机器人软件设计开发环境.384.3.2 环境地图的建立 .394.3.3 区域覆盖算法的实现.434.3.4 机器人定位系统软件设计.45第五章 仿真与测试.495.1 区域覆盖规划仿真测试.505.1.1 迂回覆盖.505.1.2 内螺旋覆盖.505.1.3 两种覆盖算法性能比较.515.2 点到点路径规划算法仿真测试 .525.2.1 快速算法.525.2.2 距离转换算法.535.2.3 两种算法性能比较 .545.3 机器人系统测试与分析.545.3.1 机器人系统实验测试.545.3.2 定位实验测试.56第六章 总结 .59致谢.61参考文献.63第一章 绪论 1第一章 绪论1.1 课题的研究背景机器人的诞生和机器人学的建立和发展是 20 世纪自动控制最具说服力的成就之一，是 20 世纪人类科学技术进步的重大成果。机器人从 20 世纪 60 年代诞生以来，随着电子技术、计算机技术、信号处理和人工智能技术的发展，在短短的几十年内取得了巨大进步。从第一台机械手到现在的大规模自动化生产线，机器人技术在工业领域的广泛应用大大提升了生产效率并获得了巨大的成功。随着机器人技术的发展，越来越多的具有智能化特点的机器人，深入到我们的生产生活中。作为机器人中重要分支之一的智能移动机器人更是给人们带来了无限的惊喜。智能移动机器人的研究始于20世纪60年代末，斯坦福研究所(SRI)的NilsNvissen和 CharlesRosen等人，在1966年至1972年中研制出了取名shakey的自主移动机器人，其目的是研究、应用人工智能技术以及在复杂环境下机器人系统的自主推理、规划和控制1。20世纪70年代末，随着计算机的应用和传感器技术的发展，移动机器人研究又出现了新的高潮。20世纪90年代以来，以研制高水平的环境信息传感器技术、信息处理技术、高适应性的移动机器人控制技术和真实环境下的规划技术为标志2，开展了动机器人更高层次的研究。图1.1 自主移动机器人shakey类似 shakey，以轮子作为移动机构、能够实现自主行驶的自主式移动机器。我们称之为智能小车，又称轮式机器人。AbstractThis research is the indoor Autonomous robot, for a variety of indoor environment,how to select the rational and efficient regional coverage path planning algorithm is thefocus of the papers research. The papers contents included two parts, one part is theanalysis of algorithms and the application of algorithm on the hardware system, anotherpart is indoor wireless location technology and its application on the system inhardware.The paper analyzed the existing various methods of path planning technology, andmainly studied map-based regional coverage path planning algorithm, the regionalcoverage path planning algorithms and the point to point path planning algorithm. Thecontents of the research included the specific process of algorithm design, theexpression of the environmental map, the basic road method and so on. The paperprogrammed achieved a software simulation of the two kinds of algorithms through theVS.NET building environment.The paper does researches on technologies related to Indoor Positioning, Analysisof a variety of indoor positioning algorithms application characteristics and methods ofmeasurement，Focus on the ZigBee wireless network based on indoor positioningtechnology.According to the test requirements, a simple autonomous robot system and itsindoor positioning system based on infineon controllers was designed and achieved,which included hardware system design and software control system design. Thehardware system included master-chip module, motor drive module, sensor module,indoor positioning module and so on. The software control system mainly included A/Dmodule, PWM modules, as well as specific coverage algorithm and positioningalgorithm. The paper used the algorithm simulated to apply to the robot systems pathplanning, which verified the effectiveness of the algorithm. There is a certain referencevalue that the papers work on the research of the robots path planning and Positioning.Keyword: Intelligent mobile robot Path planning ZigBee wireless networkIndoor Positioning第一章 绪论 51.3 论文的内容安排及主要工作本论文的课题是以室内移动机器人系统为基础的，而路径规划技术以及定位技术是机器人系统的核心。因此，本论文的主要章节安排如下：第一章主要介绍了国内外智能移动机器人的发展动态，为路径规划技术的研究提供了背景支持。第二章对室内自主机器人的路径规划技术进行了研究，介绍了路径规划技术的定义和分类，研究了区域覆盖路径规划算法和点对点路径规划算法。对当前主要的路径规划技术进行了总结和分析。第三章介绍了常用的室内机器人定位方法和无线传感器网络定位技术，对本文用到的ZigBee无线网络定位方法加以阐述和说明，为接下来的工作打下基础。第四章根据实验要求，设计实现了一个简单的基于英飞凌XC888单片机的移动机器人系统，包括硬件系统设计和软件控制系统设计。硬件系统主要有控制芯片模块，行走驱动模块，探测功能模块以及定位模块等；软件系统设计主要包括环境地图的建立，具体覆盖算法的实现以及定位系统的设计实现等。第五章主要对区域覆盖路径规划算法进行了软件仿真和机器人系统的实验调试，模拟了不同的室内环境下算法的覆盖结果，覆盖算法效果良好。对机器人的定位进行了实验验证，并用图形化的界面显示实验结果，验证了定位的有效性，达到了一定的实验目的。第六章对论文的主要工作进行了总结，并指出了一些不足之处。划与定位技术研究智能小车是一个集环境信息感知、路径规划、行为控制与执行等多种功能于一体的综合智能系统。而其中的路径规划技术是机器人研究领域的关键技术之一，它要求机器人能够根据给予的机器指令以及周围的环境信息自主地规划路径，避开障碍物，实现最终的任务指标。路径规划是机器人完成任务的安全保障，是机器人智能化程度的标志之一，同时也是人工智能与机器人学的一个重要的结合点和研究热点。自上世纪70年代起，路径规划问题就已经受到了国内外众多机构和学者的广泛关注，尤其是80年代以来，在人工智能、计算机科学、数学和机械工程等领域内的专家学者们的共同努力下，路经规划技术的研究在理论和实践方面都有了很大的提高。而随着机器人应用的日益广泛，针对路径规划问题所具有的复杂性、随机性、多约束性、多目标性等特点，如何在各种不同的环境中具体问题具体地分析，合理有效地选择路径规划方法及策略等问题已经成为机器人研究中的具有非常实际意义的课题。1.2 智能移动机器人的发展与分类近年来，随着机器人技术越来越多的渗入到我们的生产生活中，具有自主感知决策和执行功能的智能移动机器人得到了快速的发展，随着人类在生存和工作中对机器人代为劳动的要求不断增长，自主移动式机器人研究取得了很大发展，我们的目标就是使机器人能够在没有人干预、无需对环境做任何规定和改变的条件下，有目的的移动和完成相应的任务。本节主要介绍自主移动式机器人的发展过程与现状，以及自主移动式机器人研究的主要内容和发展前景。1.2.1 国内外发展动态由于移动机器人在国民经济及人们生活中有极大的应用潜力，世界各国对移动机器人的研究都极为重视，促使移动机器人得到快速开发。根据移动机器人不同的应用环境，我们主要从以下四个方面来介绍国外移动机器人发展状况。(1)工业机器人在制造业和民用工业中，移动机器人最成功的应用是作为自动化生产系统中的自动导引小车 AGV 系统2，用以完成机床之间、机床与自动仓库之间的物料传送，以及机床与工具库间工具传送。世界上第一台 AGV 是美国 Barrett 电子公司于 20 世纪 50 年代开发成功的，它是一种牵引式小车系统。随着现代电子技术和微电子技术的发展，AGV 技术水平不断得到提高。现在的 AGV 上装有车载计算机、通讯装置和物料装卸装置，整机复杂性和自动化程度都大大提高，被广泛应用在仓库、工厂、码头、机场中的自动化仓储系统、柔性加工、柔性装配系统中，以实现物流的自动化。划与定位技术研究第一章 绪论 3(2)星际探索机器人星际探索一直都是移动机器人一大应用方向。从 60 年代开始，美国开始研究火星探索用移动机器人，以便在火星上软着陆后进行移动并收集数据。自 1965 年美国成功发射水手 4 号行星探测器以来，人类就从没放过对火星的探索。1976 年7 月和 8 月美国的“海盗 1 号”和“海盗 2 号”，在火星成功着陆。1966 年 12 月 4日火星探路者登陆器在肯尼迪航天中发射，1997 年 7 月，在火星上成功着陆后，索杰纳漫游车离开登陆器在火星表面漫游，行驶了几千米，完成了预定的科学探测任务3。1998 年麻省理工大学的移动机器人小组就开发出基于视觉的火星探险机器人 Pebbles4，可以在不确定、非结构化的环境中用单目视觉进行避障。近来，美国航空航天局正在积极研制体积更大、功能更全的探测车“火星漫游者”，由美国航空航天局 NASAMarSRover2009 计划资助5，密歇根大学移动机器人实验室设计的机器人 Fluffy 旨在为火星漫游任务开发一个高精度的航位推测系统，并将基于模糊逻辑专家规则的导航(FLEXnav)方法应用于 Fluffy。(3)服务机器人近几年，移动机器人技术又被广泛应用到医疗系统或日常生活中。在服务机器人方面，日本及美国处于绝对领先地位。例如：安川电机和富士通公司联合开发的送餐机器人可以在医院分送饮食到各个病床，并在病人用完餐后收回餐具。静甲株式会社的清水工厂开发出一种自动清扫机器人可用于工厂中的清扫工作，采用了光纤陀螺来自主控制机器人的方向，对地面没有任何要求。美国也非常重视服务机器人的开发和应用。能够从事洗碗盘之类烦琐家务事的机器人，现在己经可以在美国以邮购方式获得，每个售价还不到 800 美元。(4)自主车辆在智能交通系统中的智能自主车辆研究方面，欧洲的自主移动车辆研究主要集中在结构化道路上应用。如德国国防军事大学研制的高速公路自主驾驶车VaMoRs6最快达到了在高速公路 150km/h 的速度。 Carnegie Mellon University 的Navlabl7可以以 50-60km/h的速度在存在水渍和阴影的环境中自主行驶，并在 1998年完成了从匹兹堡到加州的穿越美国大陆实验。2001 年，牛津大学移动机器人小组开发出基于主动视觉和三维激光传感器融合技术的机器人，可以实现在丘陵地带进行自主导航8。总之，自上世纪 90 年代以来，各国学者尤其是欧美和日本各国的学者，对移动机器人的研究十分活跃。目前，各种类型和智能水平的移动机器人也已经在工业生产、日常生活和军事中获得实际应用。室内移动机器人的路径规划技术 7第二章 室内移动机器人的路径规划技术随着机器人的应用越来越广泛，人们对机器人的智能的要求不断提高，其中一个最基本的需求就是实现路径规划。路径规划是指机器人如何有效地利用环境信息，规划出一条适当的避障运动路径。它是机器人执行各种任务的基础，反映了机器人在运动过程中与周围环境的交互能力，路径规划是移动机器人完成任务的保障。如何在各种不同的室内环境中选择合理高效的路径规划方法就成了研究路径规划技术的关键所在30。本章针对路径规划技术的各种方法进行了详细的介绍与分析，为后面具体的区域覆盖路径规划算法研究打下理论基础。2.1 路径规划技术的核心问题路径规划的问题描述是:在一个存在各种障碍物的空间中，对于任意给定的起始点和目标点，要求找出一条从起始点出发到目标点的路径(如果有的话)，这条路径必须绕过所有的障碍物，并且这是一条最优路径(譬如最短路径)。移动机器人路径规划主要完成的任务是：(1) 在环境中寻找一条路径，保证移动机器人沿该路径运动时不与障碍碰撞；(2) 利用自身的环境感知系统能够识别和处理环境建模中的不确定因素和路径执行中出现的误差；(3) 移动机器人能够自主避开外界干扰使其对环境感知系统的影响最小；(4) 能够按照需要找到最优路径。路径规划问题在理论上主要存在着两个子问题：环境表示和路径搜索。1.环境表示环境表示即环境建模，包括环境中障碍物的表示、目标的表示和自由空间的表示。合理的环境建模有利于规划中搜索量的减少，有利于时空开销的减少。环境建模是路径规划的第一步，可以说，环境建模方法直接决定了路径规划策略、效率。任何一种规划算法都与某种特定的环境建模技术相对应的。环境模型有静态确定模型和动态时变环境模型。目前大多数研究工作集中于静态路径规划，但动态路径规划问题已引起人们的注意。对于静态己知的环境，已有不少成功的研究成果，其建模技术也是相对较为成功的。另一方面，部分已知或完全未知环境的路径规划问题没有得到完善的解决，其根本原因在于难以建立有效的环境模型。2.路径搜索在某个指定区域中，确定机器人从起始位置移动到目标位置的最佳路径，使划与定位技术研究1.2.2 国内发展动态在国内，香港城市大学对于地面清扫机器人的导航、控制及整个硬件系统做了完整的研究，并取得了优良的成果。哈尔滨工业大学与香港中文大学相互合作，联合研制开发出一种全方位的移动清扫机器人1，成果喜人。在2005年底，哈尔滨工业大学研制完成一种能看家护院、自动清洁、操持家务，智能相当于七八岁孩子的家政服务机器人，如图1.2所示。这款家政服务机器人可以测算距离、自动识别障碍物，避免碰撞到家具和人等，能够很好地完成清洁任务。图 1.2 哈工大家政服务机器人浙江大学这方面也做了一些研究，成果显著，研制开发了一款家用的智能移动吸尘器，如图1.3所示。这种机器人利用超声波测距，并具有自动检测障碍物和自主避障的功能，可以按照沿边学习的路径规划方式完成打扫任务9。图 1.3 浙大智能吸尘器总之，移动机器人的研究开发是很具有发展潜力的，这同时也是人工智能领域研究的热点课题之一。国内外移动机器人的发展动态，也为本论文的研究提供了参考价值。划与定位技术研究得移动过程中不发生机器人与障碍物的碰撞，一系列安全位置就可以构成最佳路径。解决路径规划问题的关键在于设计一种恰当的环境模型表示方法，即一种数据结构，该结构能反映出机器人在某个位置上发生碰撞的可能性。然后，按照模型中的连通性构造与之对应的连通图。该连通图抽取了环境模型的连通性，忽略与路径规划不相干的信息，避免了因无关信息的引入使规划复杂化。这种连通图构成了问题状态空间，在该状态空间内利用搜索技术进行搜索，便可解出一条通路。将通路上的节点转化为实际模型中的表示形式，便可得到机器人的无碰路径。2.2 环境地图模型2.2.1 环境地图的建立我们用地图来表示环境的信息情况，对地图创建而言，有三个需要解决的基本问题：(1) 如何表示环境地图；(2) 如何获取环境信息；(3) 如何表示获取的信息并把它加入到地图中。一个环境表示方法所做的决策，将会影响到机器人位置表示可用的选择。并且，位置表示的准确性受到地图表示准确性的限制。所以在选择一个特殊的地图表示方法时，必须了解三个基本关系：(1) 地图的精度必须要匹配机器人需要达到的目标精度；(2) 地图的精度及其表示的特征类型必须要匹配机器人传感器返回的数据类型；(3) 地图表示的复杂性将直接影响到有关作图、定位和导航推理的计算复杂性。2.2.2 环境地图的分类关于环境地图的表示方法基本可以分为三种：可视地图，栅格地图和拓扑地图。每种方法都有其优点与缺点。可视图法是将机器人视为一点，机器人与各障碍物各顶点之间，地标点和障碍物各顶点之间以及各障碍物顶点与顶点之间的连线，均不能穿越障碍物，即直线是可视的。搜索最优路径的问题就转化为经过这些可视直线的从起始点到目标点最短距离问题。运用优化算法，可删除一些不必要的连线以简化可视图，缩短搜索时间。该法能够求得最短路径，但假设了机器人的尺寸大小忽略不计。对于 N条连线的搜索时间为 O(N2)。Voronoi图法和 Tangent 图法对可视图进行了改进。栅格地图表示法将整个环境分为若干相同大小的栅格，判断每个栅格并指出室内移动机器人的路径规划技术 9中心是否存在障碍物。栅格法将机器人工作环境分解成一系列具有二值信息单元的网格单元，多采用四叉树或者八叉树来表示工作环境，并通过优化算法完成路径搜索。该法以栅格为单位记录环境信息，环境被量化成具有一定分辨率的栅格，栅格大小直接影响着环境信息存储量的大小和规划时间的长短8。拓扑图是一种紧凑的地图表示方法，特别是在环境大而简单时。这种方法将环境表示成一张拓扑意义的图，图中的节点对应于环境中的一个特征状态地点(由感知决定)，如果节点间存在直接连接的路径则相当于图中连接点的弧。拓扑图的分辨率决定于环境的复杂度。这种方法可以实现快速的路径规划，也为人机交互下达指令提供了一种更为自然的接口。但环境中存在 2 个很相似的地方时，拓扑图法将很难确定这是否为同一节点。基于本研究的试验硬件环境，算法采用了栅格地图表示法，下面对栅格地图表示法基本思想和方法进行简要介绍。2.2.3 基于栅格法的环境地图栅格地图是在机器人系统中得到广泛应用的一种地图描述方法。首先由 Elfes和 Moraves 提出，在机器人的路径规划、导航、避障控制、位姿估计中均得到了广泛应用，并己成为一种通用的移动机器人地图描述方法。栅格地图是一种表示静态环境的方法，用每一个栅格被占据的概率值来表示环境信息，机器人所了解的每个栅格的信息直接与实际环境中某区域相对应9。栅格地图很容易创建和维护，即使使用精确度不高的声纳传感器也可以创建栅格地图来表示环境信息。1栅格地图的思想本算法选用的栅格表示法符合前面所作约定的待覆盖区域，采用二维矩形栅格表示环境，将整个待清洁环境网格化，也称为坐标离散化，通过清洁的实际面积与网格面积的映射来实现实际物理清洁区域的离散化，以“电子地图”的方式表示待清洁环境的特征。在“电子地图”中，被障碍物完全或部分占据的网格记为不可清洁区域，即障碍区域，完全没有障碍物的网格被视为可清洁区域，即自主机器人需要清洁的自由区域。2栅格地图的更新更新全局地图步骤描述如下:第一步：机器人的初始位置为全局坐标原点 X=(x，y，)T=(0，0，0)T，并从初始点开始探测周围环境，进行机器人定位、构建局部地图并更新全局地图，生成以机器人当前位置为中心的栅格。第二步：当机器人移动时，如果机器人在该栅格的范围内，转第三步，否则转第四步。划与定位技术研究第三步：机器人根据路径规划向未探测的区域移动，直到机器人超过该栅格范围为止，转第四步。第四步：老的栅格消失，同时，又创建了一个新的栅格，新形成的栅格以机器人走出前一个栅格范围边界为中心，也就是当它超过了栅格的区域时，就在当前机器人的位置为中心形成一个新的栅格，转第一步。如图 2.1 所示，位置 1、2、3 位于安全边界之内，栅格不需要新建，当机器人超过栅格区域时，下一个新的栅格就会形成，并且以机器人的当前位置，即位置 4为中心。图 2.1 栅格地图的更新机器人在行进中，不断进行路径规划，定位和全局地图的更新，直到机器人行进结束最终生成完整的环境地图。2.3 区域覆盖路径规划基于不同的研究方向，自主机器人的路径规划有不同的分类标准。根据自主机器人完成作业的不同将路径规划分为点到点的路径规划和区域覆盖路径规划两种。区域覆盖路径规划是一种在二维工作空间中特殊的路径规划，是指在满足某种性能指标最优的前提下，寻找一条在待覆盖区域内从起始点到终点且经过所有可达到点的连续路径。2.3.1 区域覆盖路径规划方法覆盖是指机器人完全遍历所有无障碍区域，区域覆盖路径规划就是指机器人行走过的轨迹所形成的区域要与目标区域重合，对整个目标区域进行探测，规划出一条自主机器人的行走路径，且无遗漏、不重复的覆盖整个区域，同时要避开区域内任何障碍物，完成特定的任务。常见的区域覆盖路径规划方法有以下几种。室内移动机器人的路径规划技术 11(1) 单元分解法单元分解法是将环境根据障碍物的形状和分布情况分解为多个单元，而后在此基础上实现遍历算法。在设计出对单元区域进行局部遍历的基础上，完全遍历规划简化为对各个单元区域进行依次遍历问题。单元分解法按单元划分的精确度分为：近似单元分解法14(ApproximateCellularDecomposition)，精确单元分解法15(Exact Cellular Decomposition)。近似单元分解法是将整个环境空间划分为障碍物区、空间区和混合区。根据划分单元的大小又分为等单元分解和不等单元分解，如图 2.2 所示。目前，有两种主要的精确单元分解算法：Trapezoidal 单元分解算法16和 Boustrophedon 单元分解算法17。Trapezoidal 算法将环境分解为梯形单元，基于矩形分解法的移动机器人完全遍历算法在单个单元区域中机器人通过往返移动来进行遍历，如图 2.3（a）所示。Boustrophedon 算法是 Trapezoidal 算法的改进，其目的是减少由于单元分解过多而造成的重复遍历，如图 2.3（b）所示。值得注意的是，Boustrophedon 算法之减少了机器人在相邻单元之间移动时所产生的重复遍历，机器人在不相邻单元之间移动时所产生的重复遍历并没有减少。Choset 详细介绍了机器人在不同分块间移动的算法18。Garcia E、Gonzalez P 对 Choset 算法进行补充，并详细介绍了在未知环境下基于 Boustrophedon 单元分解法的完全遍历算法19。图 2.2 近似单元分解法图 2.3 精确单元分解法划与定位技术研究(2) 模板模型规划法模板模型根据先验知识，定义了几种典型模板。在路径规划时让事先定义的模板与环境匹配，整个路径就是由一系列的模板组成的。在这个方法中，为了简化路径规划过程，环境事先扩大，机器人就可以考虑成一个质点。该算法首先见于参考文献20，但该文章中提出的模板算法不能应用于有障碍的环境中。参考文献21中 De Carvalho 等提出了一种依靠二维环境的地图的完全遍历路径规划模板，定义了五种模板:前进模型(Towards Marker，TM)、沿边转向模型(Side Shift，SS)、回逆跟踪(Backtracker，BT)、U 转弯模型（U-Turn，UT)、U 转弯交替模型(UTurn Interlaced，UTI)。该算法对前面提出的模板算法进行改进，可以应用于基于地图的有障碍环境并且对环境中出现的未知障碍有相应处理策略。由于环境的复杂性，很难找到能适应任何环境的一组模板。这就大大限制的模板模型法在完全遍历路径规划中的应用，特别是在一些特殊情况比如遇到存在凹陷的障碍物时，机器人就会进入无法处理的死循环状态。这种情况出现的主要原因是由于对整个环境缺乏整体规划。此外，基于模板的模型完全遍历路径规划，它要求事先定义环境模型和模板的记忆，因此对于变化着的环境就不好处理了，比如在遍历过程中突然出现一个障碍等。(3) 栅格地图路径规划法该方法是基于栅格环境地图的路径规划，具体的路径规划策略将在下一小节给予详细的介绍。2.3.2 区域覆盖策略1. 随机方式随机方式路径规划的基本思想是在一个连通区域里，使清洁机器人从起点出发，以一定的行走方式(如直线方式)，沿着某种角度行走的一种随机的路径规划。清洁机器人从起点出发，遇到边界后以一定的角度(如 30 度)转弯，继续前行，如此反复进行碰撞，转弯，直行，直至其运行的轨迹覆盖整片区域。随机方式是一种相对简单的路径规划方式。这种规划方式没有特定的运动轨迹，当遇到障碍物的时候也没有一定的避障规则。所以该方式选择的运动轨迹是随机的，在遇到障碍物时运动方向的改变也是随机的，因此该方式在覆盖效率和运行时间方面具有相当的不确定性。同时，该方式不能确定覆盖区域的大小，也无法控制重复覆盖率的大小。另外一方面，该方式无法确定运动的起始点和终止点。综上所述，虽然该方法控制简单，但是上述明显的缺点影响了它在路径规划算法中的进一步应用。据统计36，随机方式路径规划的覆盖率一般在 10%30%之间；在没有障碍物划与定位技术研究碍的边缘，到达另一边的顶端边界点，进行另一边的基本覆盖策略的覆盖。如图2.5 所示：图 2.5 孤立障碍覆盖策略3. 内螺旋方式内螺旋方式的路径规划即让机器人沿着墙壁或障碍物的边界移动，进行内螺旋式“回”字型路径规划。机器人开始工作时先绕房间行走一周，以熟悉环境，计算出清洁面积，限定后面的运行路径范围。在障碍物信息(位置和形状)预先给定的情况下，采用沿边行走的路径规划算法，即让机器人沿着墙边或障碍物的边界移动，进行内螺旋式“回”字型路径规划29，如图 2.6 所示，图中箭头表示行走方向，直线表示行走路线。这种路径规划行程较短，理论上减少了转弯的次数，可避免“外螺旋式”和“迂回式”的边缘效应，易于实现较大的覆盖率同时，“内螺旋式”的终点位于区域中心附近，远离障碍物，从而在区域覆盖问题上，有利于机器人在区域间的衔接行走，从而有效地提高了清洁效率。图 2.6 内螺旋规划方法示意图2.4 点到点的路径规划点到点的路径规划是针对室内二维工作环境，其目标是为机器人寻找一条从起点到目标点的能够避开障碍物的尽可能短的路径。点到点的路径规划是一种从室内移动机器人的路径规划技术 15起始点到终点的最优路径策略，它要求寻找一条从起始点到终点的代价最小、路径最短、时间最短并且合理的路径，使自主机器人能够在工作空间内顺利地行走而不碰到任何障碍物。2.4.1 点到点路径规划方法目前，点到点的路径规划方法大致有以下几种：1.可视图法T.Lozano-Perez 和M.A.Wesley 等人在1979年提出了一种无碰路径规划算法位姿空间法，并基于位姿空间法提出了可视图法。该方法视自主机器人为一个质点，将所有障碍物的顶点和机器人起始点及目标点用直线组合连接，要求机器人和障碍物各顶点之间、目标点和障碍物各顶点之间以及各障碍物顶点与顶点之间的连线均不能穿越障碍物，即直线是“可视的”，然后搜索从起始点到目标点的最短距离的可视直线，寻求最优的路径。2.自由空间法10该方法是把自主机器人的工作空间分成两部分，即自由空间和障碍物空间。用某种搜索策略在自由空间中找到一条路径，自主机器人沿着障碍物之间的通道中心运动。对于较狭窄的空间区域，它能保证自主机器人最大的允许误差，而避免与障碍物碰撞；而另一方面，在某些情况下，路径偏离自主机器人的前进目标太远。另外，路径会因为复杂曲折多变而不利于自主机器人的行走，因而该方法仅适用于路径精度要求不高，机器人速度不快的场合。因此该方法的优点是比较灵活，起始点和目标点的改变不会造成连通图的重构，缺点是算法的复杂程度与障碍物的多少成正比，且不是任何情况下都能获得最短的路径。3.人工势场法人工势场法11最初是由Khatib提出的一种虚拟力法，该方法的思想类似于电子在正负电荷产生的电场中运动。将目标点看作吸引点，障碍物看成排斥点，机器人沿着吸引点和排斥点产生的合力方向运动。它构造一个叫做市场函数的标量函数，使得机器人的目标位姿对应于其最小值，障碍物区域对应于一些较大的值，在任何其它的位置，势函数都是向机器人目标位姿单调递减的。这样，不论机器人处于自由空间的任何位置，只要有路径存在，它能通过势能值的负梯度方向找到目标位姿。对应于障碍物的区域有较大的值可以保证生成路径的无碰性。该方法的优点是可以使机器人迅速躲开图法障碍物，实时性好。但传统的人工势场法存在几大缺陷：存在陷阱区；在相邻障碍物之间不能发现路径；在障碍物前震荡；在狭窄通道中摆动；当目标附近处有障碍物时，机器人无法到达目标点。这些不利因素限制了人工势场法在全局路径规划中的应用。但由于其计算简单而经常被划与定位技术研究用于局部路径规划的设计，适用于避碰和动态的路径规划。4.遗传算法在20世纪60年代初J.Holland提出了遗传算法，以自然遗传机制和自然选择等生物进化理论为基础，构造了一类随机化搜索算法。它利用选择、交叉和变异等遗传操作来优化控制算法，不要求适应度函数是可导或连续的，只要求适应度函数为正，同时作为并行算法适用于全局搜索。多数优化算法都是单点搜索算法，很容易陷入局部最优，而遗传算法却是一种多点搜索算法，因此更有可能搜索到全局最优点。遗传算法的整体搜索策略和优化计算不依赖于梯度信息，解决了一些其它优化算法无法解决的问题。但是，一些遗传算法在环境中存在大量复杂的不规则障碍物时，通常不能有效求解或搜索效率很低，速度较慢。5.其他方法近年来，人工智能方法正在成为研究的热点，神经网络在机器人路径规划中的应用得到了广泛的重视。一些神经网络模型通过学习可