一种面向无人机区域协同覆盖的感知任务分配方法

宋伟中 王行业 王 宁

1(黄河科技学院信息工程学院 河南 郑州 450000) 2(华北水利水电大学信息工程学院 河南 郑州 450000)

0 引 言

智能无人机目标搜索在很大程度上取决于无人机对区域环境的协同覆盖和感知[1-2]，将无人机集群搜索的问题转化为目标区域协同最优覆盖问题，具有空间与功能上的分布性、任务执行的并行性及容错性，可以有效地对危险区域进行目标搜索和定位。感知任务的合理分配是影响多无人机区域协同覆盖的一个重要因素[3]，也是多无人机自主协同控制的重要研究方向[4]。

面向无人机区域协同覆盖的感知任务分配方法，主要分为集中式任务分配和分布式任务分配[5]。其中，集中式任务分配方法通过中心系统控制无人机之间的通信和数据传输，针对任务需求和任务约束，确定无人机之间的任务序列，从而建立调度模型进行优化求解，包括整数规划模型[6]、人工蚁群算法[7]、进化算法[8]；与集中式任务分配方法相比，分布式任务分配方法以去中心化的方式平衡任务分配的交互，能够实现对任务态势的快速优化组合及高效的同步共享，如基于合同网[9]方法，通过“招标-投标-中标”的市场拍卖机制实现无人机任务的委派和迁移，使系统以较低的代价和较高的质量完成区域协同覆盖任务。考虑目标区域的动态变化和不确定性，以及无人机的局部观测性，很多研究在动态实时环境下引入栅格化[11]的划分方法对区域覆盖，从而使无人机根据相同的栅格区域分配目标控制任务，实现代价最小的区域覆盖。但栅格化的划分使目标数据太大，导致无人机在大量的无关结果中筛选信息，计算开销较大；交互式动态图[12]和基于多agent[13]的任务分配方法可以求解空间状态的目标搜索问题，在无先验信息环境下实现区域协同覆盖，但该方法受限于知识表达和推理的局部性，不能够感知任务特征与目标区域的内部差异，使任务分配不能保证每次都计算出最优解；群智感知[14]任务分配系统寻求利益最大化的众包任务竞争与激励模式，可以为无人机区域协同覆盖提供一种渐进式的任务分发服务，但其需要绑定多样化的移动设备，且随着任务的动态程度加大，需要选择更多感知设备参与者调度无人机对区域协同覆盖的任务，对于无人机针对异构设备的数据采集过于频繁且要求较高，应用实现较为困难。

本文针对任务需求的差异，提出一种面向区域协同覆盖的任务分配方法。考虑无人机局部观测性和环境不确定性，该方法在构建分布式马尔可夫覆盖框架模型的基础上，利用目标线路集和任务扩散调度序列集对目标区域进行差异化计算，提出基于强化学习的感知任务差异化分配方法，实现动态目标区域的最优覆盖策略；采用MATLAB仿真平台验证本文方法的有效性。

1 问题描述及结构框架

1.1 环境描述

(1) 无人机属性及飞行参数。无人机在一定区域W×W内飞行，集群控制系统对目标进行搜索覆盖，并受到包括环境障碍、碰撞规避、电磁干扰和威胁入侵等干扰因素的约束和影响。设无人机集群系统为基于四旋翼无人机的同构群体，每台无人机都架构了相同的传感器和观测系统，数量为NU台，计算无人机的飞行参数，令其在固定高度下通过加速器直接测量机体坐标下的水平移动速度为VU，最大偏角度为φmax，有效探测距离为L。

(2) 动态目标搜索任务描述。设有NT个动态目标和Nd个干扰区域，如图1所示。分别用三角形表示动态目标，用圆形表示干扰因素，目标以VT的速度向任意方向移动，所有的目标信息在搜索任务前均未知，无人机系统的任务是搜索这些目标并保证无人机不进入干扰因素，利用目标线路实现对目标区域的稳定覆盖。

图1 任务搜索区域

1.2 任务分配控制框架

针对在线实时环境下区域协同覆盖的需求和目标信息的流向特点，将任务分配控制框架分为操作平台、区域覆盖和任务分配三个模块，如图2所示。

图2 感知任务分配控制框架

