基于一致性群组算法的多无人机自主协同任务分配

马云红，刘云昊，杨誉乔，王鼎涵，张 健

（1.西北工业大学，西安 710072；2.北京航空航天大学，北京 100191）

1 引 言

随着无人机的轻量化、智能化发展，无人机在各个领域发挥越来越重要的作用[1-2]，凸显了无人机智能化的优势，多无人机自主协同执行多任务成为可能。同时，随着无人机的作用得到不断的开发和拓展，无人机的协同任务分配逐步由单无人机执行单任务，转变为单无人机执行多任务，再到多无人机执行单任务的任务联盟任务分配问题。即多无人机需要适时组成小的“任务联盟”合作完成一个复杂的任务。例如，在进行大宗货物搬运或者危险环境的救援等活动时，需要不止一架无人机执行任务。这种依靠多无人机自主组队解决大型复杂任务的需求在现代化空战中更为迫切[3]。因此，对于多无人机能够自主协同完成不同类型不同数量任务的任务分配问题研究具有重要意义。

无人机任务分配通常是指一定的任务集合由多架无人机执行，根据任务的属性和任务的位置确定最佳的任务分配方案，使得无人机执行完成所有任务的时间最短或者收益最大。任务分配本质上是一种组合优化问题，可以用一般的解决NP-hard 问题的方法求解。文献[4-5]采用启发式空间搜索方法求解车辆完成多个任务的最优任务路径问题的解。文献[6]采用了蚁群算法进行这类问题的求解。文献[7]采用了遗传算法进行动态最优任务路径优化。文献[8-9]将遗传算法扩展到多个无人机多任务分配问题求解。文献[10]采用改进NSGA 算法实现无人机联盟多任务的任务分配。然而，现有的这些算法，主要解决了静态规划，依赖对全局信息的获取。而自主任务规划要求能够根据动态变化的场景进行实时规划。分散算法是无人机之间基于实时信息共享的实时任务分配，可以应对实时变化的场景，成为多无人机自主协同任务分配的重要手段。文献[11]基于分散合作优化解决了任务目标函数独立的凸优化问题，但仅适用于具有连续决策变量的凸优化函数。文献[12]采用基于分散化计算的匈牙利任务分配算法，可以解决目标函数独立的任务分配。这些算法可以在通信可靠的前提下实现基于中央集中控制中心的优化计算。但是，对于多无人机自主协同完成多任务来说，无人机通常处于敌方控制区域，没有传统通信基础设施进行通信辅助，特别是如果在空域或水下环境执行任务时，甚至没有通用基础通信条件，不能保证所有信息同时共享。为此需要设计基于无人机之间的信息共享的分散算法，提升无人机自主任务分配的适用性和鲁棒性，也降低对集中节点的指挥的依赖。文献[13]引入的基于一致性的拍卖算法（Consensus Based Bundle Algorithm，CBBA）算法，是一种基于协商机制的一致性规划方法，用于求解车辆完成运输任务的车辆路径问题。文献[14]基于拓展的CBBA 算法进行了轨装配航天器的任务分配研究。文献[15]采用合同网算法进行了多任务的分配。文献[16]提出部分重规划思想，结合合同竞拍实现了实时动态任务分配。这些文献完成了一致性算法下的任务分配。但是，在多无人机协同执行多任务的情形下，有些任务是有时间约束的，即必须在制定的时间内完成，否则失去作战价值。这类任务分配问题就是带有时间窗约束的任务分配问题。文献[17]讨论了带时间窗约束的邮递员路径问题。采用的是把具有时间约束的客户和没有时间约束的客户先聚类后求解的方法，再基于多目标优化的思想实现了带有时间限制的最佳邮递路径问题。文献[18]提出了一种聚类第一路线和第二路线的算法，即根据目标的时间窗口对目标进行聚类，然后为每个聚类生成运输问题，再用单纯形算法逐步解决这些运输问题，可以在短时间内找到高质量的解决方案。但这个算法还是一种集中式优化，需要所有信息共享，而且也不能解决多无人机协同同时到达任务的时间约束问题。本文基于目前的研究基础，对不同类型的任务分配问题，采用基于合同竞拍的机制实现实时任务分配，并重点解决带时间窗限制的多无人机自主协同执行一个复杂任务分配问题的求解。

