申请工学硕士学位文

本文是一篇机器人论文范文,机器人类有关毕业论文参考文献格式,关于申请工学硕士学位文相关大学毕业论文范文。适合机器人及算法及特征方面的的大学硕士和本科毕业论文以及机器人相关开题报告范文和职称论文写作参考文献资料下载。

(申请工学硕士学位论文)

未知环境下基于SLAM的移动

机器人导航算法研究

培养单位:物流工程学院

学科专业:机械制造及自动化

研究生:韩锐

指导教师:李文锋教授

2006年5月

分类号密级

UDC学校代码10497

学位论文

中文题目:未知环境下基于SLAM的移动机器人导航算法研究

英文题目:AResearchtotheSLAM-basedNigationAlgorithm

forMobileRobotsinUnknownEnvironments

研究生姓名:韩锐

指导教师:姓名李文锋职称教授学位博士

单位名称物流工程学院邮编430063

申请学位级别硕士学科专业名称机械制造及自动化

论文提交日期2006.4论文答辩日期2006.5

学位授予单位武汉理工大学学位授予日期

答辩委员会主席评阅人

2006年月摘 要

智能移动机器人是一种在复杂的环境下工作的具有自规划,自组织,自适应能力的机器人没有人干预下使机器人有目的地移动并完成特定任务,进行特定操作ntelligentrobotsareakindofrobotsthatareabletoworkinplexenvironmentswiththecapacitiesofself-anizingandself-planning.Nigationproblemisahotissueconcernedinresearchingonsuchkindofrobots.Itsaimistomovepurposelyanddothejobwithoutaids.WithsupportsoftheprojectofNationalNaturalScienceFoundationofChinaandtheprojectofExcellentYouthFundinHubeiprovince,thispaperaimstodevelopanewalgorithmfornigatingbasedontheSimultaneousLocalizationandMapping(SLAM)algorithmtomaketherobotstotallyautonomousintheunknownbutstructuredenvironments.

ThenigationtechniquesarefirstlyreviewedinthispaperandthentheSimultaneousLocalizationandMapping(SLAM)problemisintroduced,basedontheanalysisofthelocalizationproblemandthemapbuildingproblemwhicharetwokeypointsinthenigationtechniques,includingitsstructure,characteristics,categoriesandsoon.Asthereisaconflictbetweentherequirementsofputationalplexityandinformation-richnesswithinthepoint-featurebasedSLAMalgorithm,aline-featurebasedSLAMalgorithmiswellpresentedinthispaper.Alloperationsrequiredforbuildingandmaintainingthiap,suchaodel-setting,dataassociation,andstate-updatingaredescribedandformulated.Thisapproachhasbeenprogrammedandsuccesullytestedinthesimulationwork

Tomeettheneedofpathplanninginnigation,herewemainlyconcernthelocalplanning,thatis,obstacleoiding.WeintroducetheVFH/VFH+,analgorithmforobstacleoidance,indetailinthepaper.Whatiore,inourwork,webineVFH+andSLAMtogethertodevelopanewwayfornigation,whichhaoreapplicationsandbehesbetterthantheonebasedmerelyonVFH+does.

Keywords:nigation,SLAM,VFH/VFH+

第1章绪论1

1.1课题研究的目的与意义1

1.2课题研究的内容2

1.3论文组织结构2

第2章移动机器人导航技术4

2.1机器人导航概述4

2.2移动机器人导航方式4

2.3移动机器人的定位问题6

2.4移动机器人的制图问题7

2.4.1地图的类型7

2.4.2机器人制图存在的问题8

2.4.3同时定位与制图问题9

2.5本章小结10

第3章同时定位与制图(SLAM)算法11

3.1同时定位与制图算法介绍11

3.1.1SLAM算法性质11

3.1.2SLAM算法分类12

3.2基于特征SLAM算法构架简介14

3.3传感器的选择及特征提取15

3.3.1传感器选择15

3.3.2特征提取17

3.4噪音模型建立17

3.5滤波技术简介17

3.6卡尔曼滤波简介18

3.6.1线性卡尔曼滤波简介19

3.6.2扩展卡尔曼滤波(EKF)简介21

3.7本章小结22

第4章一种基于线特征SLAM算法研究24

4.1过程模型建立24

4.2观测模型的建立26

4.3算法的实施26

4.3.1机器人运动初始化26

4.3.2数据匹配27

4.3.3状态更新30

4.3.4新信息处理31

4.3.5地图管理32

4.4SLAM算法仿真33

4.4.1仿真环境的创建33

4.4.2SLAM算法示例35

4.5本章小结37

第5章机器人避障算法38

5.1常见的避障算法介绍38

5.2VFH避障算法介绍39

5.2.1(CertaintyValue)值的确定39

5.2.2VFH算法阐述41

5.2.3VFH+算法阐述43

5.3VFH+算法仿真47

5.3.1仿真环境的创建47

5.3.2仿真结果说明49

5.4本章小结51

第6章基于SLAM的导航算法52

6.1基于SLAM的导航算法介绍52

6.2基于SLAM的导航算法特点53

6.3导航新算法的仿真54

6.4本章小结55

第7章全文总结及展望56

7.1全文总结56

7.2本文主要贡献57

7.3未来研究方向57

本文是一篇机器人论文范文,机器人类有关毕业论文参考文献格式,关于申请工学硕士学位文相关大学毕业论文范文。适合机器人及算法及特征方面的的大学硕士和本科毕业论文以及机器人相关开题报告范文和职称论文写作参考文献资料下载。

2.4.2机器人制图存在的问题

无论要建立哪种类型的环境地图,机器人必须要通过传感器来了解环境.在这个了解过程中传感器固有的或一些人为的因素会导致测量误差即测量噪音.机器人制图过程中面临的一个主要挑战就来自于测量噪音.如果测量数据在统计意义上独立,通过多次测量可以削减,甚至消除噪音的影响.然而在实际制图过程中,这些数据却是相互联系的.可以设法将测量误差控制在一定范围内,但是它们不断积累时,就可能会影响到下一时刻机器人对传感数据的解释.整个制图过程中,机器人都要受到环境中这些系统的,互相联系的误差的影响.如何调整这些误差是正确制图的关键.但是不管是从理论的还是实践的角度来看,现存的算法都是十分复杂且需要进一步完善的.

第二个体现制图复杂性的方面是环境中要描述的实体的维度,即:要用多少元素对其进行描述.比如,要较为详细的对一个二维的建筑平面进行制图,一般需要上千的元素.而对于三维而言,则会高达上百万甚至更多.从统计角度看,每一个元素都是机器人要进行估计的对象.这样显然增加了制图问题的复杂程度.

第三方面难点在于制图本身是个协调,匹配的过程,也就是我们常说的数据关联问题.即:如何判断在不同时刻得到的传感器数据中,哪些表示的是环境中同一元素.只有找到这些相关数据,对其进行融合处理,才会得到对该物体的准确认识,从而获得更为精确的制图.

第四,目前的算法主要集中在对静态的,结构化的,中小环境的研究上,而如何在动态的,非结构的,大型环境中进行机器人制图,研究较浅.

最后一个问题在于,机器人制图是与其运动路径有关的.即机器人的定位与制图是密切联系的.如果机器人对自身的位置有准确的认识,就可以得到较为精确的制图,同样,如果机器人对环境(地图)了解很好,就很容易得到自身的位置信息.但是,当定位信息和环境信息都不确定的情况下,两者就应该同时考虑.这就是本研究中涉及的一个研究重点:移动机器人的同时定位与制图(SLAM)问题.

2.4.3同时定位与制图问题

同时定位与制图(SLAM)是当前在移动机器人领域中自主导航的热门研究方向[20][21][22].2002年在瑞典的KTH举行的一个以SLAM为主题的SummerSchool,移动机器人领域内最知名的专家到场为50名国际学生讲学,从而将SLAM的研究引向了.SLAM算法是本研究的最主要问题,将在第三章中对其进行详细的分析.

2.5本章小结

在本章中,首先概括介绍了机器人导航问题.对包括:电磁导航,光反射导航,环境地图模型匹配导航,路标导航,视觉导航,基于传感器数据的导航以及卫星导航等在内的多种机器人导航方式进行了介绍,对机器人定位与制图进行了说明,包括:定位方式,制图类型等,并在分析机器人制图研究存在的问题的基础上引出了本研究的重点之一:同时定位与制图(SLAM)算法.

第3章同时定位与制图(SLAM)算法

3.1同时定位与制图算法介绍

