自主式水下航行器(autonomous underwater vehicle, AUV)可以代替人类在水下环境中完成危险、耗时的任务。然而，在水下环境中，受成本的制约，单个AUV无法集成全部功能，需要多种类型的异构AUV协作完成任务。因此，异构多AUV系统受到越来越多学者的关注^[1]。合理的AUV任务分配能够提高多AUV协同工作的效率，降低协同工作的成本。因此，关于任务分配的研究成为了一个新的热点问题^[2]。

一般来说，任务分配问题是一个具有复杂约束条件的组合优化问题。从本质上讲，任务分配问题也是一个多项式复杂程度的非确定性问题(NP-hard)^[3]。近年来，学者们在异构多智能体任务分配的研究上取得了很大进展。早期研究者往往采用组合优化法来解决任务分配问题^[4-6]，包括线性规划法、匈牙利算法等。文献[6]采用匈牙利算法有效解决了多机器人任务分配问题，但其计算复杂、鲁棒性、实时性较差。后来，由于启发式算法在求解多智能体任务分配问题中表现出了较好的效果，越来越多的学者将启发式算法^[7-8]用于求解任务分配问题。文献[7]设计了一种改进的求解评价方法来指导粒子群算法的进化过程，有效解决了多目标优化任务分配问题。文献[8]提出了一种基于目标束编码和定制遗传算子的改进遗传算法，在进化过程中，定制了捆绑交换交叉和多类型变异算子来产生无死锁的后代，该算法在最优性和效率方面得到了明显提高。但上述算法都是集中式任务分配算法，需要建立一个拥有强大的计算能力的集中控制中心。然而，水下系统无法承担建立集中控制中心所带来的高昂成本，且目前水声通信技术无法满足集中式方法对水下大量信息交互的需求。因此，分布式任务分配方法更适合于水下系统^[9]。

目前，常用的分布式任务分配方法有阈值响应法^[10-11]、拍卖算法^[12-18]等。文献[10]提出了一种基于阈值响应模型的分布式决策方法，考虑了环境中的自然不确定性，从而实现了对环境的有效探测和攻击任务的有效分配。文献[11]采用阈值响应法实现了中等规模多机器人系统的可容错合作，但采用隐式通信，系统效率相对较低。而拍卖算法通过拍卖商与执行任务的智能体之间进行任务的拍卖从而实现分布式的任务分配，具有计算复杂性低、运行效率高的优点。因此，研究最多的分布式方法是拍卖算法。文献[15]提出了一种面向资源的分散拍卖算法用于解决多机器人任务分配问题，每个机器人根据任务的剩余资源以概率的方式生成机器人的投标值，最终通过拍卖商与机器人相互交流，将任务分配给任务完成时间最短的机器人。文献[16]以最小化无人机的成本为目标建立了无人机的数学模型，并在计算无人机的投标成本时考虑多种约束条件，解决了多无人机在多约束条件下的动态任务分配问题。然而，在上述文献的建模与算法设计中，只是充分考虑了智能体的利益，并且拍卖商选择中标智能体时，都是按照贪婪的原则选择标值最高或者最低的智能体中标，但都忽略了拍卖商的利益。在实际的拍卖市场中，拍卖商的利益对整个环境都是至关重要的，并且拍卖商与AUV的利益不是完全一致的。仅仅按照AUV递交的标值选择中标者，会降低任务分配的整体效能，并且影响拍卖商参与拍卖的积极性，不符合市场的规律。文献[17]中，拍卖商通过计算所有满足任务需求的机器人联盟及相应联盟所对应的资源福利，最终选择出一个具有最好资源福利的机器人联盟，减少了机器人的平均资源消耗。文献[18]在考虑投标者各种估值函数的基础上，同时考虑了拍卖商的各种评估函数，包括最大化利润、最小化成本等，解决了通信受限环境下的任务分配问题。但以上文献中拍卖商对于市场信息利用不充分，缺少了拍卖商根据市场反馈信息不断调整自身策略的过程，策略缺乏一定的灵活性，无法最大化拍卖商的利益。此外，水下多AUV任务分配相较于陆地上的多智能体任务分配存在着更严重的不确定性。在实际的任务执行过程中，参数扰动、水下洋流对系统影响的不确定性很可能导致预先制定的任务分配方案失效，进而导致任务分配的失败。而上述分布式的算法解决任务分配问题时，均未考虑环境不确定性对算法的影响。因此，如何设置强鲁棒性的分布式异构多AUV任务分配拍卖算法保证异构多AUV系统能在复杂的水下环境中有效进行任务分配是亟待解决的问题。