2 任务分配问题模型

2.1 单无人机单任务的任务分配模型

为了建立一般化的多无人机多任务分配模型，首先分析最简单的任务分配模型–单无人机执行单任务的任务分配模型。对于单无人机执行单任务的任务分配问题，是指限定多无人机中的每个无人机只能执行一个任务。单无人机执行单任务的任务分配的目的是将Nt个任务分配给Na个无人机，保证目标函数达到最优的任务分配方案，其对应的数学模型如下：

其中，xij表示第i个无人机执行第j个任务，xij= 1表示第i个无人机执行第j个任务，xij=0表示第i个无人机不执行第j个任务；c ij表示第i个无人机执行第j个任务的收益。式（2）表示一个任务只能由一个无人机执行的约束，式（3）表示一个无人机只能执行一个任务的约束。

2.2 单无人机多任务的任务分配模型

单无人机执行多任务的任务分配问题，是指多无人机中的每个无人机可以执行多个任务，其具体任务数量受无人机能力、任务执行难度等条件限制。单无人机对多任务分配的目标是将Nt个任务分配给Na个无人机。其中，每个无人机可以分配Lt的任务数量，并使任务收益最大。相应的数学模型如下：

其中，式(5)表示无人机最多执行Lt个任务。式(6)表示每个任务由一架无人机执行，式(7)保证所有任务都要执行。

2.3 多无人机联盟协同执行多任务的任务分配模型

将需要两架及以上无人机合作完成一个任务的分配，定义为无人机联盟协同执行多任务的分配问题，而同时参与协同执行一个任务的无人机小组定义为任务联盟。

因此，多无人机任务联盟协同执行任务的分配问题，是指每个无人机可以执行多个任务，同时有些任务又要求多架无人机组成联盟共同完成的复杂情况。任务联盟的成员数量定义为联盟规模。任务联盟规模一般有定值和最小值两种情况，如大宗物品搬运任务的规模一般为某个定值，即需要多少无人机完成搬运，集中救援则可以设置为最小值，即最少需要多少无人机参与救援，也可以设定为定值，即指定固定的无人机数量完成特定的任务。本文的任务联盟的规模采用定值。即任务联盟任务分配是将Nt个任务分配给Na个代理无人机，其中的复杂任务需要特定规模的无人机联盟完成。在任务联盟协同完成任务的前提下，以最优的资源组合完成所有的任务。记无人机可以分配Lt的任务数量，无人机联盟规模设定为Lj，相应的数学模型表示为

其中，式（9）是对无人机最多执行Lt个任务的约束。式（10）表示复杂任务至少需要有Lj个无人机完成。式（11）约定所有任务都要完成。式（12）约定无人机i执行任务j的时刻位于任务j的执行时间区间。Tij-start表示无人机i执行任务j的开始时间，Tjmin为任务j的可执行的开始时间，Tjmax是任务j的可执行的结束时间。

3 任务分配算法

3.1 基于一致性的拍卖算法原理

本文采用基于一致性的竞拍算法实现任务分配，即将任务作为待拍卖的货品，无人机根据自身完成任务的能力（到达任务的时间）对任务进行竞价，最后以所有无人机的收益综合最大达成拍卖，从而实现任务分配。常规的拍卖活动是一种集中式的控制机制，通常由拍卖师负责控制拍卖流程，是一种集中式的任务分配。本文的任务分配采用竞拍机制，但是拍卖结果是由所有竞拍者通过信息共享和通信协商达成一致实现的，即竞拍过程不需要控制中心进行计算并发放指令，而是完全依靠无人机借助通信网络进行信息交互，冲突消解，最终完成一致性和协调，得到最佳任务分配。这是一种分散式的任务分配，可以保证无人机在自带的通信设备情形下自主协商，完成任务分配。