移动机器人的定位和地图创建是机器人领域的热点研究问题,也是导航中重要环节.对于已知环境中的机器人自主定位和已知机器人位置的地图创建已经有了一些实用的解决方法.然而在很多环境中机器人不能利用全局定位系统进行定位,而且事先获取机器人工作环境的地图很困难,甚至是不可能的.这时机器人需要在自身位置不确定的条件下,在完全未知环境中,创建地图同时利用该地图进行自主定位和导航.这就是移动机器人的同时定位与地图创建(SLAM)问题,也称为CML(ConcurrentMappingandLocalization).该研究领域的代表人物有Smith,Self和Cheeseman[23].由于SLAM算法具有重要的理论与应用价值,被很多学者认为是实现真正全自主移动机器人的关键.近几年来,其研究取得了很大的进展,并已应用于各种不同的环境,如:室内环境[24][25],水下[26][27]以及室外环境[28][29].

3.1.1SLAM算法性质

SLAM算法有很多重要的属性,影响着地图特征和机器人位置估计中的不确定性.包括:状态估计的收敛性,估计过程的一致性,状态协方差矩阵更新的计算复杂度[23].

收敛性:SLAM算法具有三个重要的收敛性,这三个关键的收敛结果是:A.地图协方差矩阵的任意子矩阵地行列式随着每一次观测单调下降,B.在极限情况下,随着观测数量的增加,特征估计变得完全相关.C.地图的精度与第一个特征被观测时机器人的位置精度有关.这些结果表明:随着观测数量的增加,地图估计的不确定性将降低到有限的误差范围内,地图特征的关系将是完全确定的.

一致性:为了维护SLAM算法估计的一致性,对状态协方差矩阵进行更新维护是必要的.既然对环境的观测是相对机器人的,所以机器人估计中的任何误差和地图估计中的误差使绝对相关的.在没有其它外部的关于特征和机器人位置信息情况下,为了使系统状态估计的误差在有限的范围内,保持状态估计之间的一致性是很必要的.所以就必须维护机器人状态与环境特征之间的协方差矩阵.

计算复杂度:SLAM算法应用到大规模环境时的一个重要局限性是计算环境特征之间,特征与机器人之间的相关信息时的计算负担.由于特征数量很大,协方差矩阵的更新维护导致了SLAM算法的计算复杂性.对于那些包含上万个特征的环境,计算负担使得系统协方差的更新变的难以执行.所以需要一个有效的方法来提高算法的计算效率.

3.1.2SLAM算法分类

根据所依据的理论基础的不同,SLAM可以分为以下几种:

(1)基于扩展卡尔曼滤波(EKF)的CML/SLAM

这是最常用的一种SLAM方法,适合解决非线性系统的估计问题.该方法用平面坐标表示机器人和环境特征的位置,将机器人运动与环境特征的关系描述为两个非线性模型:机器人运动模型和观测模型.通过这两个模型,运用扩展卡尔曼理论的思想来实现.主要包括预测与更新两个阶段[26][28].

(2)基于概率的CML/SLAM

尽管不如EKF那样流行,但由于用概率表达机器人定位问题的不确定性非常自然合理,基于概率的CML也吸引了很多人的目光.其中,较流行是最大相似性(MaximumLikelihoodEstimation,MLE)方法.一种非常有效的最大相似性估计算法称为Baum-Welch(或α-β)算法[30],基于这种方法的机器人制图与定位问题可看作是机器人位置与环境特征位置的最大相似性估计问题.该算法包括两步:E-Step(expectation)和M-Step(maximization).

(3)基于粒子滤波器(particlefilter)的CML/SLAM

粒子滤波器定位也称为MonteCarlo定位[31][32],其基本思想是用一组滤波器来估计机器人的可能位置(处于该位置的概率),每个滤波器对应一个位置,利用观测对每个滤波器进行加权传播,从而使最有可能的位置的概率越来越高.

(4)基于空间扩展信息滤波器的SLAM[33]

该方法由SebastianThrun等人提出,是对EKF算法的改进.它不再用协方差矩阵表示空间信息的相关性,取而代之用空间信息矩阵来表示空间信息间的内在固有的关系,并且使用网状数据结构仅维护邻近的环境特征(地图).

(5)基于集合理论估计的SLAM[34]

基于集合理论的方法不假设噪声服从某种分布,而只假设噪声是有界的.具体方法是:定义一个可行状态集合(feasiblestateset)和一个观测集合(measurementset),前者表示机器人和环境特征的状态估计,后者表示符合条件(观测误差小于边界)的状态集合.算法首先根据机器人本身的状态方程计算可行状态集合,然后根据观测值计算观测集合,最后取两个集合的交集作为某时刻的经估计校正后的机器人与环境特征的状态集合(地图).

此外根据所制地图的不同,SLAM又可以分为:基于栅格的SLAM[35],基于特征的SLAM[28][29][36]以及基于拓扑结构的SLAM[37].

在基于栅格的SLAM算法中,环境表示为一组具有特定分辨度的栅格的组合.每个栅格中有特定概率值来表示其被占据的可能性.使用基于栅格SLAM算法的时候,假设各个栅格的状态变量是相互独立的,而没有考虑栅格之间的关联性.另外,当机器人采用该种SLAM算法运行较长一段路程后,很难再回到出发点.这是因为该方法中仅在局部坐标中考虑了估计的不确定性,却没考虑局部坐标与全局坐标中的相互联系.总的说来,基于栅格的SLAM方法可以提供较为丰富的环境描述,对于局部环境下的规划与导航有很大帮助,但是通过该方法无法获得一致性较强的全局地图.

基于特征地图的SLAM算法是将环境表示为一组组参数化的特征值,比如说点,线,角等.这里的特征指的是环境中那些突显于背景的,易于传感器分辨检测的且可以通过参数描述的东西.使用这种方法的时候,必须对环境中不同类型的特征分别建立测量模型以便准确提取.基于特征的SLAM算法是最为流行的一种,尽管在环境地图描述中仅仅用到特征的位置值,但是还可以通过大小,颜色等信息进行匹配等.这种SLAM算法常常是基于卡尔曼滤波的.使用这种方法时,状态向量不仅包括机器人的位姿信息而且还有特征的位置信息.随着新特征的不断提取与确认,状态向量将不断的变大.因为用于描述环境的特征值的测量都是相对机器人的,所以对环境特征测量的不确定性是与机器人位姿估计的不确定性息息相关的.可以在理论上证明,随着时间的不断推移,测量的不断进行,地图中的特征将是完全相关的,也就是说此时随意给定一个特征的绝对坐标值,将会得到一个精准的地图.在环境特征容易识别的场合下,该算法运用很好,但是对于特性不是太明显的非结构化环境中,算法的运用遇到难题.

在基于拓扑结构的SLAM算法中使用"图&#

本文是一篇机器人论文范文,机器人类有关毕业论文参考文献格式,关于申请工学硕士学位文相关大学毕业论文范文。适合机器人及算法及特征方面的的大学硕士和本科毕业论文以及机器人相关开题报告范文和职称论文写作参考文献资料下载。

尽管SLAM算法的理论基础已经被很好的研究,但是要将其更好的运用于实际,特别是大型的非结构化环境,仍有大量理论和实际的问题需要解决包括:计算效率,地图管理,局部地图与全局地图之间的协调融合,数据匹配以及传感器管理等[38][39].

3.2基于特征SLAM算法构架简介

上文中讲到根据所得到地图类型的不同,可以将SLAM算法化分为基于栅格的SLAM,基于特征的SLAM以及基于拓扑结构的SLAM三大类.其中,基于特征的SLAM是运用最广的一类,下文将对该类SLAM算法进行详细阐述.基于特征的SLAM算法架构由图3-1表示.

由图3-1可以看出,整个算法实际上是由三部分构成即:预测——实践——更新.首先要建立机器人的动力学模型以及运动过程中的观测模型.某一时刻,在给定控制参数后,根据动力学模型可以预测机器人在时刻的位姿状态,同时结合观测模型还可以预测在时刻机器人对旧(已经核实的)特征的观测值,在实践环节中,即在时刻到时刻的过程中,机器人基本上要完成三大工作:环境特征的提取和合理性检验,以及相关数据的匹配.从而获得对特征的实际测量,同时筛选出新的特征.将对特征的估计测量和实际测量的差异值(残差),机器人位姿估计以及旧的地图一起作为输入参数,通过一定滤波算法即可更新机器人位姿,进而得到新特征的位置信息并将其融入到旧地图中生成新地图.总而言之,该方法要求机器人的位置和所有地图特征的位置存放在同一个状态向量中,并且这个向量是增广的.当观测到环境中新的特征时,就要把它作为新的地图特征添加到状态向量中.然后通过滤波就可以构建一个收敛的地图.在极限情况下,随着对环境特征的重复观测,地图特征之间的相对关系变得完全确定,并且地图的不确定性控制在一个小的范围内.这个误差范围与机器人初始位置的不确定性有关.

图3-1基于特征SLAM算法架构

3.3传感器的选择及特征提取

3.3.1传感器选择

