基于改进合同网算法的多无人机任务分配

常松 贾子彦

摘 要：传统合同网算法在任务分配过程中存在任务分配不合理，不能有效利用资源的问题;其在进行任務分配时，不能按照任务需求进行任务分配，任务分配效率低下。针对以上问题，文中提出一种基于改进合同网算法的多无人机任务分配方法。该方法通过优化每架无人机的负载平衡，并结合时间和协作要求，解决任务分配不合理的问题，提高任务的分配和执行效率。

关键词：任务分配;无人机;合同网算法;负载平衡;资源消耗;飞行距离

中图分类号：TP393文献标识码：A文章编号：2095-1302（2020）05-00-03

0 引 言

随着无人机技术的发展，无人机的应用领域在逐渐增加，无人机可以执行的任务种类也变得多样化。但是单机无人机的任务执行能力毕竟有限，所以对多架无人机执行任务的研究也越来越多[1]。多无人机协作技术的发展是为了有效执行任务，而合理的进行任务分配则为无人机快速、高效完成任务打下了基础，所以对多无人机的任务分配算法的研究是十分有意义的。

任务分配的目的是使无人机执行任务时消耗的资源少、飞行距离短、花费的时间短。而随着无人机应用领域的增多，任务规模、种类、复杂度也增加了任务分配算法的难度。目前已有的任务分配方法主要有合同网算法、蚁群算法、粒子群算法等[2-4]。合同网算法在进行规模大、数量多、复杂度较高的任务分配时，相比于其他算法有一定的优势。

本文针对传统合同网算法分配效率低，分配不合理等问题对算法进行了改进，增加了任务分配条件，提高任务分配和无人机执行效率[5]。

1 合同网算法

合同网算法源自人们在商务过程中用于管理商品和服务的合同机制[6]。该算法是模仿经济行为的“管理者-工作者”的机制进行任务协商，实现任务分配。在合同网算法中，所有主体分为三个角色：招标者、投标者和中标者。

在多无人机任务分配的合同网算法中，招标者即任务管理者，负责任务信息的收集、发布和管理[7]。投标者是无人机，其根据自身的信息和资源对任务进行评估，参与投标，向招标者发送任务请求。中标者是获得任务的无人机，负责完成任务。任务分配过程如图1所示。

1.1 任务建模

任务分配的主要参与对象是无人机和任务。令V={V1， V2， …， Vm}代表执行任务的无人机集合，T ={T1，T2， …， Tn}代表需要完成的任务集合。

1.2 任务描述

假设有n个任务需要执行，但每个任务的紧急程度不一样，这就需要对任务限制任务完成的时间。每个任务的工作量也不一样，为了能够在规定时间内完成，工作量大的任务要求无人机协作完成。

（1）任务时间。无人机的资源消耗与时间成正比，每架无人机都需要保证自身的资源足够完成分配到的所有任务并安全返航。设：ti， j为完成某个任务的时间;ts1i， j是无人机到达目标点的飞行时间;ts2i， j是无人机执行任务时间;Di是无人机到第i任务点的飞行距离;Vj是无人机j的飞行速度;Qi是第i个任务的任务量;pj是无人机j执行任务的速率;

i=1， 2， …， n是任务编号，j=1， 2， …， m是无人机编号（给某个无人机）。

（2）任务协作。每个任务都有自己的工作量Qi，如果工作量较大，无人机单独完成会影响无人机的整体资源消耗，从而使得任务分配不合理。以所有任务的平均值为条件，如果Qi≥，则需要无人机协作完成任务。是总的平均任务量。

1.3 目标函数

无人机在收到任务信息后，在任务范围内均匀分布，每架无人机在自己的航线上搜索附近的任务，以无人机到任务的飞行距离为条件，优先选择距离近的任务，有：

式中：（xi， yi）为目的任务的坐标;（xj， yj）无人机当前坐标点。

2 改进合同网算法

利用上述方法虽然可以实现任务的分配，但是存在任务分配不合理，分配效率低的情况。为了解决传统合同网算法可能存在的问题，进行了以下改进：

无人机在以距离为限制选择任务时，也要考虑到任务时间的顺序。当任务量大于预设的平均任务量时，选择将这个任务交付于两架无人机协作完成，减少无人机投标的次数，提高分配效率。

无人机的负载可以和无人机的资源消耗、飞行距离、任务时间等条件结合起来，根据负载结果来判断任务分配结果是否合理。

设无人机i的负载量为Fi，所有无人机的平均负载能力为：

式中，m为无人机的个数，则无人机的负载率为：

