应用离散粒子群-郭涛算法分配多无人机协同任务*

颜 骥，李相民,，刘 波

(1.海军航空工程学院 兵器科学与技术系， 山东 烟台 264001；

2.中航工业洛阳电光设备研究所 光电控制技术重点实验室， 河南 洛阳 471023)

应用离散粒子群-郭涛算法分配多无人机协同任务*

颜 骥1，李相民1,2，刘 波2

(1.海军航空工程学院 兵器科学与技术系， 山东 烟台 264001；

2.中航工业洛阳电光设备研究所 光电控制技术重点实验室， 河南 洛阳 471023)

针对以往考虑时间窗约束的多无人机协同任务分配问题模型不能反映在有效时间窗内，任务执行时间对任务收益的影响及求解算法效率较低的问题。建立了将任务收益和任务执行时间直接联系起来的任务分配模型和可行解到粒子整数编码方式的映射，设计了混合离散粒子群-郭涛算法的组合优化问题求解策略。借助粒子群算法利用粒子自身信息和种群有用信息指导种群进化的本质特点，优化郭涛算法的适应性序列倒置操作；设计了可变的学习选择概率来选择个体的学习粒子，改进了序列倒置算子。仿真实验验证了该方法处理复杂任务分配问题的有效性。

离散粒子群算法；郭涛算法；任务分配；有效时间窗；多无人机

(1.DepartmentofOrdnanceScienceandTechnology,NavalAeronauticalandAstronauticalUniversity,Yantai264001,China；

2.ScienceandTechnologyonElectro-opticControlLaboratory，LuoyangInstituteofElectro-opticalEquipmentofAVIC,Luoyang471023,China)

无人机(UnmannedAerialVehicle,UAV)因其作战半径大、续航能力强、速度快、高隐身、高机动、零人员伤亡等优势，将替代有人飞机在枯燥、恶劣、危险环境中执行如防空压制、大范围搜索和摧毁、纵深打击、电子攻击、情报侦察监视等各种作战任务[1]。如此复杂的作战任务，往往需要多架飞机互相协作与配合，共同完成。将这些复杂作战任务(mission)分解成一系列UAV能够理解和直接执行的子任务(task)(后文统称为任务)，并为每架UAV分配任务集合，同时确定这些任务被执行的时序是多UAV协同任务分配问题的关键。

多UAV多任务分配是一类非常复杂的组合优化问题(NP-hard)。相关文献中针对这类问题建立的模型包括旅行商问题(TravelingSalesmanProblem,TSP)和车辆路径问题(VehicleRoutingProblem，VRP)以及这些模型的变体[1]。任务的时间窗约束是多UAV任务分配中很常见的一类约束，文献[2]将多UAV的协同侦察任务分配问题抽象为带时间窗的多旅行商(multi-TSPwithtime-windows,MTSPTW)问题，并利用反射禁忌搜索算法对模型求解；文献[3]建立了多无人机任务规划的考虑时间窗约束的车辆路径问题模型(VRPwithtime-windows，VRPTW)，并采用混合整数线性规划方法求解该问题；文献[4]针对任务的时间窗约束，建立了多无人作战飞机(UnmannedCombatAerialVehide,UCAV)协同任务调度模型，应用粒子群优化(ParticleSwarmOptimization，PSO)算法求解。颜骥等在上述研究的基础上，建立了考虑时间窗约束的多UAV任务分配模型，利用混合离散离子群(DiscreteParticleSwarmOptimization,DPSO)算法和郭涛算法的改进方法求解该问题。

1 时间窗约束的多UAV任务分配

假设二维战场空间内Nu无人机组成的战斗编队执行Nt任务集合，任务分配算法的目的就是找出任务到无人机无冲突的匹配使得某项全局收益最大。若每项任务不被指派给多于一架的无人机，则说分配是无冲突的。全局目标函数假设为所有无人机局部收益值之和，而单架无人机的局部收益则是指派给该无人机的任务的函数。

1.1 时间窗约束下的任务收益函数

