移动机器人具有很高的智能性,自主性和机动性,可以代替人类在复杂或危险的环境中完成探险、探测和操作等任务。移动机器人必须具备自主导航的能力,因为可靠的导航能力是真正实现其自主移动的基础。现在未知环境下的自主导航成为移动机器人领域关注的热点。因为未知环境下不存在可以提供准确导航信息的先验的地图环境信息,所以未知环境下的自主导航成为移动机器人领域一个亟需解决问题。解决这个问题则需要处理以下两个方面:一方面机器人如何在未知环境下确定自身的定位;另一方面,机器人如何准确描述环境特征并建立环境地图。为了解决这两个难点,移动机器人的同时定位与地图构建算法(Simultaneous Localization and Mapping,简称SLAM)被提出来。SLAM问题自提出以来就受到移动机器人领域广大研究者的关注,其重要的理论和应用价值被很多研究者认为是实现自主移动机器人的核心问题,已经成为自主导航领域研究的焦点。近十年来,许多研究者通过努力取得了令人瞩目的成果,这些成果成功在室内、室外、水下等多种环境下得到了实践。然而,这些方法应用于解决大尺度未知环境下的SLAM仍有许多不完善的地方需要改进,仍有很多问题需要解决。本文主要针对大尺度未知环境中移动机器人的同时定位与地图构建的算法进行研究。对于解决大尺度环境中移动机器人位姿和环境地图的不确定性导致定位和地图构建的精度下降问题和计算复杂度随地图特征增加而增加的问题,基于子地图的方法是比较有效的一种策略。本论文基于子地图算法,提出了一种新的SLAM方法——它组合了稀疏扩展信息滤波器SLAM(SEIFSLAM)和FastSLAM的优点,以提高大尺度环境中移动机器人定位和地图构建的准确性和执行效率。这种新算法用FastSLAM方法进行局部子地图的建立,用基于SEIFSLAM的方法进行子地图的联合,最后通过二者的有效组合实现全局地图的构建。引入FastSLAM的好处是能够避免运动过程处理中的线性化问题,同时能够得到更加稳定的数据关联。运用SEIFSLAM的好处是在子地图联合的处理过程中没有近似性问题及其相对高效的计算速度,同时能够避免由FastSLAM引起的估计的过优。这种新的处理方法在大尺度环境下有着更加出色的一致性。在此算法中,为了提高整个SLAM过程的执行速度及降低计算时间复杂度,通过一种新的子地图联合策略——基于二叉树的带决策的联合策略来进行全局状态地图的构建。这种策略使这种新算法的总的计算复杂度将到了O ( nlogn)以内。最后,通过仿真实验和著名的Victoria Park实验对所提出的算法进行了验证,并将结果与其他算法相比较。结果表明,本文提出的新算法满足了SLAM问题的一致性要求,提高了大尺度环境中移动机器人定位和构图的精确度,并且降低了SLAM算法的计算复杂度。