文章编号 2 2 2

移动机器人即时定位与地图创建问题研究Ξ

迟健男 徐心和

东北大学人工智能与机器人研究所 辽宁沈阳

摘要 基于环境特征的移动机器人即时定位与地图创建是机器人领域的开放性课题 本文从环境特征提取!定位与地图创建!数据相关三个方面对移动机器人即时定位与地图创建问题进行了综述 对移动机器人定位问题作了概述 探讨了室内环境下特征提取方法 详细地论述了定位与地图创建中面临的主要问题及其解决方法 阐述了数据相关问题的基本思想 最后 根据近期文献指出了该领域今后的研究方向

关键词 移动机器人 特征提取 定位 地图创建 数据相关

中图分类号 ×° 文献标识码

ΡΕΣΕΑΡΧΗΟΝΣΙΜΥΛΤΑΝΕΟΥΣΛΟΧΑΛΙΖΑΤΙΟΝ

ΑΝΔΜΑΠΠΙΝΓΟΦΜΟΒΙΛΕΡΟΒΟΤ

≤ 2 ÷ ÷ 2

(ΙνστιτυτεοφΑρτιφιχιαλΙντελλιγενχεανδΡοβοτιχσ,ΝορτηεαστερνΥνιϖερσιτψ,Σηενγψανγ ,Χηινα)

Αβστραχτ:ƒ ∏ 2 ∏ ∏ ≥ × ∏ ∏ ≥ ∏ ¬ √ √ √ ≥ ∏ 2 ∏ ¬ √ ∏ ƒ ∏ ∏ ∏

Κεψωορδσ: ∏ ¬ ∏

1引言(Ιντροδυχτιον)

定位问题是移动机器人的基本问题,是指移动机器人通过对内部状态的检测或对外部环境的感知估算自身位置和姿态的过程.目前,应用卫星全球定位系统等装置进行室外机器人的定位已经取得成功,但限于环境!任务等因素,移动机器多采用机载传感器定位.它主要由位姿跟踪!地图获取组成.位姿跟踪指机器人在走行中对其位置和姿态的估计过程.在二维环境中,移动机器人的位姿通常使用三元组(ξ,ψ,Η)表示,其中,(ξ,ψ)表示移动机器人相对世界坐标位置(平移分量),Η表示其方位(旋转分量).在位姿跟踪问题中,移动机器人的初始位姿是已知的.初始位姿未知的位姿估计问题称为全局定位.地图获取是指移动机器人位姿已知的情况下的环境地图创建过程.移动机器人基于地图进行定位和导航.在室内环境下主要有两种环境特征表达形式:几何地图!拓扑地图.几何地图又分为特征地图和栅格地图.拓扑地图由拓扑节点和连接节点的边组成,抽象度高,适合于大环境的结构化描述.栅格地图将工作空间分为若干栅格,每一单元代表环境的一部分,并包含一个表示该单元格被占据可能性的概率值.栅格地图是一个近似的解决方案,但其对特定感知系统的假设参数不敏感,具有较强的鲁棒性.特征地图通过对环境特征的提取和参量化描述来表征环境,具有直观!精度高的特点,运用参量法描述几何特征尤其适合于不同坐标系之间的转换以及对不同传感器信息的融合.

移动机器人的位姿估计基于对外部环境的感知

Ξ基金项目 国家 计划资助项目 收稿日期和理解 需要创建环境地图 而环境地图的创建又需要精确的定位 因此 移动机器人的定位和地图创建是两个既矛盾又相关的过程 移动机器人即时定位与地图创建 ≥ ∏ ∏ ≥ 就是将二者合而为一 在进行地图创建的同时做位姿估计 即时定位与地图创建方法与地图表达形式密切相关 如基于栅格地图的≥ 等 基于环境特征的≥ 方法的基本思想是将移动机器人的位姿和环境特征坐标表达在一个状态向量之中 在机器人的走行过程中通过对环境特征的观测作最优准则的估计 因此 基于环境特征的移动机器人即时定位与地图创建的过程将分为以下三个步骤 基于外部感知的环境特征提取 递推形式的预测和更新算法 相应的数据相关技术 本文将从以上三个方面对移动机器人即时定位与地图创建技术的现状及新进展做综述性介绍

2特征提取(Φεατυρεεξτραχτιον)