操作平台为用户提供数据基础服务和可视化操作界面，包括ArcGIS数据服务和信息系统界面，通过分布式通信组网联通实时在线的多台无人机系统。

区域覆盖模块包括区域差异划分、分布式马尔可夫覆盖模型和任务扩散调度，当获取区域覆盖需求后，首先根据任务关联比重将拟覆盖区域进行差异划分，然后构建分布式马尔可夫覆盖模型在划分的区域中选择覆盖线路，为任务的扩散调度提供数据交互的模型。

任务分配模块在实现差异化分配计算的基础上，提出强化学习的方法，利用选择目标线路集和扩散调度任务序列，从而找到一个策略使无人机达到最大的奖励回报信号，实现区域的最优协同覆盖。

2 目标区域覆盖模型

2.1 目标区域差异划分

(1)

然后，根据Voronoi图和任务关联比重对目标区域进行差异划分，计算式如下：

(2)

2.2 分布式马尔可夫覆盖模型

无人机实时在线感知已差异划分的目标区域，针对局部不确定态势环境下，对于任务分配而言根据差异划分的区域线路选择判断区域覆盖的程度，利用文献[17]所提出的分布式马尔可夫覆盖模型推测并优化最佳的个体路线集合和群体行为，可以解决对区域覆盖的任务分配。

定义1分布式马尔可夫覆盖模型。对于一台无人机Ui在子区域Ω而言，将目标区域覆盖构建为一个分布式马尔可夫模型：

M={Ui,Si,R(Ui),{Ai},{δi},Pi,Reword,X0}

(3)

式中:Ui表示无人机集合，Ui={U1,U2,…,UN}；Si为无人机状态空间；R(Ui)表示无人机访问某一子区域Ωi的线路集合；{Ai}表示为动作空间集合，以水平移动速度VU在任意方向飞行；{δi}表示无人机Ui可观测的目标集合。δi(t)={regi(t),posi(t),0≤i≤1}，表示t时刻第i台无人机Ui的局部可观测目标区域信息regi(t)和位置信息posi(t)，regi(t)表示对当前区域内观测信息的集合info={infoconvered,infounconver,Ci}，infoconvered表示已被覆盖的子区域集合，infounconver表示未被覆盖的子区域集合，Ci为满足干扰因素条件的集合。无人机在可观测范围内可以根据区域划分判定目标所在位置。

Reword计算了无人机Ui在当前状态Si下经过某个动作Ai到达状态Si+1的回报值，在覆盖线路选择时使用无人机获得了不同的回报值，从而保证对目标区域的覆盖。

X0为初始信念状态，无人机通过初始信念状态和初始函数获取当前状态向量，指导无人机的行为动作。

2.3 任务扩散调度

由于任务信息转发所需的近距离接触时间是不可忽略的，需要对任务信息在节点间的扩散复制时间进行定量分析。对于任务信息q而言，在传感器传输方式下转发所需的时间为Ttrans(q)，在数据的扩散分配过程中，对已携带任务信息的无人机，需要寻找交互时间满足数据转发时间的节点对象进行扩散。为了对节点间的交互时间进行描述，本文定义可调度序列对无人机区域覆盖的任务分配进行描述。

基于分布式马尔可夫覆盖模型，描述两台无人机之间关于某一任务数据所存在的空闲时间对，记为TP。首先将发送任务数据的发送方无人机称为出节点，接收方称为入节点。针对从出节点U1发送的任务数据q，若出节点U1和入节点U2在时刻Tmin之后存在关于[Ts,Te]的空闲时间对，其中Ts为数据传输的起始时刻且Ts≥Tmin，而Te为Ts与Ttrans(q)之和，则称为两者存在时刻Tmin之后关于数据q的可调度序列，记为:

TP=({δi},U1,U2,[Ts,Te],Reword)

(4)

式中:Reword表示当前状态下覆盖线路的回报值，用于标记任务数据q的扩散可调度结果。如图3所示，无人机U1和U2在某一区域内的停留时间为[T0,T5]和[T0,T6]，其中灰色横段表示无人机的忙碌时段，即携带的数据正在任务调度中，时段[T1,T2]和[T3,T4]为两台无人机的空闲时间对，如果U1携带的数据信息需要向U2扩散，且所需的扩散时间段[Ts,Te]∈[T1,T2]或[T3,T4]∈[Ts,Te]，则U1和U2之间为关于数据q的可调度序列。

