仪的移动机器人同时定位和地图创建_图文

山东大学 硕士学位论文 基于激光测距仪的移动机器人同时定位和地图创建 姓名:汤晓 申请学位级别:硕士 专业:控制理论与控制工程 指导教师:李贻斌 20070515

山东大学硕士学位论文





随着智能移动机器人技术的不断发展,对移动机器人能够自主完成任务 的要求越来越高。环境地图是移动机器人自主完成任务的首要条件,未知环 境中移动机器人同时定位和地图创建对于智能机器人技术的发展有着重要 的意义。本文主要是利用传感器获取数据信息实现未知环境中移动机器人同 时定位和地图创建。 本文首先指出了课题的背景、研究意义和主要的研究内容,然后讨论了 目前国际国内研究现状和方法,重点介绍了系统的硬件平台以及外部传感器 的选择方法以及地图的描述方法。 本文采用了局部地图创建一移动机器人定位一全局地图创建的步骤。通过 激光测距仪获取环境数据信息实现局部地图的创建,通过移动机器人内部传 感器获得机器人的位姿,运用扩展卡尔曼滤波算法比较两次激光测距仪的数 据以获得精确的机器人位姿,然后更新局部地图,最后融合当前全局地图和 局部地图的数据,完成全局地图的更新,最终实现全局地图的创建。 在局部地图的创建过程中,本文提出了一个“聚合一分割一聚合”的方法 来提取线段用以表示环境信息,分为区域分割、线段提取和线段拟合三个步 骤。在区域分割和线段提取中提出了动态阈值的方法,使得分割更为精确并 可以滤除一些噪声数据,可以在较短的时间内获得一个精确的局部地图。最 后采用最小二乘线段拟合方法获得线段的参数。 由于实际环境属于非线性系统,在理论上难以找到严格的递推滤波公 式,直接应用卡尔曼滤波算法比较困难。因此本文采用扩展卡尔曼滤波算法 实现移动机器人的定位。利用机器人内部传感器获得的位姿作为预测位姿的 观测值,以局部地图中的线段作为当前全局地图中相关线段的观测量,为利 用扩展卡尔曼滤波算法提供了参数。本文提出了一个“线段范围”的方法减 少了寻找局部地图和当前全局地图之间的相关线段所耗费的时间。 经过机器人定位后得到了精确的局部地图,通过比较局部地图和当前全 局地图的线段关系,可以将局部地图中的线段分为与全局地图相关的线段和 与全局地图无关的线段。分别采取不同的处理方式,将局部地图的数据融合

山东大学硕士学位论文
到当前全局地图中,实现全局地图的创建和更新。

关键词:移动机器人;激光测距仪;同时定位和地图创建

II

山东大学硕士学位论文

ABSTRACT

With

the continuous development of intelligent mobile robotics,the mobile
can

robots which

independently accomplish task will be got more and more
can

expectation.The mobile robots

independently accomplish task,one of the

most

important

conditions

is

the

environment

map.The

simultaneous

localization and mapping of mobile robots under unknown environment will have

important significance
thesis

to the

development of intelligent mobile robotics.The
to

mainly used laser

scanner

get data information,then achieved the

purpose that the simultaneous localization and mapping of mobile robot under unknown environment. The thesis expounded
on

the background,research significance and

major

research content,and then discussed the status and research
current international and domestic,and

methods of the

mainly introduced the system hardware
sensor

platform and the method of choosing environment map.

and the describing method of

A process of local map building··robot localization·global map building is introduced in the thesis.In order to get the local map,used laser acquire environment data and used the inner
sensor scanner

to

of mobile robot to get the
scanner

location of robot.Compared the twice data from laser

and used extend

kalman filter algorithm

to get more precise location of the robot.Then updated

the local map,finally fused the data of the local map and the current global map, updated the global map and achieved the purpose of creating the global map.

An improved“merge·divided—merge’’means was adopted in the local map
building,using line means
can

segments

to

denote

the environment information.The

be divided into three processes:area divided,line segment distill and

line segment fitting.In order to get more accurate local maps,a method named dynamic threshold was introduced in the thesis and used in the process of
area

Ⅱl

山东大学硕士学位论文
divided and line segment distill.The method
an can

filter some noise data and get

accurate local map in



less time。The thesis used the least squares method to

get the parameter of line segments. Because the actual environment belonged to the nonlinear system,used the kalman filter algorithm is

difficult

for finding the strict filter formula.The thesis used

extend kalman filter algorithm to realize the localization of mobile robot.The location that obtained by using the robot internal
sensor

regarded

as

the

observation value of the forecast location,the line segments in the local map regarded global
as

the observation value of the relative line segments in the current of using extend kalman filter algorithm
are

map.So the parameters

provided.A method called“line segments range’’was introduced to reduce the

time that find the relative line segments in the local map and the
map· After the robot location,the accurate

current global

local map was obtained.Through
current global

compared the relation of line segments in the local map and the
map,the line segments in the local map
can

be divided into tWO classes.One is

the line segments had relmion with the line segments in the current global map and the other is independent.The local map data
can

be fused into the current

global map adopted different processing way,and then realized the global map building and updating.

Key Words:Mobile robot;Laser scanner:Simultaneous localization and mapping

原创性声明
本人郑重声明:所呈交的学位论文,是本人在导师的指导下,独 立进行研究所取得的成果。除文中已经注明引用的内容外,本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体,均已在文中以明确方式标明。本声明

的法律责任由本人承担。

论文作者签名;

亟亟

日期:塑12:』丛

关于学位论文使用授权的声明
本人完全了解山东大学有关保留、使用学位论文的规定,同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版,允许论 文被查阅和借阅;本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索,可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 (保密论文在解密后应遵守此规定)

论文作者签名:涵旦;&导师签

山东大学硕士学位论文

第一章绪论

1.1引言
机器人的诞生和机器人学的建立和发展是20世纪自动控制最具说服力 的成就之一,是20世纪人类科学技术进步的重大成果。机器人从20世纪 60年代诞生以来,随着电子技术、计算机技术、信号处理和人工智能技术 的发展,在短短的几十年内取得了巨大的进步。从第一台机械手到现在的大 规模自动化生产线,机器人技术在工业领域的广泛应用大大提升了生产效率 并获得了巨大的成功。随着机器人技术的发展,越来越多的具有智能化特点 的机器人,深入到我们的生产生活中。

1.2智能移动机器人
作为机器人中重要分支之一的移动机器人更是给人们带来了无限的惊 喜。移动机器人的研究始于20世纪60年代末,斯坦福研究所(SRI)的Nils
Nvissen和Charles Rosen等人,在1966年至1972年中研制出了取名Shakey的

自主移动机器人,其目的是研究、应用人工智能技术以及在复杂环境下机器 人系统的自主推理、规划和控制。20世纪70年代末,随着计算机的应用和传 感器技术的发展,移动机器人研究又出现了新的高潮。20世纪90年代以来, 以研制高水平的环境信息传感器技术、信息处理技术、高适应性的移动机器 人控制技术和真实环境下的规划技术为标志【¨,开展了移动机器人更高层次
的研究。

相对于传统工业机器人,智能移动机器人具有感知、灵活的特点。为了 让移动机器人更好地适应环境,根据工作需要人们给它装上了许多不同功能 的传感器,使移动机器人具有感知外界的能力。目前,移动机器人正朝着具 有自组织、自学习、自适应的智能化方向发展,具有感知(Sensing)、思维 (Thinking)、灵巧动作(Acting)三个相互作用的基本特点。自主能力的高低是 移动机器人智能化水平的重要体现。随着移动机器人应用领域的日益增加, 对移动机器人自主能力研究不断提出新的课题,使移动机器人的研究不断深

山东大学硕士学位论文
入和发展。 近年来,随着机器人技术越来越多的渗入到我们的生产生活中,具有自

主感知决策和执行功能的智能移动机器人得到了快速的发展,移动机器人最
大的特点就是能够自由移动,这种运动能力使机器人更加适应环境,胜任更 多的工作,移动机器人可以应用在核电厂、排雷、战场搜寻、深海探测等等 条件比较艰苦危险的领域。智能移动机器人技术的发展对于一个国家科学技 术的发展具有非常重大的意义,因此智能移动机器人的相关技术成为机器人 技术研究的热点问题。 地图创建是移动机器人领域中的一个基本而且重要的问题,环境地图被 广泛地应用在移动机器人的导航系统中,在移动机器人导航定位和全局路径

规划中起到重要的作用。要实现移动机器人的自主导航,最重要的是通过定
位来获知机器人在环境中的准确位姿。根据先验地图进行的移动机器人定位 和自主导航技术得到了广泛的研究,并取得很好的应用效果。但是实际环境 往往是未知的,不能提供诸如环境大小、形状、障碍物位置等先验信息,而 且实际环境中也往往不存在路标、灯塔等人为设定的标志物,这给移动机器 人的自主导航带来了很大的问题。因此,移动机器人在未知环境中同时定位 和地图创建(SLAM
simultaneous localization and

mapping)f21【31【41成为移动

机器人研究领域的一个热点问题。

1。3地图创建涉及的问题
地图创建不是一个独立的过程,涉及到移动机器人多个方面的研究,例 如地图的描述方法,传感器的选择等等。 1.3.1地图的描述方法 地图,就是机器人对外部环境的描述方式。地图的描述方法就是机器人 内部如何表达外部环境模型,应该满足以下四个基本条件:
·

计算机便于处理模型信息。 模型表示简单,信息存储量小,但要完整的表示环境信息。 容易加入/删除信息以更新地图。 地图信息易于使用,移动机器人可以借助该地图完成特定的任务如定

·

·

·



山东大学硕士学位论文
位、路径规划等。 通常移动机器人所处的环境都是三维的,但对于移动机器人的工作环 境,一般可以简化为二维模型。本文所讨论和创建的地图都是基于二维模型
的。

1.3.2传感器 传感器是移动机器人获取外界环境信息的重要手段,也是创建地图的信 息来源。移动机器人搭载的传感器种类繁多,可以分为内部传感器和外部传 感器两类。常用的内部传感器有光电码盘、电子罗盘、机械陀螺仪等等,常 用的外部传感器有声纳、红外传感器、激光测距仪、视觉传感器等等。 现在移动机器人基本配备硬件之一的里程计是基于光电码盘和航行推
算法(dead reckoning)实现的。通过里程计总是能够得到移动机器人的位姿信

息,但是其存在的测量误差是累积而且是发散的,必须参考外部传感器来进 行位姿校正。外部传感器能够提供独立于移动机器人的环境信息,存在系统 误差但不会有累积误差,因此可以用来修正机器人的位姿误差。由外部传感 器直接提供的外部环境信息是创建地图的主要信息来源。 由于传感器自身的限制,感知的环境信息存在不同程度的不确定性,直 接使用传感器的感知信息进行地图创建很难得到准确的环境模型。通过融合 多个传感器获取的信息可以得到较为准确的环境模型。

1.4论文的研究内容和组织结构
本文系统地研究了未知环境中移动机器人地图创建所涉及的各方面问 题,给出了自己的解决方法。本文采用了局部地图创建一机器人定位一全局 地图创建的步骤来完成整个地图的创建。通过外部传感器获得当前位姿的环 境信息,经过数据处理创建局部地图。由内部传感器获得机器人的当前位姿, 通过局部地图和当前全局地图信息的匹配实现机器人的定位,同时更新局部 地图。最后实现全局地图的更新和创建。如图1-1所示。



山东大学硕士学位论文

图i一1地图创建流程图 第一章主要阐述了课题的背景和意义,未知环境中地图创建的重要性以 及涉及的问题,并说明了本文的主要研究内容和章节安排。

第二章首先介绍了地图的描述方法以及常用的外部传感器,然后介绍了
由ActivMedia 平台。 第三章到第五章是本文的核心部分,主要讲述未知环境下地图的创建方
Pioneer

3移动机器人和SICK LMS200激光测距仪组成的硬件

法,采用了局部地图创建一机器人定位~全局地图创建的步骤。第三章讲述
局部地图的创建方法,采用“聚合一分割一聚合”方法并运用动态阈值获取 精确的局部地图。采用五个参数表示局部地图中的线段,为实现移动机器人 定位和全局地图的创建奠定了基础。 第四章讲述移动机器人自定位,采用扩展卡尔曼滤波算法,通过匹配局

部地图和当前全局地图的线段关系实现了移动机器人的自定位,更新了局部
地图,进而实现了全局地图的更新。

第五章讲述全局地图的创建,经过移动机器人自定位后得到的局部地图
是比较精确的,通过融合局部地图和当前全局地图的数据,可以实现全局地 图的更新,最终完成全局地图的创建。



山东大学硕士学位论文

第二章地图描述方法及硬件平台