3.2 单无人机单任务的任务分配的基于竞拍的一致性算法

3.2.1 变量定义

定义任务分配问题为Na个无人机执行Nt个任务，则N a×Nt的矩阵表示任务分配结果，其元素为xij，xij= 1，表示无人机i执行任务j，xij=0表示无人机i不执行任务j。定义xi为状态向量，其长度为Nt，Nt是任务数量，xi记录无人机i认为当前自己获得的任务状态。记yi为胜者投标价格向量，长度为Nt，记录胜者的投标价格。ytj记录无人机i认为的任务j的胜者投标价格。ci称为出价向量，长度为Nt，记录无人机i对所有任务的出价。cij表示无人机i对任务j的出价，如果不出价则cij= 0。hi称为有效出价向量，长度为Nt，记录无人机i的每个任务出价是否有效。如果cij＞yij，即无人机i的出价大于目前它认为对任务j的最高出价，则hij= 1，否则hij= 0。Ji是代理无人机i的有效投标任务，代表无人机i所有的有效出价中最高的一个对应的任务。g为N a×Na的通信矩阵，gik= 1表示无人机i可以与无人机k通信，gik= 0则表示无人机i不能与无人机k通信。zi是胜者向量，长度为Nt，记录每个任务的竞标成功无人机编号，zij是无人机i收到的投标信息中对任务i的最高投标价格对应的无人机编号，I为无人机集合，J为任务集合。

3.2.2 基于竞拍的一致性算法流程

基于以上定义，基于竞拍的一致性算法（Consensus Based Auction Algorithm，CBAA）流程如下所述。CBAA 算法分为拍卖阶段和一致性阶段。第一阶段是拍卖阶段。如果无人机i没有任务，则进入拍卖环节，否则直接进入一致性阶段。在拍卖阶段，每一个无人机i根据自身完成任务的“能力”对任务j进行投标竞价。无人机i根据上一轮(t- 1)的拍卖结果和本轮(t)自己的出价情况更新两个向量xi和yi。第t轮次拍卖阶段的伪代码如下：

CBAA 算法的第二阶段是一致性阶段。每一个无人机i都将它最新的列表yi传送给它通信可达的邻近无人机k，同时从代理无人机k获取对方的yk，通过协商协议达成一致，消除冲突。协商原则包括：如果一个无人机发现对于某一个任务其他无人机的出价高于自己，那么该无人机放弃这个任务；如果两个无人机发现对于某一个任务的出价相同，则编号小的无人机获胜，编号大的无人机放弃这个任务。为了解决异步通信过程中的通信不同步问题，CBAA 引入时间印记s标识数据时戳，这样每轮的数据仅通信一次，降低通信损耗。一致性阶段的伪代码如下：

3.3 基于CBBA 的单无人机执行多任务的任务分配

在无人机可以执行多个任务的情形下，仍然采用基于一致性协商的合同竞拍机制进行任务分配。将每个无人机执行的任务表示成一个任务序列，称为拍卖包。每个拍卖包标明了无人机执行多个任务的顺序。竞价时，增加一个未被执行的任务进入任何一架无人机的序列。即CBBA 算法。CBBA 算法的第一阶段是拍卖包构建阶段。即每个无人机执行的所有任务形成一个拍卖包，拍卖包中的任务顺序就是无人机执行任务的路径。一个无人机i确定对任务Ji投标后，将该任务Ji插入其先前路径中某一处，则无人机i的拍卖包就相应地产生一个收益值。如果这个收益值大于当前的赢家，无人机i将把任务Ji添加到它的拍卖包中。一直重复这个过程，直到无人机i不能再添加任务到它的路径上。最后，无人机i更新它认为的中标向量zi和中标价格向量yi，进入下一轮竞标。CBBA 算法的拍卖包构建阶段伪代码如下：