本文提出的分布式鲁棒拍卖算法在保证AUV效用的同时，又能够有效降低任务分配系统的成本，并且在复杂的水下环境中表现出了较强的鲁棒性。

1.   系统模型

1.1   异构多AUV任务执行模型

异构多AUV的任务分配问题涉及到的具体应用场景如下：在整个任务区域中，m个异构AUV对n个已知的任务点执行侦察、打击或者布雷操作。下面分别介绍任务点的相关参数和AUV的相关参数。

1) T={1, 2, …, n}表示n个任务点集合。这些任务点分别由3种类型的任务组成：侦察型任务、打击型任务和布雷型任务。每个任务点的任务只属于其中的一种类型，完成每种类型任务所需要的AUV数量不同。假设任务是已知的，并且在执行过程中是静止的。

侦察型任务：T_k={1, 2, …, N_Tk}表示N_Tk个侦察型任务。对于侦察型任务，只需要一个AUV就能完成侦察。

打击型任务：T_s={1, 2，…, N_Ts}表示N_Ts个打击型任务。对于打击型任务，需要一个或多个AUV来完成任务，即有的目标只需要一次打击即可完成，有的目标需要多次打击。

布雷型任务：T_l={1, 2, …, N_Tl}表示N_Tl个布雷型任务。对于布雷型任务，只需要一个AUV就能完成布雷。

2) V={1, 2, …, m}表示m个异构AUV，AUV的异构性决定了其性能和能力的不同，考虑了3种类型的AUV。

侦察型AUV：V_o={1, 2, …, N_Vo}表示N_Vo个侦察型AUV。侦察型AUV只能执行与之匹配的侦察型任务。

攻击型AUV：V_a={1, 2, …, N_Va}表示N_Va个攻击型AUV。攻击型AUV能够执行侦察型任务、打击型任务和布雷型任务。

反潜型AUV：V_f={1, 2, …, N_Vf}表示N_Vf个反潜型AUV。反潜型AUV能够执行打击型任务和布雷型任务。

1.2   异构多AUV任务分配分布式拍卖模型

基于拍卖算法的异构多AUV任务分配中，需要3种角色的参与：拍卖商、投标者及中标者。拍卖商主要负责任务的分配; 投标者主要负责向拍卖商递交投标; 中标者是投标成功的AUV，被拍卖商授予任务。

在所建立的优化模型中，任务分配系统P作为拍卖商通过水面跨介质浮标、水下传感网络等手段发布每个任务的任务信息，给予完成任务的中标AUV一定的任务奖励，其目标是最小化自身的成本; AUV集合V={1, 2, …, m}作为投标AUV收到任务分配系统P公布的任务信息后，根据其工作状态和能力计算效用值，以最大化自身效用为目的对任务进行投标，从而实现整个系统的任务分配，系统模型示意图如图 1所示。对任务分配系统P而言，每轮选择哪些AUV中标R_p是其策略。对于AUV_i而言，每轮选择哪个任务投标d_i是其策略，其中i∈V。假设在拍卖过程中，任务分配系统P和AUV都是自私而理性的。建立了异构多AUV任务分配分布式拍卖模型，包括两部分：任务分配系统P的优化模型和AUV_i的任务分配优化模型。

图  1  系统模型

Figure  1.  System model

下载: 全尺寸图片 幻灯片

1.2.1   任务分配系统P的优化模型

在大部分关于任务分配的研究中^[12-16]，建立了AUV的优化模型，但是却没有建立拍卖商(任务分配系统P)的优化模型，导致忽略了拍卖商的利益。在实际的拍卖市场中，拍卖商的利益对整个环境都是至关重要的，如果过分追求投标者的利益，不符合市场的规律。

