毕业设计（论文）-超声测距的移动机器人路径导航.docx

1、.超声测距的移动机器人路径导航摘要随着机器人技术的不断发展，自主移动机器人正越来越成为研究的热点。导航技术是其研究核心，而路径规划又是移动机器人导航中最重要的任务之一。基于超声波测距的自主移动机器人路径规划是移动机器人技术中的一项重要研究课题。本文对基于超声波测距的自主移动机器人路径规划问题进行了较为深入的探讨和分析。首先。对自主移动机器人的发展状况，以及移动机器人导航技术和路径规划技术的国内外发展现状进行了综述。然后介绍了超声波测距原理，讨论了超声波测距系统应用于导航技术的优势。重点探讨了基于超声波测距的自主移动机器人路径规划技术，采用栅格法进行环境建模，运用了一种称作沿边走的算法进行了路径

2、规划。最后分析了现有方案的优缺点，展望了机器人路径规划技术的未来发展趋势和研究方向。关键字：自主移动机器人；超声波；路径规划 目 录第一章 绪论-51.1 论文背景和意义-51.2 国内外研究现状-61.2.1 自主移动机器人导航技术现状-61.2.2 自主移动机器人路径规划技术现状-71.3 本论文的主要内容-9第二章 超声波测距技术-102.1 移动机器人中的测距技术-102.1.1 无源测距技术-102.1.2 有源测距技术-102.2 测距传感器的选择性分析-122.3 超声波测距-132.3.1 超声波发生器-132.3.2 压电式超声波发生器原理-142.3.3 超声波测距原理-1

3、42.4 本章小结-15第三章 环境建模-163.1 栅格法简介-163.2 栅格法建模-173.3 基于超声波传感器测距的栅格化方法-173.4 本章小结-18第四章 基于超声波测距的沿边走路径规划的导航算法-19 4.1 坐标系的建立-194.2 基于超声波测距的沿边走路径规划机器人的导航算法-20 4.2.1 沿边走算法简介-20 4.2.2 沿边走过程-21 4.3 沿边走路径规划流程图-234.4 本章小结-24 第五章 结果分析-255.1仿真结果-255.2 结果分析-265.3 本章小结-26第六章 现有方案缺陷及路径规划技术的发展趋势-27 第七章 结论-29参考文献-30致

4、谢-31附录-32第一章 绪论1.1 论文背景和意义自1962年美国研制出世界上第一台工业机器人以来，经过40余年的发展，机器人技术以及应用都已取得非常大的进步。可以说机器人的出现，是20世纪人类最伟大的发明之一。 科学家对机器人的定义是：“机器人是一种自动化的机器，所不同的是这种机器具备一些与人或生物相似的智能能力，如感知能力、规划能力、动作能力和协同能力，是一种具有高度灵活性的自动化机器”1。随着机器人的应用越来越广泛，人们对机器人技术智能化本质的认识也在不断加深，机器人技术开始向人类活动的各个领域渗透。于是出现了各式各样的具有感知、决策、行动和交互能力的特种机器人和各种智能机器

5、，如微机器人、水下机器人、医疗机器人、军用机器人、空中空间机器人、娱乐机器人等。机器人技术在不断发展，人们对机器人在社会服务、野外作业以及在有害、危险环境作业中的应用也越来越重视。研究能够在复杂环境中自主运动和自动作业的智能自主移动机器人势在必行。移动机器人是机器人学的一个重要分支，其研究始于20 世纪60年代。移动机器人由于具有更大的使用灵活性已成为目前机器人技术研究的一个热点。近年来，移动机器人技术在工业、农业、航天及空间探测等许多领域都起到了重要的作用，显示了广泛的应用前景2。自主式移动机器人具有高度自规划、自组织、自适应能力，适合于在复杂的非结构化环境中工作。自主式移动机器人的目标是在

6、没有人的干预、无需对环境做任何规定和改变的条件下，有目的地移动和完成相应任务。在自主式移动机器人相关技术的研究中，导航技术是其研究核心，也是移动机器人实现智能化及完全自主的关键技术。而路径规划又是移动机器人导航中最重要的任务之一。基于超声波测距的自主移动机器人路径规划正是机器人智能控制技术中的一项重要课题。1.2 国内外研究现状 机器人技术是一门综合性的学科。世界各地的专家学者都在不断致力于机器人技术的研究，尤其是移动机器人的导航和路径规划技术方面，已经取得了相当多的研究成果。1.2.1 自主移动机器人导航技术现状导航是移动机器人应具备的基本功能，是移动机器人实现智能化及完全自主工作的关键技术

