通信延迟约束下多无人机任务指派冲突消解

符小卫, 冯 鹏, 高晓光, 刘 重

(西北工业大学电子信息学院, 陕西 西安 710072)

0 引 言

近年来,随着对无人机(unmanned aerial vehicle, UAV)作战的深入探索,多架UAV协同完成指定任务成为研究的重点方向。多UAV(multi UAV,multi-UAV)协同作战是指在不确定性的战场环境下布放成群的[1]中小型UAV,在广阔的空域范围内对UAV编队进行任务分配[2]和航路规划[3],以完成搜索打击等一系列任务。同时,由于单架UAV能力有限,仅能基于自身的传感器和局部信息进行控制与决策,所以UAV编队需要通过机间通信实现高效率的[4]协同任务指派。

multi-UAV任务指派是编队完成协同搜索[5-6]之后面临的另一重要课题,研究的领域有很多方面,例如通信约束[7-8]、异构性[9-10]以及UAV集群[11-12]的任务分配等。在早期,大多数研究的是中心式任务指派结构[13-15],即任务指派中心站收集每架UAV的局部信息,并基于所有信息为UAV编队进行任务指派。之后,分布式任务指派结构[16-17]逐渐成为主流。在分布式结构下,由于每架UAV对于战场情景认知的不一致,编队可能会生成相互冲突的任务指派方案,此时一致性算法能够有效地解决冲突。文献[18-19]运用卡尔曼滤波器(Kalman filter,KF)进行信息处理,保证编队信息的一致性,从而实现无冲突的任务指派。文献[20]提出仅在基于不同认知信息生成的指派方案存在差异时才建立通信,以较小的通信代价保证了任务指派的一致性。拍卖算法(auction algorithm,AA)[21]是另一种有效的任务指派方法。文献[22]建立竞标中心接收所有UAV的投标信息,并根据预设的价值评估规则从中选择具有最大价值的投标。文献[23]使用交换手段,并通过链接低通信代价的本地谈判环节来保持动态化复杂环境下拍卖结果的最佳性。但由于以上文献的算法实时性较差,不能适应快速变化的战场环境[24];并且为了达到一致的任务指派,需要大量的机间通信,这在存在通信限制的真实环境中很难实现。

由于通信延迟和丢包等约束的存在,编队内信息流存在不完整性和不确定性,由此导致各架UAV已知信息集合的差异化。差异化的信息集合会生成不一致的任务指派方案,进而导致指派冲突。由此可见,通信约束会严重影响任务指派的可靠性,破坏任务指派的时序要求。因此,UAV编队在任务指派过程中必须考虑通信系统中的不确定性因素。

本文针对multi-UAV协同任务指派过程中的任务冲突问题,设计了一种带比较阈值的任务指派冲突预测及消解机制。该机制对由局部信息生成的本地收益矩阵进行进一步分析处理,设计比较阈值对矩阵中最大两项收益值进行比较分析,从而预测可能存在的指派冲突,并进一步消解冲突。

最后,本文在MultiUAV2[25]仿真平台上对提出的带比较阈值的冲突消解机制进行仿真验证。结果表明,提出的算法能提高UAV编队在通信约束条件下的任务指派性能。

1 multi-UAV协同任务指派模型

1.1 UAV运动模型

本文设定编队中每个UAV都运行相同的简化动力学模型,即去掉高度自由度,且UAV具有恒定的前进速度及按最大转弯速率进行转向。

基于以上假设,动力学方程为

(1)

式中,x、y为UAV的横坐标和纵坐标;v、θ、Ωmax为UAV的速度、航迹方位角和最大转弯率;i表示UAV编号;ui为输入控制变量,且

ui={-1,0,1}

(2)

式中,ui=-1表示左转向;ui=0表示直线飞行;ui=1表示右转向。假定每架UAV的最大转弯速率和标称速度是相同的。

1.2 multi-UAV协同任务指派模型

multi-UAV协同任务指派是以任务收益为基础,选择对于UAV编队最优的任务执行方案。而任务执行成本或收益与到达任务执行位置的路径长度或时间有直接的关系。

设定由Nu架UAV组成的UAV编队,即UAV集合为

U={1,2,…,Nu}

(3)

