网络化战场环境下多无人机调度问题*

马纯超，尹 栋，朱华勇

（国防科技大学机电工程与自动化学院，长沙 410073）

网络化战场环境下多无人机调度问题*

马纯超，尹 栋，朱华勇

（国防科技大学机电工程与自动化学院，长沙 410073）

针对网络化战场下无人机（UAV）跨区飞行、信息共享等特点扩大了任务区域与规模而引发任务分配难题，对无人机运动及通信特性、任务时间窗约束和初始战场布局等因素建模，根据目标属性对其分组以降低问题复杂度，应用优化算法得到初始解，随后进行全局交换、删除及插入等调整得到最终调度方案，由此搭建快速求解多UAV任务调度的通用算法框架。最后应用遗传算法验证，仿真结果表明：该框架在解决多无人机大规模任务分配时具有较好的时效性和适应性。

网络化战场，多无人机任务分配，遗传算法

0 引言

信息化战场下，数据链将战场上的指挥中心、各级指挥所、各参战部队和武器平台链接在一起，构成陆海空天一体化数字信息网络，保证各系统之间的数据传输与资源共享。在该战场环境下，为优化资源配置，各种类无人机被统一管理，并可跨区域执行任务，相比传统多无人机任务分配，该类问题约束与规模更复杂，且要求一定时效性，传统约束满足问题（CSP）算法难以满足要求。

对复杂约束的多无人机多目标任务分配问题，传统的完全搜索方法难以有效或快速得到最优解，多采用改进的禁忌搜索［1-2］、群体进化［3-4］、市场拍卖［5］求解，或结合多种算法优势得到更优方案［2，6-7］。针对多区域和大规模无人机使用，为提高任务分配有效性和时效性，文献［8］建立多基地多UAV协同规划模型，采用“自适应”进化多目标优化算法对不同位置、不同性能的无人机进行规划；文献［9］对目标进行模糊C聚类，从局部出发优化，得到快速分配方案。文献［10］基于任务依赖关系结合迭代自组织数据分析算法（ISODATA）对任务进行分组，使用粒子群优化算法得到任务分配方案。

文献［8］中UAV被限制在所属基地控制下，UAV的使用被限制；文献［3-4，10］将任务执行时间作为代价考虑，而未考虑时间窗约束；文献［2，7，9］中对目标自身特性如其优先级等的不同未加考虑。且除文献［5，8］外，其他文献实验中目标可全部被UAV分配，对UAV不能全部完成任务时如何取舍考虑稍欠缺。除文献［8］外以上研究均在单基地下考虑。本文基于以上研究，结合问题特性，分析UAV平台特性、任务约束、战场初始布局等因素对多UAV任务分配的影响。针对问题规模较大的情况，对目标分组处理降维，得到局部初始解，随后全局调整得到最优解。

1 通用战术网下多UAV资源调度问题

通用战术网由通用数据链路和通用控制链路组成，使得战场中的平台、系统连接成有机整体。通用控制链路使得UAV活动摆脱了传统视距链约束，可由分布于战场的任一具有相应操控能力的地面站（GCS）控制飞行。通用数据链联网使得分布于战场任意位置的UAV可将得到的信息进行全局共享，使整个战场的各级作战单元共享高度的感知信息，实现作战同步化。

在此背景下，UAV、地面站及通信链路等均被作为资源由指挥中心进行统一管理和调度，根据任务约束及要求，合理选派资源，由地面站控制UAV执行任务。

1.1 问题描述

如图1，假设通用战术网络已建立，在［0，S］*［0，S］战场区域内分布有Ng个不同能力的地面控制站{GCS1，GCS2…GCSNg}和随机分布的Nv个不同类型的UAV{V1，V2…VNv}，及Nt个目标 {T1，T2…TNt}。UAV由任务管理中心进行统一管理。任务管理中心从战场全局出发，综合考虑UAV平台特性、目标特点和GCS等战场环境进行多UAV对多目标进行侦察的任务规划。

