移动机器人同时定位与地图创建研究进展



卷第 期 年 月
2 2 2

机器人

×

?

文章编号

移动机器人同时定位与地图创建研究进展
罗荣华 洪炳
哈尔滨工业大学计算机科学与技术学院 黑龙江 哈尔滨

Ξ

摘 出≥ 了≥

要 对移动机器人的同时定位与地图创建 ≥ ∏ 面临的问题 介绍了 ≥ 的复杂度 !提高 ≥ 的研究与发展方向



的最新研究进行了综述 指 实现方法的性能对比 详尽地分析了 也进行了论述 探讨

的基本实现方法 通过对各种改进的 ≥

如何降低 ≥

的鲁棒性等关键技术问题 同时对多机器人协作的 ≥

关键词 同时定位与地图创建 移动机器人 自主导航 地图创建 中图分类号
×°

文献标识码

Τηε Π ρογρε σ οφ Σιμ υλ σ τανεουσ Λοχα ιζατιον ανδ Μαππινγ φορ Μοβι ε Ροβοτ λ λ
2 ∏ 2
, Χ ηινα)

( Σχηοολ οφ Χ ομπυτερ Σχ ιενχε ανδ Τεχηνολ ογψ , Ηαρ Ινσ ιτυτε οφ Τεχηνολ βιν τ ογψ , Ηαρ βιν

Αβσ τραχτ : × ∏ √ ∏ √ Κεψωορδσ : ∏

∏√ √ ∏ 2 ∏ ∏ √

∏ ≥ ∏

∏ ∏ ∏ ∏ ∏ ∏ √ ∏ ∏

≥ ≥ ∏ ∏ ∏ ∏ √



2 2 ∏2 ∏ 2

1

引言(Ιντροδυχτιον)
移动机器人的定位和地图创建是机器人领域的

标志之间的相对位置和里程计的读数估计机器人和 特征标志的全局坐标 这种在线的定位与地图创建 需要保持机器人与特征标志之间的详细信息 近几 年来 ≥ 境≈ 的研究取得了很大的进展 并已应用于 各种不同的环境 如 室内环境≈ !水下≈ !室外环

热点研究问题 对于已知环境中的机器人自主定位 和已知机器人位置的地图创建已经有了一些实用的 解决方法 然而在很多环境中机器人不能利用全局 定位系统进行定位 而且事先获取机器人工作环境 的地图很困难 甚至是不可能的 这时机器人需要在 自身位置不确定的条件下 在完全未知环境中创建 地图 同时利用地图进行自主定位和导航 这就是移 动机器人的同时定位与地图创建 ≥ 也称为 ≤ ≤ ∏ 先是由 ≥


2
2 .1

ΣΛΑ Μ 存在的问题 (Π ροβλ σ οφ ΣΛΑ Μ) εμ
超多维问题

ι

问题 ≥ 最

需要计算机器人的位姿 ρ 和环境中的特
, , , ν) 的位置 , 在

