基于能量约束的自主水下航行器任务规划算法

赵旭浩 王轶群 刘健 徐春晖

摘 要：多水下自主航行器（AUV）任务规划是影响集群智能水平的关键技术。针对现有任务规划模型只考虑同构AUV集群和单潜次任务规划的问题，提出了适用于AUV异构集群的多潜次任务规划模型。首先，该模型考虑了AUV的能量约束、AUV多次往返母船充电的工程代价、异构集群个体间的效能差异、任务多样性等关键因素;然后，为提高问题模型的求解效率，提出了一种基于离散粒子群的优化算法，该算法引入用于描述粒子速度、位置的矩阵编码和用于评估粒子质量的任务损耗模型，改进粒子更新过程，实现了高效的目标寻优。仿真实验表明，该算法不仅解决了异构AUV集群的多潜次任务规划问题，而且与采用遗传算法的任务规划模型相比较，任务损耗降低了11%。

关键词：自主水下航行器;多AUV集群;任务规划;离散粒子群优化;多样性任务

中图分类号：TP242.6

文献标志码：A

Task planning algorithm of multi-AUV based on energy constraint

ZHAO Xuhao1，2，3，4， WANG Yiqun1，2，3，4*， LIU Jian1，2，3， XU Chunhui1，2，3

1.Shenyang Institute of Automation， Chinese Academy of Sciences， Shenyang Liaoning 110016， China;

2.State Key Laboratory of Robotics （Shenyang Institute of Automation， Chinese Academy of Sciences）， Shenyang Liaoning 110016， China;

3.Institutes for Robotics and Intelligent Manufacturing， Chinese Academy of Sciences， Shenyang Liaoning 110016， China;

4.University of Chinese Academy of Sciences， Beijing 100049，China

Abstract：

Autonomous Underwater Vehicle （AUV） task planning is the key technology that affects the level of cluster  intelligence. In the existing task planning models， only the problem of homogeneous AUV cluster and single dive task planning are considered. Therefore， a multi-dive task planning model for AUV heterogeneous clusters was proposed. Firstly the model considered the energy constraints of AUV， the engineering cost of AUV multiple round-trip charging in mother ship， the efficiency difference between heterogeneous cluster individuals， and the diversity of tasks. Then in order to improve the efficiency of solving the problem model， an optimization algorithm based on discrete particle swarm was proposed. The algorithm introduced matrix coding for describing particle velocity and position and the task loss model for evaluating particle quality to improve the particle updating process， achieving efficient target optimization. Simulation experiments show that the algorithm not only solves the multi-dive task planning problem of heterogeneous AUV clusters， but also reduces the task loss by 11% compared with the task planning model using genetic algorithm.

Key words：

Autonomous Underwater Vehicle （AUV）; multi-AUV cluster; task planning; discrete particle swarm optimization; diverse task

0 引言

自主水下航行器（Autonomous Underwater Vehicle， AUV）是進行海洋探索和海洋科学研究的有效工具。AUV以其智能化、灵活性、快速性成为各国争相发展的水下利器[1-2]。随着近年来机器人技术的快速发展，多 AUV 系统受到广泛关注。与单体AUV相比，多AUV系统的作业范围更广，作业效率更高，而且能够完成单体AUV不能完成的复杂海洋探测任务，在海洋矿产资源调查、海洋现象观测、水下目标搜索、海洋信息网络组建[3]等诸多方面有广阔的应用前景。而多AUV任务规划是多AUV系统协作的一个基本问题。多AUV系统的工作场景如图1所示，多个不同类型的AUV在水下通信网络和母船的支持下协同完成探测任务，由于AUV的布放和回收都比较困难，提高能源利用率对AUV意义重大，合理的任务规划能够提高能源利用率、提高系统的工作效率。