经过搜索发现的目标,根据摧毁目标相应的收益,划分到已知类别中。当发现目标时,用j对目标进行编号,可以得到j=1,2,…,Nt,其中Nt是发现的目标数量,设定目标集合为

T={1,2,…,Nt}

(4)

Vj表示目标j的价值。假设UAV在开始执行任务时,没有关于目标数目和位置的具体信息,但潜在目标类型的相关信息是已知的。

UAV默认执行对全域的搜索任务,同时还对每个目标需要执行分类、攻击和毁伤评估3类任务,即对每个目标执行的任务集合为

M={C,A,V}

(5)

式中,C表示分类任务;A表示攻击任务;V表示毁伤评估任务。UAV执行任务必须满足严格的顺序要求,即先分类后攻击最后毁伤评估。且对目标每项任务的完成会导致目标状态的更新,产生下一项要完成的任务,直至所有任务全部完成。Pc、Pk、Pv分别表示成功执行分类、攻击、毁伤评估任务的概率。

令m为UAV所需完成的任务编号,Nm表示对目标执行的任务数量。UAV可以执行4种不同的任务,即搜索(m=0)、分类(m=1)、攻击(m=2)、毁伤评估(m=3)。令Ns=Nm·Nt表示UAV对所有目标需要执行的任务总数,则

S={1,2,…,Ns}

(6)

代表任务指派与执行的独立阶段。在每个阶段中,只允许一架UAV对一个目标执行一种任务。在这里,阶段的意义只是在算法中人为地分割任务指派的过程,并不存在于实际的任务执行中。

定义一个二元决策变量，即

Xi,j,k∈{0,1}

(7)

当UAVi∈U在算法阶段k∈S对目标j∈T执行任务时,Xi,j,k=1;否则,Xi,j,k=0。

2 基本指派算法

有容量限制的转运指派算法用于分时段网络最优化模型,每次运行该模型,都为UAV编队进行任务指派。该模型在离散时间点上,在所有UAV上同时运行,并为每架UAV指派最多一项任务。当发现新目标或目标状态改变时,新信息输入到模型中,算法都会被再次运行解算。这一线性规划能够以网络流程的形式进行描述,如图1所示。

图1 multi-UAV任务指派网络流图Fig.1 Flow chart of multi-UAV assignment network

有容量限制的转运指派网络优化模型可表示为

(8)

约束条件为

∀i=1,2,…,Nu

(9)

(10)

(11)

3 分布式估计与冲突消解机制

3.1 分布式估计

为了运行分布式协同任务指派算法,每架UAV都需要友机的现时位置信息。为了提高UAV编队的资源利用和作战性能,UAV只在必要的时刻开启通信,交流位置状态信息。又由于存在着通信延迟的影响,需要本机对友机的位置状态进行预测和估计,这就是分布式估计。本文设计运用KF对UAV位置状态进行预测和估计。

把UAV动力学模型改写为

(12)

式中,xi=[xi,yi,vxi,vyi]T;i∈U表示UAV编号;ωi表示外部干扰因素。

(13)

为了分布式估计,需要把每个UAV动力学模型离散化表示,即

xi[n]=Φxi[n-1]+Bi[n-1]ui[n-1]+Γωi[n-1]

(14)

(15)

式中,离散周期T1等于量测周期。量测方程为

(16)

式中,vi[n]∈R2为零均值量测噪声序列,以及

(17)

Pi[n/n-1]=ΦPi[n-1]ΦT+Qaw

Ki[n]=Pi[n/n-1]HT(HPi[n/n-1]HT+Ri)-1

Pi[n]=Ki[n]RiKi[n]T+

(I-Ki[n]H)Pi[n/n-1](I-Ki[n]H)T

(18)

(19)

每架UAV同时运行所有动力学模型,对所有UAV的位置状态进行实时估计与判断，即

xi,l[n+1]=Φxi,l[n]+Bi,l[n]ui,l[n]

(20)

式中,xi,l表示UAV(i∈U)运行UAV(l∈U)的动力学模型对其位置状态的估计。再定义本地位置状态误差为

(21)

当该误差大于某一给定的阈值时,触发纠偏机制。判定式为

ei[n]TEei[n]>ε1

(22)

(23)

