基于改进PSO的多UAV协同任务分配研究

韩庆田

(海军航空大学，山东 烟台 264001)

目标任务分配是指在多任务和多UAV之间进行合理规划，充分考虑任务约束、UAV性能约束和环境约束，对UAV进行任务指派，使它们能够以最佳的方式完成既定任务，从而提高资源的利用率，UAV形成能力互补，提高任务完成率。

在对多UAV任务分配问题的研究中，研究人员已经提出了多种基于经典问题的任务分配模型，主要包括多旅行商问题(Multiple Traveling Salesman Problem，MTSP)模型、车辆路由问题(Vehicle Routing Problem，VRP)模型、混合整数线性规划(Mixed-Integer Linear Programming，MILP)、动态网络流优化(Dynamic Network Flow Optimization)模型、多处理器资源分配(Multiple Processors resources Allocation)模型等[1]。任务分配问题的研究一般分为分布式和集中式两大类[2]。基于分布式控制系统结构的任务分配方法主要包括基于合同网(Contract Net)市场竞拍机制的方法、基于粒子群优化算法(PSO)的多UAV任务分配方法、分布式模型预测控制方法(DMPC)、基于蚁群算法的多UAV任务分配方法等。集中式算法适应于数据链组网/退网时间较长且UAV计算能力和智能性较差的场景，其关注算法本身对建模后的组合优化问题的求解能力，由中心节点汇总全部信息，采用优化算法求解协同攻击方案后进行分配[3-4]。主要采用混合整数线性规划方法、神经网络方法[5]、分布估计算法[6]、遗传算法[7-8]、蚁群算法[4]、粒子群算法[9]等优化算法进行求解。PSO也广泛应用于解决UAV不确定环境任务分配[10-11]、协同侦察任务[12]、协同攻击行动序列规划[13]等问题。邢焕革等[14]运用买卖合同策略来调整PSO算法解决了异构UAV对多类型任务规划的最优分配，王强等[15]利用多分支树结构特点，采用重构策略改善粒子搜索能力，但是计算较为复杂。

任务分配问题是一类组合优化问题，其解空间随着任务数量、UAV数目、约束等的增多而大幅度提高。学者们提出的多种求解模型和改进算法加以求解，但在求解具体环境下任务分配问题的解的质量、计算效率等问题上各有不同。本文主要利用UAV特性和相应的任务类型，研究启发信息的引入，以及任务之间的冲突消解问题，来改进粒子群算法，提高算法的优化效率。

1 多UAV协同目标任务分配指标建模

为了更好地使UAV执行各任务，以UAVUi执行任务Tj时收益、相应代价、负载均衡值等组成评价函数作为分配时的效能指标。

1.1 任务分配的收益

UAV执行任务的能力是由任务本身的价值和UAV执行该任务的能力来决定的。UAV执行任务能力由其携带的载荷(如探测装置、武器系统等)和其本身性能所决定。如假设UAVUi执行攻击Tj的价值为Value(Tj)，杀伤概率为Pi(Tj)，则Ui执行此Tj的收益为：

Rewardij=Valuei(Tj)·Pi(Tj)

(1)

式(1)中，i=1,2,…,Nu，表示第i个UAV，即UAVUi。

1.2 任务分配的代价

假设UAV飞行速度、单位距离内的燃油消耗量都为常数，则第k阶段飞行时间tf的取值与第k-1阶段UAV的位置有关，则总飞行时间为：

(2)

式(2)中，Nv表示UAV的数量；Nt表示目标的数量；Nc表示任务的数量；xi, j,k表示第k阶段第i个UAV是否执行目标j的任务；1表示得到了分配,0表示未得到分配。

任务时间是UAVi完成为其分配的所有任务所消耗的时间Vti，该时间包含飞行时间tf，执行任务时间te以及延迟时间td，则最大任务时间为：

(3)

式(3)中，Nt表示目标的数量；Nc表示任务的数量；xi, j,k表示第k阶段第i个UAV是否执行目标j的任务；1表示得到了分配,0表示未得到分配。

1.3 负载均衡值

考虑负载在各个UAV间的均衡分配对系统效能的影响，若某个UAV分配的任务较多，则会影响其任务的执行。因此，定义UAVUi的负载均衡因子为：