针对上述问题，增加了任务分配系统P的优化模型，在此优化模型中，考虑到任务分配系统P分配任务所花费的总成本, 构建了任务分配系统P的目标函数，即成本函数。主要包括2部分：①支付成本z_ij^r，即任务分配系统P在第r轮中向第i个AUV支付的第j个任务的支付成本，也即任务奖励z_ij^r。②时间成本f_ij, 即任务分配系统P等待第i个AUV完成第j个任务所需要花费的时间成本f_ij。根据上述分析，任务分配系统P的优化模型如下：

在目标函数(1)中，对于时间成本f_ij而言，AUV完成任务所需要花费的时间越短，越有利于拍卖商和AUV的利益。而对于支付成本z_ij^r而言，任务奖励z_ij^r越高，AUV得到的收益越高，越能够吸引更多的AUV参与投标任务，有利于任务的完成。但是，这会增加拍卖商的支付成本z_ij^r，不利于拍卖商的利益。反之，任务奖励z_ij^r越低，拍卖商支付给中标AUV的支付成本越少，越有利于拍卖商利益。但如果任务奖励z_ij^r过低，会导致投标任务点的AUV数量不能达到任务点需要的AUV数量，造成任务不能被完成。拍卖商希望最终达到保证任务被AUV完成又不过多付出成本的目的，从而最大化自身的利益。

在约束条件(2)中，Q_ij为0-1决策变量，表示第j个任务是否被分配给第i个AUV。若对于任务点j∈T，在第r轮拍卖时，投标该任务点的AUV数量L_jbid^r超过或者等于该任务点需要的AUV数量L_j，并且第i个AUV被任务分配系统P选择为中标者时，Q_ij=1，否则，Q_ij=0。约束条件(3)是为了确保最终分配给每个任务点的AUV数量满足任务点所需要的AUV数量L_j。约束条件(4)表示在第r轮拍卖中，任务分配系统P宣布的第j个任务点的任务奖励z_ij^r不超过任务奖励上限值z_jmax，该约束是为了激励任务分配系统P积极参与拍卖。根据任务j的难度不同，构造了任务奖励上限值函数z_jmax，如下：

式中：τ_j为任务j的难度。

由式(5)可见，第j个任务点的任务难度τ_j越大，任务奖励上限值z_jmax也会越大。

本文在任务分配系统P的成本函数中考虑了任务奖励z_ij^r，建立了任务分配系统P的优化模型，将任务分配系统P的利益考虑在内，从而提高了任务分配系统P的积极性，促进了任务分配系统P参与拍卖，更加符合市场的规律。

1.2.2   AUV_i的任务分配优化模型

AUV_i的目标是最大化其效用值。因此，AUV_i的任务分配优化目标函数为

目标函数(6)表示AUV的效用函数，由收益函数U_ij^r和成本函数C_ij两部分组成。①收益函数U_ij^r，即在第r轮拍卖中，第i个AUV从当前位置到达第j个任务点所能获得收益U_ij^r。g_ij表示第i个AUV与第j个任务的匹配系数，一种类型的AUV能够执行多种类型的任务，但它们执行不同类型任务的能力是不相同的，每个AUV与任务的匹配系数反映了AUV执行每种类型任务能力的差别。若任务k∈T_k、s∈T_s、l∈T_l，当i∈V_o时，由于侦察AUV只能执行侦察型任务，第i个AUV执行侦察型任务k、打击型任务s与布雷型任务l的匹配系数可表示为G_i={g_ik, 0, 0}，g_ik=1;类似的，当i∈V_u时，G_i={g_ik, g_is, g_il}，且g_ik+g_is+g_il= 1;当i∈V_f时，G_i={0, g_is, g_il}，且g_is+g_il=1。②成本函数C_ij，即第i个AUV从当前位置到达第j个任务点所花费的成本C_ij。t_ij(tE)表示第i个AUV完成第j个任务所需要耗费的能源, T′ _ij表示第i个AUV到达第j个任务点后执行任务所花费的时间。本文将目标点形状视为一个条带，采用文献[19]的执行时间，因此，第i个AUV执行第j个任务所花费的时间为

