移动机器人同步定位与建图(SLAM)问题是移动机器人在未知环境中实现真正自主必须解决的关键问题,是当前移动机器人学界的研究重点和热点之一。SLAM包含状态估计和数据关联两部分。其中,状态估计是指对环境特征的位置以及机器人定位的估计过程;数据关联是指建立在不同时间、不同地点获得的传感器测量之间、传感器测量与地图特征之间或者地图特征与地图特征之间的对应关系,以确定它们是否源于环境中同一物理实体的过程。数据关联为状态估计提供输入,正确的数据关联是实现正确的状态估计的前提。随着机器人运行环境的日益复杂和非结构化,SLAM中数据关联相关问题研究的重要性日益突显。SLAM中主要有以下三个子问题涉及数据关联:递增建图与定位,循环闭合和多机器人SLAM中的地图合并。递增建图与定位中的数据关联研究如何确定当前连续的传感器观测之间或者当前时刻的观测与最近所创建的局部地图中特征间的关联关系,该问题即为通常意义下的数据关联问题,本文称其为局部数据关联;循环闭合中的数据关联研究机器人沿不同的路径回到某一循环的起点时,如何确定当前创建的局部地图中的特征与以前所创建的循环起点处地图中特征之间的关联关系,本文称其为循环数据关联;地图合并中的数据关联研究多个局部地图中的特征间的关联关系,本文称其为多机器人数据关联。这三类数据关联的差别在于问题解空间大小不同。本论主要文针对上述三类数据关联问题展开了研究,取得了以下成果:(1)在分析现有的描述数据关联问题的数学模型局限性的基础上,根据SLAM中数据关联问题的特点,应用关联树模型描述SLAM中数据关联问题的解空间,将数据关联问题建模为针对关联树的图搜索过程,提出了一种更为清晰直观的图模型结构。在适当的节点耗散值定义下,证明了关联树节点耗散值随深度增加的单调递增性。根据关联树模型,应用人工智能中的图搜索理论对主要的数据关联算法进行了分类,并从算法的时间复杂度、空间复杂度和最优性等方面对这些算法进行了分析比较。(2)应用示例分析了SLAM中修正过去“错误的”1数据关联的必要性。利用针对关联树“好的优先”回溯搜索,并结合基于最小二乘的完全SLAM状态估计方法,提出了一种基于关联树有限深度回溯搜索数据关联的递增式完全SLAM算法(Incremental Full SLAM with Limited Backtracking Search Data Association—BTK_SLAM)。该算法将状态估计的最小二乘残差作为关联树节点耗散值,并实现了该耗散值的递增式计算,从而引入了由状态估计到数据关联的直接反馈。算法可以在线检测并修正过去错误的数据关联,因此在系统误差较大时依然可以获得较好的状态估计。另外,设计了合理的关联树剪枝方法以减少计算量。(3)针对闭环问题始终存在的根本原因一直未得到完善的理论分析解答这一问题,本文以线性高斯SLAM问题为研究对象,对机器人定位估计的收敛特性进行了详细的理论分析,证明了SLAM本质上是航迹推算式(Dead-reckoning alike)的自定位过程:随着机器人对未知区域的不断探索,其定位估计误差总体上递增且不收敛,即无上界。闭环问题始终存在的根本原因正是源于机器人定位估计的不收敛性。当机器人沿不同路径回到某一循环起点时,其定位误差可能会非常大,递增建图和定位技术难以获得相容一致的地图估计,必须采取其他方法单独处理闭环过程。(4)以使得机器人尽早检测到循环地形,并尽快实现循环闭合为目的,本文将机器人探索策略与闭环过程相结合提出了一种在线主动闭环方法。该方法将闭环过程与增量式SLAM过程相分离,并应用多阶段决策对主动闭环过程进行建模。自主机器人根据相互承接的多个决策过程的决策结果选择合适的行为,并应用改进的非完整地图中的粒子滤波定位实现闭环确定。该方法将循环数据关联问题转化为机器人在闭环处的全局定位问题,并应用粒子滤波实现定位估计,从而将高维关联空间中的搜索问题转化为多个连续低维空间当中的搜索问题。由于该主动闭环方法不受具体的递增建图和定位方法的限制,所以它实际上是一个实现机器人未知环境探索过程中在线自主闭环的模型框架,具有通用性。(5)多机器人SLAM中,当局部地图间的相对位置已知时,可以应用局部数据关联技术解决多机器人数据关联问题,此时地图合并问题的难度将大大降低。为此,本文提出了一种基于粒子簇滤波定位的地图合并算法,主要解决局部地图相对位置未知时如何正确计算局部地图间的相对位置关系问题。该算法通过实现一个机器人的探索路径在另外一个机器人建立的局部地图中的全局定位确定局部地图间的相对位置关系,这种相对位置关系称为合并假设。算法主要采取两方面措施保证生成正确的合并假设:一是将机器人路径分段并分别确定每段路径的全局定位,每段路径的一个定位估计称为一个局部合并假设,然后通过多个局部合并假设间的相容性检验确定全局合并假设;二是应用粒子簇滤波定位算法获得每段路径的多个定位估计,从而减少丢失正确的局部假设的可能。