移动机器人配备多种内部和外部传感器 内部传感器主要有里程计!陀螺仪等 外部传感器有视觉!激光!声纳!红外等 移动机器人融合内部传感器信息和外部环境特征信息进行精确定位和地图创建 外部传感器信息经过处理形成外部环境的几何特征 以长度!宽度!位置等参量表示 特征地图可以表示为 (φι ι , ,,,Μ),φι是环境特征,Μ是地图中的特征数 由于单目视觉系统不能提供环境特征的深度信息 无法表征环境特征的位置 因此移动机器人即时定位与地图创建中 主要通过声纳或激光传感器在 ⁄平面上的扫描信息 距离!角度!强度等 获得外部环境的轮廓特征及其位置信息 声纳传感器具有成本低!波束覆盖范围宽的特点 但角度分辨率低 不精确 且容易产生虚假和多重反射回波信号 增加特征匹配的难度 而激光传感器以其快速!扫描精度高!角分辨率高!方向性强等特点 得到了越来越多的应用 环境特征的选择和描述不追求细节 注重特征的鲁棒性和稳定性 主要采用室内环境标识的最小环境模型 提取能够反映大范围环境的结构化特征 如直线和线段!角!点!垂直线等 分别与墙!墙角!凸角!门等特征对应 特征提取的方法很多 对于直线和点特征主要采取哈夫变换方法 如加权哈夫变换法!直方图法≈ 等 基于声纳传感器的三角测量融合 × ∏ ∏ 算法也是一种常用的点特征提取方法 其核心思想是从机器人声纳测距波束在不同位置获得的周边测距信息中提取环境中固定物体产生的反射 在经过时间序列上的筛选和综合之后 机器人就可以有效跟踪环境中特征点相对自身的位置变化 不同特征的组合使用是一种新的特征描述方法 点!线!垂直线!视觉边缘!角!半平面等特征可以结合为不同的特征类 由绑定矩阵 联系在一起 这样单一特征就可以和一个特征类相匹配 近年来 基于多传感器融合的特征提取方法越来越受到人们的重视 来自不同传感器的环境信息可以为特征提取提供冗余信息 提高环境特征定位的精确性和特征识别的可靠性 对冗余信息的处理和应用需要进行不确定几何信息的系统描述并保证融合机制的一致性 如 视觉信息具有高的角解析度 从灰度图像提取的垂直线和视觉边缘与激光数据匹配可以有效地识别环境特征 剔除环境地图中的模糊特征 对于杂乱!不规则环境 对环境进行二维建模不能满足需要 提取环境的三维特征进行即时定位与地图创建是目前的研究方向 文献≈ 通过双目视觉获得环境特征的深度信息 提取三维环境特征 文献≈ 则通过三目视觉获得三维比例不变 2 √ 特征进行即时定位与地图创建

3即时定位与地图创建方法(ΣΛΑΜ)

3.1扩展Καλμαν滤波(ΕΚΦ)方法

扩展 滤波是移动机器人即时定位与地图创建中最重要的理论方法≈ 最早的应用是≥ 等人提出的随机地图创建 方法 随机地图将机器人的位姿向量和环境特征向量组织在一个高维状态向量之中 用扩展 滤波作最小均方差估计 即系统状态变量Ξ [ΞΤρ,ΞΤ ,ΞΤ ,,,ΞΤΝ]Τ,其中Ξρ [ξψΗ]表示机器人的位姿,Ξι [ξιψι]Τ表示环境特征的位置坐标.系统协方差矩阵如下:

ΠΚ|Κ=

ΠρρΠρ ,ΠρΝ

Π ρΠ ,Π Ν

σσωσ

ΠΝρΠΝ ,ΠΝΝ

其中,子阵Πρρ!Πρι!Πιι分别表示机器人与机器人!机器人与环境特征!环境特征与环境特征之间的协方差矩阵.移动机器人通过外部传感器观测环境特征,用∞ ƒ估计状态变量Ξ和协方差矩阵ΠΚ Κ.随机地图的创建有两个步骤:预测和更新,如图 所示.

机器人的控制信号或里程计的信息输入到系统状态方程之中,完成对位姿和地图特征的预测;而对

