基于改进拍卖算法灾后救援多无人机任务分配

许 可高宏宇雷 鸣叶彩霞

(沈阳理工大学a.理学院，b.自动化与电气工程学院，沈阳 110159)

由于无人机体积小、成本低、机动性高等特点，可以有效代替人类深入灾区完成搜索侦察任务，以协助制定救援方案[1]。 在大型灾难救援中，如何制定一个合理的无人机侦察任务分配方案，对于减少灾害损失具有重要意义。

目前，针对多无人机灾后救援任务分配问题的研究越来越多。 张祥银等[2]考虑幸存者援助类型不同，以最小化平均等待时间为目标函数，建立多无人机协同任务分配模型。 李松锐等[3]以搜救费用、无人机使用数量、完成任务的均衡性为目标函数，建立多目标多无人机任务分配模型。 张小孟等[4]以最小化无人机总滞空时间及最大化救援总收益为优化函数，建立价值随时间变化的多无人机任务规划模型。 Liu 等[5]考虑无人机飞行距离、油耗等因素构造成本－收益函数，建立多无人机任务分配模型。 综上，在多无人机灾后救援问题中主要考虑了飞行距离、时间、油耗及收益等因素，较少综合考虑灾区地形及飞往灾区途中是否遇到障碍物，事实上由于灾区地形不同、飞行途中遇到的障碍物不同，无人机执行任务的时间也有所不同，考虑上述因素对无人机的影响更加符合实际情况。

早期，学者常采用传统的组合优化算法解决无人机任务分配问题。 刘典宏等[6]构建侦察预警任务分配动态规划模型，通过递推方程求解得到侦察预警任务分配方案。 李瑞阳等[7]以最小化飞行成本为目标建立无人机任务分配模型，并应用列生成算法对分配方案进行优化选择。 近来，学者将智能优化算法用于求解无人机任务分配问题。 王树朋等[8]针对多无人机协同任务分配问题，提出一种自适应遗传算法。 Wu 等[9]将无人机性能和任务特征作为评价函数，提出一种基于改进模拟退火的融合遗传算法。 Alhaqbani 等[10]在时间有限的搜索和救援任务中，提出一种基于鱼群的无人机任务分配算法。

动态规划在求解问题时可以将复杂问题拆分为多个子问题，在每个子问题中进行最优决策，从而得到全局最优解。 宫华等[11]针对批处理机生产与成批配送协调调度问题，设计了基于动态规划的生产调度优化方法。 王小明等[12]针对传统动态规划在求解大规模问题时面临的维数灾难问题，提出近似动态规划的求解方法。 张玉敏等[13]针对随机动态调度模型难以高效求解的问题，提出一种并行多维近似动态规划算法。 Agarwal等[14]提出了一种差分动态规划算法解决多周期最优功率流，并能扩展到包含储能设备的大型系统中。 陆坚毅等[15]针对电动汽车的充电调度问题，提出单亲遗传混合动态规划的两阶段充电调度算法。 上述动态规划算法在调度领域有着广泛的应用，但鲜少应用在无人机任务分配中。

拍卖算法在求解任务分配问题时可以协同考虑各拍卖方对不同任务的需求，能较好地解决任务分配冲突问题。 许可等[16]设计了带共享存储中心的分布式拍卖算法，并结合最大一致性算法将共享存储中心移除。 李鑫滨等[17]针对异构多自主式水下航行器任务分配问题，提出一种分布式鲁棒拍卖算法。 Otte 等[18]针对多机器人资源和有限的通信范围，提出一种基于G-Prim 改进的拍卖算法。 Bai 等[19]设计了基于分组的分布式拍卖算法解决多机器人任务分配问题。 Zhang 等[20]研究多无人机动态任务分配问题，提出一种基于混合市场机制的动态任务分配方法。 王然然等[21]针对无人机任务分配问题，提出一种分布式合同网拍卖算法。 张梦颖等[22]针对无人机群实时任务分配问题，提出改进合同网拍卖算法。 王轩[23]提出在发生无人机损毁情况下基于改进合同网拍卖机制对任务进行重分配。 综上，拍卖算法在任务分配问题中得到广泛使用。 但拍卖算法在获得分配方案时仅考虑单个任务的价值，忽视了无人机的整体收益，易陷入局部最优，而动态规划算法可在全局范围内考虑无人机的收益，得到每个无人机的最优任务序列，使无人机的分配更加合理。

