一种基于膨胀算法的 多UUV队形生成与避障策略

何喆 刘峰 马子飞

摘要：水下无人潜航器（Unmanned Underwater Vehicle，UUV）是一种集环境感知、动态决策与规划、行为控制及能源适配等功能的复杂无人系统，是执行抵近海底探测、开发、搜寻任务的重要工具。本文为解决多UUV系统面临的区域内高效探测队形生成和动态、静态避障问题提出了基于膨胀算法的队形生成与避障策略，能够高效的计算n个个体的集群在圆形区域内的均匀分布，在维持高效探测队形的同时兼顾动态、静态避障要求，并对膨胀算法的队形生成与避障进行了仿真实现，验证了基于膨胀算法的多UUV系统队形生成与避障策略的有效性。

关键词：膨胀算法;队形生成;避障;多智能体

一、引言

本文的应用背景为基于事件驱动的多UUV编队系统的区域均匀监测策略，所解决的问题为多UUV系统的区域保持。在当前的众多水下任务中，UUV群更多的是执行探测任务和工作任务。但是多UUV编队系统实际上属于多智能体，其研究方法和方向也在向多智能体靠拢。任意UUV个体都有其水下知识库来解决水下的运动、工作问题，其三维方向上六自由度的运动与无人机相似，多智能体系统的共性热点问题为队形生成与避障。

二、研究背景

水下无人潜航器（Unmanned Underwater Vehicle，以下简称UUV），是无人驾驶的水下自主航行的载具，最初用以代替潜水员、潜艇等进行危险区域作业，如探测、营救、排雷等。

UUV自问世以来就受到广泛关注，其作为水下支援平台的军事用途更使其成为现队海军利器，因而UUV在军用领域技术最为先进。随时代和技术发展，在更复杂的环境和任务面前，单UUV已不能满足要求，多UUV编队系统才是应发展的方向。其在复杂环境中的内部协同机制，高容错率为实际应用提供了诸多便利，多UUV编队系统要进行协同，必须具有确切的等级制度或协同体系。国内对于多智能体的研究重点聚集于围猎、队形生成方面，并从稳定性，通信拓扑结构，也即图论的角度来对多智能体进行研究，取得了极大的进展。

当前的多UUV系统协同控制、队形生成相关研究已非常完备，在多智能体个体控制方面，基于避障问题有人工势场法、栅格法等。在队形控制和生成方面有：基于行为的方法、领队-跟随者方法、虚拟结构法、群体势场法等。但以上方法对于个体数目不定或多变的多UUV系统队形生成和避障并不高效，因此本文提出了膨胀算法来同时解决队形生成和避障问题。

三、多UUV系统的系统结构与分布方式

多UUV系统作为一个整体来完成任务，其内部必定要有分工协作，以分层式控制体系思想来划分，系统可以分为如下四个层次，值得注意的一点是，任何一个UUV都含有上述四个部分的功能，如图1所示。

（一）感知层

UUV感知层来自UUV的各种传感器和包括光学声学在内的图像设备，通信设备和探测设备。一个UUV所获得的信息，不只是个体UUV获得的自身姿态、位置、速度、方向、水流、经纬度位置、深度，还包含别的UUV和水面母舰传递来的各种通信信息。

（二）协调规划层

协调层负责各UUV的组织关系，包括当前的通信拓扑结构、协调规划模块、任务冲突监测与消除模块、未执行目标、任务分配分解模块、水下知识库。各模块功能如下：1.通信拓扑结构：UUV的通信部分分为UUV之间的水声通信和UUV母舰间的无线电和水声混合通信。本文假设在较深水域进行，所以通信部分仅为UUV之间的水声通信，其通信拓扑结构即是协调规划层之重点。2.水下知识库：UUV预存的以应对各种水下环境的知识。3.未执行目标：工作状态的UUV都是有任务堆栈的，UUV会依据各任务优先性先后执行任务，任何当前任务可以被高优先级任务中断。4.任务分解分配模块：复杂任务必须分解为多个简单任务来赋予多个UUV个体，毋庸置疑这将提供更高的效率。5.协调规划模块：任务的多样性和水下环境的复杂多变使得UUV的任务执行机制也要根据情况不同而适时应对。6.任务冲突监测与消除模块：多UUV执行任务将有更高的概率产生协调、分配上的冲突，这是本模块产生的原因。

（三）控制决策层

控制决策层依据当前的既定策略，综合当前感知层得到的外界信息以及多UUV系统的自身状态信息，结合协调策略做出控制指令传递于执行层。控制处理层模块包括：协调策略、控制器、任务解析模块、行为决策。各模块功能如下：1.协调策略：使各UUV之间协调运作。2.控制器：综合信息得到控制结果，将指令传递给执行层。3.行为决策：任务分解为多个简单行为时，决策模块将根据各自UUV的具体情况选择合适的行为。4.任务解析模块：本模块将为各任务目标提供详细的参数，使任务可执行。

（四）执行层

作为系统的响应，类比于控制系统的执行元件。主要作用即是将控制层传递来的控制指令转化为将要运动的UUV指令，如推进器的推力大小、垂直方向和水平方向的舵角，并带有反馈。执行层主要包含以下几个部分和功能。1.推进器：主要负责给UUV提供前进的推力。2.方向舵：垂直方向舵和水平方向舵，控制UUV的转向以及上浮下潜。3.监控模块：通过反馈判断推进器和舵机是否正常运行。4.执行控制器：给出推进器、方向舵的控制量，综合反馈数据做出适当的调整。

四、基于膨胀算法的多UUV系统的队形生成策略