模型更新后,本地系统误差为零,即ei[n]=0。在UAVi广播位置信息后,周围友机经过一段时间延迟,即在ni+δil[ni]时刻接收到此信息。此处,δil[ni]表示时变通信延迟,与UAVi和UAVl的相对位置有关。UAVl接收到延迟的信息,更新估计模型,以此更加准确地估计UAVi的状态信息。UAVl估计UAVi的位置为

(24)

3.2 冲突预测与消解

收益矩阵的最大值所代表的任务即是本阶段所要指派的任务。本地收益值计算为

(25)

估计友机的收益值为

Bl,j,s=f(xi,l[n])

(26)

再深入探究,正是由于收益矩阵的最大值与次大值相差很小,所以轻微的计算误差就会产生大小关系的转变,从而导致任务指派的冲突。由此抓到了问题的关键。

本文提出,在收益矩阵形成后,比较其最大元素和次大元素的差值,若小于某给定值ε2,则判定可能存在冲突,反之则没有冲突。计算每一阶段的收益矩阵后,都要用该阈值ε2检测是否存在潜在冲突。

在某一阶段k∈S,UAVi∈U首先选择其收益矩阵的最大元素max1i,j(Bi,j,k),然后找到矩阵的次大元素max2i,j(Bi,j,k),其中j∈T。若

max1i,j(Bi,j,k)-max2i,j(Bi,j,k)<ε2(ε2>0)

(27)

成立,则表示存在潜在冲突。

阈值ε2大小的选取关系到整个算法冲突预测的性能。选取较小数值的ε2可以减少UAV通信,但也降低了成功预测冲突的概率;而正好相反,大值选取较大数值的ε2是以增加网络的通信压力为代价,提高成功预测冲突的可能性。

结合党和国家大政方针和重要纪念活动制订宣讲计划和方案，增强时政宣讲时效性。将时政宣讲与课堂教学有机结合。每次思政课必须实施“时政5分钟”，关注最新国内国际热点话题，教师做好点评。利用班会或者第二课堂活动由教师指导开展时事热点专题讨论。每位教师每学期至少进行集体时政宣讲1次，人数不少于2个自然班。鼓励教师积极参加时政宣讲活动。

当式(27)成立时,表明算法任务指派可能存在冲突。此时,本地UAV开启通信模式,向友机广播包含量测信息的投标向量

φi=[ijmkβi]T

(28)

式中,i、j、m、k∈Z+分别表示UAV编号、任务所针对的目标、指派任务及当前任务阶段。βi=max1i,j(Bi,j,k)表示本地收益矩阵的最大元素。

友机收到广播信息后,检查是否与自身得到的任务指派方案一致,并把指派方案的所有信息广播出去。当UAV收到来自所有友机的反馈信息后,比较所有方案的收益,选择收益最大的任务作为最终指派方案。因为当开启广播通信后,每架UAV都会收到来自所有UAV的信息,这些信息是相同的,所以最终所有UAV会做出相同的任务指派决策。这就是整个冲突消解的过程。

3.3 UAV优先级设定

当UAV编队成功预测冲突并进行广播通信后,若2架或以上的UAV提出的指派任务取得相同的收益值,则各架UAV在选择最终指派方案时就会产生冲突:到底选择其中的哪一架执行任务？为了解决这个冲突,考虑对UAV编队设置优先级。设Π表示对UAV的优先级排序,且UAVi∈U的优先级为

Πi=i(∀i=1,2,…,Nu)

(29)

此方法等同于对所有UAV进行编号,序列号码越小的UAV拥有越高的优先级。当发生上述指派冲突时,比较所有收益值相同的任务的源指派UAV的优先级,把优先级最高UAV指派的任务设置为最终执行的任务。

4 仿真验证

为验证本文算法的有效性,在MultiUAV2仿真平台上进行仿真验证。

为了与本文提出的冲突消解机制比较,本章采用简单的协商决策方法作为对比算法。即当冲突方案的不同执行方(UAV)到达冲突任务地点时,相互通信后发现冲突存在;交流状态信息后对冲突目标进行局部的重新指派;胜者执行原任务,败者离开该目标,飞向下一项任务地点。

4.1 算法验证仿真