目前多AUV任务规划的研究已经取得了很大的进展[4]。针对多AUV的任务规划问题，文献[5]建立了以最大收益为目标的任务规划模型，然后用混沌粒子群算法求解，但是所建立的模型只考虑了执行任务的收益和时间，没有考虑AUV和任务之间的距离信息。文献[6]根据任务的位置和能耗建立了多AUV任务规划模型，并且用蚁群算法进行求解，但是模型中缺乏传感器匹配机制和任务均衡策略。文献[7]构建了以每个AUV的能量耗费与能耗均衡为约束条件的水下三维空间下的多旅行商问题模型，并且设计了考虑巡航总路径及访问目标数的适应度函数，但是这种方法没有考虑任务的规模。文献[8]用自组织神经网络求解AUV的任务规划和路径规划问题，但是没有考虑AUV的能量约束和传感器约束。文献[9]以使用最少的AUV为目标，建立了只考虑传感器匹配和时间限制的整数规划模型。文献[10]首先建立了每个AUV和每个任务之间的匹配矩阵，然后以多目标元启发式方法求解满足约束的最优解，实现了AUV和任务之间的合理匹配。文献[11]用基于市场的分布式方法解决AUV的任务分配问题，这种方法能够合理地处理各类约束，但是对通信的穩定性要求比较高。文献[12]研究了AUV和无人机的任务协同，并且提出了考虑时间窗口的任务分配模型，取得了较好的效果。

上述文献在一定程度上能够进行多AUV的任务规划，但是所建立的模型不能够反映多AUV集群的实际工作过程。首先，作者都假设在一次任务规划过程中所有的AUV有能力执行完所有的任务，或者只分配AUV能够承担的任务，或者直接不考虑AUV的数量。但实际情况是，AUV一次下潜所能探测的区域远远小于所要探测的海洋区域，AUV不可能一次作业下潜就能够执行完所有任务，往往需要多次回母船补充能源，多次下潜才能够完成任务。再者，AUV执行任务主要依靠AUV自身所携带的传感器和探测设备，而不同的任务也是根据需要的传感器和设备来区分的，因此，考虑AUV的异构和任务的多样性至关重要。

因此，本文在上述文献的基础上建立了新的多AUV任务规划模型，考虑了AUV回母船充电的过程，对AUV在各个任务点的能量变化进行了精细建模，在满足传感器约束的条件下能够为集群内的每条AUV规划多次作业下潜。新模型以AUV的下潜次数和任务时长为优化目标，能够在下潜次数和任务时长之间达到平衡。改进了一种新型的离散粒子群算法对异构多AUV任务规划模型求解，设计了矩阵编码的方式表示粒子位置和粒子速度，将约束的处理加入到了粒子的编码和更新过程中。

1 问题描述

多个AUV组成编队协同执行海洋探测任务时，海洋探测任务需求不同，需要不同的AUV完成不同的任务，因此本文建立了AUV传感器向量和任务传感器向量，用来完成AUV和任务之间的匹配。另外，有时候任务的工作量较大，所有的AUV一次下潜并不能完成所有任务，必须将AUV回母船或者回水下基站充电的过程在任务规划模型中体现出来。针对上述问题，本文在模型中用多个虚拟充电点来模拟AUV多次回母船充电的过程，AUV经过一个虚拟充电时，表示AUV返回了母船一次。

执行海洋探测任务时，AUV的操控者和海洋科学家所关心的目标主要有两点：第一是执行任务的时间;第二是AUV的下潜次数。在多AUV的场景下，这两个目标是存在矛盾的，多个小型的AUV同时下潜能够执行完的任务对于大型AUV来说一次下潜就能够完成，如何平衡这两种目标是关键。

问题的假设条件如下：AUV的电量有限，只存在一条母船，AUV都从母船出发，母船的位置固定不变，AUV从母船出发时都是满电状态，AUV都能够顺利地执行完任务。

2 任务分配建模