由图3-1可以看出,移动机器人的自主导航中必须以有效而可靠的环境感知为基础,运用一种或多种传感器的组合,配以信息融合技术,从而对周围环境进行认识.机器人自主导航中常用的传感器主要可以分为两大类:

其中之一是内部传感器,它是机器人本身运动的感知,用来检测机器人组成部件内部状态,是实现闭环控制,伺服控制动作的不可缺少的装置.这类传感器有:惯导(INS),陀螺仪,里程计等.惯导提供加速度信息,速度计测量速度,陀螺仪测量角速度,里程计测量距离.这种传感器通常与机器人本身的运动模型一起对机器人的位置进行预测估计.由于这类传感器存在着随时间积累的漂移误差,所以不能直接用于长期定位.内部传感器记录了机器人的运动信息,能提供很高的采样频率而不依赖环境特征.

另一类传感器称作外部传感器.机器人外部传感器是用来检测机器人与对象物体外部状态的传感器.它使机器人能及时了解工作环境和对象,并视其情况来调整自己的对策,以提高机器人的适应性和智能化水平.如全球定位系统GPS).通过对已知位置的GPS卫星的观测来计算机器人当前的位置信息.其它常用的外部传感器有:激光雷达,毫米波雷达,声纳,视觉相机CCD等.

激光测距雷达(Laserrangefinder),运用激光二极管光脉冲获取目标的距离信息.距离的测量一般基于TOF(timeofflight)技术或者相移(phase-shift)技术.利用Doppler效应,也可以测量目标运动的速度信息.在基于TOF的测距中,发射,接收短的激光脉冲并测量它返回时的时间,通过特定计算就可以得到距离,在基于相移的测距中,发射,接收连续的光波并通过比较返回信号与参考信号的相位来计算距离[40][41].采用激光测距雷达的好处在于:速度快,测距精度高,相对于声纳传感器而言,角分辨率高,而且激光波束窄,测量距离长,但是其价格高,回波响应与目标的表面材料属性有关且有镜面反射和漫反射现象发生.

毫米波雷达(millimeterweradar,MMWR),通过发射接收电磁回波来测量至目标对象的距离.雷达天线的尺寸依赖于所使用的频率.频率越高,天线越小.运用的电磁波通常是短脉冲或调制的连续波.毫米波雷达的优点在于:可以适用于任何的天气条件,而且测量距离长,精度也比较高,其缺点是:成本高,尺寸大,在同样的天气条件下,比激光雷达衰减的更快.

声纳传感器(Sonar)具有成本低,波束覆盖范围宽的特点,但角度分辨率低,不够精确,且容易产生虚假和多重反射回波信号,增加特征匹配的难度.尽管如此,很多导航设计中都用到了声纳系统[42][43].超声波测距是基于超声波在介质中的传播速度特性实现的非接触式距离测量,其原理是通过超声换能器发射超声波,其在空中传播至被测物体,经反射后由超声换能器接收反射回波信号,确定出超声脉冲从发射到接收的渡越时间T,在已知超声波声速V的前提下,则可以计算出被测物体离超声换能器的距离L等于VT/2,完成障碍物及其位置的确定.

立体视觉系统(Stereo-visionsystem)运用单个或多个相机得到深度信息.得到的距离图像的质量依赖于相机标定,光照条件以及基线情况.目前,视觉已经在机器人导航中广泛运用[44][45].视觉可以提供更为丰富的信息,但是数据处理工作也相对庞大,而且视觉图像受光照条件影响比较大.

所以在选择传感器时要权衡各类传感器的弊益.一般来说,使用单一传感器进行定位制图的可靠性较差.利用多传感信息融合技术是定位与制图技术的发展方向.在本研究中主要涉及声纳传感器.声纳传感器的弱势将通过软硬件进行补偿.

3.3.2特征提取

特征提取是SLAM算法得以实施的前提条件.对于不同的传感器,不同的特征类型,都会有不同的特征提取算法.合理的特征提取算法可以提高SLAM算法的质量.由于本文侧重于SLAM算法中如何运用特征,这一问题的理论研究,故没有过多考虑特征本身的提取算法.对于从声纳传感器返回值中提取点,直线特征的算法,可以参考文献[46].

3.4噪音模型建立

上文提到,在机器人的自主导航研究中要利用各种传感器对机器人本身运动或者外界环境特征进行测量.这些测量通常会受到各种噪音的干扰,是固有不确定性的.常用一个噪音模型来表示这重不确定性.其中,最常用的噪音模型是白色高斯噪音(WGN).

另外在进行各种建模时,为了得到完全精确的模型需要很多参数,并且是非线性的.为了表示的方便通常只是用一个近似模型.在这个近似的过程中也会引入误差,该误差也是用高斯函数来表示的.

3.5滤波技术简介

由图3-1可以看出,滤波技术在基于特征SLAM算法中有着相当重要的地位,是算法的根基所在.所谓滤波就是从混合在一起的诸多信号中提取出所需要的信号.信号是传递和运载信息的时间和空间函数.有一类信号的变化规律是既定的,如调幅广播中的载波信号,阶跃信号,脉宽固定的矩形脉冲信号等,它们都具有确定的频谱,这类信号称之为确定性信号.对于这类信号可根据各信号频带的不同,设置具有相应频率特性的滤波器如:低通,高通,带通,带阻滤波器,使有用的信号无衰减的通过,使干扰信号受到抑制.这类滤波器可以使用物理方法实现即:模拟滤波器,也可以用计算机通过算法实现即:数字滤波器.对确定性信号的滤波处理也称常规滤波.

另一类信号没有既定的变化规律,在相同的初始条件和环境条件下,信号的每次实现都是不一样的,如陀螺漂移,海浪,惯性系统的导航输出误差等,它们没有确定的频谱,这类信号称之为随机信号.随机信号没有确定的频谱,无法用常规滤波提取或抑制信号,但随机信号具有确定的功率谱,可以根据有用信号和干扰信号的功率谱来设计滤波器.维纳滤波是解决此类问题的方法之一.但是设计维纳滤波器时需要做功率谱分解,只有当被处理的信号为平稳的,干扰信号和有用信号均为一维,且功率谱为有理分式时,维纳滤波器的传递函数才可以用伯特-香农设计法较容易的求解出.否则设计维纳滤波器时会遇到诸多困难.维纳滤波除设计思想与常规滤波不同之外,对信号做抑制和选通这一点是相似的.此外常用的还有卡尔曼滤波.它是从与被提取信号有关的"量测量"中通过算法估计出所需的信号.其中,被估计的信号是由白噪声激励引起的随机响应,激励源与响应之间的传递结构(系统方程)已知,量测量与被估计量之间的函数关系(量测方程)也已知.下面将着重介绍卡尔曼滤波.

3.6卡尔曼滤波简介

1960年,R.E.Kalman在其发表的一篇着名的论文[47]中,描述了用递归的方法来解决离散数据的线性滤波问题,这便是卡尔曼滤波的雏形.简单的讲,卡尔曼滤波可以看作是一组数学方程式,通过这些方程它提供了一种有效的解决过程中的状态估计问题.该方法不仅可以对过去或现在的状态进行估计,而且可以预测未来状态,所以它在机器人自主或辅助导航研究中占有很重要的位置[48][49].随后卡尔曼滤波不断发展,特别是在解决非线性滤波问题的扩展卡尔曼滤波提出之后,该技术得到了更为广泛的应用与发展.

3.6.1线性卡尔曼滤波简介

卡尔曼滤波提供了解决离散时间控制下的状态估计问题.假设该过程可以由以下线性方程表示:

,(3-1)

并且已知该过程中伴随着测量方程:

,(3-2)

其中,随即变量与分别代表过程与测量误差.假设两者相互独立,且均为白色高斯噪音,具有如下的概率分布:

,(3-3)

(3-4)

在实际中,过程噪音协方差矩阵与测量噪音协方差矩阵都会随着时间和测量的进行而不断变化.但是在这里我们假设它们是恒定的.

由方程(3-1)可以看到,时刻的状态通过矩阵与时刻状态联系起来,实际中该矩阵可能是变化的,但是在这里我们假设它不变.矩阵将控制量与状态量联系起来.在测量方程(3-2)中,矩阵将测量量与状态量联系起来.在实际操作中,随着测量过程的进行,也是可能发生变化的,但是这里我们依旧将其视为不&

本文是一篇机器人论文范文,机器人类有关毕业论文参考文献格式,关于申请工学硕士学位文相关大学毕业论文范文。适合机器人及算法及特征方面的的大学硕士和本科毕业论文以及机器人相关开题报告范文和职称论文写作参考文献资料下载。

我们定义为对时刻的一个先验状态估计,称为"先验",它表示根据时刻前获得的信息对时刻的状态进行的估计.相反,称为"后验",表示根据时刻得到的测量来估计时刻的状态.先验和后验的估计误差分别定义如下:

,以及

这样,就可以分别得到两者误差估计协方差分别为:

,(3-5)

,(3-6)

为了得到卡尔曼滤波算法的方程,首先要构造如下方程,从而将上述各量合理联系起来:

(3-7)

其中,称为测量残差.它表示预测测量值与实际测量之间的差异.为一个矩阵,为卡尔曼"增益",用来减小后验误差协方差,通常由以下式子得到:

(3-8)

由上式可以得到以及.也就是说,测量误差协方差越小,实际的测量就越准确,而预测的测量值也就越不准,然而,先验估计误差协方差越小,实际的测量反而越不准确,预测的测量值却相对更准确.

使用卡尔曼滤波进行的过程估计是通过反馈控制来完成的.在某时刻先对过程状态进行估计,然后通过测量反馈进行更正.因此,可以将算法中的方程分为两大类即:时间更新方程和测量更新方程.时间更新方程是用来通过当前状态值以及其误差协方差获得下一时刻状态的先验估计值,而测量更新方程则是用于反馈,通过反馈回来的测量值以及先验估计来获得更为准确的后验估计.实际上,时间更新方程可以看成是"预测者",而测量更新方程则可以看成是"矫正者".

图3-2预测——矫正算法

在实际使用滤波算法前,通常要通过测量采样分析获得测量噪音协方差.然而过程噪音协方差相对来说不容易直接测得,要通过考虑多方面的不定因素进行拟订.不管在选择上述两参数时是否有足够合理的理论依据,都要根据具体的模型与目的对其进行调整.

卡尔曼滤波的整体结构如下图所示:

图3-3线性卡尔曼滤波算法结构

3.6.2扩展卡尔曼滤波(EKF)简介

通过上述对卡尔曼滤波的简单介绍可以看出它主要处理的是线性问题,而通常情况下,我们更多遇到的是非线性问题.这样就应该了解一下专门用于处理这类问题的扩展卡尔曼滤波算法.

仿效泰勒级数展开,在当前估计值处对过程或测量方程求偏导,从而将非线性问题线性化.同卡尔曼滤波一样,假设过程状态向量,不同的是该过程是由以下非线性方程表示:

,(3-9)

同样,观测方程也是非线性的:

,(3-10)

其中,随机变量与分别代表的是过程与测量噪音.实际过程中,我们可能无法获知任意时刻这两中噪音的具体值,但是我们可以在忽略它们的情况下给出状态与测量向量的近似表达式如下:

(3-11)

以及,(3-12)

根据上述两式将状态向量和测量向量线性化

,(3-13)

,(3-14)

其中,与分别为实际的状态向量和测量向量,

与分别为根据式(3-11)和(3-12)得到的状态和测量向量的估计,

可以通过对求偏导而获得,,

可以通过对求偏导而获得,,

可以通过对求偏导而获得,,

可以通过对求偏导而获得,,

同样,可以将算法中的方程分为两大类即:时间更新方程和测量更新方程.时间更新方程是用来通过当前状态值以及其误差协方差获得下一时刻状态的先验估计值,而测量更新方程则是用于反馈,通过反馈回来的测量值以及先验估计来获得更为准确的后验估计.如图3-4示.

上文中对基于特征SLAM算法构架以及算法根基扩展卡尔曼滤波(EKF)进行了介绍,下一章中将以线特征为例对算法进行详细分析.

3.7本章小结

同时定位与制图(SLAM)算法是本研究的重点内容.本章首先对SLAM算法的定义,性质,发展进行了介绍,剖析了基于特征SLAM算法的构架,并对基于特征SLAM算法的算法根基卡尔曼滤波进行了详细说明.

图3-4扩展卡尔曼滤波算法方程与结构

第4章一种基于线特征SLAM算法研究

基于特征SLAM算法发展很快,许多学者以点特征为研究对象对基于特征SLAM算法进行了深入的研究[50],包括计算的复杂性,地图的管理等方面.一方面为了得到信息丰富的地图,我们希望提取,吸收尽可能多的点特征,另一方面为了减轻计算复杂程度,节省时间资源,我们又不希望过多的点特征参与计算.这显然是很矛盾的事.尽管有人通过使用压缩滤波,局部子图[50]等手段来解决该问题,并取得了一定的成果,但是仍然存在不少问题,比如:基于点特征的SLAM算法得到的往往是离散的点地图,很难满足"信息丰富"的要求.此外,在某些场合中,线状特征较点特征而言更容易被提取,这样就有必要研究如何利用线特征进行SLAM算法运用的问题.因此,本文提出了一种基于直线特征的SLAM算法.本算法较基于点特征的SLAM算法而言,计算量减少,而且地图的表示更为丰富.

4.1过程模型建立

为了对机器人的位置进行估计,首先要对移动机器人的运动过程进行建模.机器人的位置向量用一个三维向量表示即:.其中,机器人在二维空间的位置坐标表示,表示机器人朝向即:速度方向与X轴的夹角.如图4-1,假设控制移动机器人的参数主要有两个:速度以及车轮的转角.在本文研究中,假定机器人为钢性体,整体具有同一的恒定速度.以后轮轴的中点为研究对象,通过建模来预测该点在不同时刻的位置,并以之代替机器人的位置预测.运动模型如下[50]

其中,为采样时间,为过程噪音,,,如图4-1所示.注意到在机器人系统中存在着两个坐标系,分别是传感器坐标系()以及机器人坐标系().两者是可以相互转化的,在本研究中假定两者存在着简单的线性关系.为了研究的方便,我们将机器人"点"化.取传感器坐标系为机器人"点"化后的局部坐标系(),这样机器人在运动过程中的位置预测将由下式得出:

(4-1)

因为考虑静态环境,故对任意特征有:,即:

(4-2)

其中,为特征总数,,为特征的表示参数(详见下文).

由(4-1)(4-2)可以得到时刻的状态向量如下:

图4-1模型建立示意图

4.2观测模型的建立

通过特征提取算法[50]我们可以获得在机器人局部坐标下对直线特征的描述.其中,表示的是机器人局部坐标原点到该直线特征的垂直距离,表示的是与局部坐标下横轴之间的夹角.

为了制图的需要,本算法中将全局坐标系下直线特征表示为.其中,表示的是全局坐标原点到直线特征的垂直距离,表示的是与全局坐标下横轴之间的夹角(见图4-1).这样可以得到对直线特征的观测模型如下:

+

等于+(4-3)

其中为测量噪音.

4.3算法的实施

4.3.1机器人运动初始化

当机器人在未知环境中行进时,绝对坐标的选择是任意的.如果没有诸如GPS等外部手段的协助,我们很难确定自己所选的坐标原点究竟位于世界坐标的什么位置.最简便的方法可以将全局坐标原点置于机器人的起始位置,并将机器人初始位置协方差初始化为0,或者分配一个合适的值.通常假设在该位置上机器人已经检测到了直线特征(见图4-2),我们还需要分配该特征位置的初始协方差值,以及机器人与特征之间的交叉协方差值,这些值的初始化过程是至关重要的.要求尽可能准地确定初始特征的位置即:使其协方差值尽可能小.

由图4-2,假设初始时刻机器人已经观测,提取了某一特征,那么此时的状态方程则为:

其中,,

初始状态协方差矩阵为:.在本研究中,简单起见有:

.

图4-2机器人运动初始化

4.3.2数据匹配

数据匹配也称数据关联.它本是目标跟踪中的问题,用于在实际观测与预测观测之间寻找对应关系,从而达到目标跟踪的目的.常用的数据关联方法有:

最近邻(NN),概率数据关联(PDA),联合概率关联(JPDA)等.

在EKF中,数据关联是一个匹配当前观测与它所对应的环境特征的过程,可以用统计估计的方法进行观测和对应特征的关联.把观测和对应的环境特征进行关联的最一般的方法是最近邻法.数据匹配是SLAM算法中最重要的一环.

假设到时刻为止,有个线特征提取,确定并融入到地图中去设时刻,机器人通过传感器检测,提取了直线特征.根据基于特征SLAM算法,一般应有.数据匹配的过程实际上可以看成是确定与交集的过程.

对于中的任意一元素(),将会与中每一元素()进行匹配.为此我们需要建立比较函数模型,为了联合考虑与对比较结果的影响,结合图4-3可得比较函数:

其中:.

其协方差:

其中:()

()

位置误差协方差,观测误差协方差分别根据下列式子得出:

其中,为卡尔曼增益,为观测方程在时刻对的雅克比矩阵.为观测噪音协方差.

进一步可得马氏距离公式:.假设其满足分布,那么与匹配首先应该满足(4-4)

在自由度,置信度的情况下,式(4-4)中可取阈值3.841.

图4-3比较函数示意图

值得注意的是满足式4-4的可能情况有以下三种:

1).两特征近似重叠,