CBBA 算法的第二阶段是一致性阶段。每一个无人机i都将它的最新向量表zi，yi和si传达给所有可以通信的无人机，并根据它们各自的拍卖价格进行协商和冲突消解。一致性过程中的三个响应行为“更新”yij=ykj,zij=zkj，“重置”yij=0,zij=∅和“保留”yij=yij,zij=zij。这个冲突消解的过程中，如果两个无人机i和k对位于i拍卖包中的特定任务j有冲突，则失败的无人机（假设是k）不仅需要重置任务j，还需要重置竞拍包内j之后的所有任务，确保后续CBBA 拍卖包在建立阶段的竞拍方案的合理性。如果两个无人机发现对于某一个任务的出价相同，约定编号小的无人机的获胜。一致性阶段协议一致性冲突消解原则如表1 所示。根据表1 的冲突消解原则协商达成本轮一致，形成本轮竞价结果。

表1 一致性阶段冲突消解原则Table 1 Principles of conflict resolution

3.4 基于CBGA 的任务联盟任务分配算法

基于与CBBA 算法类似的拍卖包构建过程和一致性阶段过程，本文提出CBGA 算法，完成任务联盟任务分配问题的求解。定义N a×Nt的矩阵xi，如果无人机i认为无人机k获得了任务j，那么xikj= 1，否则xikj= 0。

CBGA 算法的拍卖包构建阶段伪代码如下：

Procedure Bundle（xi(t-1),yi(t-1),bi(t-1),pi(t-1),zi(t-1)）

3.5 时间窗限制的群组拍卖算法（CBGA-TW）

3.5.1 CBGA 算法的不足

CBGA 算法可以实现任务联盟完成复杂任务的任务分配，但是没有考虑到复杂任务合作执行的时间问题，如大宗货物的搬运和危险环境的救援需要多架无人机同时执行搬运任务，无人机协同打击也需要同时到达。

3.5.2 基于时间窗的CBGA-TW 算法

为了实现任务协同的同时到达要求，本文对CBGA 算法进行了改进，提出了一种有时间窗限制的CBGA-TW 算法。算法通过引入时间窗限制，解决合作执行任务的同时到达时间约束问题。

CBGA-TW 算法加入了对协同同时到达的时间窗约束，设计了能够体现时间窗约束的收益值，通过收益值的竞价，解决满足同时到达的时间约束问题。

在CBGA-TW 算法的第一阶段，如果是Lj=1的简单任务，则采取CBBA 算法进行解算。对于任务联盟任务，如果该任务尚未分配给足够多的无人机或者无人机i的出价高于现在投标价格中的最小值，则认为是对于该任务的有效出价。CBGA-TW 算法的出价cij的表达式设计为

其中，Tij-start表示无人机i执行任务j的开始时间，Tjmin为任务j的可执行的开始时间，Tjmax是任务j的可执行的结束时间，e-λΔT是对时间的惩罚项，只有能在规定时间内执行任务的无人机才能获得收益，即如果无人机能够执行该任务的时间大于任务的结束时间，则收益值为0，如果无人机能够执行的时间位于任务的执行时间窗内，则加入一个奖惩因子，时间差越小，收益值越大。保证满足带时间窗限制的任务获得优先分配权，也满足了时间窗的约束。

这里特别指出，每个无人机的收益值包括任务自身的价值以及由于任务时间满足时间窗约束的奖惩系数。而无人机对任务的出价是基于无人机到达任务的飞行代价或者飞行距离计算的。无人机到达目标的飞行距离越短，飞行时间就越短，则可以给出的出价越高。这表示在计算无人机的任务收益时考虑了执行任务的时间，但是没有考虑环境中有障碍情形的避障飞行的距离，仅采用到达任务的直线距离的飞行时间。收益函数的收益表达式加上时间窗约束的奖惩因子，可以针对时间窗满足条件进行任务估价，如果超过任务执行时间的收益值为 0。通过收益函数的评价限定了无人机联盟协同完成任务的同时达到。因此，基于这个收益函数的出价再经过一致性竞拍，可以得到最快时间完成所有任务的任务分配方案，同时保证需要多架无人机协同完成的任务的可靠执行。