(4)

式(4)中，ELoadi为UAVUi的最佳负载任务数目；Loadi为UAVUi的实际负载任务数。

设UAV编队U={U1,U2,…,UNu}分别从初始位置P={P1,P2,…,PNu}出发至目标M={M1,M2,…,MNt}，执行各任务T={T1,T2,…,TNt}。

1.4 任务分配效能

考虑任务的分配收益、消耗值及负载均衡值后，UAVUi的任务分配效能为：

(5)

式(5)中，ω1>0，ω2>0为权系数，反映了各指标的重要程度；xij用来表明是否将第i个UAV分配给第j个任务，为布尔量，xij=1表示得到了分配。

若只是考虑时间消耗值和负载均衡值，UAVUi执行Tj时的任务分配效能定义为：

(6)

式(6)中，ω>0为常系数。

UAVUi自主任务分配问题的性能指标为：

Fi=maxJi

(7)

约束条件如下：

(8)

(9)

(10)

其中，式(8)表示第i个UAV的最大执行能力约束，不超过任务数Taski。式(9)表示第k个阶段，只能为将一项任务分配给一个UAV。式(10)表示确保所有任务都被执行完。

3 改进离散粒子群算法

本文采用改进PSO，即基于整数矩阵编码方式和粒子移位运算更新对问题进行求解。

3.1 粒子编码说明

建立粒子编码与多UAV系统多任务分配问题之间的映射，是将粒子群算法用于求解分配问题的重要步骤。比较实用的粒子编码规则有：一是应使用能够易于产生与所求解问题相关，且具有递阶、短定义长度模式粒子编码方案；二是应使用能够使得题得到自然表示或描述的具有编码字符集的编码方案。这些设计编码方案的指导原则，有助于建立相应的编码方案。

根据多UAV协同任务分配的特点，UAV在执行任务过程中，通常要对同一目标执行一系列的任务，包括对目标的分类、实施攻击，以及毁伤评估等，必须使得每一项任务都有UAV来执行，而且同一目标的任务分配应当满足先后顺序，对于特殊的目标还需要满足优先级约束。这样，要求每一个粒子编码，需要表示出可能的分配方案，既要有各个目标的各项任务及其顺序约束，又要表示出执行该项任务的UAV。将粒子表示为双层矩阵，即2行Nc列的矩阵，第一层表示执行任务的UAV编号；第二层表示与第一行UAV编号所对应的阶段目标序列，每个目标在第二行出现3次，同一目标在矩阵第二行从左到右一次出现的次序，表示对目标执行任务的不同，第一次出现表示UAV对目标执行的是分类的任务，第二次出现表示UAV对目标执行的是打击的任务，第三次出现标识UAV对目标执行毁伤评估的任务。表1为一种编码方案。

表1 粒子编码方案

这种编码方法的优点在于：保证了粒子表示的UAV任务规划方案服从任务优先序约束，同时满足任务协同约束，粒子能够较直观表示UAV对各目标执行的任务情况。

3.2 粒子更新方式

根据多UAV协同任务规划问题和本文粒子编码的实际特点，粒子的第二维数据应当需要始终满足任务总数约束，也就是说，不同目标标号的总数应该保持不变，以保证任务的完整性。在基本粒子群算法中，速度位置更新与协同任务分配的离散域问题是存在一定差异的。因此，根据实际的问题，建立相关的粒子群算法到离散问题的映射，通过粒子追随个体极值和全局极值的过程进行信息更新，在离散问题空间中重构粒子群算法的位置速度更新公式，设计新的粒子更新方式，这里借助移位向量完成粒子更新，具体术语与操作符定义如下[15]。

SV(shift vector)：移位向量，该向量的元素表示移位对象在粒子中的位数，移位对象按移位向量从左至右依次移位，并将末位移至首位。

SVS(shift vector set)：移位向量集，各个移位向量组成的集合。

Fs(x,y)：操作集获取函数，该函数表示粒子x转换至粒子y所需SVS。

⊗：选择操作符，从SVS中选择一定数量的SV，构成新的SVS′，可知SVS′⊆SVS。