2.1地图描述方法
地图是移动机器人内部对外部环境的认知,是机器人运动的基础。目前 移动机器人常用的地图描述方法有三种,栅格地[](grid—based map)、拓扑地 图(topological map)和几何特征地图(geometric 2.1.1栅格地图 栅格地图是在机器人系统中得到广泛应用的一种地图描述方法。首先由
Elfes和Moraves提出I 51,在机器人的路径规划、导航、避障控制、位姿估计
feature

map)。

中均得到了广泛应用,并己成为一种通用的移动机器人地图描述方法。栅格 地图是一种表示静态环境的方法,用每一个栅格被占据的概率值来表示环境 信息,机器人所了解的每个栅格的信息直接与实际环境中某区域相对应。栅 格地图很容易创建和维护,即使使用精确度不高的声纳传感器也可以创建栅 格地图来表示环境信息,但是栅格地图最大的缺点就是精确度不高,而且随 着环境的增大存储的信息量也显著增大。在环境规模比较大或者对环境划分 比较详细的情况下,对于栅格地图的维护行为所占用的内存和CPU时间迅速 增长,使得计算机的实时处理变得很困难。 2.1.2拓扑地图 拓扑地图是一种紧凑的地图描述方法,最早由Kuipers和Byun提出[61并得 到了成功应用I 71,Cassandra和Ulrichl81等人都用拓扑地图进行了移动机器人 定位的研究。拓扑地图将实际环境表示为一张拓扑意义中的图,图中的节点 对应于环境中的一个地点或者特征状态。如果节点间存在直接连接的路径则 相当于图中连接节点的弧。拓扑地图占用存储空间较少(由环境的复杂度决 定),在不需要知道移动机器人准确的位姿信息的情况下可以实现快速的路 径规划,为人机交互下达指令提供了一种更为自然的接口,但是难以创建和 维护,特别是传感器误差较大时,如果环境中存在两个很相似的地方将很难
确定这是否为同一节点。


山东大学硕士学位论文
2.1.3几何特征地图 几何特征地图也是一种紧凑的地图表示方法f引,通过传惑器感知的环境 数据,从中提取抽象几何特征如线段、圆、弧线等来表示环境信息,Lu和 Miiios最早利用激光测距仪获取数据并从中提取直线特征。对于大多数环境

特剐是室内环境和用几何特征描述的地图都能精确的反映环境信息,而且几 何特征地图存储信息量小,方便应用于位姿估计和目标识别。目前几何特征
地图已经被广泛的研究和应用,可以直接应用在移动机器人的导航和路径规

划上,很多关于移动机器人导航和路径规划的算法都是基于几何特征地图
的。

2.2测距传感器
智能移动机器人系统能够感知外界环境信息,并利用对环境的感知, 有目的、安全的运行。距离检测传感器通常也就是外部传感器是移动机器人

感知外界环境信息的主要手段,传感器的性能将直接决定地图创建的精确
度。常用的距离检测传感器有三种,立体视觉(Stereo—vision)、声纳传感器 (Sonar)和激光测距仪(Laser)。下面介绍一下它们的基本工作原理以及优缺 点。 2.2.1立体视觉 立体视觉系统【10】111】利用单目镜头、双目镜头或全景相机来获取外界环 境的信息。相机是被动传感器,不发射声波或光波,主要依靠外界环境的 光线来获取信息。利用视觉传感器可以得到环境的3D信息,信息量大且能

够比较直观的反应环境信息。但是采集到的图像的质量依赖于相机标定、 光照条件、基线等情况,对于环境的噪声和光线的强弱比较敏感,而且从
采集到的图像中提取距离信息所需要的计算量比较大,利用立体视觉系统 创建地图不能满足实时性的要求。 2.2.2声纳传感器 声纳传感器112l∽‘是用柬测量移动机器人与障碍杨问距离的传感器.其 基本工作原理是:发射一列声波并接收反射波,根据发射与接收的时j’日J州隔


山东大学硕士学位论文
TOF(time-of—flightl和声速v得到声纳传感器与反射物间的相对距离r:

r。—vxiTO—F


(2.1)

声纳传感器由于其价格低廉、使用简单、数据处理方便等特点得到了广 泛的使用,已经成为移动机器人上的标准配置。但是利用声纳传感器测量存 在较大误差,除了声纳传感器本身的测量精度不高外,还容易受环境因素例 如温度、空气湿度等影响。由于声纳传感器发射的声波有一个散射角,因此 声纳传感器可以感知障碍物在一个扇形区域内,但是无法感知其准确位置。 如果一个系统存在多个声纳传感器,在较为拥挤的环境中可能会发生串扰, 即一个声纳传感器发出的探测波束被另外一个声纳传感器当作自己的探测 波束接收到。声波在环境中不理想的反射是实际环境中声纳传感器遇到的最 大问题,如果声波信号在嘈杂的环境中多次反射造成能量损耗,致使最后返 回时已经低于接收器响应阈值,声纳传感器就收不到反射信号。由于声纳传 感器自身的特点,通过其获取的信息量相对较少且精确度不高,因此利用声 纳传感器创建地图1141无法满足精确度的要求。
2.2.3激光测距仪

与声纳类似,激光测距仪【15】也是通过发射一列光速,然后测量光束发射 与接收间的时间间隔TOF(time-of-flight)来计算激光测距仪与反射物间的距 离,:

,。—cx—T_OF


(2.2)

其中c为光速,c-3x108m/s,和声纳相比,由于光波的特性,激光测距仪的 测量速度快,限制测量速度的主要原因是激光测距仪中机械结构的转动速 度,而声纳传感器大部分时间消耗在声波的发射返回过程。激光测距仪测量 精度高,而且散射角很小,光波的反射性能决定了数据的可靠性,不需要考 虑多次反射和错误反射的问题,读数可以直接作为真实距离使用。但是激光 测距仪价格昂贵,而且只能提供一个高度平面上的距离信息,激光不能感知 某些透明的物体如玻璃,如果环境中存在镜子或者其它非常光滑能使得激光 产生镜面反射的物体,激光测距仪在某些角度将不能发现这些目标从而导致
信息缺失。



山东大学硕士学位论文
在室内结构化环境下,地面平坦,所有障碍物都垂直于地面,移动机器

人只要获得和地面平行的平面上的信息,就可以创建出满足导航、路径规划
等任务要求的2D地图【16l。由于激光测距仪具有测量速度快,测量精度高的 特点,对于环境的噪声及光线也不敏感,利用激光测距仪做出的地图117】【18】 具有很高的精确度和鲁捧性。因此本文选用激光测距仪作为测距传感器,对 激光测距仪获取的环境信息进行处理,从而得到室内环境的2D地图。

2.3实验的硬件平台
本文研究所用到的实验平台是由ActivMedia Robot公司的Pioneer 移动机器人和SICK公司的LMS200激光测距仪组成。
2.3.1 Pioneer 3-AT

3移动机器人

Pioneer

3-AT移动机器人(如图2.1)采用四轮驱动,配备里程计、机械

陀螺仪、声纳传感器、激光测距仪等传感器,是一款智能移动机器人。

图2.I实验硬件平台

机器人系统采用C—S结构,由一上位机(PC机)和下位机(西门子H8S 单片机)构成,AROS(ActivMedia
Robotics

OperatingSystem)是机器人H8S

控制器中运行的软件系统,机器人运行于C.S模式下。在这种模式下,机器 人的大多数低端操作任务都是由AROS实现的,如电机控制、声纳数据、码

山东大学硕士学位论文
盘数据的读取等。由于激光测距仪的数据量比较大,读取速度也比较快,对 CPU和内存的要求比较高,因此在Pioneer 3-AT移动机器人通过上位机完成

激光测距仪的读数并对信息处理。上位机通过串口(RS232协议)和下位机通 信,获取下位机读取的数据并对数据进行处理,然后发送控制命令给下位机, 由下位机负责电机的控制。上位机中运行的ARIA(ActivMedia
Interface for Robotics

Application)是ActivMedia公司为其移动机器人开发的,面向对

象的,用于机器人控制的应用程序接口系统。该系统基于C++语言,是一个 可以简单、方便的用于Pioneer系列移动机器人的运动控制以及传感器操作
的客户端软件,具有强大的功能和适应性。
Pioneer

3-AT移动机器人的c.s结构提供了一个很好的开发平台,在不必

完全了解底层工作原理的情况下,通过封装好的函数可以方便的控制机器人
运动,获取传感器数据,并在此基础之上进行自己的二次开发。这也是本文 选取其作为硬件平台的原因之一。 2.3.2激光测距仪

图2.2 LMS200

图2.3 LMS测距原理图

LMS200是德[]SICK公司的一款2D激光测距仪119l(图2.2),其内部主要 由微控制芯片、激光发射器、激光接收器、高速旋转镜片和反射镜构成(图 2-3)。激光发射器发出一束光波,通过高速旋转镜片、反射镜发出,遇到障 碍物后经反射镜由激光接收器接收,通过计算发射返回的时间间隔得到激光



山东大学硕士学位论文
测距仪到障碍物的距离信息。通过高速旋转镜片的转动可以实现180度范围

内的扫描。经过微控制芯片处理褥到的距离信息通过串口(RS232/RS422协
议)传送给上位机。LMs200型激光测距仪的主要参数如表2·1所示:
表2.1 扫描范围
180'一V100"。

LMS200型激光测距仪的主要参数 '畏8晕模式
mm,cm

扫描分辨率
10/O.50/0.250

最大量程(m)
8.191/81.19

允许误差(mm)
10/100

通讯协议
R¥232fR¥422

数据传输速率(Bd)
96010/19200,38400,500K

扫描周期(ms)
13,32/26.64

数据点个数
101/181/201/3q61/401

根据选用的激光测距仪的工作参数不同,可以得到不同的测量精度和不 同个数的测量数据。本文中选取测量模式为mill模式,即最大量程为8.191m, 扫描范围为180度,间隔0.5度,这样一个周期扫描需要26,64ms,可以得到 361个数据点,通过RS232协议采用38400波特的速率和上位机通讯。这样的 工作参数可以满足创建地图的精度和实时性的要求。

2.3.3激光测距仪的特性分析 为了了解LMS200激光测距仪的测量特性,通过2个实验获得测量数据。 对其测量特性进行分析。实验均在静态室内环境中进行。
·

实验一:同一入射角度数据分析
激光测距仪在同一位置测量同一入射角(450)的数据值,重复测量300次,

得到一组数据J伍。,x:,…,x。),这些数据得到的概率是相同的,所以
数学期望和均方差公式可以表述如下:

E(x)。专著x; 咐)2专著(弘£㈣2
o(x);√D(x)

(2.3)

(2‘4)

(2.5)

按照公式(2.3)(2.4)(2.5)可以求得其数学期望E(X)=1003.43mm,均方差 口(x)=5.16ram。同实际测量值(1000mm)相比较,可以认为激光测距仪的数

10

山东大学硕士学位论文
据是精确可信的。其数据点分布图如图2.4所示,测量数据比较明显的服从 正态分布,图中显示了对应的正态分布曲线。

990

995|000

1005

1010

X(测量值ram)

图2—4多次测量数据点分布图
·

实验二:各个角度数据分析 激光测距仪面对墙角时的测量结果(如图2—5),图中的点反映了一个周

期180度的测量结果,并还原显示在以激光测距仪为中心的直角坐标系中。
从结果中看到测量不受激光入射角的影响,基本可以体现出墙角的几何特 征。



I≥

.//








图2—5室内墙角的测量结果

激光测距仪获得的数据信息是离散的、局部的,受测量量程和扫描分辨

率的影响,有可能出现盲区(如图2.6所示)。远处尺寸较小的障碍物恰在本
次测量两个扫描间隔角度的夹缝中,这样障碍物就不能被检测到。

山东大学硕士学位论文

图2.6激光测距仪盲区示意图

激光测距仪能检测到的物体的最小直径Ad满足公式(2.6):

Ad-2Dsin撰)


(2.6)

假设测距量程为D=8.191m,扫描间隔角度为a一0.5。,那么激光测距仪能 够保证可以感知其存在的测量范围内物体直径应大于0.072m。随着机器人的 移动,远处不能检测到的物体在近处可以检测到,因此在实际实验中,激光

测距仪的盲区可以忽略不计。 2.4本章小结
本章主要介绍了地图描述的三种方法,栅格地图、拓扑地图和几何特征 地图。本文的实验环境为室内环境,结构简单,通过对这三种地图特点的分 析,本文选取几何特征地图作为地图的描述方法。通过比较获取外界环境信 息的传感器:立体视觉、声纳传感器和激光测距仪的特性,本文选取精度高、 测量速度快的激光测距仪作为外界环境信息获取的传感器。最后对实验所用 的硬件平台作了简单介绍,并对LMS200激光测距仪特性作了分析。通过本 章的内容可以证明,本文选用的地图描述方法以及硬件平台满足地图创建的 要求,可以达到本文预期的目标。