多AUV任务分配模型描述如下：多样性任务点的集合为T，异构AUV的集合为R，一条母船。AUV要经过多次回母船充电的过程然后执行完这些任务。模型参数如表1所示。

2.1 建立模型

2.1 目标函数

目标函数（1）中的Z1是所有AUV的充电成本，再加上AUV在执行任务的过程中行驶的总路程。从目前来看，首先AUV的回收和布放都是带有危险性的作业，所以应尽量减少AUV回母船充电的次数;其次，即使将来采用了水下基站的方式进行充电，AUV和基站的对接过程依旧是耗时、耗力的工作;最后，现阶段AUV所使用特殊电池的使用寿命和陆地电池还有差距。因此，应该保证以最少的充电次数就能够完成任务。同时，采用多AUV编队的目的就是要减少任务的时长，因此AUV执行任务的时长也应该在目标函数中有所体现，多AUV执行任务是一个并行系统，其任务时长应该用运行时间最长的那台AUV的运行时间来表示。综上，可以得到Z1和Z2两个目标函数，Z1是充电成本和AUV在任务点之间的行驶距离相加，Z2是所有AUV中最大的那个任务时长，并且使用ω1和ω2两个参数调整它们的权重，可以根据重视程度来调整，这样既能够保证机器人的能源得到最大的利用，又能够优化机器人的运行时间。

Min Ζ = ω1Z1+ω2Z2（1）

Z1=∑r∈R∑i∈V∑m∈MCxrim+∑r∈R∑i∈V∑j∈V″dijxrij （2）

Z2=maxr∈R∑r∈R∑i∈V∑j∈V″xrij（dij+Wi）/speedr（3）

ω1+ω2=1（4）

2.2 约束条件

1）每个任务只能被执行一次。

∑r∈R∑i∈Vxrij=1;  j∈T（5）

2）虚拟充电点有可能被使用，也有可能不被使用。

∑r∈R∑i∈Vxrim≤1;  m∈M（6）

3）所有AUV都必须从起点出发。

∑j∈V′xrOj=1;  r∈R（7）

4）所有AUV都不能再回到起点。

∑j∈VxrjO=0;  r∈R（8）

5）所有AUV最终都必须回到终点。

∑j∈VxrjO′=1;  r∈R（9）

6）所有AUV都不能从终点出发。

∑j∈VxrO′j=0;  r∈R（10）

7）必须遵循流量守恒原则，AUV不能在任务点之间跳跃。

∑i∈Vxrij=∑i∈V″xrji;j∈V′，r∈R（11）

8）能量约束，AUV在一个任务点的剩余能量必须保证能到达下一个任务点，Ermax是松弛条件，保证没有连接关系的任务点也能满足约束。

E1jr≤E2ir-dijλrxrij+Ermax（1-xrij）; i， j∈V，r∈R（12）

9）AUV在离开起点时是满电量状态。

E2Or=Ermax;  r∈R（13）

10）AUV在离开虚拟充点电时是满电量状态。

E2ir=Ermax∑j∈Vxrij;  r∈R，i∈M（14）

11）离开任务点的能量为到达任务点的能量减去执行任务消耗的能量。

E2ir=E1ir-Wi∑j∈Vxrij;  r∈R，i∈T（15）

12）要保证在每个任务点执行完任务都能回到终点。

E2ir≥λrdiO′;  r∈R，i∈T（16）

13）传感器匹配约束，对于不同的AUV来说，最大的区别就是传感器，不同的任务之间的区别也是是否需要某种传感器，因此本文引入了AUV传感器向量和任务传感器向量。sensorr和sensorj都是内容为0和1的向量，维度相同，sensorr的每一位都要大于sensorj。

3 改进基于集合的粒子群算法

基于集合的粒子群（Set-based Particle Swarm Optimization， S-PSO）算法[13]是一种特殊的离散粒子群算法，