图3 任务扩散调度示意图

3 多无人机任务差异化分配方法

3.1 任务差异化分配

区域划分根据特定的任务需求和相关事务的物理位置对整个感知区域作了平面划分，计算无人机对每个子区域的任务关联比重和最优划分，为任务信息的差异化提供依据，而区域覆盖和任务扩散调度是实现差异化分配的重要部分。这是由于一方面区域覆盖用于选定直接分配的路线，另一方面任务扩散调度用于触发无人机之间任务信息的调度和动作方案。因此，首先通过分布式马尔可夫模型选择合适的无人机线路集合R(Ui)，以及用式(2)计算无人机对子区域内的关联比重J，并以J为目标进行覆盖线路选择。目标线路集合RΩ与任务关联比重之间的差异值为：

(5)

式中：G(r′,Ωi)表示当前无人机Ui线路是否覆盖子区域Ωi，如果覆盖则值为1，未覆盖则为0。在计算线路选择时通过贪婪方式不断地计算E，从而对具有差异性的目标线路集合进行选择。

3.2 基于强化学习分配方法

选择目标线路集后，为使可扩散调度序列集在任务之间达到最优分配，在分布式马尔可夫覆盖模型的基础上，引入强化学习方法[18]在任务区域未知的前提下，通过与环境交互来获取行动状态信息并评价反馈覆盖效果，利用不断选择目标线路和扩散调度任务序列，逐步改进覆盖策略。而求解任务差异分配的目的是找到一个策略使无人机达到最大的奖励回报信号，通过状态值函数寻找最优策略，最优策略对应的状态-联合动作函数(Si,Ai)为最优值函数，记为Q*。在分布式马尔可夫覆盖模型作用下，t时刻无人机Ui在状态Si下执行Ai行为的值函数为：

(6)

算法步骤具体如下：

输入：输入覆盖需求向量K；任务调度需求向量W；子区域无人机线路R(Ui)；分布式马尔可夫覆盖模型DMCM。

输出：最佳覆盖策略函数值Q*。

1. 获取DMCM中获取无人机的子区域线路R(Ui)，观测信息{δi}；

2. 根据式(5)计算每一条线路r(r∈R(Ui))加入目标线路集合RΩ，并计算与任务关联之间的差异值E；

4. 重复步骤2和步骤3，直到线路被选择完毕；

7. 从可调度序列集TP中选择距离Ω′最近的k个无人机加入到子区域的扩散调度序列集TPi中，并驱动无人机的状态转移；

8. 以一台无人机的策略开始，计算下一台无人机的值函数，根据式(6)计算状态值函数寻找最优策略Q*；

9. 重复步骤6-步骤8；

10. 输出最佳覆盖策略函数值Q*。

4 实验分析

4.1 实验数据

本文所开展的实验背景为智能旅游系统的定位设计，采用真实的旅游景点数据背景进行仿真，将全局环境区域限定为W×W=1 000 km×1 000 km，由Voronoi图分解为600个子区域，每个子区域设有中心位置节点，四台同构四旋翼无人机飞行速度为40 m/s，最大的偏角度为60°，有效观测距离为50 m，仿真实验采用MATLAB R2014b软件平台编写，采样周期为5 s。通过目标覆盖任务分配的控制结果分析以及与粒子优化方法和多链接合同方法进行比较分析说明本文方法的有效性。

4.2 任务分配控制分析

初始阶段无人机对目标和环境区域信息未知，四台无人机以任意的初始位置飞行于任务区域，对拟定目标1至目标8进行探测，如图4所示。当机载传感器接收到任务信号时，四台无人机向任意位置移动覆盖目标区域。由图4(a)可知，四台无人机以覆盖需求向量K和任务调度需求向量对目标线路选择，并通过强化学习的方法寻找了一个合理的覆盖策略，而这些都是基于在本文方法初始阶段对目标区域的差异化划分，使无人机在每次覆盖线路选择时根据需求的差异性进行飞行；由图4(b)可知，当两台无人机对目标区域覆盖重复的情况下，通过扩散调度序列集使无人机在分布式马尔可夫覆盖模型的作用下转移当前无人机的状态，驱动任意一台无人机变更目标路线动作，并在强化学习策略驱动下寻求最佳路线；由图4(c)可知，在目标随机移动情景下，无人机通过分布式马尔可夫覆盖模型，可以有效地转移无人机现有状态，对目标线路进行选择，并通过强化学习方法得出全局最优策略；由图4(d)可知，在出现干扰因素情况下，无人机通过可观测集合的分析可以有效避开干扰区域，同时将干扰区域内的目标进行线路选择，从而实现对目标区域的覆盖。