仿真将任务区域设定在6 km×20 km的区域范围内,区域内设定了3个目标,使用4架相同类型的UAV组成编队执行搜索、分类、打击及毁伤评估任务。当UAV编队完成所有任务或仿真时间达到200 s时仿真停止。设定UAV的初始航向角是0°,最大转弯率Ωmax=0.2 rad/s,恒定速度马赫数为0.333,传感器宽度为0.6 km。设定UAV编队的通信延迟为0.5 s,算法中ε2取值为2。设定编队成功进行分类、打击及评估的概率分别是Pc=0.6、Pk=0.8、Pv=1.0。UAV的初始位置和目标位置如表1和表2所示。

表1 UAVs初始位置

表2 目标位置

采用简单的协商决策方法时,编队完成对全部目标的分类任务、1号目标和3号目标的打击任务及1号目标的毁伤评估任务,但未完成对2号目标的打击和毁伤评估任务及对3号目标的毁伤评估。UAV编队的完整轨迹如图2所示。

图2 简单协商决策时UAV编队的完整航迹Fig.2 Whole trajectory of UAV formation with simple negotiation decision making

在①处,1号UAV与3号UAV同时飞向3号目标位置,试图对3号目标执行任务,这就是由于编队信息不一致导致的任务指派冲突。当他们逐渐接近时,通过相互通信发现彼此的任务方案存在冲突,在重新计算任务收益后,最终由具有较高任务收益的1号UAV对3号目标执行任务。而此时3号UAV不得不盘旋转弯飞向下一任务点。在这个过程中,任务冲突浪费了3号UAV的大量时间与资源,大大降低编队执行任务的效率。

在②处,1号UAV在空中盘旋,等待对1号目标执行毁伤评估任务。盘旋等待的过程浪费了大量的时间与资源,却没有任何收益。而且在复杂未知的战场环境中,原地盘旋极易导致UAV暴露,对整个编队产生巨大威胁。好的算法应该尽量避免盘旋等待的频次与时间。UAV过多的盘旋等待浪费任务执行时间和资源,大大影响编队执行任务的效率。优良的算法通过精确的计算与指派,有效避免UAV的盘旋等待,使编队更快地完成既定任务。

在③处,4号UAV在远离战场的情境下再次加入战场,对2号目标执行任务,这特别不符合任务收益最大化的目标。这种情况是由于在不良的通信条件下,编队内各UAV的信息不能一致,UAV单体基于自身信息达到的局部最优并不是编队的全局最优。

当加入本文提出的冲突消解机制后,UAV编队完成对所有目标的分类、打击以及毁伤评估任务。编队的完整航迹如图3所示。

图3 带冲突消解机制时UAV编队的完整航迹Fig.3 Whole trajectory of UAV formation with conflictresolution mechanism

在①处,1号UAV与3号UAV正在飞向2号目标处,准备相继对2号目标完成打击与毁伤评估任务。由于冲突消解机制的存在,即使1号UAV与3号UAV距离很近,任务收益相近,也能正确地指派任务执行的时序,保证在单体信息相近的情况下实现无冲突的任务指派。

在②处,4号UAV对1号目标执行攻击任务后自毁,编队在很早的时间点就完成对1号目标的3项任务,整个过程紧凑合理,充分利用编队资源。没有出现图2中所示的4号UAV在未得到任何任务指派的情况下远离战场,而后又不合理地返回战场执行任务的情况。

通过仿真表明,提出的冲突消解机制能有效地解决任务指派过程中的任务冲突问题,相较于一般方法大大提高了编队的任务执行效率。由于冲突消解与任务指派同时完成,发生在任务执行之前,这对编队的航路规划和自身生存保障都有极大的积极作用。

4.2 蒙特卡罗仿真

为说明本文提出的冲突消解机制对UAV编队任务指派性能的提升,又在MultiUAV2仿真平台上进行蒙特卡罗仿真。仿真采用任务完成率作为性能分析的指标。

设定通信延迟为1 s,设置3种情况如表3所示。通过50次蒙特卡罗仿真对所提出的冲突消解机制在通信延迟情况下的性能进行评估。仿真中的变量为随机产生的目标位置,其他的基本设定与仿真1相同。

表3 蒙特卡罗仿真算例设置

图4和图5分别表示编队在1 s通信延迟下采用简单的协商决策方法和加入冲突消解机制后执行任务全过程的通信数据率。