通过人为设置固定值E，若负载率小于E，则表示无人机可以继续对任务进行投标;若负载率大于E，则无人机不可以继续对任务进行投标，并放弃最后选择的任务。

为了使任务负载的均衡性更好，通过方差计算无人机每次任务中标后的负载变化。

式中，ρj代表无人机的负载均衡性，ρj越小，则任务分配越合理。

为了满足时间上的安排，结合遗传算法对无人机的任务时间进程进行了安排。在获得任务的时间信息后，每个遗传因子都是一个时间点。通过不停的迭代和遗传变异的方式使得彼此之间不会出现重合的时间点，从而使得任务时间安排合理、有效。

3 仿真实验

基于以上思路，采用Matlab平台开展仿真实验。无人机的飞行高度一致，飞行起点均匀分布，以x y∈[0，1000]的二维区间为飞行环境。总共20个任务随机分布在同一区域中。任务信息中包含时间和协作的要求。时间和任务量的关系图如图2所示。为了使无人机在接收任务后，合理安排任务的执行顺序，给每个任务设置任务完成时刻，时刻为0或者负数的任务表示无需在规定时刻完成任务，这样的任务可以留在最后执行。此图为实验的仿真条件之一。

根据实验数据中的任务量得到需要协作的任务信息见

無人机根据传统合同网算法进行任务分配的结果如图3所示。

改进后的任务分配图如图4所示。通过图3和图4的对比可以看出：传统合同网算法中每架无人机分配到的任务数量为1，4，3，7，8，6，而改进后的每架无人机分配的任务数量为4，4，3，7，5，6。从分配结果上看改进后合同网算法分配的结果更平均。若无人机在完成任务后回航或者接收到了新的任务信息需要执行，那么传统合同网中的一些无人机由于之前分配的任务较多，消耗了过多的资源，这样就不能在继续接收新的任务。而改进后得到的任务分配结果中，每架无人机消耗的资源相对较少，可以继续执行新的任务，所以改进后的合同网算法比传统合同网算法任务分配更合理。无人机以相同的飞行速度去执行任务，从分配结果的时间上看，改进后的合同网算法对传统合同网算法花费更少的时间。由此可以看出，在本文的任务分配算法中，改进合同网算法比传统合同网算法更有优势。

4 结 语

本文通过对合同网算法进行改进，在合同中的任务信息添加时间和协作的条件，将任务以整体的形式广播发送给无人机。无人机以时间、协作和飞行距离等作为约束条件实现任务的投标过程。而任务管理者通过收集对比无人机的投标，选择最优的分配方式，从而实现多无人机协作完成任务的分配方法，有效提高整体任务执行效率[8]。在已知环境下获得任务目标，采用全局与局部相结合的方法，综合考虑资源代价和任务执行能力，建立多机协作任务分配模型。

这一模型对其他自主机器设备也可以进行实际应用，但这一方案仅仅局限于静态环境中，能否适应于未知环境还需要进行更多的实验，而且在进行任务分配时考虑是否结合动态实际任务完成情况作为任务分配目标条件也是是今后的研究点之一。

参考文献

[1]郜晨.多无人机自主任务规划方法研究[D].南京：南京航空航天大学，2016.

[2] SMITH R G. The contract net protocol：high-level communication and control in a distributed problem solver [J]. IEEE transactions on computers，1980，C-29（12）：1104-1113.

[3]李士波.基于粒子群算法的多无人机任务分配[J]. 软件导刊，2018，17（7）：197-199.

[4]王灵霞，张远平，吴佩莉.蚁群算法求解分布式系统任务分配问题[J]. 计算机工程与设计，2008（6）：168-170.

[5]王钦钊，程金勇，李小龙.多无人机协同任务规划方法[J].火力与指挥控制，2018，43（3）：86-89.

[6]钱艳平，夏洁，刘天宇.基于合同网的无人机协同目标分配方法

[J].系统仿真学报，2011，23（8）：1672-1676.

[7]李新亮，翟江涛，戴跃伟. 动态环境下基于改进合同网的多Agent任务分配算法[J]. 科学技术与工程，2013（27）：104-109.

[8] LI Y W，LI B A. Research of multiple UAVs task allocation based on improved contract net [J]. Advanced materials research，2013，823：439-444.

[9]陈转，刘平，王超.无人机在侦查与监视领域的研究与展望[J].物联网技术，2019，9（10）：82-83.

[10]赵露露.有人/无人机协同互操作性研究[J].物联网技术，2015，5（5）：59-61.