山东大学硕士学位论文

第三章局部地图创建

3.1引言
地图的创建是一个复杂的过程,其实现主要依靠移动机器人的内部传感 器获取机器人自身的位姿,外部传感器获取环境数据信息。根据外部传感器 的精度不同,地图的表示方法也不同,如选用声纳传感器则一般采用的地图
描述方法是栅格地图。本文采用激光测距仪作为外部传感器,可以获得精确 的环境数据信息而且数据量比较大,测量速度较快,因此本文选用几何特征

地图作为地图的描述方法。本文采用了局部地图创建一移动机器人自定位~
全局地图创建的步骤和方法。移动机器人在初始位姿通过激光测距仪获得一 组环境数据信息,运用局部地图创建的方法得到一个局部地图。当移动机器

人移动到另外一个位姿后,在新位姿通过激光测距仪获得一组新环境数据信
息,通过里程计获得移动机器人的当前位姿,这个位姿是不精确的,存在较 大的误差,通过对两次测量的数据信息相比较,运用扩展卡尔曼滤波算法来

实现移动机器人的自定位,更新机器人的位姿。在实现移动机器人自定位后, 重新计算位姿更新后的局部地图,通过融合更新后的局部地图和全局地图的 数据,实现全局地图的创建与更新。 本章要解决的问题是根据激光测距仪获取的环境数据信息提取几何特 征,完成地图创建的第一步:局部地图的创建[eol。通过激光测距仪的一个
周期扫描,可以得到移动机器人前方1800范围内间隔0.50的距离测量值,

对这些测量数据信息进行处理,从中提取几何特征并计算特征参数,完成局 部地图的创建12l】【22】。参数估计是一个得到广泛研究的问题1231,在许多研究
领域都得到了广泛的应用,从一系列带有噪声的数据中提取线段特征是参数

估计的一个实例。在移动机器入研究中许多线段特征提取的方法来源于机器 视觉中对类似问题的研究【241,例如Hough变换【251、距离加权Hough变换、
基于模糊原型[261、迭代端点拟合(1EPF)【27】等等。但是激光测距仪测量的数

据信息有其自身的特点,它是按逆对针I颐序以一定角度闯隔排列的,而且每
个角度只有一个测量值,因此可以利用该特点选择更高效的计算方法来提取

山东大学硕士学位论文
环境的线段特征。

连续特征128】是指能够用统一模型描述且具有一定规模的特征单元。激光 测距仪获得的环境信息是离散的,而且数据量比较大,因此需要用连续特征
来表示环境信息,本文主要用线段来描述环境的连续特征,线段也是许多研 究者使用的模型,如墙壁、较大家具等都可以使用若干线段集合描述,其几 何形状也成为移动机器人定位和路径规划中的重要参考标准。 在局部地图的创建过程中,有很多成熟的算法并得到了广泛的应用,取

得了不错豹效果。Hough变换所实现的是一种从图像空问到参数空闻的映射
关系,由于其根据局部度量来计算全面描述参数,因而对于区域边界被噪声 干扰或被其他目标遮盖而引起边界发生某些间断的情况,它具有很好的容错

性和鲁棒性。在参数空闻不超过二维的情况下,这种交换有着理想的效果。
但是一旦参数空间增大,计算量便会急剧上升,同时耗费巨大的存储空间, 耗时也随之猛增。另外~种常用的方法是基于模糊原型的方法,采用模糊逻

辑的理论,使用模糊集合及隶属度函数来描述传感器获得的环境数据的不确 定性,使用模糊操作运算符完成数据的处理并建立模糊集来描述环境的几何
特征。这种方法具有很好的鲁棒性,但是也比较耗费时间。在局部地图的创 建过程中,为了避免先前算法中的耗费时间多、实时性不好的缺点,本文提

出了一个“聚合一分割一聚合”的方法来提取线段用以表示环境信息,分为
区域分割、线段提取和线段拟合三个步骤。首先把361个离散的数据点按照 连续两点间的距离大小分隔成彼此不连通的区域,然后将这些区域分隔为可 以用线段特征表示的线性区域,最后采用最小二乘线段拟合方法得到线段的 参数。在区域分割和线段提取的步骤中采用动态闽值的方法,使得分割更为 精确并可以滤除一些噪声数据,可以在较短的时间内获得一个精确的局部地 图。 本章第二节主要给出了数据的预处理,第三节详细介绍了局部地图创建 的三个步骤以及采用的方法,并给出了实验的结论和结果。

3.2数据预处理
根据2.3.2一节中选用的激光测距仪的工作参数,通过激光测距仪每次

14

山东大学硕士学位论文
扫描可以得到移动机器人前方180度范围361个数据点的信息,这些数据点 的信息是以激光测距仪中心为极点的极坐标系表示的,相对于全局坐标系来 说是局部坐标系。为了处理的方便,把这些以极坐标表示的数据信息转化为 笛卡尔坐标下的数据信息,如图3-1所示:

全Y


.M(pi.Oi)
//




,///∽,F)

-。/


么)竺一一一》.> k’x
图3-1坐标变换示意图

图中点M(见,只)是测量中的第i(/一o^…,360)个数据点,Pi是测量得到的
距离值,因为激光测距仪获得数据是按照角度顺序排列的,所以第f个点的 角度只可以通过公式(3.1)计算得到:

B—0—.5—xi石 180


(3.1)
、 ’

其笛卡尔坐标∽;,F)可以表示为:
X■Pi
X。一PJ
xcosOf

Y一
xsinof

(3.2)

15

山东大学硕士学位论文
通过移动机器人自带的里程计和机械陀螺仪,可以得到移动机器人在全 局坐标系中的坐标,进而可以求得激光测距仪中心在全局坐标系中的坐标

O‘伍。,匕),激光测距仪主轴和x轴的夹角口,这样按照公式(3.3)就可以计算

出数据点M的全局坐标肼伍;,搿),如图3.2所示。
Xf=X。+Xt瞄a—Y/sina
×。-匕+Xj sina+I。cos口 3.3局部地图创建
通过坐标变换可以得到数据点的全局坐标,下一步就是将激光测距仪采
集到的离散点的数据信息处理成用来表示环境信息的连续特征信息,也就是 (3.3)

本文采用的线段特征,并计算得到线段的参数。本文提出了“聚合~分割一
聚合”的方法,分为区域分割、线段提取和线段拟合三个步骤来完成,最后

得出线段的参数和用线段特征表示的局部环境地图。
3.3.1区域分割 通过坐标变换,可以把通过激光测距仪测量得到361个数据点的信息转 化为全局坐标系下的笛卡尔坐标。本节的目的就是把这361个离散数据点按 照连续两点问的距离大小分成彼此不连通的区域。首先假设这361个数据点 为一个区域,起点为第一个点,终点为第361个点,那么得到一个区域

4(∽。,Kl伍。,Kl…伍。,y瑚))。区域分隔的具体步骤如下:
①按照公式(3.4)计算连续两个点之间的距离

D,一√∽,一J。)2+∽一x+。)2其中J t1,2,…,360

i。o,1,…360

(3.4)

②判断D;和阈值d的关系(6的选取主要依据经验,本文中采用动态阂值的

方法,接下来会有详细介绍),如果Dj大于闽值6,则认为点Xj,■j是两
个区域的分割点,以这个点为分割点将区域分成两部分,可以得到区域

爿,“戤,Vo】,(X。,Kkk,,巧J),爿:∽Ⅲ,¨+lJ∽j.2,vj+:1...伍。,匕。)J。按照同

16

山东大学硕士学位论文
样的原则对区域A:进行分割,得到区域A:,以。依次类推,最后可以得到

相互不连通区域“,4,...,A)。如图3-3所示,在这次测量过程中,可以

得到四块相互不连通的区域“,以,A3,一。)。

图3-3区域分割示意图

◎判断每个区域内的数据点的个数,如果某个区域包含数据点的个数小于等 于三个,那么该区域被视为噪声区域,舍弃这些噪声点。



Robot

~~…。……二……;




图3-4(a)激光测距仪获得的原始数据

图3-4(b1定阈值条件下获得的局部地图

17

山东大学硕士学位论文



Robot

图3-4(c)变阈值条件下获得的局部地图

由于障碍物到激光测距仪的距离不同,相邻扫描点之间的距离也不同,

较远处连续两点间的距离较大,这个距离值有可能大于选取的阈值6,这样
就会造成出现分割过细的现象,把数据点当作噪声点舍去,造成信息的丢失 (如图3.4所示)。图3-4(a)为激光测距仪获得的原始数据信息,图3-4(b)是

按照本节中局部地图的创建方法按照定闽值生成的局部地图,从图中可以看
出,距离激光测距仪较远处的信息丢失,而且信息丢失量较大。为了获得较

为准确的分割效果,减少错误的划分,本文采用了动态阈值的方法。假设扫
描点到激光测距仪中心的距离小于等于D,选取的阈值为6,那么当扫描点 到激光测距仪中心的距离大于D且小于等于2D时,选取的阈值为26。图

3-4(c)即为采用动态阈值方法获得的局部地图,从图中可以看出,局部地图
完整地反映了激光测距仪的扫描结果,取得了很好的分块效果。通过实验可 以证明,动态阈值的应用可以提高局部地图创建的准确性和精确性。 在实验中,选取D为2000ram,按照公式(2.6),距离激光测距仪为D的

地点,能检测到的障碍物的最小直径为鲋一17.45ram,选取
6—1.3xAd=22.6ram作为区域分割的阈值,经实验证明,阈值的选取比较合 适,可以得到准确的区域分割效果。 3.3.2线段提取

经过区域分割,得到了可以用线段描述的区域4“=t,2,...,Ⅳ),这些区域
可能是一条或者多条线段的组合,本节的目的是将每一个区域分割为若干点

集,L(厶,工:,...,三。),其中的每一个点集t可以用一条线段来表示。线段提取
的方法有很多种,首先介绍几种已有的方法:
·

SEF(successive

edge

following):从区域的起始点扛l,Y1)按顺序开始搜

18

山东大学硕士学位论文

索,计算相邻两点间的距离,把后续点加入同一点集中,如果点k,y。)

和点(t。,,。)之间的距离大于阈值D一,那么以点k,y。)为分割点,
下一点集从k。,y。。)为起点继续搜索。
·LT(1ine

tracking):根据已有点集眠,Y。lG:,Y:l…,k。,y。))拟合线段,

然后计算下一点k,Y。)到该线段的距离工。。,如果工。。,工一,那么保

存已经拟合线段。新的点集设为缸。,Y。Xk。y。并,从点k。Y。)开
始新的搜索。 ·IEPF(iterative pointfit):与以上两种算法不同的是,SEF和LT都是按 照数据点的顺序进行搜索,这两种方法的搜索效率比较低,计算量大 且耗时较多。本文选用的线段提取方法为迭代适应点方法,这是一种 迭代方法(如图3.5所示)。这种方法搜索效率较高且速度较快,针对 LEPF算法中线段分割过细的情况,本文给出了改进的方法。

图3—5

IEPF方法不葸圈

以区域Ai的第一个点只(x,,E)和最后一个点£伍。,K)作一条直线£,计 算区域Aj内其余各点到这条直线L的距离,假设在点己伍。,y历)处取得距离

的最大值D一,如果距离最大值大于阈值%,以点己为分割点将区域4分
成两部分,4眈,只。…,己),4帆,己。…,C)。然后对区域4和4采用同样
方法进行处理,直到该区域内所有点到所在区域起点终点构成直线的距离的

19

山东大学硕士学位论文

最大值不大于阈值%。这样就得到了M个可以用一条线段线性表示的点集
Lia一1,2,,,肘)。图3.5示意图中可以求得两个分割点只伍。,L),只伍.,L),
这样就可以把这个区域分割成三个点集,可以用三条线段表示。
由于各个区域的距离激光测距仪的距离不同,包含数据点的个数也不 同,为了提高线段提取的精确度,阂值D。的选取采用动态闽值的办法。即

以区域起点只仅,,E)和终点只(x。,E)为端点生成的线段L的长度为参考标

准,阈值%选为线段长度的15%,经实验证明,阈值D。,的选取是比较恰
当的,提商了线段提取的精确度,减少了误差。

图3-6 IEPF分割过细示意图