相比于常见的离散粒子群算法[14]，它的特点在于用集合的概念来表示粒子的位置和速度，粒子的更新过程用集合运算来代替，最大的优点在于每次粒子更新都能够得到满足约束的解。S-PSO算法常常用来解决离散领域的组合优化问题[15]。S-PSO算法的搜索空间用一个全集S表示，每个维度代表S的一个子集Si（i=1，2，…，D），即：

S=S1∪S2∪…∪SD（18）

每个粒子位置X都是全集S的一个子集，XS，X可以表示为：

X=X1∪X2∪…∪XD; XiSi（i=1，2，…，D）（19）

如果X能够满足所有约束，X就是一个可行解。在基于集合的粒子群算法中，速度使用一个可能性集合来表示[13]：

V={e/p（e）|e∈E}（20）

3.1 粒子编码

按照上述思想，设计多AUV任务分配求解问题的编码方式如下：

Xi=010001100

VELi=00.50.80.800.630.390.220

Xi是一个0-1矩阵，表示粒子的位置编码;VELi的每一个元素值都在[0，1]区间，表示粒子的速度编码，其中矩阵的维度也是粒子的维度，在本文的问题中，粒子的维度就代表任务的数量。

3.2 速度更新公式

S-PSO算法主要利用综合学习公式，这样能避免粒子早熟。

VELid=ω×VELid+c×rd×（Pid-Xid）（21）

但是S-PSO算法重新定义了式（21）的各个运算符，将上述的运算符操作改为了概率之间的运算和集合之间的运算。式（22）～（25）中的i代表粒子编号，d代表维度，在本文的问题中，第d维元素就是所有和任务d有连接关系的任务。〈u，v〉就代表着这种连接关系， p（u，v）表示这种连接关系对应的概率。

假设当前粒子位置如Xi所示，粒子速度如VELi所示，而目前的最优粒子为：

Pi=001100010

如果要计算维度2的粒子速度更新结果，那么：

Xi2={〈1，2〉，〈2，3〉}

Pi2={〈3，2〉，〈2，1〉}

U2={〈3，2〉，〈2，1〉}

假设c=0.5

c×Ud={〈3，2〉/0.5，〈2，1〉/0.5}

c×VELi2={〈1，2〉/0.25，〈2，1〉/0.4，〈2，3〉/0.315，〈3，2〉/0.11}

那么

c×VELi2+c×Ud={〈1，2〉/0.25，〈2，1〉/0.5，〈2，3〉/0.315，〈3，2〉/0.5}

就得到了更新之后的速度值，同时可以看到有关维度2的概率值得到了更新，并且概率值得到了提升，表示从最优粒子中学到了知识。

3.3 位置更新

原始的粒子群算法的位置更新公式为：

Xi-new=Xi+Vi（26）

而S-PSO算法将式（26）中的加法运算符改成了如算法1所示的集合运算操作。在文献[15]中，作者将S-PSO应用到了多车辆路径问题上，但是本文的问题和多车辆路径问题有一定差异。因为多车辆问题不考虑车辆的异构性，不考虑车辆的数量，而AUV的异构性是本文的主要关注点，因此，本文在原有的粒子位置更新算法中加入了隨机选择AUV的过程和传感器匹配的过程，改进后的粒子更新过程如算法1所示。

算法1 粒子位子更新过程。

输入：速度，原有粒子;

输出：新粒子。

有序号的程序——————————Shift+Alt+Y

程序前

Pv为速度编码矩阵;Px为当前位置矩阵;PE为所有位置都为1的矩阵。P′X为保存新粒子，i为当前已分配的任务， j为下一个任务。

1）

Convert（Pv）//将小于0.5的概率值置0

2）

While（还有任务没有被分配）

3）

If存在Pv（i， j）>0且满足约束

4）

从满足条件的集合中以距离最短的标准从Pv中选择j

5）

end if

6）

If在Pv中没有找到满足约束的任务

7）

从Px中寻找满足条件的j

8）

end if