7、之一。理想的移动机器人应具有以下能力：当处于一个未知的、复杂的、动态的非结构环境中，并且在没有人的干预下，通过感知环境，能够到达期望的目的地，同时应尽量减少时间或能量的消耗等。正是由于有了导航装置，移动机器人在行走过程中才能确定行动的方向，才不会与障碍物发生碰撞。移动机器人常见的导航方式有磁导航、惯性导航、激光导航、视觉导航等。地下埋线的导航方式是20世纪50年代美国开发的，到20世纪70年代这种导航方式迅速发展并应用于柔性生产。目前，国内制造行业使用的移动机器人大多还是基于这种导航方式。该导航方式的技术已十分成熟，但其成本高，改造和维护困难。就国内研究现状来看，以上几种导航方式均在研究之中，

8、而磁导航方式的技术已相当成熟。中国科学院沈阳自动化研究所已生产出基于磁导航的多代机器人产品。其他导航方式的机器人也在研究之中，如：清华大学已研制的三代THMR 移动机器人，上海大学的“导购机器人”、哈尔滨工业大学研制的“导游机器人”和正在开发的各种服务机器人。诸多研究表明：视觉导航方式具有信号探测范围宽、获取信息完整等优点， 将成为未来机器人导航的一个主要发展方向。在视觉导航方式中，目前国内外应用最多的还是采用在机器人上安装车载摄像机的基于局部视觉的导航方式，如：D. L. Boley3等研制的移动机器人利用车载摄像机和较少的传感器通过识别路标进行导航，比直接采用卡尔曼滤波器获得了更好的实时性

9、，并有效抑制了噪声；A. Ohya4等利用车载摄像机和超声波传感器研究了基于视觉导航系统中的避碰问题；P. I. Corke5等对由车载摄像机构成的移动机器人视觉闭环系统的研究表明，这种控制方法对提高路径跟踪精度有较好效果。视觉导航研究由于受到现有计算设备运算速度和存储容量的限制而发展较慢，但随着计算机图像处理能力和技术的提高，加之视觉导航具有信号探测范围宽、目标信息完整等优势，在图像处理速度得到解决之后，视觉导航仍将是主要导航方式。在一个智能系统中，使用单一的智能控制方法，往往不能取得满意的效果。应综合采用常规控制方法和智能控制方法，才能够取得良好效果。 神经网络和模糊推理是自主导航研究中的

10、两个重要工具，但是神经网络样本集的完整性研究尚未取得突破，将事件空间的每一点都作为网络的学习样本显然是不可取的；模糊逻辑推理则侧重于模糊规则的选取，但有些规则很难形式化描述，或者必须用大量的规则描述而增大运算量，这样就背离了模糊逻辑应用的初衷，因此近年来将神经网络与模糊逻辑结合起来，应用到自主导航研究中就成了机器人研究的热门课题。传感器融合技术在近年来被引入到了机器人导航研究中，并已取得令人振奋的成果，采用常规传感器导航的移动机器人将成为机器人产业的主要发展方向。 当然，在一些复杂的地理条件下，非视觉传感器的探测范围就不如视觉系统那么完整，目前对于一些高精度的导航还难以胜任，因而开发新型传感器

11、或按照一定融合策略构造传感器阵列以弥补单个传感器的缺陷，以及提出新的融合方法来完善探测的结果，都将是重要的研究方向。1.2.2 移动机器人路径规划技术现状路径规划是移动机器人导航中最重要的任务之一。它是按照某一性能指标搜索一条从起始状态到目标状态的最优或近似最优的无碰路径。机器人路径规划的研究起始于20 世纪70 年代，目前对这一问题的研究仍然十分活跃，国内外学者作了大量的工作。目前，路径规划可以分为三种类型:一种是基于环境先验完全信息的路径规；另一种是基于传感器信息的不确定环境的路径规划；第三种是基于行为的路径规划方法。(1) 基于环境先验完全信息的路径规划 该方法也被称为全局路径规划，能够

12、处理完全已知环境下的移动机器人路径规划。当环境发生变化时，如出现未知障碍物时，这种方法就无能为力了。这种方法包括以下几种：可视图法，栅格法和拓扑法等。可视图法(visibility graph)6是将机器人视为一点，把机器人、目标点和多边形障碍物的各个顶点进行连接，要求机器人和障碍物各顶点之间，目标点和障碍物各顶点之间以及各障碍物顶点与顶点之间的连线，都不能穿越障碍物，这样就形成了一张图，称之为可视图。由于任意两直线的顶点都是可视的，显然移动机器人从起点沿着这些连线到达目标点的所有路径均是无碰路径。对可视图进行搜索，并利用优化算法删除一些不必要的连线以简化可视图，缩短了搜索时间，最终就可以找到

13、一条无碰最优路径。栅格法(grids)7是将移动机器人工作环境分解成一系列具有二值信息的网格单元，多采用二维笛卡儿矩阵栅格表示工作环境，每一个矩形栅格都有一个累积值CV，表示在此方位中存在障碍物的可信度。CV 值越高，表征存在障碍物的可能性越高。用栅格法表示格子环境模型中存在障碍物的可能性的方法起源于美国CMU大学。通过优化算法在单元中搜索最优路径。由于该方法以栅格为单位记录环境信息，环境被量化成具有一定分辨率的栅格，因此栅格的大小直接影响着环境信息存储量的大小以及路径搜索的时间，因此在实用上受到一定的限制。拓扑法8是根据环境信息和运动物体的几何特点，将组成空间划分成若干具有拓扑特征一致的自由