UAV每完成一项任务就会得到收益，记为vij。收益值的大小体现了任务的重要程度和飞机执行该任务的能力，vij=Pij×Vj，其中i为飞机序号，j为任务序号，Pij∈[0,1]为UAVi执行任务j的成功概率，与飞机及其挂载的传感器、武器性能和目标相关；V1,V2,…,VNt为各项任务的价值，其与任务的基准价值和被执行时间相关。为将时间窗约束合并到收益函数中，文献[5]给出了任务有效时间窗的相关定义：

2)有效时间窗(uj(t))：任务的有效时间窗指任务允许开始的时间段。任务j的有效时间窗定义为：

(1)

基于上述定义，定义无人机i执行任务j的收益函数为

(2)

无人机i执行任务j的时间τij是无人机到达任务j之前任务执行路径pi的函数，而无人机的任务执行路径又由其任务集合xi唯一确定。给定任务集xi∈{Ø∪J}Li和任务执行路径(任务执行时序)pi∈{Ø∪J}Li，τij可计算为

(3)

其中，J≜{1,…,Nt}为任务下标集合；pi(n)表示任务执行路径上的第n项任务；dj表示任务j的持续时间；Δ(a,b)表示无人机由任务位置a移动到任务位置b所耗费的时间；tloci表示任务i所处的位置;τi0表示无人机i开始执行任务的当前时间。

1.2 UAV任务执行代价函数

UAV执行任务过程中，会消耗武器、燃油，还会受到来自敌防御系统的反击，造成各种资源的损耗，统一称为UAV执行任务时付出的代价。代价的计算不仅与飞机和任务本身相关，还与飞机执行任务的路径有关，如飞行路径越长，则燃油消耗越大；在敌方雷达探测区域内暴露的时间越长，则被敌人发现和摧毁的可能性就越大[4]。因此，单独计算无人机i执行任务j付出的代价cij是不切实际的，只能在给定的任务执行序列下计算无人机总的任务执行代价。为模型表述上的方便，相关文献一般采用启发式方法计算cij，具体计算方法可借鉴文献[6-8]。

1.3 时间窗约束下的问题模型

综上所述，任务分配问题可用如下整数规划模型(一般为非线性)描述：

(4)

其中，二值决策变量xij为1则无人机i被指派给任务j，否则为0；I≜{1,…,Nu}，J≜{1,…,Nt}分别为无人机和任务的下标集。约束1为无人机载荷约束，Li表示无人机能完成的任务数上限；约束2表示各项任务仅能被一架无人机执行；约束3表示无人机的任务执行路径长度不能超过无人机的最大航程约束Mpi；约束4表示各项任务至多能被执行一次。

若仅从燃油损耗来计算无人机i执行整个分配任务的代价Ci，则

(5)

由于任务的时间窗约束很大程度上决定了任务的收益，在任务分配之初，决策者只能通过无人机的有效载荷、最大航程约束和各任务的执行时间，初步确定参加分配的任务和执行任务的无人机。因此，并非所有参与分配的任务必须被执行，而是根据约束情况来执行任务，使得任务分配的收益最大化。

2 DPSO和郭涛算法

2.1 DPSO算法

PSO算法[9]中每个粒子对应一个可行解，具有位置和速度两个属性，分别表示当前粒子在解空间的位置和移动速度，并以粒子位置向量对应的适应度函数值确定粒子的“优劣”程度。每个粒子通过下列公式更新自身状态：

(6)

目前PSO的研究大多局限在连续领域，为求解组合优化问题，一般采用3种方式对其进行离散化处理，称为离散粒子群算法(DPSO)，各求解方法采取的策略和优缺点见文献[10]，此处不再赘述。

2.2 郭涛算法

郭涛算法[11]是武汉大学郭涛提出的一种基于序列倒置(Inver-over)算子的优化算法(简称GT算法)。GT算法通过对种群内每个个体的子序列，按照一定的选择概率进行自适应的倒置，以此来提高算法的收敛速度。因郭涛算法兼具一元算子(以较小的概率p执行同一父体内的随机倒序)和二元算子(以较大的概率1-p执行不同父体间的导向性倒序)的成分，从而使其成为既有强的选择压力又有适应性算子的演化算法[12]。