2).两特征属于同一特征的不同部分,

3).两特征是共线的不同特征.

对于前两种情况,称之为真匹配,而对于第三种情况,称之为误匹配.

图4-4"误匹配"示意图

如图4-4,假定与是同一特征的不同部分,与是两个不同的特征,若及小于一定的阈值,根据式(4-4),会被误匹配.在这种情况下,需要附加条件来加以区分.令表示线特征的起点,表示线特征的终点.在满足式(4-4)的前提下

若

则说明与是匹配的.

4.3.3状态更新

本算法采用扩展卡尔曼滤波对状态进行更新.在时刻通过式(4-1)(4-2)可以预测出时刻机器人在状态下,对已确认的特征的观测值及,(),在时刻,假定通过数据匹配确认,并可得此时机器人对集合中各特征的实际观测值以及.通过这些实际观测值与其对应的预测观测值可以获得残差,利用EKF中的状态更新方程即可对状态进行更新[51].由于在状态向量中,描述直线特征的参数是与,所以在状态更新过程中更新的也将是这两个参数.但是在实际操作中,由于传感器自身的特性,我们得到的实际上是一个个的线段,为此还需要对线段特征的端点坐标进行更新.

图4-5端点更新示意图

如图4-5所示,是状态更新之前的线段,是更新之后的线段.假设变化过程如下:先经平移得到,获得过渡端点值以及,然后绕点旋转得到以及端点值和.由于旋转角度比较小,可以分别通过和向作垂线而获得和.下面以求点为例进行说明&#

本文是一篇机器人论文范文,机器人类有关毕业论文参考文献格式,关于申请工学硕士学位文相关大学毕业论文范文。适合机器人及算法及特征方面的的大学硕士和本科毕业论文以及机器人相关开题报告范文和职称论文写作参考文献资料下载。

定义为平移距离.由图可知,,则

由可以求出直线的斜率,结合点可得更新后直线的方程式为:()

()

这样,当且时,有:

当有:

当有:

4.3.4新信息处理

在添加特征的过程中,有两种情况:

(1)在已存地图中添加其不曾含有的新特征,

如前假定,在时刻机器人检测到的特征集合为,经数据匹配环节确定的匹配特征的集合为,若集合,则中各元素将做为新特征添加在状态向量中.方法如下:

假定,且,那么将其添加到地图之后,扩展的状态向量可以表示为:

,其中,,为该特征在整体坐标系下的表示参数.由式(4-3)可以得出:

其中,,以及为在时刻,通过式(4-1)预测得出的机器人在时刻的位姿参数.

设其扩展后的状态协方差为.其中,表示的是在时刻得到的新特征的位置误差协方差,为机器人与特征的交叉协方差,表示的是此时刻该特征的位置误差与机器人位置误差之间的关系.

可以根据以下两种子情况分别得出与的值.

第一,若新特征的位置估计与机器人的位置估计不相关.也就是说,可以直接获得新特征在世界坐标的位置估计.在这种情况下(),主要由测量误差决定,误差协方差.

第二,新特征的位置估计与机器人的位置估计相关.此时要联合考虑机器人的位置估计与特征位置估计,方可得到,的值.在本论文中它们由如下方法得到:

其中,,,为测量误差协方差,为机器人位置误差协方差.

(2)对已存地图中的特征添加新的约束,

这种情况发生在时,由于没有新的特征被提取,状态向量长度不变,但是新的观测结果却给地图中已存特征的位置估计附加了新的约束.本论文研究中简单起见,忽略了新约束对位置估计的影响.

4.3.5地图管理

在实际操作过程中,为了提高制图的质量,可以做以下几点优化.假设有两线段特征以及,且先于而融入到地图中:

1)为了保证制图的连贯性,计算始端点与末端点之间的距离,若小于某一给定极小阈值,则认为两个端点是同一的.

2)将线段看成若干点的集合.当与为真匹配时,只需将任意一个融入到地图中.特别的,当两者属于同一特征的不同部分时,融入到地图中的特征应满足.

在SLAM算法中,计算时间的消耗主要来自于状态更新阶段[50].由于点特征的离散性,要表示出一个线特征至少需要属于该线特征的三个点特征参与,而采用本算法则避免了对属于同一直线的所有点进行更新计算,与基于点特征的SLAM算法相比,计算负担减小,实时性提高.

4.4SLAM算法仿真

4.4.1仿真环境的创建

为了检验本算法的鲁棒性,作者在Matlab环境下编制了用户界面来创建不同的仿真环境,界面如下:

图4-6用于算法检验的用户界面

图4-6所示为用户界面.表示为米的仿真环境.通过点击左侧"Type"下的两个按扭,用户可以随意添加特征(Landmark)以及控制信息(Waypoints).

如:点击"Landmark"按扭后,用户可以在栅格处创建环境中的线段特征,如图4-7,点击"Waypoints"按钮后,鼠标输入的点将为机器人提供控制量信息,如图4-8,表示机器人将按图中点划线提供的方向信息运行一周,回到原点.在这个过程中,若需要对已有的特征等进行移动或删除处理,则需要先点击"Operation"下的"Move"或"Delete"按扭,然后做相应的处理.当Landmark和Waypoints全部输入完毕之后,点击左下角的"Se"来保存.若想调用已存的仿真环境,点击左下角"Load"按钮即可.

图4-7在用户界面上创建环境特征

图4-8在用户界面上创建机器人运动控制信息

4.4.2SLAM算法示例

下文将通过一具体的仿真示例对基于线特征的SLAM算法结果进行说明与分析.

图4-9仿真环境

图4-11特征端点位置误差

图4-10机器人制图

图4-12机器人位姿误差协方差图4-13机器人位置误差

图4-14机器人位置误差图4-15机器人位姿误差协方差

如图4-9为仿真环境.线段代表的是机器人从环境中已经提取出来的线段特征,点划线代表的是机器人的控制向量,这里主要是为机器人提供转角信息.图4-10为机器人通过SLAM算法所制的地图,也就是所提取的特征的位置.特征位置的误差重要由线段特征的端点位置误差来体现,如图4-11所示.可以看出除第一个特征的端点位置误差较大外,其余误差均较小.机器人位置误差协方差如图4-12所示,由于它的值很小,所以在处理过程中对其进行了开方处理,可见其最大值不超过0.04,而且是收敛的.图4-13中的虚线表示的是在整个运行过程中,机器人的位置估计在X轴方向的误差,实线表示的是其位置估计在Y轴方向的误差.由图可以看出,位置估计误差在8mm以内.

为了更直观的表现出SLAM算法的优越性,我们做了如下比较实验:在机器人运行的过程中不采用SLAM算法,实验结果如图4-14,4-15所示.可见,机器人位置误差明显增大,误差协方差不仅增大而且趋于发散.毫无疑问,在这种情况下机器人所制地图可信度更差.

4.5本章小结

本研究提出一种基于线特征的SLAM算法,该算法较基于点特征的SLAM算法而言,计算量减少,而且地图的表示更为丰富.对于算法所涉及的关于机器人运动模型,观测模型的建立,传感器的选择,数据匹配,状态更新以及地图维护等方面的相关内容进行了阐述,并通过仿真实验证实了该算法的正确性与鲁棒性.

第5章机器人避障算法

避障算法的研究也是机器人学中一个热门话题,避障对于导航而言具有非常重要的意义.对于任意一个成功的机器人应用来说,都有其特有的避障算法.以往的算法比较简单,需要机器人在发现障碍物之后停下来,调整方向后再行动.而现在,算法发展很快,使得机器人在发现障碍之后无需停止即可绕行避障.

5.1常见的避障算法介绍

实时避障是反映智能移动机器人自动能力的关键问题之一,国内外学者曾做过大量的研究工作,常见的避障算法有如下几种:

(1)可视图法[52]

可视图法将机器人,目标点和多边形障碍物的各顶点进行组合连接,连接的直线视为弧,要求机器人和障碍物各顶点之间,目标点和障碍物各顶点之间以及障碍物顶点与顶点之间的连线均不能穿越障碍物,即直线是可视的.机器人延这些可视线行进直至离开该障碍.使用这种方法时,缺乏灵活性,一般需要机器人停止在障碍前搜集传感器数据,并且它受传感器精度影响较大.

(2)人工势场法[53]

人工势场法是由Khatib提出的一种虚拟力法,其基本思想是建立一种虚拟力,将机器人在未知环境中的运动视为在人工虚拟力场中的运动,即假设目标对机器人存在着吸引力,而障碍物对机器人有排斥力,那么引力和斥力的合力作为机器人运动的加速力,从而计算出机器人的位置和控制机器人的运动方向(如图4-1).势场法结构简单,便于底层的实时控制,但是也存在若干缺陷,比如:在相近障碍物间不能发现路径,在狭隘的通道中会来回摆动等.