式中：a_j为任务的扩展长度。

在式(6)中，最后一项表示第i个AUV到第j个任务位置所需要花费的时间。其中，V_c表示洋流速度的标量值; V_u表示AUV速度的标量值; θ为第i个AUV到第j个任务的方向矢量与洋流矢量之间的夹角; d_ij表示第i个AUV到第j个任务点的欧氏距离; h_c表示洋流影响系数。

考虑到水下洋流对多AUV任务分配模型产生的不确定性因素，将洋流影响系数看作一个估计值与一个不确定项的和，如下:

式中：h_c和分别为洋流影响系数的实际值和估计值; Δh为不确定项。

假设不确定项Δh随估计值线性变化，即服从均值为δ的均匀分布。描述这种参数不确定性的模型较多，如一般多面体模型、D规范模型、椭球模型和列向量模型^[20]，其中，列向量模型和椭球模型由于具有易于分析的特点，较为常用。采用列向量模型，即将洋流影响系数h_c表示为

式中：列向量ε为不确定项的界限，且有ε=，ζ表示不确定度。

利用鲁棒优化对抗不确定项，降低不确定因素对算法性能的影响，从而得到AUV_i的任务分配优化目标为

式中: V_ac为洋流速度的标量值V_c与AUV速度的标量值V_u的合成标量，采用文献[21]考虑的洋流影响因素，得到V_ac的表达式为

其中：β为合成速度V_ac与洋流速度的标量值V_c之间的夹角，表达式为

式中：V_at为AUV到任务点的方向矢量; V_c为洋流速度的矢量。

将式(9)代入式(10)中，AUV_i的任务分配优化模型可以表示为

式中：为考虑不确定值因素后的AUV成本值。

在约束条件(14)中，v_i(vE)表示第i个AUV所拥有的能源，此约束是为了确保AUV执行完该任务后仍有剩余能源。约束条件(15)表示第i个AUV在选择第j个任务投标时的效用要大于0，此约束是为了保证在第r轮拍卖中，第i个AUV在参与拍卖时的效用值高于未参与拍卖时的效用值，从而鼓励AUV参与拍卖过程。

2.   分布式鲁棒拍卖算法

本文算法由4个阶段组成：①任务宣告阶段; ②投标阶段; ③中标者选择阶段; ④更新任务信息阶段。为了更清晰地描述该算法，以第r轮拍卖过程为例进行了详细说明。

1) 任务宣告阶段。任务分配系统P向AUV集合V宣告本轮还未被分配的任务信息集合Φ^r={θ^r, M^r, T^r(tE), W^r, Z^r}。其中，θ^r表示在第r轮拍卖中未被分配的任务集合，表示在第r轮拍卖中已被分配的任务集合; M^r={m_j^r, j∈θ^r}，m_j^r=[x_j^r, y_j^r, z_j^r]表示在第r轮拍卖中第j个未被分配任务位置信息; T^r(tE)={t_j^r(tE), j∈θ^r}，t_j^r(tE)表示在第r轮拍卖中第j个未被分配任务能源信息; W^r={w_j^r, j∈θ^r}，w_j^r表示在第r轮拍卖中第j个未被分配任务类型信息; Z^r={z_j^r, j∈θ^r}，z_j^r表示在第r轮拍卖中第j个未被分配任务奖励信息。当r=1时，设置

式中：α∈(0, 1)为初始任务奖励调整因子。α越大，表示在第1轮拍卖时任务分配系统P支付的成本(任务奖励)越多; 相应的，AUV完成任务所获得的任务奖励也越多，会吸引更多的AUV投标。在本文算法中，并未将α设为1，其目的是为了使任务分配系统P不公布第j个任务的任务奖励上限值z_jmax，从而保留部分任务分配系统P与AUV “讨价还价”的空间。α越小，表示在第1轮拍卖时任务分配系统P付出的支付成本即任务奖励越少; 相应的，AUV完成任务获得的任务奖励也越少，会导致其效用值小于0，从而不参与投标。在保证任务分配系统P与AUV参与拍卖时所获得的利益大于不参与拍卖时所获得的利益的前提下设置α，从而保证拍卖过程顺利进行。