1 无人机灾后救援问题研究

1.1 问题描述

某地区有B个无人机基地，基地qo(o＝1，…，B)中有不同性能的无人机，无人机U＝{ui｜i＝1，…，nu}，总数量为nu，其续航时间Hi及飞行速度Vi不尽相同。 灾难发生后无人机要前往nt个灾区执行侦察任务M＝{mj｜j＝1，…，nt}，不同地形的灾区无人机探测范围不同。 无人机进入长Lj、宽Wj的灾区后，以rp(p＝1，2，3)为探测半径沿Lj方向进行侦察，到达灾区边缘时转弯以反方向继续侦察，往复进行，直至整个灾区侦察结束。无人机侦察灾区过程如图1 所示。 基地到灾区途中可能存在障碍物，无人机遇到需要绕行。 为保证灾难救援的及时性，要求无人机执行任务总时间最短。

图1 无人机侦察灾区示意图Fig.1 UAV reconnaissance disaster area diagram

为使求解问题方便，给出如下假设:

1)将灾区近似为矩形，无人机以往复回旋的方式在灾区进行侦察；

2)无人机转弯半径等于探测半径；

3)无人机匀速飞行，自起飞后就保持最大巡航速度；

4)对障碍物进行投影，将投影形状的外接圆弧线看作其绕过障碍物路线；

5)无人机执行任务时不会出现故障或损毁。

1.2 参量描述

各参量符号及说明如表1 所示。

表1 参量符号说明Table 1 Parameter symbols description

1.3 模型建立

将无人机执行任务时间分为无人机往返基地时间、无人机侦察灾区时间、无人机绕过障碍物时间。 以最小化无人机执行任务时间和为目标函数建立多无人机侦察任务分配模型为

其中

无人机侦察灾区时间为

不同地形无人机探测半径为

无人机躲避障碍物时间为

式(7)定义决策变量；式(8)约束无人机执行任务时间小于其续航时间；式(9)约束每个任务只能分配给一个无人机。

2 混合动态规划的改进拍卖算法

本文设计了基于混合动态规划的改进拍卖算法(hybrid dynamic programming auction，HDPA)求解多无人机灾后侦察任务分配问题。 首先，采用动态规划算法求出每个无人机执行的最优任务集合，然后设计任务价格更新规则解决不同无人机之间的分配冲突问题，最终求得最佳分配方案。

2.1 拍卖算法的基本思想

拍卖算法本质上是投标者根据自身收益对商品进行投标，经过多轮投标迭代，最终得到使投标者满意的分配方案。

将无人机看作投标者，将任务看作商品，每个无人机根据执行任务所获收益进行投标。 投标价格高的无人机即可执行该任务，若投标过程中无人机执行任务集产生冲突则根据价格更新规则给出下轮投标出价，经多轮迭代，无人机间无冲突产生，即得到每个无人机执行任务集。 将无人机执行任务所需时间进行价值化处理，即无人机ui执行任务mj所获得的价值为cij(cij＝)。 在第τ轮投标迭代中，投标任务mj的最高出价记为pj(τ)，此时该任务对于ui的收益为vij(τ) ＝cij－pj(τ)。表示对于无人机ui价值第y大的任务下标，表示对于无人机ui价值最大的前n∗个任务对应的下标集。

为避免不同无人机间的冲突导致算法无法进行求解，给定参数ε>0，若无人机ui满足下式

称无人机ui得到较优的分配方案集合Ji。

2.2 基于动态规划的单无人机任务分配

为获得较优的无人机执行任务初始分配方案，将多无人机任务分配问题分解为单个无人机的优化问题，并采用动态规划算法对每个无人机需执行的任务进行初始分配。

单无人机任务分配问题如下:给定无人机ui和nt个任务，ui执行任务mj的时间为Tij，所获得的收益为vij，无人机ui须在其续航时间Hi内执行多个任务使其获得的总收益最大，其数学描述为

采用动态规划算法求解上述问题时需证明其最优子结构性质。 即若上述原问题的最优解为[xi1，xi2，…，xint]，则子问题为

其最优解为[xi1，xi2，…，xint－1]。

假设[xi1，xi2，…，xint－1]不是子问题的最优解，那么子问题至少存在一个更好的解[，…，，满足

由此构造原问题的新解

式(18)与原问题解矛盾，假设不成立，由此得证上述问题满足最优子结构性质，可递归定义问题的最优值。

设f[j][z]为子问题的最优值，表示当无人机续航时间为z时，执行{m1，m2，…，mj}中任务所获得的收益最大值。 对于当前任务mj存在两种情况:

1)当前无人机续航时间z小于任务mj执行时间，则放弃执行该任务，此时问题的最优值为f[j－1][z]；