(3)VFH(VectorFieldHistogram)J.Borenstein完全放弃了势场法,而设计了一种称为VFH的方法,它将机器人的工作环境分解为一系列具有二值信息的栅格单元,每个矩形栅格中有一个积累值,表示在此处存在障碍物的可信度,高的累计值表示存在障碍物的可信度高.这是因为传感器不断快速的采样环境,存在障碍物的栅格不断被检测的结果.栅格大小的选择直接影响着控制算法的性能.栅格选得小,环境分辨率就高,但是抗干扰性就比较弱,环境信息存储量大,使得决策速度慢,栅格选的大,抗干扰性就比较强,但环境分辨率下降,在密集障碍物环境中发现路径的能力减弱.另外,栅格大小的选取也与传感器的性能有关,若传感器的精度高而且反应速度快,栅格可以选的小些.

由VFH控制的移动机器人表现出了良好的性能.本研究中就是采用该方法作为机器人的避障策略.其算法思想在下文中具体介绍.

图5-1势场法思想简图

5.2VFH避障算法介绍

5.2.1(CertaintyValue)值的确定

在VFH算法中用二维的栅格来表征环境.将机器人的工作空间划分为若干连续的二维栅格系列.每个栅格中都包含一个概率值.这个概率值体现了在该栅格中存在障碍物的可信度,CV值越高,表示此处存在障碍物的可能性就越大.

它通过一个与所用传感器特性有关的概率方程进行更新.如图5-2,对于声纳传感器而言,它具有椎形视角,返回的是传感器到该锥形区域内最近一物体的距离值.在运行过程中,当机器人接收到传感器读数后,利用该读数值,通过使用概率函数更新锥形区域内每个栅格的概率值,从而获得对障碍的最新认识.实验表明,离该锥形轴线越近的栅格更新的越快.我们可以这样认为:被检测到的障碍物最可能的位置就是在锥形轴线附近.

由上述可知,机器人每接收到一个传感数据,就要调用一次概率函数.显然这样会使计算复杂度提高,导致反应延时而不利于数据的实时处理.这在机器人运动速度较快时表现更为明显.因此,可以将算法进行如下改动:

由于被检测到的障碍物最可能的位置就是在锥形轴线附近,所以我们每次仅仅需要更新位于锥形的轴线上且到传感器距离等于传感器读数的那个栅格即可.在机器人不断的运行,传感器连续采样的过程中,这种方法同样可以获得对障碍物的概率分布.同时注意到声纳传感器有其固有的一些缺点:比如方向性较差,抗干扰能力较低,错误读数多等.在这里我们着重考虑的是因其抗干扰能力低而产生较大噪音的问题.

图5-2声纳数据概率

为解决这个问题,可以从硬件和软件两方面进行处理.比如可以使用由24个声纳均匀分布而组成的声纳环.每次只触发四个声纳,且必须保证声纳之间均为90度.这样可以减少声纳之间声波的相互干扰.此外,在算法中也对噪音进行处理,削弱其影响.思想如下:

不在每个栅格中分配具体的概率值,而是在其中记录其被声纳"发现"的次数.每检测到一次,赋一个权值.实验中取3(初始值均为0).比如某栅格被检测到3次,那么其值则为.次数越多,表明该值的可靠性越高.同时在算法中,采用来加强合理值的影响.比如某一栅格具有合理值,值则为144,另一栅格具有噪音值,值则为9.可以看出,通过值来区分噪音似乎不是太明显,但是通过来判断的话,效果就好的多.然后可以通过设定阈值将噪音滤掉.

5.2.2VFH算法阐述

VFH算法[54]构架如图5-3所示:

图5-3VFH算法构架

任意时刻机器人对外界环境的感知范围是有限的,并取决于所用传感器的有效测量范围.定义某一时刻机器人

本文是一篇机器人论文范文,机器人类有关毕业论文参考文献格式,关于申请工学硕士学位文相关大学毕业论文范文。适合机器人及算法及特征方面的的大学硕士和本科毕业论文以及机器人相关开题报告范文和职称论文写作参考文献资料下载。

(一)栅格向量化

将活动窗口内的栅格向量化.该向量大小由下式确定:

而其方向取决于栅格与机器人中心点(VCP)

其中:,是正常数,

活动窗口内栅格的值

该栅格到机器人中心点(VCP)此刻机器人中心点(VCP)该栅格的绝对位置坐标

图5-4活动窗口说明

(二)活动窗口分区

若选择角分辨率,则分区后得到的区间总数.对于任意区间,有.其障碍密度可以由下式得出:.在本研究中.

由于值的离散性,可能导致障碍密度的过于稀散.因此要对其进行平滑处理:

(5-1)

(三)确定运动方向

通过式5-1可以得到活动窗口中每个分区的障碍密度.给定某一阈值,障碍密度低于该值的区域,称为"候选区".当有连续(实验中等于18)个候选区存在时,称它们为"宽谷",否则称之为"窄道".将这些连续候选区中最左边的一个区记为,最右边的一个区记为,则运动方向可以由下式子得出:

5.2.3VFH+算法阐述

VFH+算法是在VFH算法基础上发展起来的[55],它充分考虑了机器人的大小尺寸对算法结果的影响.如图5-5所示,在VFH+中将栅格放大,取决于机器人的尺寸.为了进一步加强机器人运行的安全性,还要将机器人与障碍可以保持不碰撞的最短距离考虑在内.所以对于任意待研究的栅格其实际上被放大了

这样,扩大角满足:.对于任意分区,其在极坐标下的障碍密度为:.

当满足条件时,否则为了使机器人得到平滑的运动轨迹,像VFH中那样使用单一阈值来决定安全区域是不够的.在VFH+中,将采用与两个阈值.具体操作如下:

若,则,

若,则,

其他情况则.

图5-5障碍扩大示意图

在VFH+算法中,为了动态分析机器人的运动,将其轨迹分解成运动方向不变时的直线与方向改变时的弧线.该弧线取决于机器人的转动半径,与机器人的速度密切相关,速度越快,其旋转半径越大.如图5-6所示,假设机器人向左旋转时的转向半径为,右转时的转向半径为.A,B为两个障碍栅格.按上述方法将A,B扩大,假定A与机器人的左转向圆有重叠交叉,那么A与左转向圆覆盖的所有区域被认为是禁止通行区(blocked),B与转向圆无交叉现象所以只有其自身覆盖的区域为禁止通行区.在图5-6所示情况下,机器人将右转.

具体算法如下:

1)确定转向圆的圆心

2)计算障碍栅格到两转向圆心的距离

3)条件判断

若,机器人右方被阻,

若,机器人左方被阻.

图5-6算法示意图

通过对上述条件的对照比较可以得到两个极限角度,分布在机器人左右两侧.分别记为及.同时定义,表示机器人当前运动方向的反向.初始时刻令.对于活动窗口中任意栅格,在其值满足的情况下若位于左侧,右侧时,令,若位于左侧,右侧时,令.这样,根据及可以得到另一形式的柱状图(maskedpolarhistogram).该柱状图表明了机器人在当前速度下的可行方向.若且,表示该区域可行,其他情况下,表示该区域内不可行.

通常情况下,我们可以得到若干符合的组合.对于每个组合,记其左右边界分别为:和.若和间包含了以上个区间(为常量,本实验中取10),则称该区域为"宽域",否则称之为"窄域".窄域只提供一个候选方向且,转化为角度后为.而宽域可以提供三个候选方向:,以及.

,转化成角度为,

,转化成角度为,

此外,当目标方向满足时有,转化成角度为.

为选出最合适的运动方向,建立以下代价函数:

,其中:

,是用来计算两个区间和绝对角度差的函数.比如表示的是候选方向与目标方向间的差角,其值越大,机器人运动时偏离目标就越远,到达目的地的代价也就越高.表示的是候选方向与机器人行进方向间的角度差,该值越大,机器人转向变化越大.表示的是当前候选方向与前次所选方向间的角度变化,值越大,车轮转向变化越大,运动震荡越大.

所以权衡系数,及的选择至关重要,它们直接决定了算法的优越性.一般情况下应满足:.在本研究中,

注意到在上述讨论中主要是针对点障碍的.但是在有些场合下线特征更容易被提取,此时就需要考虑线状障碍.这样,在用VFH+算法时就应该做一些改动.

假定VFH+算法的主体思想不变,只是在对障碍物进行放大处理的时候做如下简单变动:

图5-7线障碍的扩大处理方式

如图5-7所示,将线障碍的端点看作时两个点障碍并按照原始的VFH+算法进行放大,然后整体考虑障碍将其放大.其中为该线障碍的长度.

5.3VFH+算法仿真

5.3.1仿真环境的创建

本研究过程中,分别对点障碍环境下以及线障碍环境下的VFH+算法进行了仿真实验.在Matlab环境下编制了用户界面来创建不同的仿真环境.

