2. 天津大学电气自动化与信息工程学院, 天津 300072
2. School of Electrical and Information Engineering, Tianjin University, Tianjin 300072, China
0 引言
随着无人机(unmanned aerial vehicle，UAV)技术的快速发展，UAV在军事、民用领域内的应用越来越广泛，而无人机任务分配问题是无人机应用中的重要问题[1-3].在无人机任务分配问题中，任务类型(如侦查任务、运输任务、攻击任务等)、任务量级、无人机的性能以及携带的有效载荷都会有所区别.因此，在考虑无人机性能以及任务类型约束下，如何分配无人机去执行相关任务时使得系统总收益最大是无人机系统亟待解决的问题[2-3].
现有研究多无人机任务分配问题的算法中主要有集中式和分布式两种.相对于集中式算法，分布式算法对通信中心依赖性小，可扩展性和鲁棒性都较好，同时随着无人机性能和自主能力的增强，通信受限下基于分布式算法的无人机任务分配问题受到越来越广泛的关注[3-5].大量学者研究了无人机分布式任务分配方法，比如一致性理论[6-9]、对策论[10]、聚类算法[11]、次梯度算法[12]、多智能体[13]、拍卖算法[14-17]等，其中基于市场机制的拍卖算法具有计算复杂性低，运行效率高的优点，尤其适用于分布式任务分配问题.
Bertsekas首先提出拍卖算法，运用带共享存储中心的拍卖算法解决了简单的单个任务分配问题[18]. Zavlanos等结合一致性算法与拍卖算法，去掉共享存储中心，对简单任务分配问题提出了完全分布式的算法[6].邸斌等针对异构无人机的协同任务分配问题，采用信息熵描述任务的代价与收益，设计基于局部通信带拍卖中心的分布式拍卖算法[14].赵明明等针对多无人机实现同时攻击目标的任务，设计了不确定信息下的拍卖算法使无人机到达目标的时间趋于一致[16].吴俊成等针对空中作战的目标任务分配问题，将拍卖算法与遗传算法对比，说明在针对局部重点目标时，拍卖算法的性能更优[17].邓启波基于分层思想对UAV进行编组，对分布式系统局部任务分配问题，考虑任务之间的关联设计了基于拍卖思想的求解流程[8].程聪[15]、丁臻极[2]针对动态突发条件下任务的重分配问题，设计了相应的拍卖算法.
但是，在上述无人机任务分配问题中一般都认为任务之间相互独立，不考虑无人机自身能量限制.事实上由于续航能力、有效负载等条件限制，每个无人机可以执行的任务数量一定是有限的.另外，任务具有不同类型，比如在军事问题中，任务有侦查任务、打击任务等；在灾难救援中，任务有搜索任务、人员解救任务、物资投放任务等.由于无人机携带的有效载荷限制，每个无人机执行每种类型任务的数量是有限的，此时，就需要对任务按照类型及其相关性进行分组并确定组内执行任务数量限制.
本文针对多无人机分组任务分配问题，在考虑无人机能力限制、分组限制等约束下，建立数学模型，基于拍卖算法设计求解该模型的分布式算法.
1 多无人机分组任务分配问题模型有nu个无人机组成的无人机集合U={u1, u2, …, unu}，包含nt个任务的任务集合T={t1，t2，…，tnt}，假设每个无人机可以执行任意任务，要求当任务分配完毕后，所有任务都必须被执行，而且每个任务只能分配给一个无人机.由于续航能力以及携载限制，每个无人机最多可以执行Ni个任务，显然
|
其中，wi表示ui的单位飞行成本.匹配度sij可以根据无人机组本次执行的任务属性定义，比如如果执行的是运输任务，那么匹配度sij可以定义为
|
其中，ci为ui的理想载重量，mj为tj对应物品的重量.
决策变量定义为
|
总体目标是给定nt个任务的分配方案，使总收益最大.那么多无人机分组任务分配问题(MUAP-GT：multi-UAV task assignment problem for grouped tasks)可以描述为
|
(1) |
|
(2) |
|
(3) |
|
(4) |
|
(5) |
式(1)为目标函数，表示总收益最大.式(2)~式(5)为约束条件，式(2)表示每个任务必须分配给一个机器人，式(3)表示每个无人机最多可以执行Ni个任务，式(4)表示，每个无人机最多可以执行Nk，i个Tk中的任务.
2 基于分布式拍卖算法的MUAP-GT算法设计事实上，上述多无人机分组任务分配问题(MUAP-GT)，可以归结为最小费用流问题，采用集中式算法在多项式时间内求解[19].但是在无人机系统中，如果采用控制中心执行算法统一分配任务的方式，系统的可扩展性以及鲁棒性往往较弱，因此有必要设计MUAP-GT的分布式算法.下面首先设计具有共享存储中心的分布式算法，接下来进一步讨论如何去掉共享存储中心并提出完全分布式的算法.
2.1 MUAP-GT的对偶分解在前面的MUAP-GT中
|
(6) |
根据对偶分解原理[19]，通过将约束条件(2)对偶化，MUAP-GT的对偶优化问题可写为
|
(7) |
其中，pj是与约束(2)中tj对应的对偶变量，称为tj的价格，记p={p1，p2，…，pn}.由对偶问题(7)可知，如果价格向量p固定，可以通过对每个无人机ui求解下述问题实现整体目标：
|
(8) |
下面设计求解上述问题的拍卖算法[18].算法在每轮迭代中，每个无人机求解优化问题(8)，为能使自身获得最大收益的任务出价，当价格向量不再发生变化的时候算法停止，当然可能会出现多个无人机竞争同一任务的情况，此时就需要价格更新确保算法收敛并且没有分配冲突[21].
2.2.1 基本概念描述第τ轮迭代中tj的价格记为pj(τ)，则此时该任务对于ui的价值记为vij=aij- pj(τ)，记jkl表示Tk中对于ui价值第l大的任务的下标，Jk*表示在Tk中对于ui价值最大的前Nk，i个任务对应的下标集，ViJk*为相应任务的价值集，即：
|
记
|
(9) |
当满足式(9)时，称无人机ui是满意的，当所有无人机达到满意，称整个任务分配方案与价格达到均衡.为避免几个无人机竞争对其来说价值相等的任务，同时出价不变算法陷入死循环，给定增量ε>0，保证出价递增，如果所有分配给ui的任务都满足：
|
(10) |
称ui基本满意，如果所有无人机基本满意，称整个任务分配方案与价格达到基本均衡.
2.2.2 价格更新规则在拍卖算法中，每个无人机ui需要为Ji中的任务出价，因此价格更新规则是拍卖算法的核心.设j′k是Tk中除Jk*中的任务之外价值最大的任务下标，即：
|
设jm*是Ji*中第Ni+1大价值任务的任务下标，m是该任务所在的组别，则
|
(11) |
式中参数ε保证价格出价至少以ε增加，避免算法陷入死循环.
2.2.3 算法步骤无人机ui对于任务tj的出价记为pji，基于拍卖的MUAP-GT分布式算法应包含以下步骤：
Step 1 初始化：置τ=0，pj(τ)=0，j=1，2，…，n.
Step 2 投标阶段：ui利用价格向量[p1(τ), p2(τ), …，pn(τ)]计算需要投标的任务集Ji，根据价格更新规则(11)计算出价pji(τ+1)，并将价格传送给拍卖中心.
Step 3 价格一致性阶段：令pj(τ+1)=maxi{pji(τ +1)}，∀j=1，…，n.并向所有无人机广播pj(τ+1).
Step 4 收敛条件：如果pj(τ+1)=pj(τ)，∀j=1，…，n，算法停止；否则令τ=τ+1，转向Step 2.
在上述步骤中最关键的是投标阶段，投标阶段每个无人机详细计算步骤见算法1(如图 1所示).
|
| 图 1 算法1 Figure 1 Algorithm 1 |
记Ji(τ)表示在第τ轮迭代中，ui想要竞标的任务下标集，Ki(τ)是这些任务所在组Tk的下标集，ui在第τ轮迭代的出价向量记为pi(τ)，p是一致性阶段之后所有任务的价格构成的价格向量.
在上面的算法迭代中可能会出现这样的情形：有两个或两个以上无人机对同一任务出价相同，并且该价格为该任务的当前最高出价，此时当本轮迭代终止时，这几个无人机都会认为该任务分配给了自己，为避免这种情形出现，可以给每个无人机设定优先级，当出价相同时，把任务分配给优先级较高的无人机，共享存储中心在广播任务价格的时候同时广播该无人机标识.
前面设计的MUAP-GT分布式拍卖算法的时间复杂度为
在上面描述的MUAP-GT算法中，共享存储中心负责收集价格信息并向所有无人机广播.在本节中，将结合最大一致性算法[6]，讨论如何将共享存储中心去掉，使算法变为完全分布式的算法.
用图G(V，E)来表示无人机通信网络的拓扑结构，图中点的集合V表示无人机集合U，E表示连接各节点的边，如果两个无人机在通信距离内，则存在连接对应两个节点的边，此时这两个无人机可以彼此通信.如果网络中的任意两个节点至少存在一条链路，则称网络是连通的[21].在下面的完全分布式拍卖算法中，不妨假设整个网络G是连通的.
在完全分布式算法中，由于没有拍卖中心收集并广播价格信息，无人机ui并不知道任务tj的全局最高价格，在每轮迭代开始之前，它只通过与其相连的邻居节点更新本地任务价格：
|
(12) |
其中，pji(τ)表示在第τ轮迭代开始之前，ui存储的tj的价格；Ni+={i}∪Ni，Ni表示G中与ui存在边的邻居节点.显然，如果整个网络是连通，通过不断与邻居节点进行通信，ui最终也可以获得任务tj的最高出价pj.如果用ui*表示对任务tj出价为pj的无人机，那么ui获得pj需要的迭代次数就等于从ui到ui*最短路径的长度，记为duiui*.
基于上述讨论，在算法1的开始增加价格信息交互部分，即每个ui采用式(12)更新价格信息，最多max{duiuj，i，j=1，…，nu}轮即可获得全局价格.
4 仿真实验与结果分析假设某无人机军事基地有20架无人机出发针对某区域执行侦查、评估、打击、物资投放等任务.区域范围100 km×100 km，其中随机分布着60个任务点，即nu=20，nt=60.任务根据类型可以分为4组，即ns=4，每组15个任务.无人机ui的任务能力限制Ni=3，i=1，2，…，20；分组约束Nk，i=1，k=1，2，3，4，i=1，2，…，20.收益aij由在(0，20)上的均匀分布随机产生.
算法在Windows 10系统下，内存为4G，Matlab 2014a环境下运行.
根据前面的描述，ε是算法的关键参数，直接影响解的性能，下面测试不同ε取值对本文设计算法的求解效率与解的性能的影响.
图 2是不同ε取值与算法求得分配方案的总收益之间的关系，可以看出来随着ε的增大总收益也就是目标函数值总体趋势越来越小，随着ε的减小总收益越来越大.但是当ε缩小到一定程度时，目标函数值不再变化，为了能更清楚地看出这一点，在图 2的右上角放大了ε的取值在[0.001, 0.01]时的总收益值，很明显当ε < 0.08时，总收益基本不再变化，当ε < 0.06时，缩小其取值除了增加算法的求解时间并不能提高目标函数值，此时求得的总收益与最优值基本相等.值得注意的是，算法的整体性能较好，即使当ε>3.5时，总收益与最优值的误差也不超过4%.
|
| 图 2 参数ε的取值对算法求得分配方案总收益的影响 Figure 2 Impaction of parameter ε on the total payoffs of assignment by our algorithm |
图 3是不同ε取值与算法停止所需迭代次数即投标次数之间的关系，可以看出随着ε的增大，算法收敛所需要的迭代次数总体趋势越来越小，当ε>2.5迭代次数基本不变，保持在10次左右.
|
| 图 3 参数ε的取值对算法迭代次数的影响 Figure 3 Impaction of parameter ε on the number of algorithm′s iteration |
综合图 2和图 3可以看出，ε的取值在[0.008，3]时，对算法效率和解的性能影响较大，当ε < 0.08时，虽然总收益值基本等于最优值，但此时迭代次数接近90次，速度较慢；当ε>2.5时，虽然算法运行10次左右即可收敛，但此时与最优解差距相对较大.综合比较可知，ε的取值在[1，1.5]之间时结果较好，此时算法迭代20次左右即可收敛，解的误差也不超过2%.
表 1是当ε=1时的任务分配方案，任务后面括号内的数字表示该任务所在的组数，按照该方案执行获得的总收益为1 127.9.
| 无人机 | 执行的任务 |
| u1 | t13(1)，t40(3)，t47(4) |
| u2 | t23(2)，t31(3)，t55(4) |
| u3 | t1(1)，t20(2)，t56(4) |
| u4 | t5(1)，t22(2)，t33(3) |
| u5 | t17(2)，t39(3)，t48(4) |
| u6 | t8(1)，t32(3)，t49(4) |
| u7 | t15(1)，t29(2)，t53(4) |
| u8 | t12(1)，t27(2)，t57(4) |
| u9 | t10(1)，t16(2)，t34(3) |
| u10 | t4(1)，t21(2)，t44(3) |
| u11 | t7(1)，t24(2)，t43(3) |
| u12 | t25(2)，t38(3)，t51(4) |
| u13 | t6(1)，t35(3)，t50(4) |
| u14 | t30(2)，t36(3)，t58(4) |
| u15 | t14(1)，t41(3)，t52(4) |
| u16 | t26(2)，t37(3)，t54(4) |
| u17 | t11(1)，t45(3)，t46(4) |
| u18 | t9(1)，t18(2)，t59(4) |
| u19 | t3(1)，t19(2)，t60(4) |
| u20 | t2(1)，t28(2)，t42(3) |
为了进一步说明算法的有效性，针对本文的模型编写了lingo程序，在不同参数条件下对比了算法的运行效率，如表 2所示，下面的运算中ε都取1.
| 问题参数 | 本文算法 | lingo | ||
| 目标函数值 | 运行时间/s | 目标函数值 | 运行时间/s | |
| nu=20 | 1 127.9 | 0.5 | 1 140.7 | 3 |
| nt=60 | ||||
| ns=4 | ||||
| nu=40 | 3 752.1 | 4 | 3 782.4 | 25 |
| nt=200 | ||||
| ns=10 | ||||
| nu=50 | 8 379.5 | 14 | 8 436.8 | 82 |
| nt=500 | ||||
| ns=20 | ||||
可以看出，与lingo的求解结果相比，本文设计的算法求解的结果目标函数值略小，但这个差距并不大，误差基本在1%，并且随着问题规模的增加，误差比有下降的趋势.运行时间方面，可以看出lingo的运行时间远长于本文设计的算法.从运行结果来看，lingo的运行时间似乎也在可接受范围内.事实上，本文所提算法的最大优势在于它是一个分布式算法，也就是说在算法执行过程中，不需要统一的控制中心去执行算法给出任务分配方案，只要整个无人机网络保持连通，每个无人机可以通过与通信范围的无人机通信更新自身价格信息实现任务的分配，当部分无人机出现故障或者无人机数量增加时，也就是当无人机网络中节点的数量发生变化时，算法仍能正常运行.因此，相对于一般集中式算法，该算法在可扩展性和鲁棒性上都有较大程度的提升.
5 结论本文针对多无人机的任务分配问题，根据任务类型将任务分组，考虑无人机的执行能力约束，定义了多无人机分组任务分配问题MUAP-GT，在对问题进行对偶分解的基础上设计了求解该问题的分布式拍卖算法，算法不需要共享存储中心或者控制中心存储拍卖价格信息，每个无人机只需要通过与邻居节点通信维护与更新自身价格列表即可给出出价信息.仿真结果验证了算法的性能与效率.但是在本文设计的无人机任务分配问题中没有考虑任务执行所需要的时间，以及任务之间的偏序关系，这些问题都有待进一步研究.
| [1] | Terry S, George B, Clayton R. A cognitive task analysis to elicit preliminary requirements for an automated UAV verification & planning system[J]. Journalism & Mass Communication Quarterly, 2013, 57(1): 210–214. |
| [2] |
丁臻极. 城市环境下多无人机应急救灾任务分配技术研究[D]. 南京: 南京航空航大学, 2016. Ding Z J. Task allocation technology of unmanned aerial vehicles for emergency relief in an urban terrain[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2016. |
| [3] |
宗群, 王丹丹, 邵士凯, 等.
多无人机协同编队飞行控制研究现状及发展[J]. 哈尔滨工业大学学报, 2017, 49(3): 1–14.
Zong Q, Wang D D, Shao S K, et al. Research status and development of multi UAV coordinated formation flight control[J]. Journal of Harbin Institute of Technology, 2017, 49(3): 1–14. |
| [4] |
唐苏妍, 朱一凡, 李群, 等.
多Agent系统任务分配方法综述[J]. 系统工程与电子技术, 2010, 32(10): 2155–2161.
Tang S Y, Zhu Y F, Li Q, et al. Survey of task allocation in multi agent systems[J]. Systems Engineering and Electronics, 2010, 32(10): 2155–2161. DOI:10.3969/j.issn.1001-506X.2010.10.30 |
| [5] |
沈林成, 陈璟, 王楠.
飞行器任务规划技术综述[J]. 航空学报, 2014, 34(3): 593–606.
Shen L C, Chen J, Wang N. Overview of air vehicle mission planning techniques[J]. Acta Aeronautica et Astronautica Sinica, 2014, 34(3): 593–606. |
| [6] | Zavlanos M M, Spesivtsev L, Pappas G J. A distributed auction algorithm for the assignment problem[C]//Proceedings of the 47th IEEE Conference on Decision & Control. Piscataway, NJ, USA: IEEE, 2008: 1212-1217. |
| [7] |
王林. 多无人机协同目标跟踪问题建模与优化技术研究[D]. 长沙: 国防科学技术大学, 2011. Wang L. Modeling and optimization multi-UAVs cooperative target tracking[D]. Changsha: National University of Defense Technology, 2011. |
| [8] |
邓启波. 多无人机协同任务规划技术研究[D]. 北京: 北京理工大学, 2014. Deng Q P. Cooperative task planning of multiple unmanned aerial vehicles[D]. Beijing: Beijing Institute of Technology, 2014. |
| [9] |
张庆杰, 徐惠斌, 陶军, 等.
面向多无人机协同观测的分布式无色信息滤波方法[J]. 信息与控制, 2014, 43(6): 654–663.
Zhang Q J, Xu H B, Tao J, et al. Distributed unscented information filter method for cooperative observation using multiple UAVs[J]. Information and Control, 2014, 43(6): 654–663. |
| [10] | Sujit P B, Ghose D. Negotiation schemes for multi-agent cooperative search[J]. Proceedings of the Institution of Mechanical Engineers, Part G:Journal of Aerospace Engineering, 2009, 223(6): 791–813. DOI:10.1243/09544100JAERO438 |
| [11] |
孙小雷. 基于多阶段航迹预测的无人机任务规划方法研究[D]. 哈尔滨: 哈尔滨工业大学, 2015. Sun X L. Research on mission planning for unmanned aerial vehicles based on multi-stage path prediction[D]. Harbin: Harbin Institute of Technology, 2015. |
| [12] |
李远. 多UAV协同任务资源分配与编队轨迹优化方法研究[D]. 长沙: 国防科学技术大学, 2011. Li Y. Research on resources allocation and formation trajectories optimization for multiple UAVs cooperation mission[D]. Changsha: National University of Defense Technology, 2011. |
| [13] | Choi J, Oh S, Horowitz R. Distributed learning and cooperative control for multi-agent systems[J]. Automatica, 2009, 45(12): 2802–2814. DOI:10.1016/j.automatica.2009.09.025 |
| [14] |
邸斌, 周锐, 丁全心.
多无人机分布式协同异构任务分配[J]. 控制与决策, 2013, 28(2): 274–278.
Di B, Zhou R, Ding Q X. Distributed coordinated heterogeneous task allocation for unmanned aerial vehicles[J]. Control and Decision, 2013, 28(2): 274–278. |
| [15] |
程聪. 无人机协同作战任务分配与攻击效能评估技术[D]. 南京: 南京航空航大学, 2013. Cheng C. Research on task allocation & attack effectiveness evaluation technique for UAVs cooperatively combating[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2013. |
| [16] |
赵明明, 李彬, 王敏立.
不确定信息下基于拍卖算法的多无人机同时到达攻击多目标[J]. 电光与控制, 2015, 22(2): 89–93.
Zhao M M, Li B, Wang M L. Auction algorithm based multi-UAV arriving simultaneously to attack multiple targets with uncertain information[J]. Electronics Optics & Control, 2015, 22(2): 89–93. |
| [17] |
吴俊成, 周锐, 冉华明, 等.
遗传算法和拍卖算法在任务分配中的性能比较[J]. 电光与控制, 2016, 23(2): 11–15.
Wu J C, Zhou R, Ran H M, et al. Performance comparison of genetic algorithm with auction algorithm in task allocation[J]. Electronics Optics & Control, 2016, 23(2): 11–15. |
| [18] | Bertsekas D P. The auction algorithm:A distributed relaxation method for the assignment problem[J]. Annals of Operations Research, 1988(14): 105–123. |
| [19] | Luo L Z. Chakraborty N, Sycara K. Multi-robot assignment algorithms for tasks with set precedence constraints[C]//2011 IEEE International Conference on Robotics and Automation. Piscataway, NJ, USA: IEEE, 2011: 2526-2533. |
| [20] | Boyd S, Vandenberghe L. Convex optimization[M]. Cambridge, UK: Cambridge University Press, 2004. |
| [21] | Luo L Z., Chakraborty N, Sycara K. Provably-good distributed algorithm for constrained multi-robot task assignment for grouped tasks[J]. IEEE Transactions on Robotics, 2015, 31(1): 19–30. DOI:10.1109/TRO.2014.2370831 |