图4 情况1情境下的通信数据率Fig.4 Communication data rate in case 1

图5 情况2情境下的通信数据率Fig.5 Communication data rate in case 2

图4中,峰值数据率为50.625 kb/s,平均数据率为0.666 2 kb/s,存在至少15个通信高峰;图5中,峰值通信率为32.5 kb/s,平均数据率为0.303 3 kb/s,存在10个通信高峰。对比可以看出,在加入冲突消解机制后,通信数据率明显减小,说明该机制降低了编队内的通信频次,节省了大量的通信资源,在应对恶劣通信环境时有很好的表现。

图6表示编队的攻击任务和毁伤评估任务在不同场景下的对比情况,以平均任务完成率为依据。

图6 不同情境的任务完成率对比Fig.6 Comparison of task completion rate in different cases

从图6中可以看出,完整的通信环境下协同控制效果是最好的,攻击和毁伤评估的任务完成率分别为92%和70.7%。当存在通信时延时,效果会变差,攻击和毁伤评估的任务完成率分别为61%和46%;在加入本文提出的冲突消解机制后,两项任务的完成率分别为80.3%和67.7%,编队的任务执行能力有了很大提升。该蒙特卡罗仿真验证了本文提出的冲突消解机制的有效性。

针对通信延迟量对本文算法性能的影响,通过在不同通信延迟条件下与简单协商决策进行对比验证,并从以下两方面进行分析。

(1) 通信延迟量对任务完成率的影响。随着通信延迟量的增加,UAV之间状态信息和估计结果的差异不断扩大,因此导致指派冲突的存在概率大大增加。编队频繁预测到潜在冲突并开启通信消解冲突,降低了任务指派的有效性和可靠性,编队取得任务指派一致性的时间也不断增长。因此,随着通信延迟的增加,任务完成率不断下降。相比之下,冲突消解机制可以通过调节阈值ε2以灵活应对通信延迟量的变化。在通信延迟较高时,可以选择较小的ε2以提高任务指派的效率。因此,冲突消解机制受通信延迟的影响更小,具有更优良的表现。

(2) 通信延迟量对算法计算时间的影响。如(1)所述,通信延迟量的增加主要导致冲突消解过程反复运行,解决冲突所需的算法轮次不断增多。但单次的冲突预测及消解算法与通信延迟没有关联,因此算法的计算时间受通信延迟量的影响较小。

以上仿真实例证明,本文提出的算法可以有效地预测和消解指派冲突,同时在这个过程中,可以大大降低通信频率,减少通信代价。

5 结 论

在本文中,为研究multi-UAV任务指派过程中的冲突消解,首先建立UAV动力学模型以及任务指派模型。以分布式有容量限制的转运指派算法为基础,提出合理的算法解决由通信延迟导致的指派冲突。通过仿真对比表明,该算法能真实有效地预测和解决指派过程中的冲突,保证UAV编队完成对指定空域目标的搜索打击任务。但此算法也有不足,在通信条件极其恶劣时,不能较好地解决冲突。进一步的工作是研究在高通信延迟和低通信效率下对冲突的预测和解决。

参考文献：

[1] SURESH M, GHOSE D. UAV grouping and coordination tactics for ground attack missions[J]. IEEE Trans.on Aerospace & Electronics Systems, 2012, 48(1): 673-692.

[2] ELLOUMI S. An efficient linearization for the constrained task allocation problem[J].Applied Spectroscopy, 2015,56(9):1170-1175.

[3] DI B, ZHOU R, DUAN H B. Potential field based receding horizon motion planning for centrality-aware multiple UAV coope-rative surveillance[J].Aerospace Science and Technology,2015,46: 386-397.

[4] LI J, HAN Y. Optimal resource allocation for packet delay minimization in multi-layer UAV networks[J]. IEEE Communications Letters, 2017, 21(3): 580-583.

[5] HU J W, XIE L H, LUM K J, et al. Multi-agent information fusion and cooperative control in target search[J]. IEEE Trans.on Control Systems Technology, 2013, 21(4): 1223-1235.

[6] ZHAO W, MENG Q, CHUNG P W. A heuristic distributed task allocation method for multivehicle multitask problems and its application to search and rescue scenario[J]. IEEE Trans.on Cybernetics, 2016, 46(4): 902-915.