14、空间，然后根据彼此间的连通性建立拓扑网，从该网中搜索一条拓扑路径。该方法的优点在于因为利用了拓扑特征而大大缩小了搜索空间，其算法复杂性只与障碍物的数目有关，在理论上是完备的。但建立拓扑网的过程是相当复杂而费时的，特别是当增加或减少障碍物时，如何有效地修正已经存在的拓扑网络以及如何提高图形搜索速度是目前亟待解决的问题10 。但是针对一种环境，拓扑网只需建立一次，因而在其上进行多次路径规划就可期望获得较高的效率。(2) 基于传感器信息的局部路径规划人工势场法( artificial potential field) 最初由Khatib 提出9，这种方法由于它的简单性和优美性而被广泛采用。其基本思想

15、是把移动机器人在已知全局环境中的运动看作一种虚拟的人工受力场中的运动。目标点对机器人产生引力作用，障碍物对机器人产生斥力作用，引力和斥力的合力控制机器人的运动。这种方法结构简单，易于实现。但是这种方法也存在着一些缺点:如存在陷阱区，在相近的障碍物前不能发现路径，在障碍物前产生振荡以及在狭窄通道中摆动等缺点。针对人工势场法的缺陷，国内外许多专家学者不断寻找新的途径，以克服该方法所存在的弊端。如文献10结合栅型声纳测试，建立一种新类型的势场函数，为距离转换路径寻找算法。文献11采用预测与势场法相结合的算法解决移动机器人的导航问题，取得了良好的效果。文献12通过引入虚拟障碍物使搜索过程跳出局部最优的

16、陷阱，但引入虚拟障碍物可能会产生新的局部极小点，同时也增加了算法的复杂度。基于传感器的模糊控制方法和神经网络控制方法见文献，因其对硬件要求比较高，简单的配置不易使移动机器人实现快速实时运动规划。(3) 基于行为的路径规划方法 所谓基于行为的研究方法是把移动机器人所要完成的任务分解成一些基本的、简单的行为单元，这些单元彼此协调工作。每个单元有自己的感知器和执行器，二者紧耦合在一起，构成感知动作行为，机器人根据行为的优先级及结合本身的任务综合作出反应。该方法的主要优点在于每个行为的功能较简单，因此可以通过简单的传感器及其快速信息处理过程获得良好的运行效果。但这种方法主要考虑机器人的行为，而对机器人

17、所要解决的问题以及所面临的环境没有任何的描述，只是通过在实际的运行环境中机器人行为的选择，达到最终的目标。如何构造和优化机器人行为控制器是成功与否的关键。主要方法包括:基于传感器信息的局部运动规划方法和基于模糊逻辑及神经网络的监督学习方法等。1.3 本论文的主要内容本论文的主要研究基于超声波测距的自主移动机器人路径规划技术，重点进行了以下工作：（1）概述自主移动机器人的发展状况，以及国内外导航技术和路径规划技术的发展现状。（2）介绍移动机器人中的两种常用测距技术有源测距和无源测距。并详细介绍机器人超声波测距原理以及超声波测距系统应用于导航技术的优势。（3）重点探讨基于超声波测距的自主移动机器人

18、路径规划技术。采用栅格法进行环境建模，运用一种称作沿边走的算法来进行路径规划。（4）分析现有方案的优缺点，展望机器人路径规划技术的未来发展趋势和研究方向。第二章 超声波测距技术2.1 移动机器人中的测距技术 在研究机器人的避障时，环境信息的采集是研究的关键问题。距离测量为移动机器人提供了周围环境的二维或三维信息，是移动机器人中不可缺少的组成部分。移动机器人可以根据这些信息进行实时避障、导航和执行特定的任务。通常，对获取这类环境信息的传感器有两方面的要求：一方面，需要有足够大的视场来覆盖整个工作区；另一方面，需要有足够高的采集速率以保证在运动的环境中提供实时的信息。2.1.1 无源测距技术经典的

19、距离测量方法使用无源测距技术，我们称之为被动方法，例如立体视觉和结构光方法。立体视觉：在机器人获取信息的各种感知器中，视觉系统无疑是最重要的。从仿生学的角度来说，基于双目视觉原理的立体视觉系统最接近生物体的视觉系统，但由于受到原理计算法的限制，测距精度和成象速度不能满足要求。结构光测距：结构光测距的原理与光学测距法类似，使用单一光点或平面逐点测量从而获得物体的完整的三维描述。这种方法虽然能够产生比较精确的结果，但是其速度过慢而无法用于实时任务。在移动机器人的领域中，无源测距方法大都无法同时满足可靠性或实用性的要求。有源测距技术使用主动传感器替代被动传感器，它由于具有以下的两大优点而在实时机器人