由于GT算法是随机选择种群中的个体进行学习的，当前个体并非每次都能学到有用经验，其学习的盲目性，影响了算法的收敛速度[10]。并且，随着问题规模的扩大，GT算法解的质量下降很快[13]。

3 混合DPSO-GT算法的多UAV任务分配

多UAV多任务分配是复杂的组合优化问题，受DPSO算法和GT算法思想的启发，采用混合DPSO-GT算法求解该问题。

3.1 基本思路与粒子编码方式

混合算法的基本思路是：在DPSO算法中引入序列倒置算子，该算子在学习时不是随机选择学习对象，而是按照一定规律，从具有全局极值的粒子、具有局部极值的粒子子群以及种群中随机选择的粒子；保留GT算法中粒子自身的变异操作(随机倒序)，保证种群的多样性；改进GT算法的序列倒置算子，提高算法的收敛速度和精度；单次子序列倒置操作后立即对粒子评价，若新粒子优于旧粒子，更新旧粒子。

采用正整数向量编码的方式。对每个可能的解，编码应能表示Nt个任务在Nu架无人机之间的分配。设3架无人机执行6项任务某个可能的解可用路径序列[14]表示为：

5-0-4-3-6-0-2-1

这表示无人机1执行任务5，无人机2依次执行任务4，3和6，无人机3则依次执行任务2和1。若路径序列中存在相邻的两个0，如

5-2-1-0-0-4-3-6

则表示有一架无人机(无人机2)未被分配任务。

因此，多无人机多任务分配问题解的编码可用Nt+Nu-1维的向量表示。向量每一维对应的正整数表示任务或任务分割节点，该正整数在向量中所处的维数则表示其在任务路径序列中的位置。不至于引起后文倒置算子的混淆，用大于Nt的整数表示任务分割节点0。如上例3架无人机6项任务的任务路径序列

5-0-4-3-6-0-2-1

可用编码表示为：

5-7-4-3-6-8-2-1

3.2 序列倒置算子的改进

假设当前粒子s为5-7-4-3-6-8-2-1，图1为基本序列倒置操作的单次迭代过程：

图1 基本序列倒置操作单次迭代过程Fig.1 Single iteration of basic inver-over operator

由图1可知，第一次倒置操作为当前解引入了新的边(3,2)，第二次倒置操作在引入新边(7,2)的同时却将上次倒置引入的新边(3,2)从解中移除。

事实上，基于当前种群中各个体所包含的有用信息来指导倒序是郭涛算法成功的关键[12]，为尽量保留这些有用的信息，即倒置操作引入的新边，采用带方向的循环序列倒置[13,15]方法，将粒子的编码看成一个有方向的虚拟圆环，编码中所有的倒置操作均发生在从c的下一位基因到基因c′的有向子序列中，如图2所示。

图2 带方向的循环序列倒置操作单次迭代过程Fig.2 Single iteration of inver-over operator considering the direction of the tour

3.3 混合DPSO-GT算法参数设置

根据3.1节的思路，设计的混合算法引入3个学习选择概率参数和1个局部最优子群比参数：p1,p2,p3和rs。局部最优子群[10]指由种群中适应度较高的部分粒子组成的子群，若种群粒子规模M=100，rs=0.2，则局部最优子群由适应度较高的前20个粒子组成。

图3 粒子学习来源及选择概率区分Fig.3 Learning resource of particles and selection probability differentiating

如图3所示，概率p1用于决定当前粒子是从自身挑选一个基因进行随机倒置操作还是从其他粒子中挑选基因进行导向性倒序操作；p2和p3则用于区分当前粒子向种群中其他粒子学习时，粒子的来源。类似PSO算法中的可变惯性权重w，概率值p1和p3随迭代的进行逐步减小，如图3中箭头所示，其值按式(7)变化

(7)