[7] 符小卫, 李建, 高晓光. 带通信约束的多无人机协同搜索中的目标分配[J]. 航空学报, 2014, 35(5): 1347-1356.

FU X W, LI J, GAO X G. Target allocation in multi-UAV cooperative search with communication constraints[J]. Acta Aeronautica et Astronautica Sinica, 2014, 35(5): 1347-1356.

[8] LIU L, MICHAEL N, SHELL D A. Communication constrained task allocation with optimized local task swaps[J]. Autonomous Robots, 2015, 39(3): 429-444.

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

DI B, ZHOU R, DING Q X. Distributed coordinated heterogeneous task allocation for unmanned aerial vehicles[J]. Control and Decision, 2013, 28(2): 274-278.

[10] 孙海波,周锐,邹丽,等.通信和测量受限条件下异构多UAV分布式协同目标跟踪方法[J].航空学报,2011,32(2):299-310.

SUN H B, ZHOU R, ZOU L, et al. Distributed cooperation target tracking for heterogenous multi-UAV under communication and measurement constraints[J]. Acta Aeronautica et Astronautica Sinica, 2011, 32(2): 299-310.

[11] WEI Y, MADEY G R, BLAKE M B. Agent-based simulation for UAV swarm mission planning and execution[C]∥Proc.of the Agent-Directed Simulation Symposium, 2013: 7-14.

[12] WEI Y, BLAKE M B, MADEY G R. An operation-time simulation framework for UAV swarm configuration and mission planning[J].Procedia Computer Science,2013,18(1):1949-1958.

[13] BELLINGHAM J, TILLERSON M, RICHARDS A, et al. Multi-task allocation and path planning for cooperating UAVs[C]∥Proc.of the Conference on Cooperative Control:Models,2003:1-19.

[14] CASSANDRAS C, LI W. A receding horizon approach for solving some cooperative control problems[C]∥Proc.of the IEEE Conference on Decision and Control, 2002: 3760-3765.

[15] ALIGHANBARI M. Task assignment algorithms for teams of UAVs in dynamic environments[M]. Cambridge: Massachusetts Institute of Technology, 2004.

[16] CASTANON D, WU C. Distributed algorithms for dynamic reassignment[C]∥Proc.of the IEEE Conference of Decision and Control, 2003: 13-18.

[17] SHIMA T, RASMUSSEN S J, CHANDLER P. UAV team decision and control using efficient collaborative estimation[C]∥Proc.of the American Control Conference, 2005: 4107-4112.

[18] REN W, BEARD R, KINGSTON D. Multi-agent Kalman consensus with relative uncertainty[C]∥Proc.of the American Control Conference, 2005: 1865-1870.

[19] ALIGHANBARI M, HOW J P. An unbiased Kalman consensus algorithm[C]∥Proc.of the American Control Conference, 2006: 6.

[20] DIONNE D, RABBATH C A. Multi-UAV decentralized task allocation with intermittent communications: the DTC algorithm[C]∥Proc.of the American Control Conference, 2007: 5406-5411.

[21] BERTSEKAS D P. The auction algorithm for assignment and other network flow problems[J].Interfaces,1990,20(4):133-149.

[22] LAGOUDAKIS M G, BERHAULTT M, KOENIGT S, et al. Simple auctions with performance guarantees for multi-robot task allocation[C]∥Proc.of the IEEE/RSI International Confe-rence on Intelligent Robots and Systems, 2004, 40(3): 698-705.

[23] AHMED A, PATEL A, BROWN T, et al. Task assignment for a physical agent team via a dynamic forward/reverse auction mechanism[C]∥Proc.of the International Conference on Integration of Knowledge Intensive Multi-Agent Systems, 2004: 311-317.

[24] WEI C, HINDRIKS K V, JONKER C M. Dynamic task allocation for multi-robot search and retrieval tasks[J]. Applied Intelligence, 2016,2016(2): 1-19.

[25] RASMUSSEN S J, MITCHELL J W, CHANDLER P R, et al. Introduction to the MultiUAV2 simulation and its application to cooperative control research[C]∥Proc.of the American Control Conference, 2005: 4490-4501.