图5-8所示为创建点障碍环境的用户界面.表示为米的仿真环境.通过点击左侧"Type"下的按钮,用户可以随意设置起始点(startpoint),目标点(endpoint)以及环境中的点障碍(pointobstacle)如图5-9.在这个过程中,若需要对已有的特征等进行移动或删除处理,则需要先点击"Operation"下的"Move"或"Delete"按钮,然后做相应的处理.当起始点,目标点以及点障碍全部输入完毕之后,点击左下角的"Se"来保存.若想调用已存的仿真环境,点击左下角"Load"按钮即可.

图5-8点障碍环境创建界面

图5-9点障碍环境示例

图5-10所示为创建线状障碍环境的用户界面,同样表示为米的仿真环境.通过点击左侧"Type"下的按钮,用户可以随意设置起始点(startpoint),目标点(endpoint)以及环境中的线状障碍(landmarks)如图5-11所示.在这个过程中,若需要对已有的特征等进行移动或删除处理,则需要先点击"Operation"下的"Move"或"Delete"按钮,然后做相应的处理.当起始点,目标点以及线障碍全部输入完毕之后,点击左下角的"Se"来保存.若想调用已存的仿真环境,点击左下角"Load"按钮即可.

图5-10点障碍环境创建界面

图5-11线状障碍环境示例

5.3.2仿真结果说明

在如图5-9,图5-11所示仿真环境中运用VFH+算法,结果如图5-12,5-13所示.机器人从出发点到目的地的过程中,检测到障碍,然后运用VFH+算法避障后前行.

图5-12点障碍环境下仿真结果

图5-13线障碍环境下仿真结果

实验中发现:随着机器人的移动,传感器不断的采样,环境信息会越来越大,这不仅会溢出存储器容量,而且对环境信息的处理时间会越来越长,这将不能满足实时性的要求.因此必须对环境信息进行优化.比如说,随着机器人的不断移动,在移动机器人后面一定距离的信息利用率是很低的,删除这些信息不会对决策产生大的影响.

此外,如图5-12仿真结果所示可以看出,VFH/VFH+算法均是局部优化的算法,没有过多的考虑路径规划问题.如果要得出更优化的路径来,必须采用其他方法来补偿,比如采用动态规划理论等.

5.4本章小结

本章中在对常用的几种避障算法做了简单介绍的基础上对本研究所采用的VFH/VFH+算法进行了详细的分析,包括环境栅格向量化,活动窗口分区以及新方向确定等环节,最后通过仿真实验对算法进行了校验.

第6章基于SLAM的导航算法

Leonard和Durrant-Whyt曾经指出,机器人导航可以归结为以下三个问题:"我在何处","我要去何处"以及"我如何到该处"[56].其中,第一个问题是后两个问题的基础.机器人只有知道了某一时刻自身的位置,才有可能解决下一时刻去哪及如何去的问题.也就是说,机器人导航问题是将机器人定位,制图以及避障等集于一体的综合性问题.为了满足机器人在未知环境中导航的需求,本章中提出了一种新的导航算法.

6.1基于SLAM的导航算法介绍

从上文介绍中可以看出,SLAM算法可以为在未知环境中工作的机器人提供位置信息即:可以给机器人定位.但该算法要求在每个控制时刻应该提供确定的控制量信息,在本研究中主要是指机器人的转角信息.该信息至关重要,它决定了机器人是否可以避障以及是否可以到达目的地,避障算法VFH/VFH+可以为机器人提供准确的控制信息,但是要求在每个控制时刻必须有机器人的位置信息.这样在未知环境中,特别是诸如GPS等外部手段无法提供机器人位置信息的场合,该避障算法将无法实施.容易发现SLAM算法与VFH算法是可以相互辅助的,将两者结合可以得到一种新的导航算法.利用该新算法,机器人可以在未知环境中通过传感器了解环境,建立环境地图,根据该自制地图进行自我定位,并将自身位置信息提供给VFH+算法以实现避障.

图6-1所示为基于SLAM的导航算法构架.在初始时刻给定初始的控制量后,机器人开始行进.在了解环境的过程中,机器人通过传感器获取环境信息,提取环境中的特征,运用SLAM算法获取自身位置信息.该信息一方面用来进行避障算法VFH+的计算,另一方面用于和目标位置进行比较.通过比较,若机器人已经到达目的地,则停止或者返回,若没有到达,则根据VFH+算法所提供的控制量信息继续前进,以此循环直至到达目标点为止.

图6-1基于SLAM的导航算法构架图

6.2基于SLAM的导航算法特点

SLAM算法与VFH算法的结合具有一定的优势,下文将从以下几个方面进行分析.

1)在未知环境中,机器人要运行SLAM算法首先必须从环境中提取特征.而这些特征是指凸显于环境中的那些物体,显然障碍物也包含在内.换句话讲,机器人从传感器数据中提取出的特征既可以用于SLAM算法,同时也可以用于VFH+算法.这样从某种程度上讲可以节省时间资源.

2)以往在运用VFH算法进行机器人避障时,必须首先通过GPS等外部手段获得其自身的位置信息,这样就使得算法的应用场合受到限制.而当SLAM算法与VFH算法结合之后,机器人自身的位置信息由SLAM算法提供,这使得VFH算法可以运用于任何场合之下.

3)在仅仅运用VFH算法进行导航时,机器人的位置误差会不断积累,当误差增大到一定程度时将会影响机器人作业.但是将SLAM算法引入到VFH算法中后,会通过滤波来不断更新机器人的位置估计,从而将误差控制在一定范围之内.

6.3导航新算法的仿真

同样在Matlab环境下,作者编程实现了对该导航新算法&#

本文是一篇机器人论文范文,机器人类有关毕业论文参考文献格式,关于申请工学硕士学位文相关大学毕业论文范文。适合机器人及算法及特征方面的的大学硕士和本科毕业论文以及机器人相关开题报告范文和职称论文写作参考文献资料下载。

图6-2导航新算法仿真环境

图6-3机器人位置误差I图6-4机器人位置误差II

6.4本章小结

根据同时定位与制图(SLAM)算法与避障算法(VFH/VFH+)的特点,本章中将两者结合产生了一种新的导航算法.文章首先对新导航算法的构架进了详细的阐述,并在此基础上分析了其优势所在,并通过编程在仿真环境下验证了该导航算法的可靠性.

第7章全文总结及展望

7.1全文总结

本论文结合国家自然科学基金(60475031)和湖北省青年杰出人才基金项目(2005ABB021)的需求,主要研究移动机器人自主导航算法.文章对机器人导航领域的重要问题比如:定位与制图,避障等进行了较系统,深入的研究.

第一章为全文的概述,在介绍本文研究的目的与意义的基础上,指出本课题主要研究的是当机器人在未知环境中,靠自身传感器感知环境的情况下,自主的建立环境地图并根据该地图实现定位,避障与导航的算法,同时介绍了本研究要处理的关键问题,在最后对论文的组织结构进行概括说明.

第二章中主要对移动机器人导航技术进行了概述,包括移动机器人的导航方式:电磁导航,光反射导航,环境地图模型匹配导航,路标导航,视觉导航,基于传感器数据的导航以及卫星导航等,同时介绍了机器人导航中的两个主要问题:机器人定位与制图,具体包括定位方式(相对定位,绝对定位),地图类型以及机器人制图研究中存在的难点等,并追踪概述了相关技术的国内外发展现状与发展趋势.

第三章对移动机器人同时定位与制图(SLAM)算法进行了详细的剖析,包括算法的发展现状,属性等,并详细说明了基于特征SLAM算法构架以及其算法根基卡尔曼滤波.

第四章中详细介绍了本研究中提出一种基于线特征的SLAM算法,该算法较基于点特征的SLAM算法而言,计算量减少,而且地图的表示更为丰富.并通过仿真实验证实了算法的正确性与可靠性.

第五章简单介绍了常用的几种避障算法,并对本研究所采用的VFH/VFH+算法进行了详细的分析,包括环境栅格向量化,活动窗口分区以及新方向确定等环节,最后通过仿真实验对算法进行了校验.

第六章中,根据同时定位与制图(SLAM)算法与避障算法(VFH/VFH+)的特点,将两者结合产生了一种新的导航算法.本章首先对新导航算法的构架进了详细的阐述,并在此基础上分析了其优势所在,并通过编程在仿真环境下验证了该导航算法的可靠性.

7.2本文主要贡献

通过对同时定位与制图(SLAM)算法以及避障算法(VFH/VFH+)的深入研究,本文的主要贡献与创新点有:

1)提出了一种基于线特征的SLAM算法,并给出了相关的比较函数公式,数据匹配方式等,并在仿真环境下证实了算法的鲁棒性.与基于点特征的SLAM算法相比,该方法可以提供信息更为丰富的地图而且计算量相对减少.