IEPF是一种精确且计算效率较高的方法,但是受原始数据精度和阈值参 数选取的影响,一些情况下也会出现线段提取不当或者分割太细的情况(如 图3.6所示),实际可以用三条线段来表示的区域被错误的分成了四条线段。 因此在IEFF算法基础上进行了改进,将线段提取分为二个步骤完成。先按 照IEPF算法进行分割,然后根据3.3.3节中的最小二乘线段拟合算法,得到 线段的参数,然后计算任意相邻两条线段L;和£:之间的夹角d。,和相邻两 条线段端点的最小值d。。。如果满足条件(3.5) 口“+I<dm,且d…1.(d陆, (3.5)

那么假设认为这两条线段是被错误分开的线段,应该为同一条线段,以其中

山东大学硕士学位论文
一条的起点和另外一条的终点作一条直线r,然后重新计算这两条线段工。和 L上的所有数据点到这条直线r的距离,如果所有数据点到直线£‘的距离均 小于阈值Do,那么这两条线段为同一条线段,重新计算新线段的参数。 3.3.3线段拟合 经过上述处理,得到了可以用一条线段线性表示的点集

‘一仍,最,...,B},这些数据点存在噪声,并不是严格的线性关系,因此需
要寻找一条线段能最大程度的反映出这些点的关系。本文采用Deriche等人 提出的最d'--乘线段拟合算法(Least 段特征参数的计算。 如图3.7所示,p为坐标原点到线段L的距离,口为坐标原点到直线L的
Square Line Fitting

Algorithm)来完成线

垂线与X轴的夹角,口∈【_石,石】。那么线段L上的点Pb,y)满足:
XCO¥口+ysina—P

(3.6)


图3.7最小二乘线段拟合算法示意图



假设以为点只G;,Y,)到线段£的距离(3.7),那么最小二乘线段拟合算法就 是求最优(p,a),使得所有点到线段的距离的平方和最小(3.8):
dj=,j
cos

G一0,)一p

(3.7)

山东大学硕士学位论文

缸£暑‘“荟d?=ar毒牙“善“cos仁一B)一p)2
最优(p,口)的计算方法为:

(3.8)

口’_三…(熹a c)一三










(3.9)

p’一X—COSO!’+一ysina‘

(3.10)

其中:


扣百刍墨


1卷

(3.11)

p百蔷甄

1卷

f3.12)

口一耋k一;)2
6:z妻b一;xy;一y) 6=2∑k一;br一)
cI蓍cyr 一歹P

(3.13)

(3.14)

(3.15)

经过最小二乘线段拟合算法,得到了这条线段的最优(p,Ct),那么点 只k,Y。),BG,,Y。)在这条拟合线段上的投影就是线段的端点只仁,,Y,), 只b,,Y。)。 工,一X1+cosa(p—zICOSCt—Y1 sinct) Y,=Yl+sina(p—X1toga—Yl sina) x:一x《+cosa(p—X qCOSOl—Y sina、


(3.16) (3.17) (3.18) (3.19)

Y。一YⅣ+sina(p一工ⅣCOSt)/一YⅣsina)
得到线段的端点后,可以计算线段的长度:

三;瓜j可可■玎

(3.20)

山东大学硕士学位论文
线段和x轴的夹角: 8。苎+口


(3.21)
、 7

经过上述步骤地处理,一条线段就获得了五个特征参数:起点和终点、 长度、与x轴的夹角,坐标原点到线段的垂线距离、包含数据点的个数。
虽然选取其中的起点和终点参数就可以准确的表示出这条线段,但是计算出

线段的多个参数有利于机器人定位和全局地图创建的实现。这样通过激光测 距仪得到的离散数据点就处理为用线段几何特征表示的地图。图3-8(a)为激
光测距仪获得的原始数据(离散的点),图3-8(b)为按照上述步骤得到的局部

地图(连续的线段)。从图中可以看出得到的局部地图可以完整的反映出激
光测距仪获得环境数据信息。

o 图3-8(a)原始数据点示意图



图3-8(b)局部地图示意图

3.4本章小结
本章主要介绍了局部地图的创建过程,激光测距仪扫描一次得到前方 180度范围内361个环境数据信息。得到的数据信息是以激光测距仪中心为

极点的极坐标系表示的,通过数据预处理,将数据信息转化为全局笛卡儿坐 标系,然后采用“聚合一分割一聚合”的方法,通过区域分割、线段提取和
线段拟合三个过程来完成局部地图的创建。在区域分割的过程中采用“动态 阈值”的方法,提高了区域分割的精确度并且滤除了一些噪声点。在线段提 取的过程中采用迭代适应点(IEPF)方法并作了改进,提高了线段提取的精确

度。在线段拟合过程中采用最小二乘线段拟合算法,得到了线段的参数,为

山东大学硕士学位论文
机器人定位算法奠定了基础。经过实验证明,本章的算法是快速可行的,能 有效的将激光测距仪获取的环境数据信息处理为线段特征,得到了精确度较 高的局部地图。

山东大学硕士学位论文

第四章机器人定位

4.1引言
在全局地图的创建过程中,机器人定位【29]130】是非常重要的一个环节,机 器人定位的精确程度直接决定了生成的全局地图的精确程度,同时也是移动 机器人导航和自主作业等任务实现的关键问题。 移动机器人定位方法可以分为两大类【31l【321,一类是相对位姿测量,主要
依靠移动机器人的内部传感器如里程计、陀螺仪等,但是这类方法存在累积

误差,定位精度不高。第二类方法是绝对位姿测量,一种是依靠环境标志信 息如主动灯塔、人工路标等1251,另一种是通过外部传感器获取环境数据信
息进行数据匹配来获得定位。

在未知环境的地图创建过程中【331【341,不存在人为的环境标志信息,所以
本文主要通过移动机器人内部传感器和外部传感器获得的数据进行融合来

实现移动机器人定位,通过移动机器人内部传感器数据获得机器人的参考位
姿,通过外部传感器如激光测距仪获取环境数据信息进行数据匹配来实现移 动机器人的精确定位。

数据匹配135】是指对激光测距仪两次测量生成的局部地图进行匹配,即把 移动机器人从当前位姿(通过内部传感器获得的位姿)获得的测量值与从上
一位姿得到的测量值进行匹配,尽可能找到一个较好的配准,从而计算出当

前位姿与上一位姿之间移动机器人角度和平移距离的变化值,计算的结果用
于修正移动机器人的当前位姿,从面得到一个精确的位姿,有效地减少了累 积误差。

Lul36】提出了一种迭代的算法来建立两次测量数据间的对应关系从而进 行数据匹配,他利用了最近点规则和对应距离点规则,由此得到两次测量闯
移动机器人位姿的变化。Gonzalezl371等人让移动机器人沿指定路径作连续扫 描测量,对测量结果求取空间中的线性特征来估计机器人的转动。Crowleyl38】 等人把距离测量结果转换到多维空问中的一个点上,对环境中的系列表面用 该空间的一个特征值表示,通过机器人位姿空间和特征值的匹配决定机器人

山东大学硕士学位论文
的当前位姿,这种方法的精确度和鲁棒性在实验中表现并不好而且需要大量 的存储空间。Thrunl39I通过比较当前的局部栅格地图和全局地图的对应关系 以帮助定位。 图像处理中的直方图概念作为数据匹配的要素也被用来移动机器人定 位中。Wetzler[40】提出了角度直方图的概念,用来表示测量结果中相邻点组 成的向量的角度分布,通过两次测量直方图的变化找到最优匹配处以估计移 动机器人的转动角度,移动机器人的距离变化值也可以通过计算x.Y直方的 方法估计求得。当移动机器人沿着以前走过的路径前进时这种方法表现出了 较好的估计结果,但是对于初始位姿状态有过高的要求而且需要存储大量的 数据信息。Duckett和Nehmzowl411使用类似的方法解决了全局定位的问题, 他们使用电子罗盘来减少里程计的误差,但是这种方法需要大量的计算,实 时性不好。 由于移动机器人定位过程中存在很多不确定性因素【42l【431,例如里程计累 积误差和传感器噪声数据等,因此越来越多的研究者把概率理论144J【45l应用 到移动机器人定位中。马尔可夫定位【46l(Markov Localization)是通过计算机 器人位姿在栅格地图中的概率分布,从而确定机器人位姿的定位方法,根据 每次传感器的测量结果在环境中所有可能的位姿上计算机器人位姿的概率 分布。这种方法的特点是在存在全局地图的前提下,能够在初始位姿未知的 情况下定位机器人,能够应用于噪声较大、测量不是特别精确的传感器,能 够表现位姿分布的=义性并主动扩展以消除这种二义性,计算量与栅格大小 和数量有关。但是这种方法随着环境的复杂程度增加,计算量成几何倍数增
长,实时性不好。蒙特卡罗定位147l(Mont
Carlo

Localization)是马尔可夫定位

方法的扩展,这种方法并不计算环境中所有位姿的概率分布而只是选择其中
的一些样本。移动机器人根据里程计信息,在运动的过程中产生这些样本,

并根据传感器的测量进行更新。蒙特卡罗定位比马尔可夫定位效率更高的原
因是它的计算量根据样本的数量线性增长,而样本的数量与整个环境信息量

相比少的多。这两种定位方法都需要预知全局地图,多用于栅格地图中的定
位。 卡尔曼滤波【4 8lf49II如J(Kalman Filter,K.F)定位方法是移动机器人定位中常

山东大学硕士学位论文
用的一种方法,它一般分为两步:预估和校正。通过读取内部传感器获取的 机器人的位姿信息作为预测位姿的估计值,然后根据外部传感器获取的环境 信息与先前已知的环境信息进行数据匹配,最后基于误差矩阵得到最优的位 姿估计结果。Durrant.Whytel51】等人提出了基于卡尔曼滤波的分布式信息滤 波器,它与分布式贝叶斯分类和信息的测度方法相结合构成了分布式信息决 策系统的核心内容,应用这种分布式的决策理论他们解决了移动机器人依靠 声纳进行定位【52】的问题。Jetto[53】等提出了一种基于模糊逻辑的自适应卡尔 曼滤波算法来进行传感器数据融合以完成定位,这种算法的特点是通过设定 模糊规则,计算并调整卡尔曼滤波器的参数来提高算法的自适应能力,具有 较好的鲁棒性,但是计算量比较大。 卡尔曼滤波算法是基于线性系统提出的滤波算法,由于本文主要任务是 实际环境地图的创建,所涉及的实际系统属于非线性系统,在理论上难以找 到严格的递推滤波公式,直接应用卡尔曼滤波算法比较困难,因此目前大都 采用近似方法来研究。非线性滤波的线性化就是用近似方法来研究非线性滤 波问题的重要途径之一。非线性滤波的线性化主要有两种形式:线性化卡尔 曼滤波和扩展卡尔曼滤波(Extended 展卡尔曼滤波算法。 在扩展卡尔曼滤波算法中,移动机器人位姿的预估值可以通过移动机器 人内部的传感器获得,这是位姿的一个参考值,数据匹配的目的就是对这个 参考值进行校正,得到比较精确的机器人位姿。数据匹配过程需要全局地图 中已经存在线段的实际观测值,由于局部地图采用的是全局坐标系,因此对 于相同环境测量得到的线段应该是同一条,因此全局地图中己存在线段参数 的观测值可以由当前测量获得局部地图中的对应的线段参数提供,这样的一 对线段就定义为相关线段,寻找局部地图和当前全局地图的相关线段是应用 扩展卡尔曼滤波算法进行移动机器人定位的前提条件。 本章第一节简要介绍了移动机器人定位的方法,第二节主要介绍相关线 段的判断方法,第三节主要介绍卡尔曼滤波算法和扩展卡尔曼滤波算法,第 四节介绍扩展卡尔曼滤波算法在移动机器人定位中的应用,最后给出实验的
结果。
Kalman

Filter,E.K.F),本文选用的是扩

山东大学硕士学位论文 4.2相关线段的判断
4.2.1线段范围 应用扩展卡尔曼滤波算法进行移动机器人定位的需要的关键参数是局 部地图和当前全局地图的相关线段。因此在寻找局部地图和当前全局地图相 关线段的过程中,为了减少需要判断的线段数量,缩短计算的时间,本文提

出了“线段范围”(如图4.1所示)的方法。经实验证明,该方法能有效地 减少需要判断的线段数量,特别在当前全局地图的线段数量比较多时能有效
地缩短计算的时间。 R
’.
。.

..,



.·’

图4-1线段范围示意图

工。为全局地图中的一条线段,以k的两个端点S、E和激光雷达中心0
为顶点可以得到一个范围R,对于给定的范围R,局部地图中的线段可分为 以下四种情况: ①线段的两个端点都在R外部而且与R无交点。 ②线段的两个端点都在R内部。

⑨线段的一个端点在R内部,一个端点在R外部。
④线段的两个端点都在R外部而且与R有两个交点。 判断一条线段符合以上哪一种情况时,本文选择了一个比较简便的方 法,通过判断线段的端点和直线OS、OE的关系来确定线段符合的条件, 将端点带入直线的方程,如果大于O,那么端点位于直线上方,如果小于0, 那么端点位于直线下方。这种方法计算量小,能有效地缩短判断时问。在当

山东大学硕士学位论文
寻找相关线段时,只考虑这些在R区域范围内的线段(如线段2,3,4),

“线段范围”提供了一个简便的方法,减少了寻找局部地图和当前全局地图
相关线段时要检查的线段数量,缩短了计算的时间。

4.2.2相关线段判断方法
在局部地图的创建过程中,每条线段经过计算得到了五个参数,这为判 断相关线段提供了参考标准,具体可分为以下四个步骤:

①取出全局地图的一条线段工。,按照“线段范围”的方法,得出局部

地图中符合条件的线段Lc"L。…,LcⅣ,如果不存在,则取出全局地图的下一
条线段工。。,再次计算,直到找出所有符合条件的局部线段为止。

②取出局部地图中的符合条件①的一条线段L。。,判断和全局地图中的 线段£。是否相关,需要满足以下两个条件:
·

A0·h一%ltd(吼是局部地图中线段L。。和X轴的夹角,%是全局地图
中线段三。和x轴的夹角)。

·Ap—p。-p。j.(y(几是坐标原点到局部地图中线段己。的垂线距离,Pa是

坐标原点到全局地图中线段k的垂线距离)。
如果满足以上两个条件,则认为这两条线段工。,和£。是相关的。 ③对于符合条件①的局部线段Lc2,L。,,...,工cⅣ,按照②的判断准则,计算

得到所有的“A吼,Ap。X(A口:,Ap:I…,(AOM,△m)),

然后计算

△q·K。AB 4-K:△n。选取符合条件且具有最高簧信度,也就是Aq值最小

的局部线段k作为全局线段工。的相关线段。
④重复步骤①一③,找出满足条件的所有全局地图和局部地图的相关的
线段对。

山东大学硕士学位论文 4.3卡尔曼滤波算法
4.3.1随机线性离散系统的卡尔曼滤波算法

假设存在随机线性离散系统s(A。G,C,w,v)

严2例黠㈦

y伍)一c(七k忙)+v忙)

。。V ∽t,

式(4.1)中,x(k+1)是系统的小维状态向量,彳酝)是系统的m×埘维状态转移矩