20、领域显示出诱人的魅力：（1）主动传感器不存在复杂的图象匹配技术，不象立体视觉需要通过大量的计算获取距离数据，因而实时性好，测距速度快。（2）主动传感器不易受到如天气状况、光照条件及表面标记、阴影、污渍等外界条件的影响。主动传感器工作时不仅使用自然光照，它自身也对被测物体产生光照。此外，在多数主动传感器系统中，有源光的发送和接受是同轴的，这就从本质上解决了结构光和立体视觉方法难于解决的“消失片段”问题。2.1.2 有源测距技术 在有源测距技术中，常用的主动传感器主要有超声波、微波雷达和激光雷达三种。（1）超声波传感器超声波是一种只有少数生物（如蝙蝠、海豚）才能感觉到的机械波，其频率在20KHz以

21、上，波长短，绕射小，能定向传播。它具有纵波（在气、液、固中传播）、横波（在固体中传播）和表面波（沿固体表面传播）三种波形，而且遇到杂质或传播界面回产生明显的反射13。这种反射不是严格定向的，具有散射性。在移动机器人中应用的超声波传感器，是利用超声波在空气中的定向传播和固体反射特性（纵波），通过接收自身反射的超声波反射信号，根据超声波发出和回波接收时间差及传播速度，计算出传播距离，从而得到障碍无物到机器人的距离。从发射波束特性知，由于扩散角的原因，使超声波测距的角度分辨率较低，但距离分辨率较高。超声波传感器具有反应灵敏、探测速度快的优点，而且结构简单，体积小，成本低，因而在目前已知的移动机器人中

22、，多数都安装了它，用于室内和室外近距离避障。通常，以多个传感器组成阵列形式，根据单个传感器扩散角及反射特性。确定合理的密度，以覆盖要求的探测区域。总的来说，超声波传感器的造价低廉、速度快、距离分辨率较高，但其方向性差、镜面反射严重、测距范围小，因此，比较适用于室内环境的距离测量。（2）微波雷达微波是一种电磁波，其波长为，频率为，定向传播及反射性能介于超声波和激光之间。作为新型测距传感器，其工作原理与超声波传感器相同。角度分辨率高于超声波和红外传感器，低于激光传感器，距离分辨率略高于超声波传感器。目前最大探测距离介于超声波和激光测距之间，最小探测盲区距离略低于超声波传感器。微波雷达的优点是因目标

23、的颜色、材质等不同而引起的反射率变化小，对雾的透过率高，受灰尘、雾、雨的影响小，在各种目标和气候条件下都能比较稳定的进行探测。缺点是利用车载的小型天线时因为不能形成尖锐的射束，所以不能进行高精度测角。一般很难进行高精度测位。另外，根据目前的电波法规定，微波一般是不能使用的，但是不久的将来，经过修改以后，这种规定会被解除的，这项高新技术的产品，已用于国外汽车倒车及高速公路车辆间距监测等实用技术领域，并开始安装在新研制的移动机器人上，是一种很有前途的移动机器人深度信息传感器。（3）激光雷达近年来，激光雷达因具有测量速度快、测程远、测距精度高、方向性好、镜面反射小、造价适中等优点而受到广泛重视。激光

24、调制波的强度大，有利于远距离目标的测量及目标与背景的区分；光速窄、平行性好、散射小，保证了很好的测距方向分辨率；一般为单一频率的光波，光谱比较纯，保证了较高的信噪比。通过二维或三维的扫描激光束或光平面，激光测距雷达能够以相对高的频率提供大量准确的距离数据。激光测距雷达与其它距离传感器相比，它能够较好的同时考虑到精度要求和速度要求，特别是在移动机器人领域。它与传统获得深度信息的方法不同，激光测距雷达不仅可以在有环境光的情况下工作，也可以在无环境光中工作，而且在无环境光的情况下测量效果更好。但由于光线的传播速度极快，通常难以通过简单的装置估算其传播距离，因此在简单、低成本的应用中，并不适用。2.2

25、 测距传感器的选择性分析在本课题中，自主移动需要在实现避障和路径规划的基础上，完成局部自主式移动，因此它必须对其工作环境的状态有一清楚的了解。同时，由于涉及到不同的工作场合，成本的高低，安装麻烦等限制，我们在设计的过程中，排除了用外部的测量、定位和导航系统的可能性。因此，在这里，机器人将依靠其自身携带的传感器，通过主动探测的方式来完成对外部环境的感知。由于在实现避障和无碰撞路径规划的过程中，机器人本身与周围环境以及障碍物之间的距离是最关键的因素。因此，我们对于传感器的选择，也集中在测量距离这一参数上。如上一节所述，超声波测距技术是一种有源非接触性测距技术，是利用超声波在空气中的定向传播特性和固