UAV平台特性主要考虑其巡航速度、搭载传感器不同等方面，目标考虑其优先级和时间窗特性等，GCS能力的不同则体现在其可操控的UAV数量和通信覆盖范围等。表1用多元数组对各因素进行了形式化描述。

1.2 通用求解框架

针对网络化战场下大规模UAV任务分配难以快速找到最优解，提出的解决方案是首先将任务目标按照一定原则分类，分为有一定共同特性的子集合。根据任务子集需要的UAV能力选取执行任务的UAV集合，对目标子集合分别按时间窗、优先级等排序后，依次采用优化算法求得最优初始解，最后进行全局调整，得到优化分配方案。

1.2.1 算法设计及步骤

算法框架主要分为任务目标预处理、求解初始解和初始解改进3部分。下页图2给出了算法设计流程。

具体实施过程如下：

（1）目标预处理。主要进行目标分组，降低问题规模。目标分组目的是对一组目标点尽可能使用同样的UAV资源执行，通常的分类原则有：①目标侦察情报类型要求（图像、视频及其分辨率等）。②目标紧急程度。③目标位置（聚集在同一区域或在某无人机活动半径内）。④对时间跨度较长的目标，将处在同一时间段内的目标分为一组。⑤同一通信覆盖区域内的目标归为一组等等。针对分组并排序后的目标集合，选取具有执行该组目标能力的UAV集合进行调度。

（2）求解初始解。对得到的目标与无人机集合，依照其不同分组原则等，选取如遗传算法、粒子群算法等合适的最优化算法求取子问题初始解。

（3）初始解改进。按照步骤2得到的初始解，只是问题的局部较优解，需要从全局进一步改进。对于不同的解序列，根据其时间窗的共同覆盖程度，可以对解序列进行一系列插入、删除、交换、重新排序等调整，从而获得全局最优或较优解。

如图3所示全局调整优化方案实例，对UAV1、UAV2的任务序列，任务j在UAV1的空闲时间窗内，若j目标位置满足UAV1从i目标飞行至i+1目标的时间段内执行，则可将j目标插入UAV1的任务序列中。同样，若i+2与j+2目标交换后使全局优化值更高，则可以进行交换。

1.2.2 问题数学建模

对某含有N个目标的任务子集合T={1，2，3，…，i，j，…，N}，其对应含M架无人机集合UAV= {1，2，3，…，k，…，M}，决策变量xijk表示无人机k从执行完任务i后继续执行任务j。UAV分配任务的3个优化指标主要为任务完成的收益最大、代价最小和分配的目标尽量多。

任务收益优化目标：

rijk表示从i出发去执行j时获得的收益，收益由目标的优先级确定，rijk=xijk*L（j），保证尽量执行优先级高的目标。

任务代价优化目标：

cijk表示从i出发去执行j时的代价，包括路径代价和通信代价。通信代价与目标位置距离GCS距离相关，dis为目标间距离。结合通信信号在自由空间衰减公式

可以将无人机从i目标出发执行j目标的代价表示为式（4）。式（5）中Lbf：自由空间损耗，F：信号频率，D:传输距离。路径代价即各个目标点之间距离之和。

任务分配个数优化指标，表示分配的目标个数尽可能多：

式（7）约束每个目标只被某一UAV单独执行。式（8）为航程约束，式（9）、式（10）为时间窗约束：

［ai，bi］代表任务i的任务时间窗，tstarti/tstartj：实际开始侦察目标i/j的时间，tleavei/tleavej：实际离开目标i/j的时间，twaitj：开始侦察目标j时的等待时间，tworkj：目标j的实际侦察持续时间。

2 遗传算法求解算例

为验证算法框架合理性，根据分析的问题特点，对传统遗传算法进行改进并验证。

2.1 编码

本文将任务序列集合作为一条染色体，每个基因表示一个任务目标，基因取值为无人机的编号。图4表示大小为n的目标集合编码。编号为2的无人机执行第1、3、7…等个目标，0为该目标未被任何UAV执行。采用对基因位随机赋值UAV编号的形式进行群体初始化，并用时间窗约束式（9）、式（10）判断生成的群体是否可行。