2) 投标阶段。每个收到任务信息Φ^r的AUV选择本轮效用集合θ^r}中效用最高的任务b，并向任务分配系统P递交投标d_i(b, y_ib)，b∈θ^r，y_ib为AUV投标任务b的效用。AUV_i效用y_ij^r的具体计算方法如下：

式中：若AUV_i满足约束条件(14)和(15)且与任务类型相匹配，则q=1，否则，q=0。

值得注意的是，利用鲁棒优化算法对抗不确定项，降低了不确定性因素对算法性能的影响，即AUV会更加保守地递交投标，提高了算法的鲁棒性，并且增强了多AUV任务分配系统应对复杂水下环境的能力。

在文献[18]的平行拍卖算法(parallel auction algorithm)和序贯拍卖算法(sequential auction algorithm)中，AUV对本轮任务分配系统P宣告的所有任务都递交投标。相比于平行拍卖算法和序贯拍卖算法，在本文算法中，每个AUV选择效用值最高的任务向任务分配系统P递交投标，这样能够保证AUV的效用。这是因为在此种投标方式下，无论任务分配系统P与哪个AUV达成合作，对于中标AUV而言，这种投标方式都能够保证此AUV的效用最大。如果AUV按照平行拍卖算法或者序贯拍卖算法的投标方式，那么当任务分配系统P与AUV利益不一致时，由于任务分配系统P是按照最大化自身利益来执行策略。那么会导致中标者被分配的任务不是对AUV而言最高效用的任务。

3) 中标者选择阶段。任务分配系统P收到AUV递交的投标后，统计在本轮中，满足分配条件L_jbid^r≥L_j, ∀j∈θ^r的任务数量L^r。

若本轮所有未分配任务都满足分配条件，即L^r=|θ^r|，则对于每个任务j∈θ^r，按照式(18)计算出第j个任务的成本集合C_j={c_ρj, ∀ρ∈B}，B为投标该任务点的AUV集合，c_ρj表示当任务分配系统P选择第ρ个AUV完成该任务时，任务分配系统P所需要花费的成本。

任务分配系统P在集合C_j中找到前L_j个值最小的c_ρj所对应的AUV作为中标者。任务分配系统P宣告所有中标者集合w_assigned，拍卖算法结束，任务分配完成。此时，任务分配系统P所付出的总成本C如下：

式中：λ_ij为决策变量，若第i个AUV最终被分配完成任务j，则λ_ij=1，否则，λ_ij=0。

所有中标AUV的总效用Y为

若本轮所有未分配任务中存在不满足分配条件的任务，即L^r≠|θ^r|，此时，对于任务j∈θ^r任务点的AUV供需情况存在以下3种情况：①如果L_jbid^r=L_j，表明该任务点供需平衡，恰好满足分配条件，不必再调整任务奖励，将任务j放入集合Ω₁中，与上述选择中标AUV步骤相同，选择L_j个中标AUV并通知其完成任务，重新更新即可。②如果L_jbid^r>L_j，表明投标该任务点的AUV过多，任务分配系统P仍然有调整任务奖励的空间，放入集合Ω₂中并进入阶段4。③如果L_jbid^r <L_j，表明投标该任务点的AUV过少，任务分配系统P仍然有调整任务奖励的空间，放入集合Ω₃中并进入阶段4。

4) 更新任务信息阶段。针对j∈Ω₂的情况，表明在第r轮拍卖中，投标该任务点的AUV数量超过该任务点需要的AUV数量，此时，供过于求。那么任务分配系统P需要下调任务奖励，以达到节约P的成本的目的。针对j∈Ω₃的情况，表明在第r轮拍卖中，投标该任务点的AUV数量低于该任务点需要的AUV数量，此时，供不应求。那么任务分配系统P需要上调任务奖励，以吸引更多的AUV下一轮投标该任务。针对上述问题，本文提出一种任务奖励反馈机制。