⊕：移位操作符，按移位向量集进行移位操作。

粒子通过这种移位方式更新时，始终可以满足约束，确保了分配方案的可行性。

3.3 冲突消解处理策略

根据初始条件，可以生成各UAV执行任务的情况，任务分配方案如图1所示。

图1 任务分配方案

任务分配的初始方案存在着时间冲突，如目标4的三个任务M10、M11、M12，三个任务是存在这先后顺序的，即首先进行分类，然后进行攻击，最后进行毁伤评估，后者必须在前者完成之后才可进行，因此需要进行任务执行的冲突消解处理。针对冲突情况，本文提出以下几种处理策略。

3.3.1分组任务调整策略

分组任务消解，采用先调整后续任务的方法，减少调整任务开始时间，即在分类、攻击、评估任务中，满足先后顺序的作为一组进行调整，如图2所示，比如M8和M9属于目标3的任务，M11和M12属于目标4的任务，在执行时间允许的情况下，作为一组进行调节，或者保留两者的先后顺序，这样就可以避免增加调整的次数，提高调整策略。

图2 任务分组后分配方案

3.3.2任务交叉消解策略

采用交叉协商的方法进行任务的互换。如图3所示，M6和M7分别属于不同的目标任务，由不同的UAV执行，但是存在着时间冲突，M6需要在M4、M5之后执行，M7需要在M8之前执行，如果采用交叉消解的方法，互换M6和M7的位置，换位后M7在M8之前执行完毕，M6的时间向后调整，为再次调整M5和M6的时间提高了效率，同时M7的时间长于M6，互换后原来M6的后续任务M11和M12向后调整，同时满足了在M10之后的执行的条件，因此大幅度提高了调整效率。

图3 分组任务调整

3.3.3飞行时间调整策略

为了满足任务执行顺序，需要对任务次序进行调整的同时，通过调整飞行时间达到时间调整的目的。如图4所示，M11的开始执行时间，应向后调整它与M10结束时间的差值，从而满足任务先后顺序要求。

图4 飞行时间调整

3.3.4时序先后调整策略

为了减少调整量，采用从前往后的顺序进行调整，这样后面时间调整对前面时间调整不会产生影响。如图5所示，UAV3的任务调整过程中，首先调整M2和M3，然后再调整M8和M9。如果顺序相反，先调整M8和M9，再调整M2和M3则M8和M9的执行时间会受到影响，降低了冲突消解的效率。

图5 时序先后调整

4 仿真实验

仿真环境设置为UAV的初始坐标为V1(1，1)，V2(1，5)，V3(5，1)，V4(2，3)，V5(7，8)，目标坐标为T1(6，3)，T2(3，8)，T3(7，7)，T4(7，9)。

粒子群算法参数设置为种群大小为50，最大迭代次数为100。

对目标任务分配和航迹规划进行仿真，优化后任务分配方案如图6所示，目标任务分配方案见表2，算法仿真计算结果比较见表3，加入启发信息和改进冲突消解策略前后的算法收敛情况如图7所示

图6 优化后的任务分配方案

表2 任务分配方案

方案UAV1UAV2UAV3UAV4UAV5目标任务执行顺序14710112851236

表3 算法仿真结果比较

图7 适应度值收敛曲线

仿真结果表明，方案考虑了UAV任务均衡型、航迹长度，同时考虑了飞行约束，规划方案可行有效。通过进行冲突消解策略改进PSO算法，计算得到的总任务时间优于PSO算法，且仿真计算用时短、效率高，表明改进PSO算法的收敛性和全局搜索能力较好。

UAV任务执行情况如图8所示。

图8 任务分配方案示意图

5 结论

针对多UAV目标任务分配问题进行研究。本文考虑UAV总飞行时间代价、最大任务时间、负载均衡值以及任务时序约束因素的情况下，建立了多UAV协同任务分配模型。将任务类型匹配信息作为启发信息，同时提出分组任务调整、飞行时间调整、任务交叉消解、时序先后调整等冲突消解处理策略，改进粒子群算法。仿真实验结果表明，基于启发信息和冲突消解策略的改进PSO算法，提高了算法的收敛性和全局搜索能力，提升了任务分配和航迹规划效率。