2.2 适应度函数

该问题是复杂的多目标优化问题，为便于求解，将多个目标函数设置不同权值融合在一个目标函数中。由此定义适应度函数：

其中Reward为染色体对应解得到的总收益，Cost为其总代价，Percent为目标完成度（完成目标数与总目标数的比值）。权值设定一般根据决策者的偏好或经验确定。由于目标函数的量纲不同，为保证优化结果的合理性，需将它们统一到同一数量级上。如本问题未调整时Reward的数量级在102而1/Cost数量级在10-1，则代价的变化对适应值的影响将被收益指标所“淹没”，导致优化结果不合理。

2.3 遗传算子

根据本问题自身特殊性，遗传算子中除选择算子仍采用传统轮盘赌法，对交叉算子和变异算子均做如下改进。

2.3.1 交叉算子

对随机两两配对的每对父代个体，生成0-1内的随机数与交叉概率Pc比较，小于Pc的配对按照设置的交叉点进行交叉。交叉算子如图5，长度为n的染色体存在n-1个交叉点，设置交叉点时首先随机生成n-1个［1，n-1］范围内的不重复随机数，依次按照生成的随机数设置交叉点，直到交叉后个体仍为可行个体，将其遗传到子代种群。若全部交叉点设置完仍无可行个体，则不进行交叉，直接遗传到下一代。

2.3.2 变异算子

变异算子的处理是对每个长度为n的染色体生成［0，1］内的n个随机数，与变异概率Pm比较，小于变异概率值的进行变异。在该问题中，如图6，当个体需要变异时，优先变异基因值为0的位置，置换为其他无人机编号，判断变异后个体是否为可行解，若均不可行，则变异随机数小于Pm的位置，置换为不同于该位置的无人机编号，判断是否可行。若均不可行则不进行变异。规定同一染色体只有一处基因值发生变异。

3 仿真结果与分析

3.1 结果分析

假设在800 km*800 km的战区内存在3个地面控制站，8架侦察UAV对随机分布在战区不同位置的40个目标进行侦察。下页表2、表3给出了UAV和目标的仿真数据。

对40个目标根据位置进行分类，按照时间窗和优先级进行排序，并选取相应UAV集合，最终得到3组目标集合及对应UAV的编号集合，如下页表4。

根据上述算法描述，优先对T1、T3进行分配，对T1、T3中未进行分配的目标选取优先级较高的加入T2，初始群体设置为100个，交叉概率Pc=0.75，变异概率Pm=0.01，遗传1 000代，权重值w1=0.5，w2=0. 3，w3=0.2。每组目标序列执行10次算法，由于遗传算法的初始解是随机生成的，且进化方向不定，因此会产生适应度收敛到一定值的几个不同结果，挑选适应值最大的4组，得到图7分配结果，T2序列中被标记出的为其他两个序列未分配且优先级较高而加入的目标。

程序平均规划时间72 s，40个目标点中10个目标未分配，成功率为75%。仿真实验中目标点与UAV位置及任务时间窗均是随机得到的，目标特性与UAV能力导致目标并不一定被分配。图8和图9给出了仿真实验结果中不同UAV执行任务的顺序和时间窗，综合两图及目标参数可以看出：①未被分配的目标其优先级一般较小。②未分配目标其位置和时间窗相互约束，即尽管其时间窗在其他UAV空闲时间范围内，但地理位置相差较远导致不可能完成该目标，同样在UAV执行路径附近的其他目标因时间窗不符合同样不能被分配。根据时间窗进行全局调整已经找不到更优解，且规划时间较短，可判定该方案是最优的。

3.2 算法比较

为判断算法的适应性，分别进行4架UAV对20个目标，8架UAV对40个目标，15架UAV对80个目标，用传统遗传算法和本文先分组求初始解并全局调整的改进算法进行分配，得到结果数据如下：