26、体反射特性，通过接收自身反射的超声波反射信号，根据超声波发出及回波接收时间差及传播速度，计算出传播距离，从而得到障碍物到机器人的距离。由于超声波传感器具有成本低廉，采集速度快，距离分辨率高，质量轻、体积小、易于装卸的优点，并且超声波传感器在采集环境信息时不存在复杂的图象匹配技术，不需要通过大量的计算就可获得数据，因而其测距速度快，实用性好。同时超声波传感器不易受到天气条件、环境光照及障碍物阴影、表面粗糙度、裂缝等外界环境条件的影响。鉴于以上种种优点，使得超声波传感器在移动机器人的应用中具有很大的优势。因此，在这里我们选择超声波测距传感器作为智能机器人的主要传感部件。目前，超声波测距传感器在移动

27、式机器人导航中应用十分广泛。它的测量原理是基于测量渡越时间，即测量从发射换能器发出的超声波，经目标反射后，沿原路返回到接收换能器所需的时间。由渡越时间和介质中的声速即可求得目标与传感器之间的距离。2.3 超声波测距 为了检测作业对象及环境或机器人与它们的关系，在机器人上安装了触觉传感器、视觉传感力觉传感器、接近觉传感器、超声波传感器和听觉传感器，大大改善了机器人工作状况，使其能够更充分地完成复杂的工作。由于外部传感器为集多种学科为一身的产品，有些方面还在探索之中，随着外部传感器的进一步完善，机器人的功能越来越强大，将在许多领域为人类做出更大贡献。为了使移动机器人能自动避障行走，就必须装备测距系

28、统，以使其及时获取距障碍物的距离信息（距离和方向）。由于超声波指向性强，能量消耗缓慢，在介质中传播的距离较远，因而超声波经常用于距离的测量，如测距仪和物位测量仪等都可以通过超声波来实现。利用超声波检测往往比较迅速、方便、计算简单、易于做到实时控制，并且在测量精度方面能达到工业实用的要求，因此在移动机器人的研制上也得到了广泛的应用。 2.3.1 超声波发生器 超声波发生器可以分为两大类：一类是用电气方式产生超声波，一类是用机械方式产生超声波。电气方式包括压电型、磁致伸缩型和电动型等；机械方式有加尔统笛、液哨和气流旋笛等。它们所产生的超声波的频率、功率和声波特性各不相同，因而用途也各不相同。目前较

29、为常用的是压电式超声波发生器。 按收发方式又分两类：一类是发射和接收分别是两种不同的分体式超声波传感器，此类传感器测距有效范围比较大，但不具备防尘、防水性能，如用于发射的MA40A5S及用于接收的MA40A5R 。另一类是具有双向的发射/接收功能的收发一体式超声波传感器，如R/S40，不仅用于发射超声波，也用于接收超声波，此类超声波测距有效范围比较小，防尘、防水性能好，主要用于汽车倒车雷达。2.3.2 压电式超声波发生器原理 压电式超声波发生器实际上是利用压电晶体的谐振来工作的。超声波发生器内部结构如图2-1所示，它有两个压电晶片和一个共振板。当它的两极外加脉冲信号，其频率等于压电晶片的固有振

30、荡频率时，压电晶片将会发生共振，并带动共振板振动，便产生超声波。反之，如果两电极间未外加电压，当共振板接收到超声波时，将压迫压电晶片作振动，将机械能转换为电信号，这时它就成为超声波接收器了。超声波传感器在机器人上的分布如图2-2所示。 图2-1 超声波传感器结构 图2-2 超声波传感器位置分布图 2.3.3 超声波测距原理超声波是一种一定频率范围的声波。它具有在同种媒质中以恒定速率传播的特性，而在不同媒质的界面，会产生反射现象。利用这一特性，就可以根据测量反射波与发射波之间的时间间隔，从而达到测量距离的作用。其主要有三种测量方法：（1）相位检测法相位检测法虽然精度高，但检测范围有限（2）声波幅

31、值检测法声波幅值检测法易受反射波的影响（3）渡越时间检测法超声波测距是通过不断检测超声波发射后遇到障碍物所反射的回波，从而测出发射和接收回波的时间差t，然后求出就可以计算出发射点距障碍物的距离：D = C T/ 2 （2-1）这就是渡越时间法测距机理。式中：D距离；S声波在介质中传播的速度； T声波传输所用时间。声波在空气中传输速率为： （2-2） 式中：T绝对温度；331.4 m/s。在测距精度不是很高的情况下，一般认为C为常数340m/s。附录中表2列出了几种不同温度下的声速。在使用时，如果温度变化不大，则可认为声速是基本不变的。如果测距精度要求很高，则应通过温度补偿的方法加以校正。用于行

