自主导航是实现自主式水下机器人(Autonomous Underwater Vehicle,AUV)完全自主化的关键技术之一。由于海洋任务需求日益复杂,传统导航手段已很难满足水下机器人开展海洋任务的需求。同步定位与构图技术(Simultaneous Localization And Mapping,SLAM)因其对传感器要求简单,无需先验地图信息的优点成为水下机器人导航方面的研究热点。本文主要针对基于随机有限集的水下SLAM算法展开研究。首先,针对基于栅格地图的水下SLAM未能对前视声纳传感器观测信息进行充分有效表达和未考虑状态数目不确定性的问题,将多用于目标跟踪的随机有限集理论应用到基于栅格地图的水下SLAM中,并提出随机有限集水下SLAM算法框架。随机有限集理论能更好地处理低精度前视声纳中存在的漏检和虚警不完美的观测信息,更好地对SLAM中状态的数目不确定性和概率不确定性进行估计。其次,对于基于随机有限集的贝叶斯滤波中存在着计算复杂度随状态数目的增加成指数增长问题,利用概率假设密度对状态后验概率密度进行近似,通过粒子滤波实现概率假设密度滤波,降低了算法的复杂度。同时对随机有限集水下SLAM的建议分布做出改进,提出最大后验有限次重采样策略,并通过仿真实验验证改进后的算法能有效提高水下机器人的定位和建图精度。然后,由于随机有限集水下SLAM中每个粒子携带一个独立完整的环境栅格地图,粒子之间地图有很大的相似性,为充分利用粒子间地图的冗余,提出数据结构宗代树。数据结构宗代树记录的是所有粒子之间的代际演替,反应了粒子间的运动关系和地图资源继承关系。通过对宗代树进行剪枝和融合操作,使宗代树的尺寸维护在一定范围之内。最后,在随机有限集水下SLAM算法重采样过程中,针对大量地图数据流动和占用内存问题,提出分布式粒子映射方法。该方法将宗代树和分布式栅格地图这两种数据结构紧密联系。数据结构分布式栅格地图利用粒子间的关系,通过高效的地图管理方式,用一个栅格地图将所有粒子联系起来,将粒子与栅格地图的映射关系从一对一变为多对一,减少了地图维护对内存的需求,提高了地图维护的效率。