从实验可以看出，在问题规模较小时，本文提出的分组遗传算法由于需要进行多次求解并全局调整，传统遗传算法更具优势，但当问题规模扩大，需要搜索的解空间规模呈指数级增长，分组遗传算法的规划时间远低于传统遗传算法，在15架UAV，80个目标时，传统算法在执行1 h后仍未找到可行解，分组遗传算法则在较短时间内可以给出合理的分配方案。

4 结束语

本文研究了基于战术通用数据链在战场全局调度下无人机的多目标分配问题，对问题规模较大难以求解的难题，提出对目标分组降低问题纬度，求得一系列初始解并进一步进行全局调整，得到最终解决方案的思路方法。通过仿真实验可以看出本文设计的目标分组求解并在全局调整寻找最优解的算法，对较大规模的无人机目标分配问题具有较好的合理性、时效性和适应性。同时可以根据决策者的不同偏好设置适应度权重系数以满足决策需要，具有较大的实际应用性。下一步工作将对约束因素更加实际化考虑，如将路径代价替换为油耗模型，侦察得到的不同情报类型的回传方式对分配的影响，调度过程中的安全问题及动态任务的调整，使算法更具实际性。

［1］陈英武，方炎申，李菊芳，等.卫星任务调度问题的约束规划模型［J］.国防科技大学学报，2006，28（5）:126-132.

［2］Yan P，Tan B.Evolutionary Group Theoretic Tabu Search Approach to Task Allocation of Autonomous Unmanned Aerial Vehicles［C］//Control and Automation（ICCA），2013 10th IEEE InternationalConference on.IEEE，2013: 687-692.

［3］施展，陈庆伟.基于改进的多目标量子行为粒子群优化算法的多无人机协同任务分配［J］.南京理工大学学报，2012，36（6）:945-951.

［4］王婷，符小卫，高晓光.基于改进遗传算法的异构多无人机任务分配［J］.火力与指挥控制，2013，38（5）:37-41.

［5］Lin L，Sun Q B，Wang S G，et al.Research on PSO Based Multiple UAVs Real-Time Task Assignment［C］//2013 25th Chinese Control and Decision Conference（CCDC），2013: 1530-1536.

［6］龙国庆，祝小平，周洲.多无人机系统协同多任务分配模型与仿真［J］.飞行力学，2011，29（4）:68-71.

［7］Liu Z，Quan L，Ding W，et al.A Task Assignment Algorithm for Multiple AerialVehicles to Attack Targets With Dynamic Values［C］//IEEE Transactions on Intelligent Transportation Systems，2013，14（1）:236-248.

［8］田菁.多无人机协同侦察任务规划问题建模与优化技术研究［D］.长沙：国防科学技术大学，2007.

［9］龙国庆，祝小平，董世友.基于聚类算法的多无人机系统任务分配［J］.火力与指挥控制，2011，36（12）:54-59.

［10］谭和顺，曹雷，彭辉，等.一种多无人机层次化任务分配方法［J］.解放军理工大学学报（自然科学版），2014，15（1）:18-24.

A Study on Multi-UAVs Scheduling in Networked Battlefield

MA Chun-chao，YIN Dong，ZHU Hua-yong
（College of Mechatronic Engineering and Automation，National University of Defense Technology，Changsha 410073，China）

In networked battlefield，UAVs can fly cross regions and share information to others，which expand the area and scale of tasks.In order to address the difficulties of mission allocation caused by that，this paper will first model UAVs motion and communication features，task time window，initial battlefield layout，etc.，group the targets by their characteristics in order to reduce the complexity，then apply optimization algorithm to obtain initial solution and adjust them through exchange，deletion or insert so as to obtain the final plan，and build a common algorithm framework for fast solution.Genetic algorithm will be employed for verification.The simulation results indicate that the framework may achieve higher timeliness and adaptability in large-scale multi-UAV mission allocation.

networked battlefield，multi-UAVs mission allocation，genetic algorithm

V279

A

1002-0640（2015）10-0031-06

2014-09-05

2014-10-17

国家自然科学基金青年科学基金资助项目（71303252）

马纯超（1990- ），男，河北衡水人，硕士研究生。研究方向：无人机系统技术。