32、走机器人上的超声测距系统共有4对超声波换能器，分别装在前、后、左、右4个方向上。采用AT89C52单片机，由单片机定时向发射机发出控制信号，其脉冲宽度为0.25ms，同时启动定时器。发射机产生40KHz左右的调制脉冲，经换能器转换为超声波信号向前方空间发射。超声波信号在空间中传播遇到障碍物后，将反射回波。其反射波被接受机收到后，变成电信号脉冲，该信号经放大、滤波、整流、比较后，产生负脉冲触发单片机外部中断读出此时定时器值，即得出超声波在空气中传播的时间。再根据公式（2-1）即可求得距离。2.4 本章小结本章先介绍了移动机器人中常用的两种测距技术无源测距和有源测距，并对测距传感器的选择做了分析，

33、讨论了超声波测距的优越性。然后详细讲述了超声波发生器原理和超声波测距原理。 第三章 环境建模对环境的感知是自主式移动机器人研究的关键技术之一。环境信息的描述是实现机器人自主式导航的算法基础。环境信息采集和建模描述的精确度应该以实现对机器人导航的可靠性为基础。强制要求传感器对环境信息采集和描述的精确度会影响传感器的信息采集速率，增加算法复杂度和计算量，从而影响算法的实时性、可靠性和鲁棒性。虽然现在对环境信息的建模方法有很多种，比较成功和有效的方法主要有势场法和栅格法。这里仅介绍和使用栅格法来进行环境建模。3.1 栅格法简介栅格法(grids) 是将移动机器人工作环境分解成一系列具有二值信息的网格

34、单元，多采用二维笛卡儿矩阵栅格表示工作环境，每一个矩形栅格都有一个累积值CV ，表示在此方位中存在障碍物的可信度。CV 值越高，表征存在障碍物的可能性越高。用栅格法表示格子环境模型中存在障碍物的可能性的方法起源于美国CMU大学。通过优化算法在单元中搜索最优路径。由于该方法以栅格为单位记录环境信息，环境被量化成具有一定分辨率的栅格，因此栅格的大小直接影响着环境信息存储量的大小以及路径搜索的时间，因此在实用上受到一定的限制。栅格法将基于传感器系统的地图模型识别法和测距法相结合，环境描述易于创建和维护，对某个网络的感知信息可直接与环境中某个区域对应，机器人对所测的障碍物具体形状不太敏感，具有直观简洁

35、、分辨率高等特点，适用于室内等中小环境路径规划地图模型的建立14。栅格法与其它环境建模方法相比具有以下特点：（1）所建立的栅格跟系统所采用的传感器类型有关。不同的传感器由于采集环境信息的方法不同，所获得栅格形状和精确度也不同。（2）对栅格中的障碍物形状和具体定位在全局坐标中不能表示出来。3.2 栅格法建模在这里采用栅格法建立环境地图模型。忽略机器人的旋转运动，墙壁为直线型，视房间为一个矩形，按照设定好的清洁范围，以机器人大小尺寸为基本单元，将房间自动划分成互不重叠的单元格，形成栅格图，每个栅格表示一个自由区域或障碍区域。如图 图3-1环境地图模型图中，A点为机器人停放位置，机器人的工作位置可以

36、通过坐标（x，y）表示，设工作房间长X，宽Y，则x为沿X方向坐标，y为沿Y方向坐标。参数X和Y可以任意调整。白色区域表示自由区，机器人可以自由活动。黑色区域表示障碍区，机器人不能通过，非线形障碍物可以近似等效为线形。3.3 基于超声波传感器测距的栅格化方法如图3-2所示，我们利用多对超声波传感器的角度扫描范围，以及传感器最大距离探测误差为半径分割整个平面，这样，我们就得到一个被分割成许多栅格的平面。 图3-2 超声波扫描测距示意图由于超声波传感器角度分辨率差，利用栅格法获取环境信息是较为可行的基本方法。现在，我们就两个超声波传感器A、B讨论一下环境信息的获取。图中，a为传感器的角度探测范围，b

37、为传感器B的角度探测范围。Ra为A探测到的最近障碍物的距离，Rb为B探测到的最近障碍物的距离。当RaRb(Ra与Rb之间差距大于一个阀值)时，我们认为距离A最近的障碍物在栅格1中，也就是栅格1中存在障碍物，而在栅格2中不存在障碍物。同理，当RbRa时我们认为距离B最近的障碍物在栅格3中，也就是栅格3中存在障碍物，而栅格2中不存在障碍物。而当Ra=Rb时，我们认为距离a 或b最近的障碍物可能在1，2，3任意栅格中，也就是1，2，3中都有有存在障碍物的可能。当然，这只是推理的原理，在实际应用中，我们是根据栅格中存在障碍物的可信度来记录环境信息的。也就是说，当我们进行一次探测后，我们将可能

38、存在障碍物的栅格的CV值加1。而在另一方面，我们将不可能存在障碍物的栅格的CV值设为05。这样，我们就超声波传感器获取的环境信息转化为我们所需的栅格信息。我们可以看到，随着超声波传感器数量增多，栅格的粒度就越小，我们获取的栅格信息也就越精确。由于超声波扫描本身的特性，使得所建立的栅格是扇形的，这样不利于对整个工作环境（如房间，大厅等）进行栅格化，只要传感器的数量较多，这样的近似是可以接受的。另外，如果是家用自主式移动机器人如智能吸尘机器人，其所工作的环境是室内，并且由于超声波测距范围和精确度，以及工作环境面积大小等因素，这样就不能要求超声波传感器能在某个具体的位置，就能把整个室内环境的信息全部