征标志 μ (ι

维空间中机器人

和≤ 提出来的≈ 由于其 重要的理论与应用价值 被很多学者认为是实现真


的位姿 ρ ( ξρ , ψ , Η Τ 包括 个变量 , 由机器人的平 ) ρ 面坐标( ξρ , ψ ) 和机器人的朝向 Η 组成 , 特征标记 ι ρ
ι 的位置 μ ι ( ξιμ , ψμ ) Τ 包括两个变量 .如果地图中有

正全自主移动机器人的关键 在≥

中 机器人利用自身携带的传感器识

ν 个标志 , 那么就有

ν

个变量 , 每一个变量是状 的状态是一个 ν 维的矢

别未知环境中的特征标志 然后根据机器人与特征
Ξ 基金项目 国家 收稿日期

态估计中的一维 ,≥

计划资助项目



卷第



罗荣华等

移动机器人同时定位与地图创建研究进展

量 . 而对实际环境进行描述可能需要上千甚至上万 个特征标志 , 因此 ≥
2 2

是一个超多维问题

包括系统状态预测和更新两步 曼滤波器的 ≥ 同时还需要进行地图信息的管理 如 新特征标志的 加入与特征标志的删除等 卡尔曼滤波器假设系统是线性系统 但是实际 中机器人的运动模型与观测模型是非线性的 因此 通常采用扩展卡尔曼滤波器 ∞? ? 2 扩展卡尔曼滤波器通过一阶泰勒展开来近似表 示非线性模型 另一种适用于非线性模型的卡尔曼 滤波器是
? ? ? 采用条

数据关联 数据关联是对两个特征标志进行匹配 确定它

中的数据关联 们是否对应环境中的同一物体 ≥ 主要需要完成三个任务 新特征标志的检测 !特征标 志的匹配以及地图之间的匹配 虽然在目标跟踪 !传 感融合等领域 数据关联已经得到较好的解决 但是 的实时性要 这些方法的计算量大 不能满足 ≥ 求 . 实现 μ 个标志与拥有 ν 个标志的地图之间的数 据关联的复杂度与 μ 之间呈指数关系 , 假设每个观 测到的标志 ι 有 νι 个可能的匹配 , 那么对于 μ 个标 志需要在指数空间
Φιμ νι 中搜索正确的匹配 . 数据

件高斯分布来近似后验概率分布 与 ∞ ? 相比 ? ≈ 的线性化精度更高 而且不需要计算雅可比矩阵 法
≈ ?

卡尔曼滤波器已经成为实现 ≥ 的基本方 其协方差矩阵包含了机器人的位置和地图

关联的搜索空间与环境的复杂程度以及机器人的定 位误差有关 , 环境的复杂程度的增加会使 μ 增大 , 而误差的增大会使 νι 增大 .
2 3

的不确定信息 当机器人连续地观测环境中的特征 标志时 协方差矩阵的任何子矩阵的行列式呈单调 递减 从理论上讲 当观测次数趋向于无穷时 每个 特征标志的协方差只与机器人起始位置的协方差有 关≈ 卡尔曼滤波器的时间复杂度是 Ο( ν ) 由于每 一时刻机器人只能观测到少数的几个特征标志 基 的时间复杂度可以优化为 于卡尔曼滤波器的 ≥ Ο( ν ) , ν 表示地图中的特征标志数 . 3 .2 低复杂度的实现方法 基于卡尔曼滤波器的 ≥ 的计算量主要来源 于系统协方差矩阵的更新 即维持机器人与特征标 志之间以及各特征标志之间的相关关系 这些相关 关系对于 ≥ 算法的收敛性十分重要 研究表明 忽略这些相关关系不能保证地图的一致性 使创建 的地图失去意义≈ 为了降低 ≥ 的时间复杂度 需要在不影响地图一致性的条件下限制这些相关关 系
3 2 1

累积误差


中的误差主要来自三个方面 观测误差 !

里程计的误差和错误的数据关联带来的误差 当机 器人在已知地图的环境中进行定位时 机器人可以 通过观测位置已知的特征标志对里程计的误差进行 补偿 每一次观测使机器人的位置误差趋向于观测 中 误差与特征标志的位置误差之和 然而在 ≥ 由于机器人的位置和环境中的特征标志的位置都是 未知的 观测信息不能有效纠正里程计的误差 机器 人的位置误差随着机器人的运动距离而增大 而机 器人的位置误差的增大将导致错误的数据关联 从 而增大特征标志的位置误差 反过来 特征标志的误 差又将增大机器人的位置误差 因此 机器人的位置 误差与特征标志的位置误差密切相关 它们之间的 相互影响使机器人和特征标志的位置估计产生累计 误差 难以保证地图的一致性

局部子地图法

3

ΣΛΑ Μ 的 实 现 方 法 ( Με τηοδσ φορ ιμ πλ 2 ε μ εντατιον οφ ΣΛΑ Μ)

分解为一 局部子地图法从空间的角度将 ≥ 些较小的子问题 子地图法中主要需要考虑以下几 个问题 如何划分子地图 如何表示子地图间的相互 关系 如何将子地图的信息传递给全局地图以及能 否保证全局地图的一致性 最简单局部子地图方法是不考虑各子地图之间 的相互关系 将全局地图划分为包括固定特征标志 这 数的独立子地图 在各子地图中分别实现 ≥ 种方法的时间复杂度为 Ο 但是 由于丢失了表 示不同子地图之间相关关系的有用信息 这种方法 不能保证地图的全局一致性 对此 等人提


3 .1 基于卡尔曼滤波器的实现方法

是一个滤波问题 也 从统计学的观点看 ≥ 就是根据系统的初始状态和从 到 τ 时刻的观测信 息与控制信息 里程计的读数 估计系统的当前状 态 在≥ 中 系统的状态 ξτ [ ρ μ ] , 由机器人 τ 的位姿 ρ 和地图信息 μ 组成 (包含各特征标志的位
Τ

置信息) . 假设系统的运动模型和观测模型是带高斯 噪声的线性模型 , 系统的状态 ξτ 服从高斯分布 那 可以采用卡尔曼滤波器来实现 基于卡尔 么≥

方法 出了 ?≥ ? ∏ ≥ ?≥ 中各子地图分别保存自己的机器人位置估计 当机











器人从一个子地图

进入另一个子地图

时 采用

关系进行局部更新 这种局部更新使得信息矩阵近 似于稀疏矩阵 对其进行稀疏化产生的误差很小 根 据这一点 ≥ × ∏ 等人提出了一种基于稀疏信息滤 的≥ 波器 ≥∞ ? ≥ ∞? ? 方法 并证明利用稀疏的信息矩阵实现 ≥ 的时 间复杂度是 Ο ≈ 虽然 ∞ ? 可以有效降低 ≥ 的时间复杂度 但

基于 ∞ ? 的方法来将子地图 中的信息传送给子 等人提出了一种基于 ≤ ≥? ≤ 2 地图 ? 的≥ 方法≈ ≥∏ ? ≤ ≥? 在地图中创建全局坐标已知的子地图 机器人前进 过程中只利用观测信息更新机器人和局部子地图中 的特征标志的位置 并且按一定的时间间隔把局部 子地图信息传送给全局地图 虽然实验表明这两种 算法具有很好的性能 但是没有从理论上证明它们 能够保持地图的一致性 没有任何信息丢失的 ≥
∞? ? ∏√

是在地图信息的表示和管理方面还存在一些问题 首先 在常数时间内只能近似算得系统状态的均值 其次 在基于 ∞ ? 的 ≥ 不方便 3 2 3 分解法
° ?

等人提出了一种

方法中 特征标志的增删

优化算法 ≤∞ ? ≤ 2 ≈ ≤∞ ? 将已经观测 两部分 表示与机器人

到的特征标志分为 在活动子地图



等人提出了一种基于粒子滤波器 的 ? ≥ 方法≈ 将 ? ≥ 分解为机器人定位和特征标志的位置估计两 ≥ 个过程 粒子滤波器中的每个粒子代表机器人的一 条可能运动路径 利用观测信息计算每个粒子的权 重 以评价每条路径的好坏 对于每个粒子来说 机 器人的运动路径是确定的 因此特征标志之间相互 独立 特征标志的观测信息只与机器人的位姿有关 每个粒子可以采用 ν 个卡尔曼滤波器分别估计地图 中 ν 个特征的位置 . 假设需要 κ 个粒子实现 ≥ 总共有 κν 个卡尔曼滤波器 ? ≥ 的 时间复杂度为 Ο( κν) 通过利用树型的数据结构进 行优 化 其 时 间 复 杂 度 可 以 达 到 Ο( κ ν ? 2 方法的另一个主要优点是通过采用粒子滤波 ≥ 器估计机器人的位姿 可以很好地表示机器人的非 线性 !非高斯运动模型
3 3 ? ≥

当前位置相邻的区域 被称为活动子地图 当机器人 中运动时 利用观测信息实时更新 并采用递归的方法记录 机器人的位置与子地图 观测信息对子地图 的影响 当机器人离开活动子 地图 时 将观测信息无损失地传送给子地图 一 次性地实现子地图 的更新 同时创建新的活动子

地图 该方法的计算时间由两部分组成 活动子地图 其时间复杂度为 Ο( ν α) , να 是活动子地 中的 ≥ 图 中特征标志的数目 子地图 的更新 , 其时间复 杂度为 Ο( να ? ν β ) , νβ 是地图 中特征标志的数 目 当子地图合并的时间间隔较大时 ≤∞ ? 能有效 减少 ≥
3 2 2

的计算量

去相关法 降低 ≥ 复杂度的另一种方法是将表示相关 然而这也会因信息的丢

关系的协方差矩阵中一些取值较小的元素忽略掉 使其变为一个稀疏矩阵≈ 失而使地图失去一致性 但是 如果能改变协方差矩 阵的表示方式 使其中的很多的元素接近于零或等 于零 那么就可以将其安全地忽略了 基于扩展信息滤波器 ∞ ? ∞? 的≥ 就是出于这一思想 ∞ ? 是 ∞ ? 的基 ? 于信息的表达形式 它们的区别在于表示信息的形 式不 一 样 ∞ ? 采 用 协 方 差 矩 阵 的 逆 矩 阵 来 表 征 中的不确定信息 并称之为信息矩阵 两个不 ≥ 相关的信息矩阵的融合可以简单地表示为两个矩阵 相加 信息矩阵中每个非对角线上的元素表示机器 人与特征标志之间或特征标志与特征标志之间的一 种约束关系 这些约束关系可以通过系统状态的信 息矩阵与新的观测信息矩阵的相加而进行更新 由 于观测信息只包括机器人与当前观测到的特征标志 之间的约束关系 因此两个信息矩阵相加只对约束

鲁棒的实现方法 如何提高 ≥ 方法的适应能力 使其适用于

需要考虑的另一个重要 现实中的复杂环境是 ≥ 的鲁棒性主要从以下几个方面进 问题 提高 ≥ 行
3 3 1

降低观测信息的不确定性 但是距离传感器获取的信

目前 大多数研究者都采用声纳和激光雷达等 距离传感器来实现 ≥ 息量少 分辨率也相对较低 在复杂的环境中 由于 的准确性 传感器的观测数据的高度不确定性 ≥ 和可靠性显著降低 为了解决这一问题可以采用分 辨率高的视觉传感器≈ 或者多传感器信息融合≈ 利用视觉信息进行 ≥ 还需要解决很多相关的技 术问题 最主要的是信息的处理量和计算时间问题 多传感器信息融合是提高 ≥ 可靠性的有效方 通过将视觉与距离传感器结合 可以对图像信息 法



卷第



罗荣华等

移动机器人同时定位与地图创建研究进展

与距离信息进行综合处理 从而充分利用它们之间 的冗余和互余信息
3 3 2

3 4

基于多机器人协作的 ΣΛΑ Μ 一些研究者对基于多机器人协作的同时定位与
≤ √ ≥ ∏
≈ ?

改进地图表示方法

地图创建 ≤≥



机器人领域的地图表示方法主要有 栅格表示 法 !特征表示法和拓扑图表示法 基于栅格的地图表 示方法将地图划分成一些大小相等的栅格 便于表 示环境中的障碍物 有益于机器人的自主导航 但是 随着栅格的增多需要大量的存储空间和计算时间 基于特征的表示方法利用稀疏的几何特征来描述环 境 表示更为紧凑 拓扑图法采用一些关键的节点以 及它们之间的相互关系来描述环境 不需要维持地 图的全局一致性 但是当环境中的特征很相似时 拓 扑图表示法不能将它们区分开 而且定位精度较低 在≥ 中为了减少计算量与存储空间 一般采用 基于特征的表示方法和基于拓扑图的表示法 但是 在复杂大环境中单纯采用特征表示法 难以保证地 图的全局一致性 而单纯采用拓扑图表示法又难以 实现精确定位 近来 采用特征表示与拓扑图表示相 结合的方法取得了较好的效果 这种方法集成了两 种表示法的优点 只需要保证局部地图的一致性 可 以降低系统的累积误差≈ 3 3 3 鲁棒的数据关联 中的一个难 如第 节所述 数据关联是 ≥ 中通常采用最邻近法 进行数据关联 题 ≥ 这种方法的突出特点是其时间复杂度为 Ο( μν)( μ 是要进行匹配的特征标志的数目 , ν 是地图中的特 征标志的数目 但是最邻近法没有考虑相邻特征标 志之间的相关关系 只适用于比较简单的环境 对 此 文献≈ 中提出了一种联合数据关联法 他们把 环境中的一些相关的特征联合在一起形成有意义的 环境标志 如门 !墙角等 然后再进行数据关联 文献 将数据关联视为图的匹配问题 通过求取最大 ≈ 公共子图来实现特征标志的匹配
3 3 4

进行了探讨和研究

与单机器人

相比 通过机器人之间的相互协调与合作以及信息 可以提高地图创建的效率和提高定位 共享 ≤≥ 与地图的精度
≤≥

按照地图的存储与处理方式的不同可以

分为两大类型 集中式 ≤≥ 和分布式 ≤≥ 在 中 存在一个中央处理模块 每个机 集中式 ≤≥ 器人分别在自己所在的局部地图中进行定位与地图 创建 然后利用无线通信装置将在局部地图中获得 的信息传送给中央模块≈ 这种方法通过子地图的 匹配 可以充分利用子地图间的冗余信息提高定位 与地图创建的精度 但是 当机器人数量增加时中央 模块的计算量会显著增大 而且集中式的信息传递 需要很大的带宽 系统的可靠性也比较低 一旦中央 模块出现故障 整个系统都会陷入瘫痪状态 在分布 中 不存在中央模块 每个机器人都拥有 式 ≤≥ 自己的全局地图 在每一时刻机器人把来自其他相 邻机器人的信息和自己的观测信息融合到自己的全 局地图中 然后以点对点的方式将新的信息传送给 其他机器人 每个机器人只能获得与其相邻的机器 人的位置信息 不知道整个系统的拓扑结构 这种方 法与分布式的信息融合十分相似 可以利用信息滤 波器来实现≈ 由于两个不相关信息矩阵的信息融 可以避免复杂的计算 合可以通过两个矩阵的相加而实现 所以利用信息 滤波器实现分布式 ≤≥

4


结论(Χονχλυσ ιον)
综上 所 述 近 几 年 来 机 器 人 领 域 的 研 究 者 对 进行了大量的研究 特别是在降低计算复杂

度 !提高鲁棒性等方面取得了很大的进展 但是在以 下几个方面还需要更进一步研究 的应用环境 目前 ≥ 还局限于 维静态环境中的研究与应用 而现实中的环境通常 是动态的 维环境 将 ≥ 的研究与应用扩展到 维动态环境以及 维动态环境具有重要的意义 更有效的 ≥ 实现方法 ≥ 的各种实现方 的研 法都不是很完善 基于多机器人协作的 ≥ 究还刚刚起步 可以将人工智能 !智能控制等领域的 方法引入到 ≥ 中 开发更有效的 ≥ 算法 更好的地图表达方式 开发其他更好的地图表 示方式 特别是复杂地形中的地图表达方式是 ≥ 扩展 ≥

主动 ΣΛΑ Μ

在一些没有明显特征或者特征的可分辨性很低 的环境中 即使是人进行自我定位 创建地图也很困 难 这时 人通常采用主动的方法 如做标记 !主动地 探索有用的特征 近几年来 提高机器人的主动性在 机器人领域受到了广泛的关注 并在很多方面做到 了很好的应用 如主动视觉 主动定位等 有关主动 同时定位与地图创建的研究还不多 文献 ≈ 对基 进行了研究 文献 ≈ 利用信 于主动视觉的 ≥ 息论的方法控制机器人的运动以获得更有用的信 息






≤ ° × ∏ ≥ ∏ 2 2 ≈ ? √ ∏ √ √ ≤ ∏ ≥ ∏ ? ≥ ∏ ≈ ∏ ° ≈≤





中值得研究的问题 参考文献
≈ ≥ ≥ ≈ ≈≤ ≈ ≤ √ ≈ ? ∏ ∏ ≈ ?∏ ∏ 2? ∏ ? ≥ ∏ ≈ ∏ ° ≥ ≈≤ ≈ ∏ ∞∞∞ 2 2 ° ≈ ≥ ∏ ? ° ≥ ετ α λ ∏ ≈ ∞∞∞ × ∏ ∏ 2 ≈ ≤ ∏ ∏ × ∏ ≤ ° °

(Ρε φερενχε σ)
∞ ≤ 2 ∏ ≈? ? 2 ∏



∞∞∞

∏ ≈

??

≥ ∏

∏ °

2 ∏ 2

∞∞∞ ×

× ≈

?







2

∞∞∞ ×

∏ ∏ ∞∞∞ ≈≤

≥ ∏ 2 ≤



∏ ≈ ∏ 2

≈ ∏

?



∏ ≈ ° ≈≤ ≥

2

× ∏

∏ ∏ ∏ ∏ ≥ ? ? ≈





∏ ≈

≥ ? ≈ ∏√ ∏ ≥ ≈ ? ≈ ° ≈ ≤ √ ∞∞∞ ∞ ° ≈≤ × ∞



2 ≈ ×

∏ ∞∞∞ × ∏ 2

≥ ∏





√ ≈ ∏

∏ ≈ × √ √ ≥ ≥ 2 ≈ ≈ ° ∏ ≈≤ ≈ ? ? ? ≈ × ≤ ∞

? ≈ ∏ ° ≈≤ ∞∞∞ 2

×

∏ ∞∞∞ ≥ ≤ ? ≥ ∏

2





≤ ∏







° ≈ ° ∏ ≈≤ ?∏ ≈ ∏ 2? °



√ ∞∞∞





? ∞



?





∞∞∞

∏2 ≤ ≈ ? ∏ ≥ ∏ ≤ ∞∞∞ ≈ ∞ ∏ ≈ ∏ ° ?



? °



∞ ≈? ≥ ∞

≥ ∏ √

∏ ≥





2

? ×

∏ 2√ ∞∞∞ 2



∏√

∞ 2 ∏

∏ 2 ∏

∏ ≈

≈≤

× ≈ ∏ ≥ ∏ ≤ ≈ × ∏ ≥ ? ? ≥ × ∏ ≈ ∏ ∞ ∏ ≤ ∏ ∏ ≤ ≈

° ?∏ ∏ ∏

2?

≤ ∏ ≥ ≈≤ ∏ ≥

∏ ≥ ?∏ ≥ ≥° ∞

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

∏ ∞∞∞



2

ετ α ≥ ∏ λ

° ≤ ∏

作者简介
罗荣华
2 2

男 博士生 研究领域 机器人自主导航 男 教授 博士生导师 研究领域 空间机

× ∏ ≥

∏ ° ≈≤ ∞2

机器人视觉 多传感器信息融合 洪炳 器人 虚拟现实 足球机器人


相关文档

移动机器人的同步自定位与地图创建研究进展
移动机器人同步定位与地图构建研究进展
移动机器人同时定位与地图创建算法研究
基于粒子滤波器的移动机器人定位和地图创建研究进展
移动机器人即时定位与地图创建问题研究
移动机器人定位、地图创建及路径规划研究
移动机器人同时定位与地图创建自适应算法研究
基于全景视觉的移动机器人同步定位与地图创建研究
仪的移动机器人同时定位和地图创建
移动机器人的同时定位和地图创建方法
电脑版