9）

If在Px、Pv中都没有找到

从PE中寻找满足约束的任务

10）

end if

11）

If从上述3个集合中都没找到合适的任务

12）

说明当前机器人不合适，以随机选择的方式更换AUV并且记录当前的i和AUV，让当前AUV回到终点，即P′X（i，1）=1

13）

end if

14）

i=j;将j加入到已分配任务序列中

15）

end while

16）

return P′X

程序后

上述算法模拟的过程是：按照AUV的编号随机选择一个AUV，给AUV分配满足约束的任务，直到AUV达到电池容量约束或者再没有合适的任务可以执行，然后让该AUV回到母船充电，再次随机选择新的AUV，直到所有任务分配完毕。该算法在更新粒子的过程中能够保证上述模型中的约束都能够得到满足，因此，一次循环之后得到的一定是一个可行解。

3.4 粒子评估

粒子评估采用上文中建立的多目标函数，目标函数的值代表着执行任务总的损耗，这个损耗既有电池能量上的损耗也包括时间上的损耗，任务损耗的值越小，表明粒子的适应度越好。

3.5 粒子解码

假设有一个起点（终点和起点相同）和3个待分配任务的问题，那么这个粒子位置的一种可能性如下：

P=0101100010000010

从这个矩阵中可以得到P（1，2）=1，P（2，1）=1，P（1，4）=1，P（4，3）=1，P（3，1）=1。那么这3个任务就是依靠AUV的两次下潜来完成的，执行任务的顺序分别是1-2-1和1-4-3-1。虽然得到了两次下潜执行任务的顺序，但是不知道由哪个AUV执行的任务。好在在粒子更新的过程中记录了每个粒子在更新AUV时，前一个AUV执行的最后一个任务编号以及AUV型号，这样就能到解码得到每个 AUV所要执行的任务。

3.6 S-PSO算法总流程

S-PSO算法的工作流程和原始粒子群算法的流程没有区别，流程如图2所示。

4 仿真分析

本文的实验环境为I5-6300HQ，8GB RAM，实验软件为Matlab R2016a。仿真实验的基本参数为：粒子种群数量为20，惯性参数为2，加速度系数为0.7，目标函数中的ω1=0.5，ω2 = 0.5，总的任务数量为30个。表2展示的是30个任务的信息，任务信息中分别有4个数字，这4个数字的含义分别是（任务横坐标/km，任务纵坐标/km，任务代价/（kW·h），任务所需传感器向量）。编号1属于母船，母船的位置是（35，35）。

仿真实验设定有4条AUV，每条AUV的参数设置如表3所示，其中电池表示AUV的电池容量，可以看到4条AUV所拥有的传感器都不一样。其中AUV2和AUV3能够执行执行所有的任务，而AUV1和AUV4只能够执行部分任务。这样的参数设置能够最大限度地保证AUV之间的异构性，也能够有效地测试算法的有效性。AUV行驶单位距离所用的电量都设为λr=1。充电成本设为100。

首先，对待分配的任务量小于多AUV系统一次下潜的工作量的情况进行仿真。从上述30个任务中抽取前10个任务，分配给4个AUV。粒子群算法迭代200次，结果如图3（a）所示，可以看到AUV1-AUV3分配得到了任务，而AUV4没有分配到任务。因为前10个任务都需要传感器S2，AUV4没有这个传感器，所以AUV4沒有分配到任务;再者，能够执行任务的AUV都被分配到了任务，没有单个AUV负载过重的情况，而且AUV3的电池容量最大，它承担的任务也最多，带来了最少的下潜次数，任务分配的结果完全符合目标函数的设定。