在第r轮中，任务分配系统P调整任务奖励的方程为

式中：若表示在第r轮拍卖中，与任务点j需求的AUV数量相比较，多余的投标AUV数量占AUV总数量的比值。投标该任务点的AUV数量越多，的比值越大，表明对于该任务的竞争越激烈，任务分配系统P可下调任务奖励z_j^r的空间也越大。因此，从式(21)中可以看出，的比值越大，任务分配系统P在本轮中下调的任务奖励也越多，任务分配系统P付出的成本也越少。

与上述情况类似，若L_jbid^r < L_j，则投标该任务的AUV数量越少，的比值越大，表明任务点j当前的任务奖励z_j^r不足以吸引更多的AUV投标该任务。需要上调更多的任务奖励z_j^r，从而满足下一轮任务点j的AUV数量需求。因此，从式(21)中可以看出，的比值越大，任务分配系统P在本轮中上调的任务奖励也越多，从而能够吸引更多的AUV在下一轮中投标该任务。

式(21)中，第2项z_jmax-z_j^r表示在第r轮拍卖中，最高任务奖励上限值z_jmax与本轮任务奖励值z_j^r的差值。一方面，z_jmax-z_j^r保证了在增加任务奖励后，也不会超过任务奖励上限值z_jmax，从而保证了任务分配系统P的利益，促进任务分配系统P拍卖任务。另一方面，此差值越大，表明本轮任务分配系统P(拍卖商)与AUV“讨价还价”的空间越大。因此，本轮任务奖励可调整的空间也会越大，拍卖商会在保证自身利益的条件下更大幅度地调整任务奖励，以更快地与AUV商议出一个双方均满意的任务分配结果。

通过上述任务奖励反馈机制，达到了自适应调节任务奖励的目的，任务分配系统P每轮通过分析任务点需要的AUV数量与投标任务点的AUV数量之间的差距来自适应调整任务奖励。通过多轮试探拍卖市场，达到既保证任务被AUV完成又不过多付出任务奖励的目的，从而能够节约任务分配系统P的成本。

任务分配系统P重新更新任务信息集合Φ^r，反馈到下一轮作为下一轮宣告的任务信息Φ^r+1={θ^r+1, M^r+1, T^r+1(tE), W^r+1, Z^r+1}。更新后的任务集合，任务位置集合M^r+1={m_j^r+1, j∈θ^r+1}，任务能源集合T^r+1(tE)={t_j^r+1(tE), j∈θ^r+1}，任务类型集合W^r+1={w_j^r+1, j∈θ^r+1}，任务奖励集合Z^r+1={z_j^r+1, j∈θ^r+1}。

本文算法流程如图 2所示。为使整个过程易于解释，图 2中只描述了任务分配系统P和一个AUV的情况。

图  2  分布式鲁棒拍卖算法流程

Figure  2.  Distributed robust auction algorithm flowchart

下载: 全尺寸图片 幻灯片

在整个任务分配过程中，任务分配系统P(拍卖商)需要的信息为任务奖励信息和投标信息(AUV选择哪个任务投标及递交的投标值)。其中，任务奖励信息为拍卖商的本地信息; 投标信息是通过与AUV信息交换得到的。AUV需要的信息为任务相关的信息(任务位置、任务所需能源、任务奖励)、与洋流相关的信息(洋流速度、洋流影响系数)及AUV自身信息(AUV速度、AUV与任务的匹配程度)。其中，与任务相关的信息是通过与任务分配系统P信息交换得到的; 与洋流相关的信息和AUV自身信息均为本地信息。在这个过程中，AUV并不需要清楚其余AUV的具体决策，只通过市场反馈回来的任务奖励调整自己的优化策略。任务分配系统P或者AUV任何一方并不能单独决定任务分配的最终结果，最终结果是通过双方“讨价还价”的结果共同决定的。双方是通过自发地追求自身利益最大化从而实现分布式的任务分配。

3.   仿真分析

为了验证本文算法的可行性和有效性，进行了不同情况下的仿真和对比实验研究。将本文算法与文献[18]中的平行拍卖算法和序贯拍卖算法进行比较，通过比较任务分配系统P的成本C和AUV的总效用Y来验证算法的性能。