其中，g为当前运行的代数，Ng为算法设定的运行代数。在算法运行初期，p1和p3较大，类似文献[10]的方法，粒子随机倒置操作和向种群中全局最优以外的其他粒子学习的导向性倒置操作较多，有利于算法跳出局部极小点，便于全局搜索；而到了算法运行后期，则算法类似文献[12]的快速倒序算法，粒子向种群中其他粒子学习的概率和向全局最优值学习的概率相近，在保持种群多样性的同时，利用当前最优解指导倒序，加快算法收敛。概率值p2不变，设定为0.5。

3.4 适应度函数

算法的适应度函数即为式(4)，通过对粒子的编码可实现约束2和约束4，对于无人机任务能力约束和最大航程约束，采用如下方法：

当分配方案(粒子)中某架无人机的任务数超出其能完成最大任务数时，算法不再计算方案中后续任务给该架无人机带来的收益和付出的代价。

当分配方案中某架无人机的任务数在其能完成最大任务数之内时，判断无人机的当前航程是否超出其最大航程，若是，则将任务列表中的当前及其后续任务去除。

3.5 混合DPSO-GT算法描述

混合算法可描述如下：

步骤1 设置种群大小M、运行总迭代数Ng、学习选择概率p1～p3、局部最优子群比rs。

步骤2 根据种群大小，按3.1节的编码方式随机产生粒子并计算其适应度值。求每个粒子的Pi，并求出种群的Pg。

步骤3 按式(7)计算p1和p3，根据rs值确定局部最优子群M′。

步骤4 对种群中的每个粒子S，随机选择一个基因c。

步骤6 判断S的基因c和c′是否相邻。若相邻，判断是否种群中所有粒子都已完成学习，如学习未完成，转入步骤4；若已完成，转入步骤9。若两基因不相邻，则转入步骤7。

步骤7 按3.2节提供的方法进行子序列倒置。单次倒序操作后，按照式(4)、式(5)，立即计算该粒子的适应度值，若该值大于序列倒置前适应度值，则更新当前粒子；否则，不更新当前粒子。若更新后该粒子的适应度值大于其Pi值，则更新该粒子及其Pi值，否则不更新。同样，若Pi值大于Pg值，则更新相应的Pg值及其对应的粒子。

步骤8 令c=c′，转入步骤5。

算法的具体流程如图4所示。

图4 混合DPSO-GT算法流程框图Fig.4 Flow chart of mixed DPSO-GT algorithm

4 仿真算例

4.1 任务想定

假设经前期作战，我方由3架具备侦察、监视能力的无人机组成的编队，欲实施对敌10个目标的侦察、监视任务。本节仿真分析运用混合算法，完成3架无人机对上述10个目标进行任务分配的效果。

仿真场景中，3架无人机的初始位置，10个任务的期望开始时间和位置坐标在横坐标为(-2km，2.5km)，纵坐标为(-1.5km,5.5km)的二维平面内随机生成；设侦察监视任务的持续时间均为10s；采用式(1)～(5)的无人机任务分配模型。

表1和表2中的数据为某次仿真实验中的无人机信息和目标信息。假设目标和无人机在二维平面内运动，便于说明问题，假设任意两目标位置距离远大于无人机最小转弯半径，无人机在不同位置间的航行距离为该两点间的Euclidean距离。

表1 无人机信息表

表2 目标信息表

4.2 任务分配结果

基于4.1节中的想定，设各架无人机最大任务数为4，使用混合DPSO-GT算法得到任务分配结果如图5、图6所示。图5表示各无人机的任务分配和任务执行路径(任务执行顺序)，图6表示各无人机的任务计划表，即任务的执行时间，图6中粗实线表示任务实际执行时间，细虚线表示任务期望执行时间。

图5 时间窗约束下的无人机任务路径Fig.5 UAV paths with time windows

图6 无人机计划时刻表Fig.6 UAV schedules

由图6可知，运用本算法生成的无人机任务计划表，任务1比预计时间推迟7秒执行，任务7因各架无人机距其较远，无法在其有效时间内到达而无法执行，其他任务都按计划执行，取得了很好的规划结果。设各架无人机最大任务数为2，则规划结果如图7所示。