多UUV系统可认为是一个同构多智能体系统，面临水下探测问题时均需要进行避障与队形生成，本文提出了基于膨胀算法的多UUV系统队形生成与避障策略。膨胀算法基于数值计算，在多个约束条件下进行趋近计算，最终形成符合多个约束条件的趋近解。在平面几何角度可理解为多个相同大小的刚体小球在一球形区域内进行膨胀，初始状态所有小球均随机分布，半径相对区域而言极小，随时间增长，小球半径增大，规定任意两小球外壳相挤压或与区域轮廓挤压将会产生力使二者分离直至不再出现挤压，继续膨胀过程，直至半径不再增大。最终小球在封闭区域内的分布即为符合膨脹极限的个体分布。

因多UUV系统面临的绝大多数探测队形为二维平面队形，在此仅讨论膨胀算法在二维平面的应用，

在区域内随机部署n个点，以此n个点为圆心（此n个圆称作n个个体），半径为R1，R1取一较小值，使n个圆都不相切或交叠，以一低增速逐步增大半径，当半径取Rn时，出现圆彼此交叠或与边界相切，圆心向交叠或相切方向的反向180°（即以反向为正90°刻标，左右各90°范围）内任意角度移动一步，对于与多个个体圆交叠相切的情况，运动方向取其公共区间，无公共区间的个体则不可移动，与其交叠的其他可移动个体移动速度作一适应性提升，然后检测当前是否所有个体满足不交叠条件，否则继续随机移动，持续随机移动过程直至满足所有个体不交叠条件，继续增大半径，重复如上的判断过程和随机移动过程，直至出现部分个体相叠，且所有点不可移动的情况，以下称为自锁情况，出现自锁情况则认为是最终的分布结果。以上算法的程序框图实现如图3所示。

进行算法实现后，设定实验初始条件，9个个体初始位置位于直线L ：y=x上，设定圆形区域圆心为原点，半径为5。实验结果如图4，图4左为最终个体分布结果，图4右为个体移动轨迹。试验结果表明了膨胀算法对于多智能体队形生成的应用是有效的。

五、膨胀算法对于高效探测队形生成的应用

UUV的主要探测功能集中在侧扫声纳上，其保持位置不变，姿态可变的情况下，在三维空间的探测范围为一以侧扫声纳扫描范围为半径的球体，在二维平面上是一圆域。多UUV编队系统实际进行区域探测时一般形成三角形编队或一字形编队，对区域内进行正弦曲线的巡航来探测，其应对大多数水下环境都是足够的，即水下环境的实时变化并不大，较大区域内的信息基本不变，然而随科技进步，UUV趋于小型化，集群化，批量生产，应对复杂水下环境的探测就需要大量的UUV分布在整个区域内，各UUV在满足通信距离情况下尽可能承担同样大小的探测区域。基于以上需求提出了高效探测队形，使其集群分布效能最优。

多UUV系统的高效探测队形计算就成了n个固定大小球体对一圆形区域的覆盖分布。此处直接引入蜂巢原理，即蜂巢的正六边形结构排布是无空隙，且最节省边界的结构，其优点有多篇文献说明。在此直接使用，承认正六边形的外接圆结构是重叠率最小的排布结构，并给出如下的探测多UUV系统最优解。如图5所示。

对于虚线圆域内任意区域都是完全探测的，由此，给出了多UUV系统对任意形状封闭区域完全探测的最少UUV排布计算方法。

首先对目标区域作外接圆，在外接圆内按左图结构扩展全覆盖，将与目标区域无交叠的UUV剔除，所得的剩余UUV排布即是较优探测排布。

六、基于膨胀算法的多UUV系统避障策略

多UUV系统在执行行进避障或躲避动态障碍物时，为保持队形的相对松散与一致，需进行同时进行避障与队形变换，应对策略应尽可能符合总体能耗最低原则。对于上述情况提出了基于膨胀算法的多UUV系统避障策略。即将障碍物视作仅能进行固定方向移动的个体，执行逆膨胀算法。算法策略如下：

有一外界圆球状障碍物沿直线L ：y=x穿越区域，包含安全距离的碰撞域即为图5所示的红色障碍物。设定其仅能沿直线L ：y=x单向移动，任意时刻，如果动态障碍物不可移动，则缩小所有个体圆半径，可使障碍物移动，依据膨胀算法内的调整机制障碍物只沿直线L ：y=x單向移动，各UUV个体则做避让运动，同时维持队形的相对松散，其最终结果，将是动态障碍物由左下方离开圆域，然后圆域内的多UUV系统重新膨胀至高效探测队形。

七、结束语

本文针对多UUV系统的水下探测需求，提出了基于膨胀算法的多UUV队形生成和避障策略。并进行了多UUV系统的队形生成与避障的相关仿真，验证了所设计的策略在高效探测队形生成方面的有效性，可用于任意数目的同构智能体集群生成松散均匀队形，具有较好的参考价值。本文针对多UUV编队系统的区域保持问题，使用膨胀算法进行了控制律层面的队形控制，避障研究，并针对区域保持的评价体系提出了区域均匀规划。

作者单位：何喆     刘峰    马子飞    航空工业西安航空计算技术研究所

参  考  文  献

[1]邓超.AUV三维轨迹跟踪控制方法研究[D].哈尔滨：哈尔滨工程大学，2011.

[2]王国英.欠驱动水面艇运动控制建模及三维仿真实现研究多水下机器人编队控制方法研究[D].哈尔滨：哈尔滨工程大学，2011.

[3]王爱兵，严浙平.不同优先级的多水下机器人避碰技术研究[J].微计算机信息，2007，（14）：232-233，253.

[4]李晔，由光鑫，庞永杰.多水下机器人视景仿真系统技术研究[J].计算机仿真，2005，（06）：161-163，217.

[5] Fahimi F.Sliding-mode formation control for underactuated surface vessels.IEEE Transactions on Robotics，2007，23（3）：617-622.