2)当前无人机续航时间z大于等于任务mj执行时间时，若无人机ui执行任务mj所获得总收益大于f[j－1][z]则执行任务mj，否则不执行，递归式如下。

由此设计单无人机任务分配动态规划算法执行过程如下。

算法1:动态规划(Dynam)

输入:vij，Hi，Tij

输出:Ji∥无人机ui执行的任务集

∥计算单无人机执行任务最优总价值

f[0][z] ＝0，∀z＝1，…，Ti

f[j][0] ＝0，∀j＝1，…，nt

forj＝1:ntdo

forz＝1:Hido

ifz≥Tijthen

f[j][z] ＝max(f[j－1][z]，f[j－1][z－Tij] ＋vij)

else

f[j][z] ＝f[j－1][z]

end if

end for

end for

j＝nt，z＝Hi，Ji＝∅

∥追溯最优分配

whilej>0 do

iff[j][z]≠f[j－1][z] then

z＝z－Tij

Ji＝Ji∪{j}

end if

j＝j－1

end while

2.3 基于HDPA 算法多无人机任务分配

通过动态规划算法得到单无人机执行任务集，但对多无人机进行分配时易发生任务之间的冲突问题。 基于此设计价格更新规则如下。

当任务mj在无人机ui的当前任务序列Ji中，pj(τ＋1) ＝cij，否则，pj(τ＋1) ＝pj(τ)。

利用价格更新规则对任务进行报价，根据无人机收益对单无人机任务集中进行重分配，以避免任务冲突问题。 混合动态规划的改进拍卖算法执行过程如下。

算法2:混合动态规划的改进拍卖算法

输入:cij，Tij，pj(τ)，Hi

J′i∥上一轮投标分配给ui的任务集

{b′j｜j∈J′i}∥上一轮投标报价

输出:pj(τ＋1)，Ji

whileτ≤Cdo

fori＝1:nudo

∥之前迭代中分配的任务价格重置为零

forj∈J′ido

ifpj(τ) ＝＝b′jthen

pj(τ) ＝0

pj(τ＋1) ＝0

end if

end for

∥收集新的投标信息

vij(τ) ＝cij－pj(τ)

Ji＝Dynam(vij(τ)，Hi，Tij)

∥开始投标并更新价格信息

forj∈Jido

bj＝cij，pj(τ＋1) ＝bj

end for

for taskj∉Jido

pj(τ＋1) ＝pj(τ)

end for

end for

end while

定理1HDPA 收敛到可行解。

证明:在无人机ui的每次迭代中，算法1 优化了无人机ui的总收益，价格更新规则保证了在任务分配过程中总分配收益不降低。 此外，无人机总分配收益受所有任务价值之和的限制。 因此，算法2 收敛。 算法1 保证满足约束(7)和(8)。任务价格更新规则保证了所有任务要么保持未分配状态，要么从一个无人机切换到另一个无人机。所以约束(9)可满足，可得出算法2 收敛于一个可行解。

通过算法1 中的两层for 循环可知其时间复杂度为O(Hint)，由于算法1 内嵌到算法2 中，且算法2 需对nu个无人机执行的任务序列进行优化，所以算法2 的时间复杂度为，其中C为HDPA 的迭代次数。

3 实验分析

3.1 仿真环境及数据设定

实验采用Intel(R)Core(TM)i5-8265U CPU＠ 1.6 GHz 1.8 GHz 处理器，8 G 运行内存，500 G 硬盘，Matlab R2017b 编程软件实现。

为验证本文算法的有效性，设计如下实例进行仿真实验。 设任务区域为800 km ×500 km 的矩形，其卫星图如图2所示。将矩形区域进行坐标化，把无人机基地及灾区中心视为坐标点，如图3 所示。 灾区分为平原、山地和森林3 种地形，在平原中ζ1＝1，实际探测半径与原始探测半径同为7 km；在山地中ζ2＝0.85，实际探测半径为6 km；在森林中ζ3＝0.71，实际探测半径为5 km。 无人机参数信息、任务属性与障碍物信息如表2、表3 所示。

表2 无人机参数信息Table 2 UAV parameters information