图7 最大任务数约束下的无人机任务路径Fig.7 UAV paths with maximum workload constrains

设各架无人机最大任务数为4，单架无人机最大航程不超过6km，则规划结果如图8所示。

图8 最大航程约束下的无人机任务路径Fig.8 UAV paths with maximum range constrains

4.3 与其他方法的比较

为验证混合DPSO-GT算法(后文简称之为MIDPSO算法)的有效性，将该方法和文献[4]的DPSO算法、文献[12]的快速倒序算子(FasterInversionOperator,FIO)、文献[10]的反序DPSO(Inver-overDPSO,IDPSO)算法对上述想定条件下进行100次蒙特卡洛仿真结果比对，其中种群规模为40，迭代次数为100，其他参数设置见3.3节及相关文献。

表3为DPSO算法，IDPSO算法，FIO和MIDPSO算法的运行结果。

表4为其他3种算法获得与MIDPSO算法同等求解质量时，种群大小、迭代次数、平均运行时间的100次蒙特卡洛仿真统计值。

表3 4种算法同等运行条件下的求解质量

表4 4种算法同等求解质量下的运行条件

由表3、表4结果可知，在同等运行条件下，和同等的求解质量要求下，MIDPSO算法相比其他算法，在时效性和求解质量方面都具有显著优势。

仿真发现，MIDPSO算法的运行效率受学习选择概率参数p1～p3的影响较大，3.3节对3个参数的设置是经过多次蒙特卡洛仿真实验得出的结果，限于篇幅，不做进一步说明。

5 结论

讨论了时间窗约束下的多UAV协同多任务分配问题。时间窗的约束，任务必须在指定的时间范围内完成，建立了时间窗约束下的任务分配模型；设计了简洁的任务分配编码方式；提出的混合DPSO-GT算法综合了离散粒子群算法和郭涛算法的优势，同时又较好地克服它们的缺点。以多无人机编队执行对敌监视侦察任务为例，说明了该算法的有效性。考虑无人机航路可飞性约束以及任务的时序性约束将是课题进一步讨论的内容。

References)

[1] 沈林成，牛轶峰，朱华勇.多无人机自主协同控制理论与方法[M].北京：国防工业出版社,2013:1-20.

SHENLincheng,NIUYifeng,ZHUHuayong.TheoriesandmethodsofautonomouscooperativecontrolformultipleUAVs[M].Beijing:NationalDefenseIndustryPress, 2013: 1-20. (inChinese)

[2]RyanJL,BaileyTG,MooreJT,etal.Reactivetabusearchinunmannedaerialreconnaissancesimulations[C]//ProceedingsofWinterSimulationConference, 1998,1: 873-879. [3]WeinsteinAL,SchumacherC.UAVschedulingviathevehicleroutingproblemwithtimewindows(Preprint)[R].AFRL-VA-WP-TP-2007-306, 2007.

[4] 霍霄华，沈林成. 多UCAV协同控制中的任务调度问题研究[J]. 系统仿真学报, 2007, 19(16): 3623-3626.

HUOXiaohua,SHENLincheng.Taskschedulinginmulti-UCAVcooperativecontrol[J].JournalofSystemSimulation, 2007, 19(16): 3623-3626. (inChinese)

[5]PondaS,ReddingJ,ChoiHL,etal.Decentralizedplanningforcomplexmissionswithdynamiccommunicationconstraints[C]//Proceedingsof2010AmericanControlConference,Baltimore,MD:AACC, 2010:3998-4003.

[6] 杜继永，张凤鸣，杨骥，等. 多UCAV协同任务分配模型及粒子群算法求解[J]. 控制与决策, 2012, 27(11): 1751-1755.DUJiyong,ZHANGFengming,YANGJi,etal.CooperativetaskassignmentformultipleUCAVusingparticleswarmoptimization[J].ControlandDecision, 2012, 27(11): 1751-1755. (inChinese)

[7] 邸斌，周锐，丁全心. 多无人机分布式协同异构任务分配[J]. 控制与决策, 2013, 28(2): 274-278.

