随着多机器人学的发展和水下机器人技术的进步,多水下机器人协同作业被公认为未来水下机器人应用的重要方向之一。编队航行是最基本、最具代表性的协同作业行为,通常是指多个机器人在空间上保持特定几何队形、共同行进(或作业)的过程。多水下机器人编队与多移动机器人、多无人机编队相比,核心难点是水声通信和相互感知的局限性。这些局限性使得多水下机器人之间既不能实时准确的传递位置信息,也不能通过感知手段获得相对方位信息,如何在这种不完全、不确定信息条件下实现大规模多水下机器人编队是难点之一。在不能建立通信组网的条件下,一种思路是找到多水下机器人编队的基本单元,然后实时地将复杂编队分解为基本编队以实现任意队形的控制。本课题基于这一思路引入图论基本理论,从建模、分析和控制的角度深入研究了多水下机器人复杂编队问题。主要研究内容包括:1)分析了图和多水下机器人控制图的对应关系,给出了控制图刚性和维持性的定义,并构建了多水下机器人复杂编队和基本编队控制图模型。2)依据图论方法对复杂编队控制图进行分析,提出了复杂编队分解为基本编队的连通图条件,以及复杂编队控制图生成的充要条件和邻接矩阵产生方法。3)针对不同通信条件下基本编队的实现,提出了三种编队控制方法并对每种方法应用的局限性进行了分析。4)对所提出的基本编队控制方法和复杂编队生成方法进行了仿真验证和实验验证。研究结果表明:应用图论进行编队分解是实现不确定通信下大规模多水下机器人编队的有效途径之一,能够将复杂编队合理分解为若干基本编队,并根据通信状态选择不同的编队控制方法实现稳定的编队航行。