阵,G伍)是埘×.|}维噪声输入矩阵,啡)是系统的七维过程噪声序列,y忙)是
系统的,l维观测向量,c(七)是席Xm维观测矩阵,v任)是胛维观测噪声序列。

假设谁Xv仅)为统计独立、零均值、高斯白噪声过程,满足

{卢如妊)};、o

f£{w取))一0

Ep睡)w7(fj}=R1任p。
Ep任p70)}一只:(七弦。
(4.2)

I£{∥恤≯7(f)J;0

式(4.2)中,R。忙)是系统过程噪声谁)的kxk维对称非负定方差矩阵,R:仅)是
系统观测噪声p伍)的疗×n维对称正定方差阵,而“:是Kronecker.6函数。
fl
k=l 七≯,

6材害10

(4·3)

i忙+1);彳忙房仁)

叭1)-A(km)P(k卜)A谁黜肌跳)
P伍+1)= 7皓)+G仅皿;妊)G7忙) 只任,z)-C(k)P(k,f)c7(f)+R:似)

(4.4) ”‘斗’

山东大学硕士学位论文

式(4.4)中往犯lm))为k时刻仁(七ly往))的数学期望,雕1只忙,f)为系统的协
方差阵,对初始状态石(o)有

I㈨一捌蒯牙。v(o)
1Ek(o)一i(0)B(o)一i(o牙t
状态估计 经过递推可以得到卡尔曼滤波的基本公式 滤波增益矩阵



p。’ (4.5)

j使/七)一爿伍一1瓷妊一llk—O+Klkb(k)一C(k)A(k~1弦妊一1/k一1)】

(4.6)

K忙)一P(k/k—I)C7伍Ic伍)P忙/七一1)cr伍)+马化圩1
估计误差方差阵

(4.7)

尸隹/后)一[,一鬣任F往炉任/七一1)
一步预测误差方差阵

(4.8)

雕+1/尼)一彳忙)P忙/七n’仅)+G伍k忙)G7忙)
递推初值为

(4.9)

叠(o/o)一i(o),V(Ol一1)一P(o)
公式(4.6)·(4.9)RO为随机线性系统的卡尔曼滤波方程,只要给定初始值

萱(0)和尸(o),根据k时刻的观测值y@),就可以递推计算得到七时刻的状态 估计值膏忙融-1'乙…)。
由公式(4.6).-7得到随机线性系统卡尔曼滤波器方框图(如图4.2所示), 滤波器的输入是系统状态的观测值,滤波器的输出是系统状态的估计值。

照r恸~矿够L 留


加两Ⅲ~—上医孙一m-l/#,-1)
31

量据肛1)

圈4—2随机线性系统卡尔曼滤波器方框图

由公式(4.7)-(4.9)可知,K仉)与在线观测值_,,似)无关,而爿任),c似),G伍),

山东大学硕士学位论文

蜀似),R:任)已知,因此卡尔曼滤波期的增益K伍)可以离线计算,计算过程
如图4.3所示


I..............。.....一

豳茴

R:忙)c(k)

只。伍)4伍)G妊)

图4.3滤波增益K忙)计算流程图
4.3.2随机非线性离散系统扩展卡尔曼滤波 随机线性离散系统的卡尔曼滤波算法是卡尔曼滤波的基础,很多实际系 统和过程都可以抽象为线性数学模型,可以运用线性卡尔曼滤波算法得到较 好的状态估计值。但是对于一般的非线性系统,在理论上难以找到严格的线 性数学模型,因此不能直接应用线性系统的卡尔曼滤波算法求解,目前大都 采用近似方法来研究。扩展卡尔曼滤波就是应用比较广泛的一种方法,本文 的实际系统由于受到多方面噪声的影响,实际为非线性系统,因此采用扩展 卡尔曼滤波算法实现机器入的定位。 假设随机离散非线性系统为

P瓣h∽t毒(札k),kl觜批’

式(4.10)qu

_),@)=

+v伍)

r’ (4.…tuI

w忙lv忙)为统计独立、零均值、高斯白噪声过程,其统计特性满

足公式(4.2)。,b似l≈】,占b忙l女】和^k似lt】为非线性函数,它们均存在行阶
导数,因此可在条件均值j任/七)或立以/k一1)附近展开成泰勒级数。

山东大学硕士学位论文

,b忙l后】.,k忙/七I七】+爿伍)b忙)一量伍/七)】+… gb任l七】。g&忙/七l七】+… .Ilb(七l七】一h[Yc(k/k一1l七】+c任)b任)一萱(k/k一1)]+…

(4.11)

(4.12) (4.13) (4.14)

舯制·期蛳, c¨割Oh[x,k神州
项,式(4.10)可以近似线性化为

(4.15)

令G取)。g瞄任/七l七],忽略泰勒级数中Ix(k)一量伍/七)]或k任)一戈(k/k一1)】的高次

P伍+1)一爿(七k似)+G仅)w任)+“伍) 1 y忙)一c忙b任)+V仅)+z伍)
式中

(4.16)

“伍)一,瞄传/七X.|}]一A(k)嚎(klk) z忙)一h[戈(klk一1X七卜C(k)i(klk一1)

(4.17) (4.18)

对式(4.16)所描述的系统,利用上一节的线性卡尔曼滤波公式,可以得到以 下扩展卡尔曼滤波计算公式

:O(klk)一:O(klk一1)+K忙){y取)一|Il瞄仁/七一1l七丑
主任+l/k)。,[王任/七l七】

(4.19)

(4.20)
(4.21) (4.22) (4.23)

置忙)。e(klk一1)cr(k《C(k)P(klk一1)cr忙)+R:伍汗1
P(klk);【,一K似)c忙)]P(klk一1)
尸伍+1/后)一爿忙)P伍/七妇70)+G@k仁p7任)
递归初值为

主(o,一1);i(o),P(OI一1)=P(O) 假设系统对k时刻的观测预测值为夕伍) 多Q)一^B@/k一1≥女】
(4.24)

那么传感器的实际观测值和预测值之间的差值就是卡尔曼滤波的新息

山东大学硕士学位论文

v伍)-y忙)一夕@)一y以)一h[i(k/k一1l七】
4.4扩展卡尔曼滤波在机器人定位中的应用

(4.25)

当机器人从位姿工@)处开始运动,经过一段时间后到达位姿记为工皓+1),

“似)一陋伍lA口任牙,其中岱@)为新旧位姿的位移长度,△口任)为新旧位姿
z伍+l/k)一,k忙X七]+gk忙l七,舷) ,b娘),七]即为通过移动机器人内部传感器获得的新位姿。

(4.26)

批捌忧怦舞嘲
制一掣;
必辫蕊可 业盟剖丽砧瓦』‰ 型 巫础显啡
嚣 二基|;。
坩甙㈤D


似27,

将,b忙X七]系数线性化,在条件均值王伍+1/七)附近展开成泰勒级数,滤去二





这样可以得到系统的滤波预测和预测方差

主任+1,女)=,k往),七]
尸伍+l/k)一爿似)P似/七n7忙)+G(七h忙)G7伍)
②计算系统的观测预测

(4,29) (4.30)

假设全局地图中的一条特征线段为_),。O),这条直线在机器人坐标系中的

山东大学硕士学位论文

参数为(几01%(f)),系统的观测方程为
(4_31)

萝(七xf)t【p日((七k))Jl=.Il[圣(七/七一1xy。(f)】

其中^p忙/七一llyc(f)】一[pGo’一j@7七-%1)(f.),s—o占o((七i)/-七y一(1k)7七一1’sin%01(4.32)
将^瞄伍/七一1ly。(f)】系数线性化,可以得到

cm唑姥产-

一ap伍)ap(七) a,£(k/k-1)醪(k/k一1)og(k/,一1) ap忙) a口【七)’ 一ap伍) a,£(k/k一1)@(k/k一1)ag(k/k一1)
(4.33)

!旦堡!

-【-警∞“秽爿
那么系统对这条线段的删测预测和预测方差为

y(kXi)-h[叠(k/k一1),y。(f)】
C,一C(kg"(k/k一1)C(k)r
③计算扩展卡尔曼滤波的新息

(4.34) (4.35)

根据4.2节的寻找相关线段的方法找到线段y。O)的实际观测量y(kXi).那 么线段Yo(f)对应的新息为

V妊Ⅺ)一),忙酢)一萝忙弛)一y化Ⅺ)一h[土<k/k一1ly。O)]
新息方差

(4.36)

s(kXO-c任)P伍/七一1)C(k)r+R:伍)
④计算卡尔曼增益

(4.37)

每一条全局地图中的线段y。(f)和其对应的观测都有一个卡尔曼增益,可
以由式(4.38)计算得到

K忙酢)一P伍/七一1)c7伍妊(七)P伍,七一1)cr伍)+岛忙)】_1
一P(k/k一1)c7妊砖僻Ⅺ)。1
(4.38)

山东大学硕士学位论文
⑤状态更新 重复步骤①一④,计算得到系统对k时刻所有存在的匹配的卡尔曼增益, 则移动机器入新的位姿向量