DIBin,ZHOURui,DINGQuanxin.Distributedcoordinatedheterogeneoustaskallocationforunmannedaerialvehicles[J].ControlandDecision, 2013, 28(2): 274-278. (inChinese)

[8] 王婷，符小卫，高晓光. 基于改进遗传算法的异构多无人机任务分配[J]. 火力与指挥控制, 2013, 38(5): 37-41.WANGTing,FUXiaowei,GAOXiaoguang.Cooperativetaskassignmentforimprovedgeneticalgorithm[J].FireControl&CommandControl, 2013, 38(5): 37-41. (inChinese)

[9]KennedyJ,EberhartrC.Particleswarmoptimization[C]//ProceedingsofIEEEInternationalConferenceonNeuralNetwork,USA:IEEE, 1995: 1942-1948．

[10] 郑东亮，薛云灿，杨启文，等. 基于Inver-Over算子的改进离散粒子群优化算法[J].模式识别与人工智能, 2010, 23(1): 97-102.

ZHENGDongliang,XUEYuncan,YANGQiwen,etal.ModifieddiscreteparticleswarmoptimizationalgorithmbasedonInver-Overoperator[J].PatternRecognitionandArtificialIntelligence, 2010,23(1): 97-102. (inChinese)

[11]TaoG，MichalewiczZ．Inver-overoperatorfortheTSP[C]//Proceedingsofthe5thInternationalConferenceonParallelProblemSolvingfromNature, 1998: 803-812．

[12] 闭应洲，丁立新，杨小雄. 快速倒序算子的研究[J]. 计算机工程与应用, 2009, 45(4): 45-47.

BIYingzhou,DINGLixin,YANGXiaoxiong.Onfasterinversionoperator[J].ComputerEngineeringandApplications, 2009, 45(4):45-47. (inChinese)

[13]WangYT,SunJ,LiJQ,etal.AmodifiedInver-Overoperatorforthetravelingsalesmanproblem[C]//Proceedingsof7thInternationalConferenceonIntelligentComputing,2012:17-23.

[14]PengY，ZhuHY.ResearchonvehicleroutingproblemwithstochasticdemandandPSO-DPalgorithmwithInver-Overoperator[J].SystemsEngineering-Theory&Practice, 2008, 28(10): 76-81.

[15] 安晶，徐森. 一种结合粒子群优化理论改进的郭涛算法及其应用[J]. 计算机应用与软件, 2014, 31(2): 296-299, 320.ANJin,XUSeng.APSOtheoryintegratedimprovedGUOTAOalgorithmanditsapplication[J].ComputerApplicationsandSoftware, 2014, 31(2): 296-299, 320. (inChinese)

Cooperative task allocation of multi-UAVs with mixed DPSO-GT algorithm

YAN Ji1, LI Xiangmin1,2, LIU Bo2

Ageneralmathematicsmodelforcooperativetaskallocationofmulti-UAVswithtimewindowsconstrainswasproposedwhichincorporatingtaskgainsandexecutiontimedirectly,andsimplifingthemodelformulationandalgorithmdesigning.Bydefiningasuitableparticlestructure,analgorithmbasedontheprinciplesofdiscreteparticleswarmoptimizationandGuoTaoalgorithmwasdesigned.TheInver-overOperatorwasdirectedbytheswarm,thelocalandglobaloptimal.Variablelearningselectionprobabilityisintroducedintothealgorithmtoselectthelearningparticles,andtheInver-Overoperatorwasmodified.Simulationverifiestheproposedtaskplanningmethodologyforcomplexmissions.

discreteparticleswarmoptimizationalgorithm;GuoTaoalgorithm;taskallocation;timewindowsofvalidity;multi-UAVs

2014-10-27

航空科学基金资助项目(20135184008)

颜骥(1984—)，男，湖南湘阴人，博士研究生，E-mail：53072472@qq.com;李相民(通信作者)，男，教授，博士，博士生导师，E-mail：xiangmin_li@163.com

10.11887/j.cn.201504027

http://journal.nudt.edu.cn

TP

A