2)详细剖析了避障算法VFH和VFH+,并通过Matlab软件对算法进行了仿真实验.

3)将SLAM算法与VFH+算法结合,扩展了VFH+算法的使用场合.

7.3未来研究方向

移动机器人技术是一个不断发展和创新的技术,机器人的研究内容涉及到多个学科的内容.结合当今机器人研究的发展潮流和国内外的研究内容,作者认为以下几个方面还需要进一步研究:

1)本文中对同时定位与制图的研究都是假设环境中的特征是静态的,对于大规模,动态环境下的SLAM问题,特别是3D的SLAM问题,有待深入的研究.

2)本研究中只考虑了一种传感器,而在实际运用的过程中通常会联合采用若干传感器,这就需要研究多传感器的信息融合问题.

本文是一篇机器人论文范文,机器人类有关毕业论文参考文献格式,关于申请工学硕士学位文相关大学毕业论文范文。适合机器人及算法及特征方面的的大学硕士和本科毕业论文以及机器人相关开题报告范文和职称论文写作参考文献资料下载。

[28].J.Guivant,E.Nebot,H.Durrant-Whyte,Simultaneouslocalizationandmapbuildingusingnaturalfeaturesinoutdoorenvironments.InProc.IAS-6Intell.Auton.Syst.,Italy,July2000,pp.581-586.

[29].J.Guivant,E.Nebot,andS.Baiker,Localizationandmapbuildingusinglaserrangesensorsinoutdoorapplications,J.Robot.Syst.,vol.17,pp.565-583,Oct.2000

[30].ThrunS,BurgardW,FoxD.Aprobabilisticapproachtoconcurrentmappingandlocalizationformobilerobots[J].MachineLearning,1998,31(1-3):29-53.

[31].DellaertF,FoxD,BurgardW,MonteCarlolocalizationformobilerobots[A].ProceedingsoftheIEEEInternationalConferenceonRoboticsandAutomation[C].Detroit:1999.1322-1328.

[32].YuenD,MacDonaldBA.AparisonbetweenextendedKalmanfilteringandsequentialMonteCarlotechniqueorsimultaneouslocalisationandmapbuilding[A].ProceedingsofAustralianConferenceonRoboticsandAutomation[C].Auckland:2002.335-340.

[33].Thrun.S,Koller.D.SimultaneousMappingandLocalizationWithSparseExtendedInformationFilters:TheoryandInitialResults[R].USA:CarnegieMellonUniversity,2002.

[34].DiMarcoM,GarulliS,LacroixS.Asettheoreticapproachtothesimultaneouslocalizationandmapbuildingproblem[A].Proceedingsofthe39thIEEEConferenceonDecisionandControl[C].Sidney:2000.833-838.

[35].Elfes.A.,Sonar-basedreal-worldmappingandnigation.IEEEJournalofRoboticsandAutomation,RA-3(3):249-265,1987

[36].S.Thrun,D.Koller,Z.Ghahramani,H.Durrant-Whyte,andAYNg,Simultaneouappingandlocalizationwithsparseextendedinformationfilter,Proc.ofWAFR,2002

[37].H.Choset,K.Nagatani.TopologicalSimultaneousLocalizationandMapping(SLAM):TowardExactLocalizationWithoutExplicitLocalization.IEEETransactionsonRoboticsandAutomation,17(2),125-137,April2001

[38].王璐,蔡自兴,未知环境中移动机器人并发建图与定位(CML)的研究进展,机器人,200426(4):380-384

[39].罗荣华,洪炳镕.移动机器人同时定位与地图创建研究进展,机器人,200426(2):182-186

[40].Hoppen,P.,Knieriemen,T.,vonPuttkamer,E.,Laser-radarbasedmappingandnigationforanautonomouobilerobot.Proc.oftheIEEEInternationalConferenceonRoboticsandAutomation,2:948-953.1990

[41].Buchberger,M.,J.,K.W.,vonPuttkamer,E.,Laserradarandsonarbasedworldmodelingandmotioncontrolforfastobstacleoidanceofanautonomousrobot.Proc.oftheIEEEInternationalConferenceonRoboticsandAutomation,1:534-540,1993.

[42].Kleeman,L.,Kuc,R.,Anoptimalsonararrayfortargetlocalizationandclassification.InIEEEConferenceonRoboticsandAutomation,volume4,pp.3130-3135,1994

[43].Heale,A.,Kleeman,L.,Arealtimedspsonarechoprocessor.InProc.IEEE/RSJInternationalConferenceonIntelligentRobotsandSystems,Takamatsu,Japan,2000

[44].Taylor,C.,Kriegman,D.,Vision-basedmotionplanningandexplorationalgorithmormobilerobots.ProceedingsoftheWorkshopontheAlgorithmicFoundationsofRobotics.1995

[45].Murray,D.,Jennings,C.,Stereovisionbasedmappingandnigationformobilerobots.Proc.oftheIEEEInternationalConferenceonRoboticsandAutomation,1997

[46].D.Sack,W.Burgard,Aparisonofmethodorlineextractionfromrangedata,_inProc.oftheIFACSymposiumonIntelligentAutonomousVehicles(I2004),vol.1,2004.

[47].Kalman,R.E.ANewApproachtoLinearFilteringandPredictionProblems.TransactionoftheAE-JournalofBasicEngineering,1960pp.35-45.

[48].R.KalmanandR.Bucy,Newresultsinlinearfilteringandpredictiontheory,Trans.AEJournalofBasicEngineering83,95-108,1961.

[49].S.I.Roumeliotis,G.A.Bekey,Bayesianestimationandkalmanfiltering:AunifiedframeworkforMobileRobotLocalization,inProceedingofIEEEInternationalConferenceonRoboticsandAutomation,SanFranciso,California,April22-28,pp.2985-2992,2000

[50].J.Guivant,E.Nebot.OptimizationoftheSimultaneousLocalizationandMap-BuildingAlgorithmforReal-TimeImplementationIEEEJournalofRoboticandAutomation,vol.17,NO.3,June2001,pp.242-257

[51].P.Cheeseman,R.Smith,M.Self,EstimatingUncertainspatialrelationshipsinrobotics,inUncertaintyinArtificialIntelligence,NewYork:ElsevierScience,1988,vol.2,pp.435-461

[52].吴峰光,溪宏生,一种新的基于切线的路径规划方法,机器人,2004,26(3):193-197

[53].Park,M.G.,Lee,M.C.,ExperimentalevaluationofrobotpathplanningbyartificialpotentialfieldapproachwithsimulatedannealingSICE2002.Proceedingsofthe41stSICEAnnualConference,Volume:4,5-7Aug.2002,pp:2190-2195

[54].J.Borenstein,Y.Koren.TheVectorFieldHistogram-FastObstacleAvoidanceforMobileRobots.IEEETransactiononRoboticsandAutomation,7(3):278-288,1991

[55].I.UlrichandJ.Borenstein.VFH+:ReliableObstacleAvoidanceforFastMobileRobots.IEEEInt,Cof.onRoboticsandAutomation,pp:1572-1577,1998

[56].H.F.Durrant-Whyte..WhereamIAtutorialonmobilevehiclelocalization.IndustrialRobots,21(2):11-16,1994

[57].孙明明,超声导航移动机器人关键技术研究,浙江大学硕士学位论文2005.1

致谢

首先衷心感谢我的导师李文锋教授.本文的研究是在李老师的悉心指导下完成的.李老师的渊博知识,敏捷思维以及对学科前沿与研究方向的敏锐洞察力给我留下了十分深刻的印象.感谢导师给予我悉心的指导和帮助,正是由于导师的严格要求,精心教诲与指导,让我锻炼了独立从事科研工作的能力,学到探求知识的方法,导师严谨的治学态度,求实的工作作风,孜孜不倦的探索创新精神将永远是我学习的楷模！

此外,还要感谢一直支持我的家人！感谢一切帮助我的朋友们！

谢谢大家！

韩锐

2006年4月

作者攻读硕士期间参与项目及发表的论文

作者在攻读硕士期间参与的项目有:

1.国家自然科学基金(60475031):"传感器网络环境中移动机器人动态特征与可重构控制框架".

2.湖北省青年杰出人才基金项目(2005ABB021):"自治体系统的分布式智能传感,控制与协作".

作者在攻读硕士期间发表的论文有

1.韩锐,李文锋,一种基于线特征的SLAM算法研究,自动化学报2006.1,pp.43-46.

2.韩锐,李文锋,基于特征SLAM算法构架剖析,中国人工智能学会第11届全国学术年会论文集

武汉理工大学硕士学位论文

-64---

测量更新方程

卡尔曼增益

后验估计

后验估计误差协方差

时间更新方程

先验估计

先验估计误差协方差

测量更新

(矫正者)

时间更新

(预测者)