随着科学技术的发展,自主式水下航行器(AUV)的相关技术研究受到了越来越多的关注。历年来,对水下航行器的研究与开发主要集中在材料、电力系统、导航与定位系统、水下通信技术以及智能控制系统。各个方面研究的发展使得水下航行器的整体性能得到了很大的提高。如今,日益发达的AUV技术已广泛用于军事和商业领域,对AUV的自主性和智能性具有越来越高的要求,而路径规划技术是体现其智能程度的重要技术。水下航行器海底路径规划主要考虑三方面因素:执行的任务、海底环境约束、航行器自身物理约束。海洋环境具有各种各样的特征,如洋流、漩涡等等。航行器自身物理约束主要是动力学约束。不同的执行任务将考虑不同的环境特征和航行器自身的约束,现有学者已就不同的路径规划问题提出相应的算法求解。现有的路径规划问题主要是两点间路径规划。已有学者提出基于物理、数学和数据结构思想的算法、智能算法、图搜索算法和多种方法混合的算法,但是这些算法缺乏对环境空间中障碍边缘信息的有效压缩与筛选。本文针对此提出Tree-EP算法,该算法基于离散空间提出可靠边缘点模型进一步压缩搜索空间,之后再使用树扩散架构筛选出真正有潜力的边缘点进行搜索。在路径搜索过程当中,本文还提出了局部回溯优化机制,能有效对路径进行局部搜索,进一步降低路径代价。在只考虑路径长度的单目标优化测试和考虑路径长度、升降幅度、转向角度代价的多目标优化测试中发现,Tree-EP算法和引入局部调整的改进Tree-EP算法在两点间路径规划问题上具有很好的路径搜索能力。现今多监测点路径规划问题的研究相对较少,本文提出了S-PSO-A~*算法用于求解该问题。由于多监测点问题的计算量较大,本文对S-PSO-A~*算法分为离线方法和在线方法,分别记为S-PSO-A~*离线和S-PSO-A~*在线。S-PSO-A~*离线是先完整计算由监测点构成的图G,再利用S-PSO求解和优化监测点访问序列;在线方法是同步计算和优化图G和访问序列。在由多峰函数构建的实验环境测试中,S-PSO-A~*在线具有良好的回路搜索能力和灵活性。