x(t)=曼(七,露一-)+丢耋K(%xiIy(kXi)一,l[置(k/k-1xy。(f)Ⅲ

=王忙肛1)专;}K(kX/)V(kXi)

(4.39)

经过以上步骤的处理,更新了移动机器人的位姿,得到了一个较为精确

的新位姿,以这个新位姿为基础按照第三章局部地图创建的方法,重新转换
激光测距仪获取的数据信息,进行局部地图的创建,这样可以获得一个精确 的局部地图,为全局地图的创建做好基础。

4.5实验结果
4.5.1仿真实验 为了证实扩展卡尔曼滤波算法在移动机器人定位中的可行性,首先在机 器人Pioneer 3的仿真软件MobileSim下进行实验,分别采用MobileSim自带 的航位推算算法和扩展卡尔曼滤波算法进行移动机器人定位实验(如图4.4 和图4.5虚线所示)。移动机器人从起点s点出发,前进1500mm,左转90度, 前进1000mm,左转90度,前进1500mm,左转90度,1i{『进1000mm,左转90 度,最后到达终点£。移动机器人位移改变大于20cm或者转动角度大于lO 度时就运用机器人定位算法进行机器人定位,修正机器人的位姿。按照理论 值,移动机器人在终点E的位姿应该和在5点的位姿相同。图4.4为移动机 器人在航位推算算法下的运动轨迹图,终点和起点的误差为
At=105mm,ay一57ram,AO

a11.3。,图4.5为移动机器人在扩展卡尔曼滤波算

法下的运动轨迹图,终点和起点的误差为Ax=25ram,Ay一19mm,AO=4.3。。通 过实验可知,扩展卡尔曼滤波算法在移动机器人定位中是可行的、有效的算
法。

山东大学硕士学位论文

图4-4航位推算算法下的轨迹图

图4.5扩展卡尔曼滤波算法下的轨迹图

4.5.2实际环境中的实验



图4.6未经过自定位的地图

图4.7经过白定位的地图

在实际环境中,移动机器人从起点S出发,移动到终点E,当机器人位 移大于20cm或者转动角度大于10度时就读取一帧数据,这样一共获得了10 组数据,得到了10个局部地图。图4.6和图4.7为10个局部地图的直接叠加, 图4.6是未经过机器人自定位叠加得到的地图,图4.7是采用扩展卡尔曼滤波 算法后进行机器人定位后叠加得到的地图。从地图中可以看出,未经机器人 自定位的地图存在较大误差,而采用扩展卡尔曼滤波算法经过机器人自定位 后得到的地图误差较小。由仿真结果和实际环境下实验结果可以证明扩展卡 尔曼滤波算法在实现移动机器人自定位中是有效的算法。

4.6本章小结
本章主要介绍了卡尔曼滤波算法以及扩展卡尔曼滤波算法在移动机器

山东大学硕士学位论文
人定位中的应用。利用扩展卡尔曼滤波算法实现移动机器人定位的关键是寻
找局部地图和当前全局地图之间的相关线段,以局部地图中的线段作为当前 全局地图中相关线段的观测量,为利用扩展卡尔曼滤波算法进行移动机器人

定位提供了参数。本文提出了一个“线段范围”的方法,减少寻找局部地图 和当前全局地图之间的相关线段所耗费的时间。通过实验证明,这个方法可
以有效地缩短寻找相关线段的时间。仿真实验和实际环境的实验证实,扩展

卡尔曼滤波算法在移动机器人定位中是有效可行的算法,能够得到很好的定
位效果。

山东大学硕士学位论文

第五章全局地图创建

5.1引言
完成局部地图创建和移动机器人定位后,本章讲述地图创建的最后一

步,全局地图的创建。全局地图是通过融合多个局部地地图的数据得来的。
当完成移动机器人定位后,可以得到一个精确的机器人位姿和更新后的局部 地图,比较更新后的局部地图和当前全局地图的线段关系,可以把局部地图

的数据融合到当前全局地图中,这样就更新了全局地图,直至最后完成全局
地图的创建。

5.2局部地图和全局地图的融合
对于每一个局部地图中的线段,根据4.2相关线段的判定方法可以将局部 地图中的线段分为与全局地图相关的线段和与全局地图无关的线段。具体可 以分为以下四种情况,如图5.1所示,图中实线代表全局地图中的线段,虚 线代表局部地图中的线段。 (a)局部地图中的线段和全局地图中的线段为同一条,完全重合。 (b)局部地图中的线段是全局地图中的线段的一部分。 (c)局部地图中的线段与全局地图中的线段的部分重合。 (d)局部地图中的线段不存在全局地图中。

图5一l(a)局部线段和全局线段完全重合

图5-l(b)局部线段为全局线段的一部分

山东大学硕士学位论文

图5—1(c)局部线段和全局线段部分重合

图5.1(d)局部线段与全局线段不相关

在移动机器人定位算法中,得到了局部地图和全局地图的相关线段,经 过机器人定位后,局部地图的线段参数得到了纠正,它们和全局地图中的相 关线段的关系符合图5-1中的(a)(b)(c)中的一种。由于激光测距仪的数据是按 照逆时针顺序排列的,因此得到的线段的端点也是按照逆时针顺序排列的, 可以根据线段局部地图和全局地图相关线段端点的关系来判断。

假设局部地图线段的端点为(x。,y皿l伍。,y皿),和其相关的全局地图的

线段的端点为伍。,‰X扭。,‰),它们的关系有以下几种。
①fz。一x。fcd&&Iz。一石。fc 6&&ly皿一lkIc 6&&pr皿一‰Ic6
(5.1)

其中6为一闽值,一般取为0.05p。(p£为原点到局部地图中线段的距离)。 如果满足条件(5.1),那么认为这两条线段是同一条线段(如图5-1(a)所 示),可以直接把局部地图中的线段删去,保留全局地图中的相关线段。

②伍。一x。)×伍。一x。)一co&&阢一%)×(‰一y皿)co

(5.2)

如果满足条件(5.2),那么认为局部地图中的线段是全局地图相关线段的 一部分(如图5-1(b)所示),可以直接把局部地图中的线段删去,保留全局 地图中的相关线段。

(萤(xsG一工。)×(x。一x。),o&&('岛一y皿)×pr肼一y皿),0

(5.3)

如果满足条件(5.3),那么认为局部地图中的线段与全局地图相关线段是 部分重合的(如图5.1(c)所示),需要重新计算线段的参数,取出局部地图

山东大学硕士学位论文
和全局地图相关线段的原始数据信息,根据3.3.3一节中的最小二乘线段拟合 算法重新计算得到新线段的参数。由此可以得到一条新的线段加入到全局地 图中,同时删除全局地图和局部地图中原来的线段。 如果局部地图中的线段和全局地图中的线段不相关(如图5-1(d)所示), 可以直接把局部地图的线段插入到全局地图中,同时从局部地图中将该线段 删除。重复以上步骤,直至局部地图中的线段为空,这样就完成了局部地图 到全局地图的融合,更新了全局地图。具体流程图如图5—2所示。

图5.2局部地图和全局地图的融合流程图

5.3实验和结论
本文通过调用ActivMedia公司的Aria类库,运用C++语言编程实现激
41

山东大学硕士学位论文
光测距仪数据的读取、移动机器人位姿信息的读取以及移动机器人运动的控 制。采用Microsoft公司的Visual C++6.0作为本系统的界面开发工具,运 用MFC实现地图的界面显示,并实现了地图的移动,缩放等功能。 实验采用的环境为室内环境,选用激光测距仪的扫描范围为 i800(.900~900、。扫描间隔为0.50,每次扫描可以{寻到361个数据点,最大量 程为8.191m,其误差为1ram。按照本文提出的算法,全局地图创建的流程 图如图5-3所示。



:◇ N。匡NO ,宣 直 ◇ 匡
匿5.3全局地隧的生成蛉流程圈

移动机器人在室内移动时,当机器人的移动距离大于20era或者转动角度 大于10度时,读取一帧数据,按照本文提出的算法通过比较已经存在的全 局地图进行机器人定位和全局地图的更新。在3m'3.5m的实验环境中(如 图5.4所示),共读取了84帧数据,图5.5为实验得到的全局地图,整个全 局地图由28条线段组成。从图中可以看出,全局地图能够准确的反映出环 境的特征,实验结果表明算法是准确可行的。

山东大学硕士学位论文

图5.4实验环境示意图

图5.5全局地图示意图

山东大学硕士学位论文 5.4本章小结
本章主要介绍了全局地图的创建过程,经过机器人定位后得到的局部地
图是精确的,通过比较局部地图和当前全局地图的线段关系,可以将局部地 图中的线段分为与全局地图相关的线段和与全局地图无关的线段,分别采取 不同的处理方式,经过实验证明,本文采用的算法得到的全局地图是精确的, 能准确地反映出环境信息。

山东大学硕士学位论文

第六章总结

6.1课题总结
随着智能机器人技术的发展,自主能力的机器人会越来越广泛的应用在 我们的生产生活中,而环境地图是实现智能移动机器人自主运动的先决条 件,而机器人定位的精确度直接决定了环境地图的精确度。移动机器人同时 定位和地图创建成为智能移动机器人领域中的一个重要研究课题。 本文的主要研究内容集中在三个方面。 首先,硬件平台的选取是课题的关键部分,通过分析对比各种测距传感 器的优缺点,本文选取了LMS 200激光测距仪作为环境信息的获取工具,
同时选取Pioneer 3移动机器人作为移动平台。实验结果表明,硬件平台的

选择是合适的,得到了很好的效果。 第二部分是局部地图的创建过程,通过分析环境地图的表示方法以及本 文实际的环境,选用几何特征地图作为环境地图的表示方法,移动机器人在 一个特定地点可以获得一组激光测距仪的数据,通过区域分割、线段提取、 线段拟合三个步骤处理,得到当前环境的局部地图,实验结果表明,按照此 方法获得的局部地图是精确的,为下一部分的处理奠定了基础。 第三部分是机器人自定位和全局地图的创建,通过机器人自身的传感器 获得的位姿信息作为扩展卡尔曼滤波算法的实际观测值,通过匹配局部地图 和当前全局地图的相关线段实现机器人的自定位,更新了机器人的位姿和当 前的局部地图。通过融合局部地图和当前全局地图的数据实现全局地图的创 建和更新,最终得到了完整的全局地图。通过仿真和实际环境的地图创建证 实,本文提出的方法和步骤是有效可行的,取得了良好的效果。

6.2论文的创新点
1.本文采用了局部地图创建一机器人自定位一全局地图创建的步骤,通 过激光测距仪获得的数据可以创建用几何特征表示的局部地图,通过机器人 自定位后减少了机器人的位姿误差,融合全局地图和经过机器人定位后的局

山东大学硕士学位论文
部地图可以得到精确的全局地图。 2.局部地图的创建过程中,在区域分割、线段提取两个步骤中提出了 “动态阈值”的方法,按照扫描点距离激光测距仪的距离不同选取不同的阈 值。通过实验证明,动态阈值的方法可以提高区域分割和线段分隔的精确度, 并能滤除噪声数据点,提高了局部地图创建的精确度。 3.机器人自定位步骤中,为了较快的寻找到局部地图和全局地图的相 关线段,提出了“线段范围”的方法,减少了寻找相关线段的搜索范围,提

高了搜索的速度,为实现实时定位和地图刨建提供了可能。实验证明,特另q
是在地图数据量较大的情况下,此方法可以显著减少机器人定位的时间。

6.3课题不足与展望
移动机器人同时定位和地图创建是智能机器人领域的一个重要的研究

方向,本文利用激光测距仪,选取几何特征地图实现了环境地图的创建,取 得了较好的效果。但是由于时间、技术等方面的限制以及本人水平有限,特
别是在理论研究方面不够深入,一些新的理论成果不能很好的应用在实际工 作中,本文的研究还存在很多不足,一些新的内容需要进一步研究和完善。 1,在局部地图创建过程中,分割采用的阈值依靠经验值过多,在新的 环境下不能自适应,影响地图创建的精度。 2.在机器人自定位中,采用扩展卡尔曼滤波取得了较好的定位效果, 但是还存在定位不准确的情况,特别是转动过程,有必要进一步研究,以求 达到精确的定位效果。 3.本文主要是创建室内环境的2D地图,下一步的工作主要集中在考虑 复杂的室外环境地图的创建和室内室外3D地图的创建。

山东大学硕士学位论文

参考文献
【1】.蔡自兴,贺汉根,陈虹.未知环境中移动机器人导航控制研究的若于问题
【J】.控制与决策,2002,17(4):385·390. 【2】.Dissanayake G,Newman
localization and map P,Clark S.A.Solution
to

the

simultaneous
on

building(SLAM)problem[J].IEEE

Trans

Robotics

and Automation,2001:229—241.

【3】.Guivant

J E,Nebo!E

M.Optimization

of the simultaneous localization and

map-building algorithm for real—time implementation.IEEE Trans.Robotics and

Automation[J].2001,17(3):242-257.
optimal robot motion control in simultaneous of the and

【4】.Huang S,Wang z.Time
localization and map IEEE

building(SLAM)problem[C].Proceedings
Conference
on

/RSJ

International

Intelligent

Robots

Systems,2004:3110—3115.

【5】.Elfes A,Moravee

H.High resolution maps from wide angel
on

sonar[C].IEEE

International Conference

Robotics and Automation,1985:116—121.
on a

【6】.Kuipers

B,Byun Y T.A robot exploration and mapping strategy based

semantic hierarchy of spatial representations【J】.Robotics and Autonomous
Systems 1991:47-63.

【71.Cox

I J,Blanche.An

Experiment in Guidance

and

Navigation Robotics

of

an

Autonomous

Mobile

Robotic【J】.IEEE

Transactions

and

Automation,1991:193·204.

【8】.Cassandra,L.Kaelbling,J.Kuiren.Acting
Bayesian

under Uncertainty:Discrete

Models

for

Mobile
on

Robot

Navigation[C].Proc

IEEE/RSI

International Conference

Robotics and

System.1996,(2):963—972.
building using of Intelligent

【9】.Guivant
natural

J,Nebot E.Simultaneous localization and map features in outdoor

environment[C].Proceedings

Autonomous System,2000:581·588.

【101.C

Jennings,D Murray.Stereo Vision Based Mapping and Navigation for

47

山东大学硕士学位论文
Mobile Robots[C].Proceedings
of the IEEE International Conference
on

Robotics and Automation,1997:1694—169.

【11].Yoshiro

N,Jun M,Yoshiaki

S.Mobile

Robot Navigation in

Unknown

Environments Using Omni directional Stereo and Laser Range

Finder[C].
Systems,

IEEE/RSJ

International Conference

on

Intelligent Robots and

2004:2737—2742.

【121.S

Thrun,C

Martin,Y

Liu D.A

Real·time

Expectation·maximization

Algorithm for Acquiring Multi—planar Maps of Indoor Environments with Mobile Robots【J】.IEEE Trans Robotics and Automation,2004,20(3):
433.443.

【13].B

Barshan,R Kuc。Differentiating Sonar Reflections from Corners and by Employing
an

Planes

Intelligent

Sensor【J】.IEEE

Transactions

on

Pattern Analysis and Machine Intelligence,1990:560-569.

【141.J

D Tard‘OS,J Neira,P

M Newman.Robust Mapping Data【J】.Inter

and Localization in of Robotics

Indoor

Environments Using Sonar

Journal

Research.2002,21(4):311—330.
【15].Arras
K O,Tomatis N.Improving robustness and precision in mobile robot by using laser ranging finding
on

localization

and

monocular

vision[C].
Robot,

Proceedings of Third European 1999:177一185.

Workshop

Advanced

Mobile

【16].Zezhong
with