假设水下随机分布15个任务(n=15)，24个AUV(m=24)，任务相关参数设置如表 1所示。

表  1  任务参数

Table  1.  Task parameters

任务序号θj	任务类型wj	任务能源tj(tE)	任务难度τj	需求AUV数量Lj
1	k	0.66	0.61	1
2	s	0.68	0.73	2
3	l	0.73	0.62	1
4	k	0.54	0.55	1
5	l	0.75	0.74	1
6	s	0.43	0.48	2
7	k	0.66	0.54	1
8	l	0.56	0.80	1
9	s	0.30	0.29	1
10	l	0.57	0.62	1
11	s	0.68	0.63	1
12	k	0.75	0.52	1
13	k	0.56	0.47	1
14	l	0.78	0.73	1
15	s	0.34	0.14	1

下载: 导出CSV 

| 显示表格

图 3中，柱状图表示每个任务点任务分配系统P最终实际支付给中标AUV的任务奖励值z_j，折线图上的点表示每个任务点任务分配系统P能够支付给AUV的任务奖励上限值z_jmax，折线图上的点与柱形图上的点的差值表示任务分配系统P少支付给中标AUV的任务奖励。从图 3可以清晰看出，任务分配系统P最终没有支付给AUV每个任务的任务奖励上限值，因此任务分配系统P能够赚取一部分任务奖励，从而验证了本文算法的最终分配结果严格满足了式(4)的任务奖励约束条件，有利于提高任务分配系统P的积极性，促进任务分配系统P参与拍卖。

图  3  每个任务点的任务奖励情况

Figure  3.  Task rewards for each task point

下载: 全尺寸图片 幻灯片

图 4为鲁棒解和标称解的AUV总效用值Y的对比。图中：在不同的不确定界下得到鲁棒解，利用洋流影响因子的标称值得到标称解。从图 4能够清晰看出，鲁棒解的Y值高于标称解的Y值，并且两者性能差距随着不确定度δ的增大而增大。这是由于引入了鲁棒优化理论对抗不确定因素，提高了多AUV任务分配系统应对复杂水下环境的能力。

图  4  鲁棒解和标称解Y值的比较

Figure  4.  Comparison of Y values between robust solutions and nominal solutions

下载: 全尺寸图片 幻灯片

表 2和表 3表示当α分别为0.6, 0.7, 0.8, 0.9时，3种算法的任务分配系统的成本C和AUV的总效用Y的比较。当α小于0.6时，Y小于零，没有AUV参与投标，不符合限制条件式(15)，当α大于0.9时，任务分配系统P第1轮公布的任务奖励会超过任务奖励上限值z_jmax，不满足限制条件式(4)，以上2个条件是保证拍卖过程顺利进行的必要条件，因此仅选取α在0.6~0.9时进行仿真验证。C越小、Y越大表示算法的性能越好。从表 2、表 3可以看出，α值无论如何变化，本文算法在任务分配系统的成本C与AUV的总效用Y方面均优于平行拍卖算法和序贯拍卖算法。

表  2  不同α下3种算法的C值比较

Table  2.  C value comparison of three algorithms under different α

α	C
	本文算法	平行拍卖算法	序贯拍卖算法
0.6	4 988.2	5 205.8	5 092.9
0.7	5 875.8	6 032.6	5 919.7
0.8	6 459.9	6 859.5	6 746.6
0.9	7 072.5	7 686.3	7 573.4

下载: 导出CSV 

| 显示表格

表  3  不同α下3种算法的Y值比较

Table  3.  Y value comparison of three algorithms under different α

α	Y
	本文算法	平行拍卖算法	序贯拍卖算法
0.6	2 103.5	1 981.7	2 094.6
0.7	2 593.5	2 354.5	2 467.4
0.8	2 920.2	2 727.2	2 840.1
0.9	3 247.9	3 100.0	3 212.9

下载: 导出CSV 

| 显示表格

