自主移动机器人的定位与地图创建（SLAM）关键性问题

F（Unscented Kalman Filter），UKF采用条件高斯分布来近似后验概率分布，与EKF相比，UKF的线性化精度更高，而且不需要计算雅可比矩阵。

卡尔曼滤波器已经成为实现SLAM的基本方法。其协方差矩阵包含了机器人的位置和地图的不确定信息。当机器人连续地观测环境中的特征标志时，协方差矩阵的任何子矩阵的行列式呈单调递减。从理论上讲，当观测次数趋向于无穷时，每个特征标志的协方差只与机器人起始位置的协方差有关。卡尔曼滤波器的时间复杂度是O( )，由于每一时刻机器人只能观测到少数的几个特征标志，基于卡尔曼滤波器的SLAM的时间复杂度可以优化为O( )，n表示地图中的特征标志数。

3.2局部子地图法
局部子地图法从空间的角度将SLAM分解为一些较小的子问题。子地图法中主要需要考虑以下几个问题：1）如何划分子地图2）如何表示子地图间的相互关系3）如何将子地图的信息传递给全局地图以及能否保证全局地图的一致性。

最简单局部子地图方法是不考虑各子地图之间的相互关系，将全局地图划分为包括固定特征标志数的独立子地图，在各子地图中分别实现SLAM，这种方法的时间复杂度为O(1)。但是，由于丢失了表示不同子地图之间相关关系的有用信息，这种方法不能保证地图的全局一致性。
对此，Leonard 等人提出了DSM（DecoupledStochasTIc Mapping）方法，DSM中各子地图分别保存自己的机器人位置估计，当机器人从一个子地图A进入另一个子地图B时，采用基于EKF的方法来将子地图A中的信息传送给子地图B；B.Williams等人提出了一种基于CLSF（ConstrainedLocal Submap Filter）的SLAM方法，CLSF在地图中创建全局坐标已知的子地图，机器人前进过程中只利用观测信息更新机器人和局部子地图中的特征标志的位置，并且按一定的时间间隔把局部子地图信息传送给全局地图。虽然实验表明这两种算法具有很好的性能，但是没有从理论上证明它们能够保持地图的一致性。J.Guivant等人提出了一种没有任何信息丢失的SLAM优化算法CEKF(CompressedExtended Kalman Filter)。CEKF将已经观测到的特征标志分为A与B部分，A表示与机器人当前位置相邻的区域，被称为活动子地图。当机器人在活动子地图A中运动时，利用观测信息实时更新机器人的位置与子地图A，并采用递归的方法记录观测信息对子地图B的影响；当机器人离开活动子地图A时，将观测信息无损失地传送给子地图B，一次性地实现子地图B的更新，同时创建新的活动子地图。该方法的计算时间由两部分组成：活动子地图中的SLAM，其时间复杂度为O( )， 是活动子地图A中特征标志的数目；子地图B的更新，其时间复杂度为O( ) ， 是地图B中特征标志的数目。当子地图合并的时间间隔较大时，CEKF能有效减少SLAM的计算量。

3.3去相关法
降低SLAM复杂度的另一种方法是将表示相关关系的协方差矩阵中一些取值较小的元素忽略掉，使其变为一个稀疏矩阵。然而这也会因信息的丢失而使地图失去一致性。但是，如果能改变协方差矩阵的表示方式，使其中的很多的元素接近于零或等于零，那么就可以将其安全地忽略了。基于扩展信息滤波器EIF（ExtendedInformaTIon Filter）的SLAM就是出于这一思想。EIF EKF的基于信息的表达形式，它们的区别在于表示信息的形式不一样。EIF采用协方差矩阵的逆矩阵来表征SLAM中的不确定信息，并称之为信息矩阵。两个不相关的信息矩阵的融合可以简单地表示为两个矩阵相加。信息矩阵中每个非对角线上的元素表示机器人与特征标志之间或特征标志与特征标志之间的一种约束关系，这些约束关系可以通过系统状态的信关系进行局部更新。这种局部更新使得信息矩阵近似于稀疏矩阵，对其进行稀疏化产生的误差很小。根据这一点，S.Thrun等人提出了一种基于稀疏信息滤波器SEIF(Sparse Extended InformaTIonFilter)的SLAM方法，并证明利用稀疏的信息矩阵实现SLAM的时间复杂度是O(1)。虽然EIF可以有效降低SLAM的时间复杂度，但是在地图信息的表示和管理方面还存在一些问题。首先，在常数时间内只能近似算得系统状态的均值；其次，在基于EIF 的SLAM 方法中，特征标志的增删不方便。

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