(a) 任务扩散调度控制 (b) 目标重复覆盖控制

(c) 随机移动目标覆盖 (d) 随机移动目标覆盖图4 目标区域覆盖任务分配控制

4.3 线路代价分析

对于任务的不断扩散调度，使无人机目标线路选择在差异化的学习过程中不断迭代更新，采用任务线路代价[4]进一步说明本文方法在目标区域集群覆盖的性能。图5所示为4台无人机的任务区域覆盖线路代价变化曲线，在迭代至25次时代价值达到收敛水平，说明覆盖结果的任务扩散调度方差计算值较小，同时说明了每台无人机在经过多次任务调度和学习后，目标线路的选择和区域覆盖策略趋于最优。这是由于在Voronoi不规则图的基础上对任务需求进行了区域的差异划分，强化了目标任务的依赖关系和扩散调度的时序关联，并在强化学习Q值函数中找到了一个最优函数使任务合理分配，最终能够在较少迭代次数中实现对目标区域的全局覆盖。

图5 目标任务线路代价变化曲线

4.4 性能比较

为综合验证本文方法对于区域覆盖时任务分配的有效性，与现有的其他方法如人工蚁群方法、基于合同网方法和多agent方法进行性能比较，从目标函数适应和平均区域覆盖率两种指标衡量不同方法下的任务分配效果[4]。其中，目标函数适应指标描述了在任务分配过程中无人机对区域目标信息的不确定程度，表示为多无人机的信息熵的代数平均值；平均区域覆盖率指标描述了多无人机在一定任务时间内所覆盖区域占整个区域的面积比重。不同方法下四台无人机协同覆盖的目标函数适应和区域覆盖率随时间变化的结果如图6所示。

(a) 目标函数适应比较

(b) 平均区域覆盖率比较图6 四种任务分配方法对区域协同覆盖的性能比较结果

由图6(a)可知，本文方法在每代最优值会出现微小的波动，有利于算法跳出局部最优解区域，并在第16次迭代时收敛速度趋于稳定且适应值为1.0左右。这种现象主要受益于基于强化学习的差异化算法，该算法的最优策略解使得无人机的根据任务需求的状态转移性更强，同时差异化的区域划分也触发了无人机对目标区域覆盖需求的适应值，保证了算法收敛稳定。而人工蚁群方法在第25代时才逐步收敛稳定，收敛速度较慢；基于合同网方法的适应函数虽然与本文方法相近，可以解决任务分配的局部优化问题，但随着迭代次数的增加陷入了不稳定状态；多agent方法在后期存在较不稳定状态。

由图6(b)可知，随着时间的变化，当仿真结束时，人工蚁群方法的覆盖率为82.5%，基于合同网方法的覆盖率为86.6%，多agent方法的覆盖率为87.9%，本文方法的覆盖率为92.3%。由此可知本文方法在区域覆盖效率方面要优于其他方法，这是由于该方法在初始时对每个区域进行了差异划分，体现了分布式马尔可夫模型控制无人机飞行状态的优势，从而提高了区域协同覆盖效率。

5 结 语

本文针对目标区域需求覆盖问题，提出一种面向目标区域覆盖的任务分配控制方法。在基于区域差异化任务关联比重的基础上，构建了分布式马尔可夫覆盖模型，提出任务差异化分配的强化学习方法，实现了动态目标区域的最优覆盖策略。本文方法可以使任意两台无人机之间合理地分配任务，而且通过差异化学习方法使目标线路代价和目标适应函数收敛稳定，对于在旅游景点等复杂环境或人群密集中的危险目标搜索定位具有重要意义。然而，对于大规模问题，本文方法不能保证每次迭代都可以覆盖到最优解，下一步工作将使任务数量增加到一定程度，解决陷入局部最优的情况，并结合语义搜索的方法进一步提高覆盖的准确率。