4 基于CBGA-TW 任务分配仿真

包含带时间窗约束的多无人机任务联盟任务分配是本文综合考虑多种约束的复杂任务分配问题，以这类问题的任务分配进行本文的算法仿真验证。设定仿真任务场景如下：多架异构型无人机执行不同类型的任务分配。即6 架无人机完成12 个任务，其中Ⅰ型无人机3 架，Ⅱ型无人机代理3 架；Ⅰ型任务6 项，每个任务需要5 s 的执行时间，Ⅱ型任务6 项，每个任务需要10 s 的执行时间。无人机型号和它能够执行的任务匹配，即Ⅰ型无人机可以执行Ⅰ型任务，Ⅱ型无人机可以执行Ⅱ型任务。其中任务2 和任务7 设定为需要两架无人机共同完成的任务,即L2=L7= 2,任务2 和任务7 的时间窗都设置为[5,15]。将无人机执行任务的时间（到达任务时间）作为出价和收益标准。参与作战的无人机之间都可以通信，即

针对上述任务场景进行CBGA-TW 算法仿真,采用Matlab R2016b 软件作为仿真计算平台,并假设所有无人机间都能通信并正常收发数据。

仿真结果如图1 和图2 所示。

图1 CBGA-TW 任务分配结果Fig.1 Task allocation results with CBGA-TW

图1 中Δ表示无人机的位置，×表示任务位置，实线表示规划后的代理无人机的路径。不同的颜色表示不同的无人机类型和任务类型，相同颜色进行无人机和任务匹配。

仿真结果显示，经过约0.224937 s，11 轮的CBGA-TW 解算之后，所有任务得到最佳竞价方案，得到该场景下的任务分配结果。执行这组任务的总时间，即多无人机完成最后一个任务的时间为39.354 s，得到的总收益为749.6437。

通过图1 和图2 可以看到，任务2 被同时分配给了无人机1 和无人机2，任务7 被分配给了无人机4 和无人机5，两个任务都在时间窗限制内执行，满足了时间窗约束并达到同步，实现了多无人机协同执行一个复杂任务。可以说明CBGA-TW 算法能够有效解决带时间约束的任务联盟的任务分配问题。

图2 CBGA-TW 任务分配结果甘特图Fig.2 Gantt chart of CBGA-TW task allocation result

可以发现，采用CBGA-TW 算法的多无人机联盟任务分配是基于时间窗限制的群组拍卖算法，通过时间窗限制条件的加入，保证了任务的同时执行。依靠无人机之间通信和一致协商，可以达到最终的协同任务执行方案。整个过程不需要集中控制中心或人工参与，提升了多无人机自主任务分配、自主协同作战的能力。同时，本文提到的单无人机执行单任务的无人机任务分配和单无人机执行多任务的任务分配，也是基于无人机之间的通信协商的一致性竞拍协商机制完成的，也是自主任务分配。

5 结 论

本文进行了一致性群算法的多无人机协同作战的自主任务分配，包括单无人机执行单任务的多无人机任务分配、单无人机执行多任务的任务分配，以及无人机任务联盟的任务分配。本文提出了基于时间窗限制的多无人机一致性群组拍卖算法CBGA-TW 算法，解决了在时间约束下的无人机联盟同时到达并执行任务的任务分配的问题求解。本文仿真验证了算法的有效性。同时说明基于信息共享的无集中控制的任务分配，可以完成多无人机自主任务联盟任务分配，提升了多无人机自主任务分配、自主协同作战的能力。