Xu,Jilin Liu,Zhiyu Xiang.Map building for indoor environment range

laser

scanner[C].IEEE

5th

International

Conference

on

Intelligent Transportation Systems,2002:136—140.

【171.张奇,顾伟康.激光测距雷达及其在移动机器人中的应用【J】.机器人, 1998,20(3):227—231. 【18].李清泉,李必军,陈静.激光雷达测量技术及其应用研究【J】.武汉测绘科 技大学学报,2000,25(5):387-392. 【19].Telegrams for Operating/Configuring
the LMS 2xx Laser Measurement

Systems,Firmware Version V 2.10/X 1.14,SICK

【201.H
48

Choset,K

Nagatani.Topological

Simultaneous

Localization

and

山东大学硕士学位论文
Mapping(SLAM)Toward
【J】.IEEE Transactions
on

Exact Localization without Explicit

Localization

Robotics and Automation,2001:125-137.

【211.G

A Borges,M J Aldon.A Split·and—Merge Segmentation Algorithm for

Line Extraction in 2一D Range

Images[C].IEEE

International Conference

on

Pattern Recognition,2000:441-444.

【22].J

Vandorpe,H Van Brusse,H Xu.Exact dynamic map building


for



mobile

robot using geometrical primitive produced by

2D range

finder[C].IEEE

International Conference On Robotics and Automation,1996:901-908.

【23].Li Zhang,Bijoy

K Ghosh.Line 2D Laser

Segment

Based

Map
IEEE

Building

and

Localization
Conference

Using

Range

finder[C].the

International

on

Robotics and Automation,2000:2538-2543.

【24].Frigui

H,IC_rishnapuram R.A robust competitive clustering algorithm with
in

applications

computer

vision[J].IEEE

Tran

on

Patter Analysis

and

Machine

Intelligence,1999,21(5):450·465.
J,Ahman


【25].Forsberg

P,Wernersson

A.The Hough transform inside the
Conf Robotics and Automation

feedback loop of 1993:791.798.

mobile

robot[C].IEEE

【26].J



Castellanos,J



Tardos.Multisensor

Fusion

for
on

Simultaneous Robotics and

Localization and

Map

Building[J].IEEE

Transactions

Automation,2001:908-914.

f27].Siadat

A,Kaske A,Klausman S.An optimized segmentation method for



2D laser-scanner applied to mobile robot
on

navigation[C].In

3rd IFAC symp

intelligent components and instruments for control applications,1997:

153.158.

【28].Huang

S,Kwok N M.Multi—step look ahead and
on

trajectory
of the

planning in IEEE

SLAM:

possibility Conference

necessity[C].Proceedings

International

Robotics and Automation,2005:1103-1108.

【29].Amigoni

F,Caglioti V.A mobile robot mapping system with information

based exploration
on

strategy[C].Proceedings

of the International Conference

Informatics in Control,Automation and Robotics,2004:71—78.
49

山东大学硕士学位论文
【30].罗荣华,洪炳铭.移动机器人同时定位与地图创建研究进展【J】.机器 人,2004,26(2):183—187.

【31].李群明,熊蓉,褚健.室内自主移动机器人定位方法研究综述【J】.机器 人,2003,25(6):560-567. 【321。迟建男,徐心和.移动机器人即时定位与地图创建问题研究【J】.机器 人,2004,26(1):92-96. 【33].陈卫东,张飞.移动机器人的同步自定位与地图创建研究进展【J】.控制
理论与应用,2005,22(3):455—459。 【34].Xu
Zezhong,Liu Jilin,Xiang Zhiyu.Map building and Localization Using

2D Range

Scanner[C].IEEE

International Symposium

oll

Computational

Intelligence in Robotics and Automation,2003:848—853,

【351.S Wci,Y

Yagi,M Yachda.Building local floor map by

use

of ultrasonic
on

and omni—directional vision

sensor[C].IEEE

International Conference

Robotics and Automation,1998:2549一2553.

【361.Lu

F.Shape registration using optimization for mobile robot

navigation[D].

Ph D Thesis,University of Toronto,Toronto,1995.

【37].Gonzalez

j,Gutierrez

R.Direct motion

estimation from



range

scan

sequence[J].Journal 【381.Crowley


of Robotics

Systems,16(2),1999:73·80.

L,Wallner
of range

F,Schiele B.Position estimation using principal

components

data[C].IEEE

Conf

Robotics

and

Automation

1998(4):3121-3128. 【39].S
Thrun.Learning metric—topological maps for indoor mobile robot

navigation[J].Artificial 【401.Wei G,Wetzler

Intelligence,1998:21,71.

C,Puttkamer E.Keeping track of position and orientation by correlation of range·finder

of moving indoor systems

scans[C],IEEE

Conf Intelligent Robots and Systems,1994:595—601.

【41 1.T

Duckett,U Nehmzow.Mobile robot self—localization and measurement

of performance in middle—scale Systems,1998,24:57—69.

environments[J].Robotics

and Autonomous

50

山东大学硕士学位论文
【42].厉茂海,洪炳熔.移动机器人的概率定位方法研究进展【J】.机器人, 2005,27(4):380·384. 【43].崔茂源,董再励.移动机器人激光全局定位系统的算法研究【J】.系统工程 与电子技术,2001,24(11):73—75. 【44].N
Vlassis,Y Motomura.Supervised linear feature extraction for mobile

robot

localization【c】.IEEE

Int Conf On Robotics&Automation,2000:

2979.2984.

【45].Arulampalam

S,Maskell S.A tutorial

on

particle

filters

for
on

on—line Signal

non-linear/non·Gaussian Bayesian tracking[J].IEEE Transactions

Processing,2002,50(2):174—188. 【46].D Schulz,W
with


Burgard.Probabilistie state estimation of dynamic

objects

moving mobile

robot[J].Robotics

and Autonomous Systems,2001,

34:107.115.

【471.W

Burgard,A Den,D.Fox.Integrating tracking

global position

estimation and localization

position

for

mobile

robots

the

dynamic Markov
on

approach[C].the

IEEE/RSJ International Conference

Intelligent Robots

and Systems,1998:730—735.

【48].Rudy
2003.

N.Robot Localization and Kalman

Filters【M】.Utrecht

University,

【49].冯培悌.系统辨识【M】.浙江大学出版社,2004.
f501.Roumeliotis
S I,Bekey G A.Bayesian estimation and Kalman filtering


unified framework IEEE International

for

mobile

robot
on

localiza“on【c】.Proceedings
Robotics and

of the

Conference

Automation,2000:

2985.2992.

【511.Julier



J,Durrant—Whyte

H.Navigation and parameter estimation of high

speed road vehicles.IEEE Conf Robotics and Automation,1995.

【52].Albert

D,Geoffrey

T.Interactive

SLAM
on

using

Laser and Advanced

Sonar[C].IEEE
1103.1108.

International Conference

Robotics and Automation,2005:

【53].L

Jetto,S I_onghi,D Vitali.Localization of a wheeled mobile robot by

sensor

data
51

山东大学硕士学位论文
fusion based
on


fuzzy logic adapted Kalman filter[J].Control Engineering

Practice,1999,7:763-771.

山东大学硕士学位论文





本文是在尊敬的导师李贻斌教授以及宋锐老师的精心指导和悉心关怀下完 成的。在论文的选题、研究以及撰写的整个过程中,始终得到两位老师的悉心 指导和亲切教诲,对于课题研究过程中遇到的任何问题,宋锐老师总是以饱满 的热情认真地给予讲解,令我深受感动。老师渊博的知识、严谨的治学态度、 高度的责任心,和蔼可亲的学者风度,使我无论从理论水平还是动手能力上都 得到了很好的提高,为今后就业或继续深造做了很好的知识和技术储备。将对我 今后的工作和学习产生长远而又积极的影响。尤其李贻斌老师,无论是在学习 上还是生活上都给与了我最热心的关怀和帮助,这些最真诚的帮助我会铭记在 心。值此论文完成之际,谨向导师表示衷心的感谢,并致以崇高的敬意。 十分感激山东大学控制学院的各位老师在学习和生活中给予的关心、支持 和帮助。感谢牛君、柴汇、张娟、罗晓、肖莎、王彦堂、王小鹏、赵玉良等同 学给予的支持与帮助。并向所有给予作者关心与帮助的人们表示深深的谢意。 我要特别感谢我的爸爸和妈妈,感谢他们的含辛茹苦、精心培育和支持。 他们生活和学习给予我的帮助是双重的,在此表示深深的感谢! 最后,还要感谢一个对于我来说有着特殊意义的人,我的女朋友王元华, 她给予我的是无微不至的关心、帮助和支持,是无人能取代的,今天我所取得
的成绩与她密不可分。

山东大学硕士学位论文

作者攻读硕士期间发表的论文
汤晓,李贻斌,王彦堂,张娟。基于Maplnfo的最短路径混合搜索算法。山东理 工大学学报(自然科学版),2006,20(2),pp:81—84.

基于激光测距仪的移动机器人同时定位和地图创建
作者: 学位授予单位: 汤晓 山东大学

相似文献(10条) 1.学位论文 温安邦 基于激光测距仪的室内机器人定位方法研究 2009
定位问题是自主移动机器人要解决的首要问题,也是其实现自主导航、即时定位与建图和完成其它智能任务的关键。定位问题也是一个复杂的问题 ,涉及到移动机器人研究领域的多个方面,包括移动机器人的运动学,环境表示方式,信息融合,不确定信息处理等。本文主要研究移动机器人定位的 理论和实现,主要工作如下: 建立了移动机器人的运动学模型。分析了里程计和激光测距仪两种常用传感器的原理及其误差模型。比较了机器人学中的三种环境表示方法,包括 几何地图,栅格地图和拓扑地图。 分析了室内环境中移动机器人的定位问题,并对此问题进行建模。分析了卡尔曼滤波器和基于此滤波器的马尔可夫定位,重点研究了粒子滤波器和 基于此滤波器的Monte Carlo定位。比较了在室内环境中两种定位方式的优点和不足。通过分析ICP,PSM等几种能够对激光数据进行关联的扫描匹配算法 ,在Monte Carlo定位算法的基础上提出了一种改进方法。 设计了基于激光测距仪的移动机器人定位实验,以验证移动机器人定位算法的有效性。在室内环境中进行实验,并对实验结果做出了分析,主要分 析机器人位姿初始分布和粒子数目对定位精度的影响。 本文最后描述了SLAM问题以及与机器人定位的关系,并将本论文的主要工作延伸到SLAM问题中,探讨使用基于Rao-Blackwellized粒子滤波器的 FastSLAM解决SLAM问题。