第 卷第 期迟健男等 移动机器人即时定位与地图创建问题研究环境特征的观测和提取,则用来更新位姿和特征地图.更新包括新特征的增加!消失特征的删除!重复观察特征的更新.预测与更新之间.要进行特征匹配或数据相关,只有匹配特征才能用来更新位姿和特征地图.应用∞ ƒ进行即时定位与地图创建,所面临的最主要问题是定位的实时性问题,即位姿与环境特征更新过程中,计算协方差矩阵产生的Ο(Ν )的计算复杂性.就是所谓环境规模问题( 2 ∏ 机器人走行过程中 位姿和基于外部传感器信息的环境特征均具有不确定性 用不确定的位姿去更新特征地图和用不确定的环境特征去更新位姿 它们的相关性度量是必须的 且机器人与环境特征之间的相关性不能传播 即使在保持完整的协方差矩阵的情况下 也会造成地图的不连贯 因此机器人与环境特征!环境特征与环境特征之间的交叉相关性 2 导致了计算的复杂化 针对交叉相关问题主要有两种解决方法 其一 采用相对地图 √ 代替绝对地图 ∏ 表述环境特征的位置信息≈ 采用相对地图对环境建模 系统的状态变量不是环境特征相对公共坐标系的位置坐标 而是两特征之间的相对位置 相对地图解决了环境特征之间的相关问题 同时将环境地图创建和机器人定位分解开来 地图创建误差和机器人定位误差也是互相的 但它的缺点是地图创建缺乏连贯性 没有一个确定统一的方法由相对地图向绝对地图转换 机器人只能工作在一种相对的框架中 ≈ 发展了相对地图的思想 形成几何投影滤波 解决了地图创建连贯性问题 其二 应用扩展信息滤波 扩展信息滤波是扩展 滤波的另一种形式 用信息矩阵取代协方差矩阵 滤波是一种递推形式的以最小均方误差为准则的后验估计理论 写成贝叶斯定理形式

Π(Ξτ|Ζτ,Υτ)Ω ¬ −

(Ξτ−Λτ)ΤΕ− τ(Ξτ−Λτ)

( )

式( )中,Λτ是状态向量的均值向量,Ετ是协方差

矩阵.则信息矩阵和信息向量分别定义为Ητ Ε τ,βτ ΛΤτΕ τ 信息矩阵中的元素同样表示机器人!环

境特征之间的相关性 与协方差矩阵是等价的 但

信息矩阵中的元素体现了一种稀疏化的特点 只有

小部分元素值较大 而这些元素体现了相邻特征的

相关性 而且距离越近 值越大 其它元素的值接近

零 ≥ ≈ 等人研究了机器人!环境特征之间的

相关性 将信息矩阵中数值较小的元素删除 并补偿丢失信息 使信息矩阵进一步稀疏化 形成所谓稀疏扩展信息滤波方法≥∞ ƒ ≥ ∞¬

ƒ 使用≥∞ ƒ方法 可使更新时间为常数 并且不随地图增大及特征增加而变化

图 基于环境特征的移动机器人即时定位

与地图创建图

ƒ ≥ ∏ 2 ∏ ∏

3.2Παρτιχλε滤波方法

移动机器人定位是对不确定信息的处理 这种不确定因素主要有 机器人对外部感知能力的 外部环境的扰动 机器人内部传感器的误差 系统噪声和观测噪声的任何模型和假设都有局限性 且复杂的概率模型影响决策的实时性 ° 滤波以样本集合的方法逼近概率分布 当样本数Νψ]时可以逼近任何形式的概率分布≈ 因此 ° 2 滤波能够比较精确地表达基于观测量和控制量的后验概率分布 ° 滤波是针对离散时间!部分能观!能控 √链的后验概率估计方法 目前主要应用在室外大环境下的即时定位与地图创建 π(ξτ υτ,ξτ )是系统的运动模型,π(ζτ ξτ)是系统的观测模型.通过观测量ζτ ζ ,,,ζτ,控制量υτ υ , ,,υτ恢复系统的后验概率分布,通常应用递推形式 滤波算法:

π(ξτ|Ζτ,υτ)= #π(ζτ|ξτ)Θπ(ξτ|υτ,ξτ− )≅

