·830· 智能系统学报 第13卷 图四、几何地图以及拓扑地图等。然而，地图 和粒子数的条件下获得可靠的估计，整体性能得 构建问题与定位问题紧密相关，定位的结果用于 到较大提高，能够精确估计出机器人的位姿并获 地图构建，而已经构建好的地图又能实现精确定 得高精度的地图。 位，因此同时定位与地图构建(SLAM例被提出并 受到广泛研究和应用。目前，SLAM技术大都基 1 RBPF-SLAM 于概率理论，比如卡尔曼滤波及扩展卡尔曼滤 移动机器人SLAM实质上是一个Markov链的 波、最大似然估计网、粒子滤波9和Markov定位o 过程：在一个未知环境中机器人从起始位置出发， 等。文献11]将UT和UKF运用到高斯项更新及 在运动过程中，使用里程计记录自身运动的信息 采样粒子权重计算过程中，提出一种无迹高斯混 (1=u1,2,…,山)和外部传感器获取的环境信息 合概率假设密度SLAM算法；文献[12]在雁群粒 (亿u=z1,z2,,z,估计机器人的轨迹(1u=x1,x2,…,x) 子群算法的基础上采用分数阶微积分和混沌思想 与构建增量式环境地图m,同时使用创建好的地 训练模糊自适应扩展卡尔曼滤波，从而实现同时 图及传感器的信息实现自定位。根据贝叶斯滤波 定位与地图创建；文献[I3]在基本SLAM算法的 递归原理，从概率学的角度得出SLAM的递归公 迭代过程中引入元胞自动机(CA),建立“SLAM- 式为 CA生长-重定位”的闭环作用机制。 Bel(x,m)=p(xmu)=np(m Rao-Blackwellized粒子滤波算法是目前解决 )-Bel(m SLAM问题的有效方法，它将SLAM问题分解成 机器人的位姿估计和地图估计，采用粒子滤波器 式中表示归一化常量。 和扩展卡尔曼滤波器估计概率，但仍存在算法运 SLAM中包含运动模型p(x,x-1,4-)与观测 模型p(z,x,m)两种模型。运动模型表示在给定上 行时间长，粒子退化严重等不足；此后很多改进 一时刻移动机器人轨迹x-1和控制命令u-1条件 的RBPF算法被提出，如文献[14]提出一种基于高 下，机器人获得新位姿x,的概率密度；而观测模型 斯分布的RBPF-SLAM算法，通过高斯分布分散 表示在给定移动机器人地图m与位姿x,的条件 高权重粒子获得新粒子，虽然算法能在粒子减少 下，传感器获取环境的不确定性。 的条件下保持可靠估计，但忽略对低权重粒子的 基于Rao-Blackwellized粒子滤波SLAM算法 考虑，抑制样本匮乏现象还存在不足；文献[15]提 的思想：计算机器人轨迹x和地图m的后验概率 出一种粒子群优化遗传重采样的改进RBPF-SLAM p(x1,mlz1a,1-1),将其分解为式(2)所示的轨迹估 算法，采用粒子群优化策略调整粒子集，并对权 计和地图估计两个后验概率乘积。 重较小的粒子进行变异操作，但粒子群的引入容 p(m)=p)p(m)(2) 易陷入局部最优，加上重采样中只针对权重较小 首先对机器人的轨迹进行估计，利用Rao- 粒子操作，对缓解粒子退化无法产生满意的效 Blackwellized粒子滤波器实现，其中每个粒子代 果。文献16]采用改进的提议分布并结合基于等 表机器人一条可能的行走轨迹。 级的自适应局部重采样(APRR)算法，设计了一 然后再结合观测模型对地图进行更新。将地 种基于退火参数优化混合提议分布的RBPF算 图表示为服从高斯分布的特征路标的集合，因此 法，对高权重和低权重粒子只进行复制操作，对 对地图的估计可通过特征路标估计得到，这里采 增加粒子多样性缓解粒子退化效果不佳。 用扩展卡尔曼滤波来实现。 考虑这些不足，本文从解决RBPF算法运行 因此，在粒子代表的轨迹上利用传感器实时 时间长、提议分布精度不高以及重采样过程的粒 观察获得的路标信息构成最后的地图。 子退化出发，将量子粒子群算法引入到Rao 利用Rao-Blackwellized滤波器在传感器观测 Blackwellized粒子滤波算法，提出一种QPSO- 信息与里程计信息基础下构建增量式地图的步骤 RBPF-SLAM算法，一方面在基本提议分布中加 可以分为4步： 入观测信息，使改进的提议分布更加接近真实状 1)初始化：当=0时，选取N个粒子，每个粒 态，另一方面在重采样中根据QPSO算法更新粒 子的权重为o。=1N。 子位姿，对高低权值粒子进行自适应交叉变异操 2)采样：机器人的运动模型作为提议分布π，从 作。QPSO-RBPF-SLAM保持了粒子的多样性，有 上一代粒子集合x2采样得到下一代粒子集合{x。 效缓解了粒子退化，同时算法能在减少运算时间 3)粒子权重：为了弥补采样时提议分布跟目图 [2] 、几何地图[3]以及拓扑地图[4]等。然而，地图 构建问题与定位问题紧密相关，定位的结果用于 地图构建，而已经构建好的地图又能实现精确定 位，因此同时定位与地图构建 (SLAM[5] ) 被提出并 受到广泛研究和应用。目前，SLAM 技术大都基 于概率理论，比如卡尔曼滤波[6]及扩展卡尔曼滤 波 [7] 、最大似然估计[8] 、粒子滤波[9]和 Markov 定位[10] 等。文献[11]将 UT 和 UKF 运用到高斯项更新及 采样粒子权重计算过程中，提出一种无迹高斯混 合概率假设密度 SLAM 算法；文献[12]在雁群粒 子群算法的基础上采用分数阶微积分和混沌思想 训练模糊自适应扩展卡尔曼滤波，从而实现同时 定位与地图创建；文献[13]在基本 SLAM 算法的 迭代过程中引入元胞自动机 (CA)，建立“SLAM￾CA 生长–重定位”的闭环作用机制。 Rao-Blackwellized 粒子滤波算法是目前解决 SLAM 问题的有效方法，它将 SLAM 问题分解成 机器人的位姿估计和地图估计，采用粒子滤波器 和扩展卡尔曼滤波器估计概率，但仍存在算法运 行时间长，粒子退化严重等不足；此后很多改进 的 RBPF 算法被提出，如文献[14]提出一种基于高 斯分布的 RBPF-SLAM 算法，通过高斯分布分散 高权重粒子获得新粒子，虽然算法能在粒子减少 的条件下保持可靠估计，但忽略对低权重粒子的 考虑，抑制样本匮乏现象还存在不足；文献[15]提 出一种粒子群优化遗传重采样的改进 RBPF-SLAM 算法，采用粒子群优化策略调整粒子集，并对权 重较小的粒子进行变异操作，但粒子群的引入容 易陷入局部最优，加上重采样中只针对权重较小 粒子操作，对缓解粒子退化无法产生满意的效 果。文献[16]采用改进的提议分布并结合基于等 级的自适应局部重采样 (APRR) 算法，设计了一 种基于退火参数优化混合提议分布的 RBPF 算 法，对高权重和低权重粒子只进行复制操作，对 增加粒子多样性缓解粒子退化效果不佳。 考虑这些不足，本文从解决 RBPF 算法运行 时间长、提议分布精度不高以及重采样过程的粒 子退化出发，将量子粒子群算法[17]引入到 Rao￾Blackwellized 粒子滤波算法，提出一种 QPSO￾RBPF-SLAM 算法，一方面在基本提议分布中加 入观测信息，使改进的提议分布更加接近真实状 态，另一方面在重采样中根据 QPSO 算法更新粒 子位姿，对高低权值粒子进行自适应交叉变异操 作。QPSO-RBPF-SLAM 保持了粒子的多样性，有 效缓解了粒子退化，同时算法能在减少运算时间 和粒子数的条件下获得可靠的估计，整体性能得 到较大提高，能够精确估计出机器人的位姿并获 得高精度的地图。 1 RBPF-SLAM u1:t = u1,u2,··· ,ut z1:t = z1,z2,···,zt x1:t = x1, x2,···, xt mt 移动机器人 SLAM 实质上是一个 Markov 链的 过程：在一个未知环境中机器人从起始位置出发， 在运动过程中，使用里程计记录自身运动的信息 ( ) 和外部传感器获取的环境信息 ( )，估计机器人的轨迹( ) 与构建增量式环境地图 ，同时使用创建好的地 图及传感器的信息实现自定位。根据贝叶斯滤波 递归原理，从概率学的角度得出 SLAM 的递归公 式为 Bel(xt , mt) = p(xt , mt |z1:t ,u1:t−1) = ηp(zt |xt " , mt )· p(xt , mt |xt−1 , mt−1 ,ut−1)·Bel(xt−1 , mt−1)dxt−1dmt−1 (1) 式中 η 表示归一化常量。 p(xt |xt−1 ,ut−1) p(zt |xt , m) xt−1 ut−1 xt xt SLAM 中包含运动模型 与观测 模型 两种模型。运动模型表示在给定上 一时刻移动机器人轨迹 和控制命令 条件 下，机器人获得新位姿 的概率密度；而观测模型 表示在给定移动机器人地图 m 与位姿 的条件 下，传感器获取环境的不确定性。 x1:t p(x1:t , m|z1:t ,u1:t−1) 基于 Rao-Blackwellized 粒子滤波 SLAM 算法 的思想：计算机器人轨迹 和地图 m 的后验概率 ，将其分解为式 (2) 所示的轨迹估 计和地图估计两个后验概率乘积。 p(x1:t , m|z1:t ,u1:t−1) = p(x1:t |z1:t ,u1:t−1)· p(m|x1:t ,z1:t ) (2) 首先对机器人的轨迹进行估计，利用 Rao￾Blackwellized 粒子滤波器实现，其中每个粒子代 表机器人一条可能的行走轨迹。 然后再结合观测模型对地图进行更新。将地 图表示为服从高斯分布的特征路标的集合，因此 对地图的估计可通过特征路标估计得到，这里采 用扩展卡尔曼滤波来实现。 因此，在粒子代表的轨迹上利用传感器实时 观察获得的路标信息构成最后的地图。 利用 Rao-Blackwellized 滤波器在传感器观测 信息与里程计信息基础下构建增量式地图的步骤 可以分为 4 步： ω (i) 0 = 1/N 1) 初始化：当 t=0 时，选取 N 个粒子，每个粒 子的权重为 。 π { x (i) t−1 } { x (i) t } 2) 采样：机器人的运动模型作为提议分布 ，从 上一代粒子集合 采样得到下一代粒子集合 。 3) 粒子权重：为了弥补采样时提议分布跟目 ·830· 智 能 系 统 学 报 第 13 卷