图3（b）和表4展示的是把30个任务分配给4个AUV的结果，粒子群算法迭代1000次。30个任务的工作量明显超过了多AUV系统一次下潜的工作量，因此AUV2和AUV3都下潜了两次，而AUV4单次下潜执行的任务最多，这种情况非常符合所设计的目标函数。首先，目标函数中的Z1是最小化下潜次数，AUV4的电池容量最大，它基本上执行了它所能执行的所有任务，AUV2和AUV3的能力最强，能执行所有任务，所以这两个AUV执行的任务也多，符合目标函数的设定。如果只看Z1，最优的情况应该是AUV3和AUV4执行完所有的任务，只有这样分配任务才能得到最少的下潜次数，但是这样会造成任务执行时间过长，失去了部署多AUV执行任务的意义。所以，本文在目标函数中加入了Z2，同时实验结果也体现了目标函数一和目标函数二之间的均衡，AUV1号和AUV2分担了一部分任务，将任务时长降低，如果在AUV3执行任务期间多次派遣AUV1执行任务，确实可以进一步减少任务执行时间，但是这样又会造成下潜次数增加，给保障工作带来负担。

[9]GRAY G， MAHMUT K， LOVELL S D， et al. Automated mission parallelization for a group of UUVs [C]// Proceedings of the 15th International Symposium on Unmanned Untethered Submersible Technology. Durham： Durham NH， 2007： 28-40.

GIGER G， KANDEMIR M， Dan LOVELL S， et al. Automated mission parallelization for a group of UUVs [C]// Proceedings of the 15th International Symposium on Unmanned Untethered Submersible Technology. Durham： Durham NH， 2007： 28-40.

GIGER G， KANDEMIR M， Dan LOVELL S， et al. Automated mission parallelization for a group of UUVs [EB/OL]. [2019-01-12]. https：//www.researchgate.net/publication/228900865_Automated_Mission_Parallelization_for_a_Group_of_UUVs.

[10]LANDA-TORRES I， MANJARRES D， BILBAO S， et al. Underwater robot task planning using multi-objective meta-heuristics [J]. Sensors， 2017， 17（4）： Ariticle No. 762.

[11]DENG Y， BEAUJEAN P P J， AN E， et al. Task allocation and path planning for collaborative autonomous underwater vehicles operating through an underwater acoustic network [J]. Journal of Robotics， 2013（10）： 1-9.

[12]WILDE J， DIBIASO D， NERVEGNA M. Team planning for unmanned vehicles in the risk-aware mixed-initiative dynamic replanning system [C]// Proceedings of the OCEANS 2007. Piscataway， NJ： IEEE， 2007： 1-8.

[13]CHEN W， ZHANG J， CHUNG H S H， et al. A novel set-based particle swarm optimization method for discrete optimization problems [J]. IEEE Transactions on Evolutionary Computation， 2010， 14（2）： 278-300.

[14]程畢芸，鲁海燕，徐向平，等.求解旅行商问题的改进局部搜索混沌离散粒子群优化算法[J].计算机应用，2016，36（1）：138-142.（CHEN B Y， LU H Y， XU X P，et al. Improved local-search-based chaotic discrete particle swarm optimization algorithm for solving traveling salesman problem [J]. Journal of Computer Applications， 2016， 36（1）： 138-142.）

[15]GONG Y， ZHANG J， LIU O， et al. Optimizing the vehicle routing problem with time windows： a discrete particle swarm optimization approach [J]. IEEE Transactions on Systems， Man， and Cybernetics， Part C （Applications and Reviews）， 2012， 42（2）： 254-267.

This work is partially supported by the National Key Research and Development Program of China（2017YFC0306800）.

ZHAO Xuhao， born in 1994， M. S. candidate. His research interests include task planning of multi-AUV.

WANG Yiqun， born in 1985， M. S.， associate research fellow. His research interests include navigation methods and path planning algorithms of underwater AUVs.

LIU Jian， born in 1962， M. S.， research fellow. His research interests include navigation methods and control algorithms of underwater AUVs.

XU Chunhui， born in1982， M. S.， associate research fellow. His research interests include control algorithms of underwater AUVs.