2.学位论文 郑宏 移动机器人导航和SLAM系统研究 2007
移动机器人导航和SLAM技术在制造业、空间开发和服务机器人领域具有广阔的应用前景。 导航技术需要解决三方面的问题:(1)地图,映射移动机器人工作空间的模型,是移动机器人路径规划的平台。(2)路径规划,指移动机器人按 照某一性能指标,在地图中搜索一条从起始状态到目标状态的最优或次最优的无碰路径,是移动机器人导航的核心技术。(3)定位,确定移动机器人在 二维工作环境中相对于全局坐标的位置及其本身的姿态,是保障移动机器人导航质量的最基本环节。 移动机器人实现自主导航的前提是精确的定位,特别是在地图事先未知的情况下,因此,同步定位与地图创建技术(SLAM)始终是移动机器人领域的 关键基础问题。SLAM问题所涉及到的5大问题:(1)地图的表示方式;(2)不确定性信息处理方法;(3)数据的关联;(4)自定位;(5)探索规划 ,几乎涵盖了移动机器人研究的各个领域,并且这些问题并非孤立存在,相互间存在着紧密的联系和渗透。 在过去的研究中,人们针对移动机器人技术中的地图建模、路径规划和自定位问题分别提出了许多理论和方法,并都有不同程度的实际应用。但是 ,从整体的角度上整合各项技术,设计实用的移动机器人导航软件平台,却是目前研究中较少涉及的领域。 针对地图已知的情况,本文设计并开发了一个基于混和地图模型的全自主移动机器人多层递阶导航系统。该系统由地图编辑器模块、多层递阶规划 模块以及自定位模块三部分组成。地图编辑器负责导航地图的编辑,可以同时编辑几何地图和拓扑地图,不但提供了友好的人机交互界面,而且方便了 地图的创建与保存;多层递阶规划模块包括基于拓扑地图的全局规划、基于栅格地图的局部规划和底层的行为控制功能,做到了全局环境的简化规划、 局部环境的精细规划和避障功能相结合,提高了整个系统的计算效率;自定位模块采用里程计和激光测距仪混合定位的定位技术,充分利用里程计的短 距离相对精度较高、激光测距仪局部探测精确的特点,从而达到机器人大范围导航过程中准确定位的目的。 为了解决地图事先未知情况下的自定位问题,本文设计并开发了一个基于扫描匹配的SLAM方法。该方法采用几何地图表示环境,既节省了存储空间 ,又便于使用激光传感器创建;利用沿墙走的策略,降低了探索路径算法的复杂度,保证了实时性;通过里程计和激光测距仪混合定位方法,克服了 SLAM过程中由于单一传感器带来的不确定性问题;通过比较线段间的距离关系和角度关系,采用线段合并算法方便快捷的把局部地图与全局地图间的线 段进行合并,实现了数据的关联。 最后,将该导航和SLAM系统集成在一台全自主移动机器人上,传感器采用激光测距仪和里程计,进行了地图已知情况下的大范围的导航实验和地图 未知情况下的SLAM实验,实验结果表明本文提出的关于地图创建、路径规划、自定位和SLAM等方法是可行的,验证了由这些方法组成的系统的有效性和 鲁棒性。

3.学位论文 赵季 基于激光测距仪的同步定位与建图研究 2008
同步定位与建图(SLAM)是自主移动机器人领域的重要研究方向,也是机器人实现自主导航、在未知环境中完成复杂智能任务的关键,集中体现了机 器人的感知能力和智能水平。同步定位与建图又是一个复杂的问题,涉及到移动机器人研究的各个方面,特别是环境的表示方法、不确定信息的描述和 处理方法、数据关联、环路闭合、探测策略等问题。本文主要研究机器人同步定位与建图的理论和实现,主要工作如下: 介绍了机器人学中的环境表示方法,包括拓扑地图、占有栅格地图和特征地图。针对室内环境中线段特征丰富的特点,使用特征地图表示室内环境 。采用分层聚类的方法从激光测量数据中提取直线特征,并创建局部地图。 介绍了同步定位与建图的概率框架、图模型。介绍了SLAM的两种主要解决方案,即扩展Kalman滤波器方法和Rao-Blackwellized粒子滤波器方法。 设计了室内环境下基于激光测距仪的同步定位与建图方案。移动机器人使用二维激光测距仪测量距离,采用编码器记录机器人的路径。采用一种分 层聚类的方法从原始激光测量数据中提取直线特征,并计算直线特征参数的方差矩阵。通过扩展Kalman滤波器更新机器人位姿和直线特征的参数。文中 还给出了机器人的运动学模型、观测模型,预测、状态更新等方面的相关公式。采用扫描匹配的方法对创建的地图进一步校正。 最后,利用移动机器人平台对本文提出的SLAM方案进行了大量实验。实验结果表明,机器人采用本方案可以在室内环境中创建特征地图,同时利用 该地图进行定位。扫描匹配方法可以进一步提高创建地图的精度。实验结果验证了方案的有效性。

4.会议论文 邱权.韩建达 移动机器人激光测距仪性能综述 2008
对当前移动机器人上常用的激光测距仪的性能研究进行了全面的总结。分析了检测SICK、Perceptron、Explorer等常用激光测距仪各方面特性的各 种实验结果。根据影响激光测距仪测量性能的方式,把激光测距仪的时变特性、角度偏移、数据传输影响、混合象素现象、色度亮度干扰现象、辐射干 扰现象等,分为内因和外因两大类进行了分类讨论。

5.学位论文 徐晓东 移动机器人几何—拓扑混合地图构建及定位研究 2005
本文主要研究移动机器人几何—拓扑混合地图的构建以及自主定位这两个问题。   本文首先对SmartROB-2移动机器人所装配的里程计传感器和激光测距仪传感器的模型和误差分别进行了分析讨论。研究了由里程计进行航迹推算的 局限性,给出机器人位姿误差协方差矩阵的更新方程。此外,分析了各种环境因素对激光测距仪的影响,重新界定双激光测距的距离和角度的方差分布 ,依据误差传递公式给出了激光测距的不确定信息描述,并完成双激光测距仪的硬件配置以及驱动程序调试工作。   针对不同地图构建的方法,本文提出了一种基于双激光测距仪的几何地图构建方法一点簇聚类法。该方法具有处理数据量大、计算时间短、地图精 确的优点,在静态环境和动态环境下都具有较好实用性和鲁棒性。 本文对基于POMDP的拓扑导航做了探索性的研究,讨论了在实现拓扑导航过程中状态 估计器,状态集,决策集,观察函数以及转换模型,为今后开展拓扑导航实验工作奠定了理论基础。

6.学位论文 赵妍 移动机器人自主地图库构建与环境认知 2008
移动机器人的研究涉及到智能控制技术、计算机技术、模式识别以及人工智能等许多学科,其相关技术的研究越来越受到国内外学者的重视。地图 构建是移动机器人研究中的核心问题之一,是移动机器人实现自主完成定位、导航等任务的基础。而环境认知是机器人领域的新兴研究热点,也是认知 学领域的一项重要研究项目。本文主要研究复合地图库的构建以及基于激光测距仪的环境认知问题。 本文首先对SmartROB-2移动机器人所装配的里程计传感器和激光测距仪传感器的模型进行了讨论,采用Split-Merge算法实现了对原始激光数据点进

行直线拟合。通过实际实验结果讨论了这种方法的优点和缺陷并分析了其适用环境。 本文提出了复合地图库的环境描述方法,包括几何地图、拓扑地图和非规则障碍区描述。其中采用基于栅格统计的方法非规则障碍区的原始激光数 据点进行预处理,以便去掉室内环境中的动态障碍的影响,之后使用基于网格的共享近邻聚类算法进行点聚类,最后通过对聚类后的点集进行数学分析 得到非规则障碍区的环境描述。复合地图库解决了单一地图无法很好地满足机器人自主完成复杂任务的问题,并且可以适应室内环境中几何结构的复杂 性和房间内障碍区的非规则性。仿真结果和实际复杂室内环境下的实验结果均验证了这一结论。 针对基于激光数据的环境认知问题,借鉴了认知学和指纹识别的方法,从环境中提取出由多个特征点构成的环境指纹,并提出了同时路径规划与环 境匹配(SPAC算法)实现环境指纹的匹配。为减小通路点特征的误差影响,本文采用ICP算法在每次匹配前将环境指纹按照参考模板进行校准。仿真结果验 证了所提方法的有效性和实用性。

7.期刊论文 刘洞波.刘国荣.胡慧.喻妙华.Liu Dongbo.Liu Guorong.Hu Hui.Yu Miaohua 基于激光测距的温室移动 机器人全局定位方法 -农业机械学报2010,41(5)
针对无土栽培温室类结构化环境下机器人的全局定位问题,采用激光测距仪感知环境特征,提出了一种以自适应曲率计算方法进行环境特征分割的移 动机器人Monte Carlo全局自定位方法.在机器人定位过程中,利用运动模型预测机器人的位姿,感知模型根据激光测距仪感知的环境特征的几何相似性更 新粒子集的分布,实现了机器人的自主定位.仿真实验验证了算法能够满足温室移动机器人定位的需要.

8.学位论文 叶迪 移动机器人基于激光测距的三维场景重构 2008
移动机器人对其工作环境的有效辨识、感知与重构是其自主导航与环境探索的前提条件和基础。非结构化环境与结构化环境相比具有不确定性、不 稳定性和不可预知性等特性。本文基于装备有激光测距仪的移动机器人系统,对激光数据获取、场景匹配、重构策略等问题展开理论和应用研究,旨在 实现快速、有效、自主的非结构化三维场景重构,并尝试创新性的探索与研究。 本文首先介绍了具有三维场景感知能力的移动机器人系统,其中包括三维激光测距系统以及自主移动机器人系统。采用模块化思想自主设计和开发 了三维场景重构软件,实现了三维场景的在线显示与实时重构,验证了场景匹配与重构算法的有效性与实时性。 针对不同视点下的场景两两匹配问题,采用基于线段端点的最近点迭代算法来解决。首先利用激光点云数据的有序性,采用距离比较法简单快速的 提取线段特征。由于线段端点能在一定程度上表征场景的关键信息,本文采用基于线段端点的最近点迭代算法实现场景匹配。对匹配对的选取做进一步 的限制来剔除误匹配,从而提高场景匹配的准确性。通过在实验室环境里完成的一系列实验,验证本文所提场景匹配算法的有效性和自主性。 多场景的匹配策略影响着场景重构的效果和精度。本文通过分析场景之间的拓扑关系,提出基于核心场景的大范围三维场景重构策略。对于相邻场 景重合区域的数据冗余问题,采用栅格划分的方法来进行数据精简。在走廊环境里做了一系列实验,采用不同策略实现大范围三维场景重构,通过对重 构结果的分析与比较,验证了本文所提方法的优越性和实用性。

9.期刊论文 徐玉华.张崇巍.徐海琴.XU Yuhua.ZHANG Chongwei.XU Haiqin 基于激光测距仪的移动机器人避障新方 法 -机器人2010,32(2)
针对向量场直方图(VFH)算法对阈值敏感的问题,基于激光测距仪提出一种通过自适应调节阈值求可行方向的移动机器人实时避障算法.对于给定的一 组阈值,用其中的每个阈值求可行方向,在获得的接近目标方向的所有可行方向中,选取最大阈值所对应的方向作为机器人的参考行驶方向.根据当前行驶 方向与参考行驶方向之间的偏差和所选闽值的大小对线速度进行限制.在ASR机器人上进行实验的结果表明,当最大运行速度设为0.8 m/s时,机器人能够以 0.61 m/s的平均速度安全平滑地通过障碍区.

10.期刊论文 徐玉华.张崇巍.徐海琴.XU Yuhua.ZHANG Chongwei.XU Haiqin 基于聚类的迭代双向最近点机器人位 姿估计 -机器人2010,32(3)
针对迭代最近点(ICP)算法在存在严重遮挡的情况下容易陷入局部最小值的问题,对最近点规则(CP)进行了修改,提出双向最近点规则(DCP).DCP规则 包含两次CP规则对应,使计算量增加了一倍.为了降低算法的复杂度,继而提出基于聚类的迭代双向最近点(IDCP BoC)算法.IDCP BoC对扫描数据进行聚类 ,在聚类的基础上进行数据精简.在相邻两次迭代的残差之差小于某个阈值之前,用精简数据进行迭代以提高计算速度,之后冉改用非精简数据以保证精度 .实验结果表明,IDCP BoC算法能够有效避免陷入局部最小值的问题且其实时性也是可接受的.

本文链接:http://d.g.wanfangdata.com.cn/Thesis_Y1066354.aspx 授权使用:西南科技大学(xnkjdx),授权号:42980bb5-4eb1-4361-81ba-9e0000b72e80 下载时间:2010年9月29日


相关文档

移动机器人的同时定位和地图创建方法
移动机器人同时定位与地图创建算法研究
移动机器人同时定位与地图创建研究进展
移动机器人即时定位与地图创建问题研究
移动机器人的同步自定位与地图创建研究进展
移动机器人同时定位与地图创建自适应算法研究
移动机器人在未知环境下的自定位导航和地图创建
移动机器人的同时定位和地图创建方法(200407)
基于全景视觉的移动机器人同步定位与地图创建研究
电脑版