π(ξτ− |ζτ− ,υτ− )δξτ− ( )° 滤波易于实现 不需要线性化非线性模型 但对于高维状态空间 样本数很大 需要高的运算速度 对计算机硬件的要求高 因此° 滤波常用于全局定位问题 ≤ 定位 ° 滤波在移动机器人即时定位与地图创建中属于高维应用 主要针对室外非结构化环境 称为 2 2 滤波 与 滤波相比 2 滤波在以下三个方面具有优越性 2 2 滤波的计算量是Ο(Ν Κ),Ν是样本数 实践证明 在一定的不确定范围内 Ν是常数 2 滤波可以处理后验概率为非高斯!

机器人 年 月多模型分布的情况 可更充分地利用观测数据 处理否定信息 √ 而在这种情况下 ∞ ƒ将导致数据相关的失败 应用 2 2 滤波处理数据相关问题具有较强的鲁棒性 ° 滤波在ƒ ≥ 中的应用类似于 ≤ 定位 ƒ ≥ 算法≈ 把≥ 问题分解为定位问题和一系列基于位姿估计的自然路标 环境特征 估计问题 将° 滤波和 滤波结合起来 用° 滤波做整个路径的位姿估计 滤波则用来估计环境特征位置 每一个 滤波对应一个环境特征 其状态变量为二维 这样ƒ 2≥ 算法的计算时间为Ο(ΝΚ 采用树状的数据结构 计算时间可减少为Ο(Ν Κ 优于扩展 滤波

3 3基于地图结构方法

在大范围室内环境下 应用单一的滤波算法会导致计算量增大 人们尝试使用分解地图的方法解决上述问题 具有代表性的方法有两个 分解随机地图方法≈ ⁄≥ 和合成地图方法 × ≈

3.3.1分解随机地图(ΔΣΜ)方法

⁄≥ 方法≈ 的思想是在全局的参考框架之内 将环境分解为多个互相重叠的子地图区域 运用不同子地图间的重定位和状态更新方法 来完成机器人状态信息在不同子地图之间的转换 地图分割的目的是为了压缩存储空间和提高定位的实时性 各子地图之间是互相的 局部地图之间的相互关系由全局坐标确定 机器人通过观测子地图区域内的环境特征进行定位和子地图创建 在子地图内保持完整的相关信息 地图的分割策略注重子地图创建的实效性和准确性 基于栅格结构的子地图划分将全局地图分割为大小固定的区域 每一部分覆盖全局地图的一定区域 但是当机器人在某些子地图的分界线附近行走时 容易造成特征重叠和频繁的地图转换 按照环境的结构划分子地图区域的方法可以避免上述缺陷 如按照房间和走廊划分地图区域 而门则是两个子地图的转换接口 分解随机地图方法的关键问题是在地图之间的转换过程中保持误差估计的一致性和全局误差的收敛性 局部地图之间的转换主要有两种情况 从已存在的子地图区域向新的地图区域转换 在两个已经存在的子地图区域之间转换 这其中存在地图创建先后之分 当机器人从一个地图区域到另一个地图区域的走行过程中 要利用两地图区域内的相邻特征进行重新定位和协方差矩阵的更新转换 控制转换过程中误差的传播和增加 保持误差估计的一致性以及不增加全局的不确定性 应用⁄≥ 方法可使定位与地图创建时间为常数

3.3.2合成地图(ΗΜΤ)方法

拓扑地图和特征地图称之为合成地图 拓扑地图具有全局连贯性好!鲁棒性强的特点 适合于描述环境的结构化特点 但定位空间离散!定位不精确!对拓扑节点依赖性强 特征地图对环境的描述比较精确 但存在航位推算累计误差大!全局地图不连贯等缺点 将拓扑地图与特征地图结合起来对环境建模≈ 可以很好地解决大范围!动态环境下的定位问题 既能保证局部定位的精度 又能保证全局的一致性 如图 所示

图 合成地图方法示意图

ƒ ≥ 2

在某些局部区域 采用环境特征地图 与拓扑节点相连 由拓扑地图将特征地图连接起来 构成全局地图 由拓扑地图到特征地图的转换 通过可探测到的局部地图特征实现 此特征用来确定转换点和初始化局部特征地图 同时作为特征地图在全局地图中的标识 反过来 这个特征也是移动机器人由特征地图进入拓扑地图的标识点 在大范围环境的导航中 某些执行任务的目标区域需要精确的定位和地图 而在其它走行区域 全局定位的连贯性和鲁棒性更为重要 利用拓扑地图和特征地图互补的特点 可以很好地解决这个问题

4数据相关(Δαταασσοχιατιον)

数据相关是指不同时刻对环境的观测是否来源于同一特征 数据相关与采用的理论方法及传感器模型有关 在通常的≥ 算法中 观测量要与系统状态变量匹配 以确定更新目标 成功的数据相关涉及正确的观测与相应的状态变量匹配!探测和排除虚假观测以及初始化新的轨迹 数据相关是数据融合的关键技术 方法很多 在移动机器人即时定位与地图创建中 大多数方法都是基于更新序列和预测协方差矩阵 更新序列定义为观测值与基于观测模

第 卷第 期迟健男等 移动机器人即时定位与地图创建问题研究型的状态变量预测值之差 ϖκ ζκ ⊥ζκ,则标准距离定义为δ κ ϖΤκΣ Κϖκ,其中ΣΚ为更新协方差矩阵.如果更新序列符合高斯分布,则ϖΤκϖκ将是ς 分布的;当观测值落入ς 分布的某个固定的区间时,作为可接受观测值,否则予以排除.即根据ς 分布确定的可接受区间,得出确认门限,与根据公式δ κ ϖΤΣ Κϖκ得出的标准距离比较,确定观测值是否可以接受.然后根据最近邻滤波 ∏ ƒ 方法筛选出距离最近的特征作为更新特征

5结论(Χονχλυσιον)

移动机器人即时定位与地图创建将定位与地图创建合而为一 为机器人导航奠定基础 本文比较全面详细地论述了该领域的主要理论方法及相关技术的现状和最新进展 国外学者在这方面做了大量的研究工作 近年来 随着计算机技术!传感器技术的发展 移动机器人的定位技术取得了较大的进展 针对的环境也从静态的结构化室内环境向非结构化室内环境和自然环境延伸 综合近年来的相关文献 以下几个方面将是今后研究的热点

基于多传感器融合的特征提取方法 特别是应用双目和三目视觉的 ⁄空间的特征提取 对于复杂的!大范围环境和室外非结构化环境的即时定位与地图创建 主要解决减少计算量!增强定位实时性的问题

实际应用环境中的数据相关问题

针对此类问题的新的理论方法

参考文献(Ρεφερενχεσ)

≈ ° ≤ ∏ ∏ √ ≈ ° ∞∞∞ ≥ 2 ∏ ∏ ≈≤ ¬

≈ ⁄ √ ∏ ∏ ⁄ ∏ ∏ ∏ ∏ √ √ √ ∏ ∏ ≈ ° 2 ∞∞∞ ≤ ≤ ∏ ∂ ≈≤ 1 ≈ ≥ ≥ ⁄ ∂ 2 2 ∏ 2 √ ∏ ≈ ° ∞∞∞ 2 ≤ ∏ ≈≤

≈ ⁄∏ 2• ƒ ⁄ ∏ ∏ ∏ ≈ ∏ 11

≈ ∏ ° ≤ ≥ ∏ ∏ √ ≈ ° ≥ ∏ ≈≤

≈ × ∏ ≥ ƒ ≥ ∏ ∏ 2 ∏ ≈ ° ∞ ≤ ≈≤ ∞ °

≈ ∏≥ ∏⁄⁄ ∏ 2 √ ∏ ∏ ≈ ∞∞∞ ≤ ∞ × 2 ƒ ∏ ≈≤ ≥

≈ ⁄∏ 2• ƒ ⁄ ≥ ≥ √ ≈ ∏ °∏

≈ × ∏ ≥ ° ≈ ° ≈≤ ≥ ƒ ∏ °∏

≈ ƒ ≥ ≥ ∏ ∏ ≈⁄ ≥ ×

≈ × ≥ ≤ ∏ ∏ ∏ ∏ ≈ ° 2 ƒ ∏ ∞∏ • √ ≈≤ ≥

≈ ⁄ ∏

2 ∏ ≈ °

≥ ∏ ≈≤ ≥ 2√

≈ ° ≥ ∏ ∏ ≥ ∏ ≥ ∏ ∏ 2 ° ≈⁄ ∏ × √ ≥

作者简介

迟健男 2 男 博士研究生 研究领域 数据融合 移动机器人定位技术等

徐心和 2 男 教授 博士生导师 研究领域 智能机器人 计算机视觉 模式识别等

机器人 年 月下载本文