39、记录下来。因此超声波传感器采集信息的工作方式应该是边走边扫描记录。在这种采集信息的工作方式下，其采集到的信息数据不仅跟环境静态的结构布局有关，并且室内环境中还存在动态的物体如人等，因此对采集到的信息进行建模时还应该考虑到时间的因素。也就是说采集到的物体位置信息（X，Y）不仅应该是二维平面的x和y的函数，也是时间t的函数。3.4 本章小结 本章主要介绍了栅格法的原理及特点。讲述了利用栅格法进行环境建模的建模过程以及基于超声波传感器测距的栅格化方法。第四章 基于超声波测距的沿边走路径规划的导航算法4.1 坐标系的建立在移动机器人的环境信息（主要是环境结构布局以及障碍物分布布局信息）进行描述时，必须

40、建立两个坐标系：全局坐标系和机载运动局部坐标系。这两者的关系如图4-1： 图4-1 全局坐标与机载运动坐标关系图（1）全局坐标系建立全局坐标系的目的是用来描述整个环境的信息，标识当前机器人的位置。全局坐标值描述了机器人当前在整个工作环境中所处的位置，因此全局坐标值可以用来对机器人定位。（2）车载坐标系由于自主式移动机器人是在运动过程中，探测当前环境的信息的。每次探测的距离信息都是以当前机器人的运动姿势来定量测量的。建立车体局部坐标系就是为了描述当前探测到的局部信息，它主要用于控制机器人的当前行走。全局坐标系与车载坐标系转换全局坐标系和机载运动坐标系的转换关系为： 其中为机载坐标系绕全局坐标系所

41、转过的角度。并定义为顺时针方向为正，逆时针方向为负。4.2 基于超声波测距的沿边走路径规划机器人的导航算法超声波传感器测距具有成本低廉，采集信息速率快，距离分辨率高，质量轻、体积小、易于装卸等优点，更加适合于家用的自主式移动机器人。因此本文在充分考虑家用自主式移动吸尘器的工作环境和设计时的相关因素的基础上，提出了一种称为沿边走的路径规划算法。4.2.1 沿边走算法简介所谓沿边走，顾名思义，是让移动机器人沿着墙边移动，在移动过程中，可以不断根据与墙边的距离调整所走方向，这样对于在移动中自身坐标不是很确定的移动机器人来说，可以辅助周边的事物对其当前位置进行调整。这就是我们采用“沿边走算法”的基本出

42、发点。当然，我们也考虑了效率的因素。首先，对于移动机器人，转弯是相当费时的，理论上，除了顺次扫描，沿边走能有效的减少转弯的次数。另外，考虑到家用型吸尘器通常工作环境为不大的房间(一般不超过30 平米) ，而我们采用的超声波传感器有效测距范围是2m ，这样，采用“沿边走算法”，我们能在沿墙边2m 的空间中始终采用沿边走的策略，也就是说，对于5 * 6 平米的房间，采用沿边走的策略可以扫描28 平米的范围(对于这样的效率，我们认为是可以接受的) 而对另外2 平米的空间可以采用扫描方法进行处理。这就是说，沿边走算法通常会分为两个步骤来进行，首先是沿着墙边进行有次序的扫描;另外是对于房间中间部分的扫描

43、，当然由于在这一部分区域中，机器人可能无法探测到墙壁或其他障碍物，可能会迷失方向，因此，并不需要采用沿边走策略。这种路径规划行程较短，理论上减少了转弯的次数，可避免“外螺旋式”和“往复前进式”的边缘效应，易于实现较大的覆盖率。同时，“内螺旋式”的终点位于区域中心附近，远离障碍物，从而在区域覆盖问题上，有利于机器人在区域间的衔接行走，从而有效地提高了清洁效率。清洁机器人路径规划是根据所感知到的工作环境信息，按照某种优化指标，从起始点到目标点规划出一条与环境障碍无碰撞的路径，并实现封闭区域内机器人行走路径对工作区域的最大覆盖率和最小重复率。清洁机器人的路径规划方法可以分为两类：无环境模型的路径规划

44、方法和基于静态结构化环境模型，在障碍物信息（位置和形状）预先给定的情况下，采用沿边走的路径规划算法，即让机器人沿着墙边或障碍物的边界移动，进行内螺旋式“回”字型路径规划，如图4-2所示。 图4-2 内螺旋式“回”字型路径示意图图中箭头表示行走方向，直线表示行走路线，虚线表示返回停放位置的可能路径。清洁机器人工作开始时先绕房间行走一周，一熟悉环境，计算出清洁面积，限定以后的运行路径的范围。4.2.2 沿边走过程下面我们看一下，在“沿边走算法”中的第一个步骤，我们称之为沿边走过程。在沿边走过程中，我们会遇到以下几种情况:(1) 墙边的障碍物对于墙边存在的障碍物，例如衣柜、沙发等，我们通常可以不去理