表3 任务属性与障碍物信息Table 3 Task property and obstacle information

图2 任务区域地形图Fig.2 Topographic map of the task area

图3 无人机基地与灾区坐标图Fig.3 Coordinate graph of UAV base and disaster area

3.2 实验结果

应用上述实验数据，采用HDPA 算法对问题进行求解，得到无人机任务分配结果，如表4所示。

表4 无人机任务分配Table 4 Task assignment of UAV

根据表4 知18 项任务均已得到无人机分配，无人机执行任务总花费时间为212.37 h。

图4 为目标函数的迭代曲线图，从图4 可以看出HDPA 算法经3 次迭代便可收敛，其收敛速度较快。

图4 目标函数迭代曲线图Fig.4 Objective function iteration curve

3.3 实验对比

为验证算法的有效性，分别在nu＝9、nt＝18实验规模下和nu＝27、nt＝55 实验规模下，采用传统的拍卖算法、遗传算法、海洋捕食者算法(marine predators algorithm，MPA)和HDPA 对问题求解并进行对比分析。 为增强实验说服力，将无人机参数信息进行相同设置，即无人机续航时间为32、30、28 h，巡航速度为150、200、300 km/h，并对算法独立运行10 次，最终结果取其平均值。

在nu＝9、nt＝18 实验规模下算法对比结果如表5、图5 所示。

表5 nu ＝9，nt ＝18 无人机执行任务时间Table 5 nu ＝9，nt ＝18 UAV task execution time

图5 nu ＝9，nt ＝18 规模下迭代对比图Fig.5 Iterative comparison chart under nu ＝9，nt ＝18 scale

由表5 可知，采用HDPA 算法对无人机侦察任务进行分配可以提高时间的利用率，相比拍卖算法总用时提高3.5%，相比遗传算法提高4.4%，相比MPA 提高2.5%。 此方案充分考虑到大多数无人机对于不同任务的需求，使各无人机分配到较优的任务。 由图5 知，遗传算法达到较优解时的迭代次数比拍卖算法少，但所求的解差于拍卖算法，MPA 达到收敛代数多于遗传算法但少于拍卖算法，而HDPA 算法仅经过3 次迭代就能达到稳定值，且求得的解优于拍卖算法、遗传算法与MPA。

在nu＝27、nt＝55 实验规模下算法对比结果如表6、图6 所示。

表6 nu ＝27，nt ＝55 无人机执行任务时间Table 6 nu ＝27，nt ＝55 UAV task execution time

图6 nu ＝27，nt ＝55 规模下迭代对比图Fig.6 Iterative comparison chart under nu ＝27，nt ＝55 scale

由表6 可知，采用HDPA 算法求得分配方案总用时为621.14 h，相比于拍卖算法、遗传算法和MPA 分别提高了3.4%、6.8%和7.0%。 由图6知，拍卖算法、遗传算法、MPA 经过多次迭代达到稳定值，而HDPA 仅经过3 次迭代便能达到稳定值，其迭代次数有较大提升。

为进一步对比算法，在不同规模下计算不同算法求解无人机执行任务的平均时间及方差。 对比结果如表7 所示。

表7 不同规模无人机执行任务平均时间及方差Table 7 The average time and variance of different scale UAV performing task

由表7 可以看出，在不同的实验规模下，HDPA 求得的无人机侦察任务分配方案平均耗时均优于其他算法，且相比拍卖算法、遗传算法和MPA 方差缩小了48.5%、56.7%、62.9%，表明HDPA 实现了各无人机负载均衡，且相比其他算法所求得的分配方案有较大提升。 因此，本文算法在求解多无人机灾后侦察任务分配问题时具有更高的效率。

4 结束语

本文在灾后救援环境下针对多无人机侦察任务分配问题进行研究。 考虑无人机续航时间、灾区地形以及是否遇到飞行障碍等因素，以无人机执行任务时间最小为目标函数建立多无人机侦察任务分配模型。 设计了HDPA 算法对模型进行求解。 在不同的实验规模下进行仿真分析并与传统的拍卖算法、遗传算法、MPA 进行对比。 结果表明，采用HDPA 算法求解多无人机灾后侦察任务分配问题是可行的，且相较于传统的拍卖算法、遗传算法、MPA 效率更高。 本文在研究多无人机灾后侦察任务分配问题时并未考虑不同任务之间的路径，未来在灾后救援背景下，进一步研究基于航路规划的多无人机任务分配问题。