为了验证本文算法的有效性，分别对AUV数量m不相同情况下的算法性能进行了仿真对比，仿真结果如图 5、图 6所示。

图  5  不同AUV数量下3种算法的C值比较

Figure  5.  C value comparison of three algorithms under different AUV numbers

下载: 全尺寸图片 幻灯片

图  6  不同AUV数量下3种算法的Y值比较

Figure  6.  Y value comparison of three algorithms under different AUV numbers

下载: 全尺寸图片 幻灯片

图 5表示在任务数量n=15，AUV数量m分别为24, 26, 28, 30, 32和34情况下3种算法的任务分配系统P的成本C对比。从图 5可以看出，当m变化时，本文算法的C值远远低于其余2种算法。这是由于任务奖励反馈机制使任务分配系统P通过多轮试探拍卖市场，达到既保证任务被AUV完成又不过多付出任务奖励的目的，从而节约了任务分配系统P的成本C，验证了本文算法的有效性。在图 5中，AUV数量m不同时，曲线呈现出波动变化。这是由于m增加时，任务分配系统P所选择的中标AUV发生变化，导致C值也会不断发生变化。

图 6表示在任务数量n=15，AUV数量m分别为24, 26, 28, 30, 32和34情况下3种算法的AUV总效用Y对比。从图 6可以看出，m变化时，本文算法的Y值远远高于其余2种算法，并且随着AUV数量m的增加，本文算法优势更加明显。这是由于在平行拍卖算法或序贯拍卖算法中，AUV对本轮公布的所有任务都递交投标，那么当任务分配系统P与AUV利益不相同时，会导致中标AUV被分配的任务不是对AUV而言最高效用的任务。随着AUV数量的增加，存在上述情况的概率会增大，因此当m增加时，本文算法的优势会更加明显。在图 6中，AUV数量m不同时，曲线呈现出波动变化。这是由于m增加时，中标AUV会发生改变，导致AUV的总效能Y会不断发生变化。

分别对任务数量n不相同的情况下的算法性能进行仿真对比，仿真结果如图 7、图 8所示。

图  7  不同任务数量下3种算法的C值比较

Figure  7.  C value comparison of three algorithms under different task numbers

下载: 全尺寸图片 幻灯片

图  8  不同任务数量下3种算法的Y值比较

Figure  8.  Y value comparison of three algorithms under different task numbers

下载: 全尺寸图片 幻灯片

图 7表示在AUV数量m=34，任务数量n分别为10, 13, 16, 19, 22和25情况下，3种算法的任务分配系统P的成本C的对比。从图 7可以看出，随着n的增加，3种算法的C值不断增加。这是由于随着n的增加，任务分配系统P所支付的任务奖励必然会增加，因此，任务分配系统P的成本C也必然会随之增加。从图 7还可以清晰看出，与平行拍卖算法和序贯拍卖算法算法相比，本文算法的C值更小。

图 8表示在AUV数量m=34，任务数量n分别为10, 13, 16, 19, 22和25情况下，3种算法的AUV总效用Y的对比。从图 8可以看出，随着n的增加，3种算法的Y值不断增加。这是由于随着n的增加，相应的中标AUV数量也会增加，因此，AUV的总效用Y也会随之增加。从图 8还可以清晰看出，与平行拍卖算法和序贯拍卖算法算法相比，本文算法的Y值更大。由于本文算法能够保证中标者每轮被分配的任务都是对AUV而言最高效用的任务，本文算法的AUV总效用高于其余2种算法。

4.   结论

1) 针对异构多AUV任务分配问题，建立了异构多AUV任务分配分布式拍卖模型。

2) 针对现有拍卖算法忽略拍卖商利益的问题，设计的任务奖励反馈机制在保证任务被AUV完成的同时，又降低了任务分配系统的成本。

3) 针对水下洋流对任务分配模型产生的不确定性因素，提出了鲁棒优化理论对抗不确定因素，提高了多AUV任务分配系统应对复杂水下环境的能力。

4) 仿真结果表明，本文算法能够在保证AUV效用的同时，降低任务分配系统的成本，并且在复杂水下环境中表现出了较强的鲁棒性和可适用性。