45、会，因为，对于移动机器人来说，它会把这些障碍物当作墙壁来处理，在这里，我们就不继续讨论了。(2) 不在墙边，但在沿边走过程中会碰到的障碍物对于此类障碍物，由于不在墙边，因此，在走第一圈时，是不会碰到的，但由于离墙边的距离小于超声波传感器的测距范围，因此会记录到障碍物链中。因为，我们关心的是沿着墙壁走以及离墙壁的距离，对这类障碍物并不需要进行特别处理，而只需沿墙壁的方向绕开即可。(3) 机器人自身定位为了能够提供机器人坐标系与全局坐标系的转换，机器人自身的坐标是相当重要的。相对机器人转弯的角度误差，我们较为相信移动机器人步进机前进时的距离信息。这也正是我们采用沿边走算法的主要因素之一。因为，我们

46、认为墙壁是直的，四周的墙壁应该形成矩形，这样在机器人沿墙边走的同时，我们可以让机器人与墙壁的距离来进行角度调整。另一方面，在沿边走算法中，机器人每走完一圈就要将移动时离墙壁的距离递增，因此，我们需要对完成一圈的行走进行判断。我们是通过两方面的信息进行的：一是角度信息，当机器人进行转弯时，记录角度值表示当前的行走方向。由于多数是90 度的转弯，因此可以对接近90 度的弯进行近似，这样就可以根据当前角度值，判断机器人是否走完了一圈，如果与初始角度值相同，则可认为在角度上机器人完成了一圈的行程。这样做，主要是有90 度的近似处理，因此只要在一圈中误差不超过45 度就可以进行判断，另外，由于是沿边走，

47、在一圈中机器人转弯次数并不多。因此，我们可以较好的处理机器人转弯时带来的角度误差。二是直角坐标信息，这一点不需要多介绍，因为距离信息始终是很重要的，由于我们认为机器人步进机采样的距离信息是相对可靠的，因此，我们对机器人获取的直角坐标信息无需做任何处理。结合两方面的信息，我们就可以完整而且准确的判断“走完一圈的过程”。(4) 非直线型障碍物前面我们提到的都是针对直线型障碍物的处理，因为我们认为大多数障碍物对于机器人来说，多可以认为是直线型的。然而，当我们面对非直线型障碍物时，会遇到什么样的问题呢?在这里，我们就来讨论一下。首先，对于墙边的障碍物，如果是非直线型的，机器人经过时，会认为它与墙壁的距

48、离在不断变化，同时，根据前面所谈到的，机器人会为了维持与墙壁的距离，会不断调整角度，因此它不会认为障碍物是非直线型的，这样就会造成很大的麻烦。为处理这种情况，我们采用角度调整窗口。所谓角度调整窗口是对于机器人在微调角度时，用于记录历史数据的。这样就可以根据历史角度微调的数据判断是否遇到非线型的障碍物了，因为，碰到非线型的障碍物，机器人会不断向一个方向转动，然而，一般做微调时，主要是由于地面摩擦或偶然出现的因素造成的(因为在此之前，机器人的移动过程已经被反馈纠正过了) ，这些因素的出现是随机的，因此，机器人不可能始终向同一方向微调。这样就可以有效的区别非线型障碍物与随机事件产生的机器人微调了。在

49、遇到非线性障碍物后，我们将转过的角度和记录下来，当然，这样就相当于没有墙壁做参考，然而，由于只要在一圈中，误差不超过45 度，就可以满足算法的精度要求了，因此，我们认为是可行的。另外，对于不在墙边的障碍物，如果是非直线型的，机器人会选择沿墙边的方向绕过(因为，不在墙边，我们可以肯定能够从墙边绕过) 。在此过程中，我们将记录下当前扫描离墙边的距离信息，然后，执行绕动过程，这一过程相当简单，当绕开障碍物后，只要保持与墙壁平行，并且恢复与墙边的距离值即可。这一过程中，障碍物的形状并没有关系，因此，我们无需对不在墙边的障碍物进行特殊处理。4.3 沿边走路径规划流程图（1）无障碍路径规划地面清洁机器人从停放位置（通常为墙角）开始工作，采用沿边走路径算法，按照内螺旋式“回”字型路径进行清扫，对所走过的路径及时进行标记并且自动确定前进方向，直至全部清扫完毕自动返回。静态无障碍环境下回字型路径规划流程如图4-3，图中m与n分别为沿X与Y方向的栅格数目。图4-3 无障碍环境“回”字型路径规划流程图（2）避障路径规划避障算法应该满足下列三个要求：实时性、应用性和可靠性，即要求算法简单可行，在保证与障碍物不发生碰撞和安全的前提下移动。避障路径规划流程：避障路径规划中