仿灰狼合作捕食行为的无人机集群动态任务分配

彭雅兰 段海滨 张岱峰 魏 晨

(1.北京航空航天大学自动化科学与电气工程学院飞行器控制一体化技术国家级重点实验室仿生自主飞行系统研究组,北京 100083;2.鹏城实验室,深圳 518000)

1 引言

近几年随着人工智能技术飞速发展,无人机(unmanned aerial vehicle,UAV)在军事与民用领域都经历了革命性的发展[1].为了弥补单机执行任务能力的局限性,将无人机以大规模形式聚集、互联互通形成无人机集群,在功能上承担单机无法实现的复杂任务.当多架无人机协同执行同一项任务时,无可避免的需要进行合理的任务分配,以减少资源的浪费,提高单次任务的成功率与执行任务的鲁棒性[2-3].无人机集群在进行动态任务分配时需要考虑不同的目标类型,针对性地指派适合类型的无人机执行任务.不仅如此,随着任务复杂度的不断提升,无人机集群飞行不再是单一任务序列的简单时序执行过程,任务环境的不确定性要求无人机集群可以及时对执行范围内的突发情况做出响应[4].目标威胁与有限载荷资源是无人机集群任务分配需要着重考虑的两种约束[5].目标威胁主要影响无人机类型、编队队形与载荷类型等的实时选择与调整,有限载荷资源约束了无人机集群的任务效能与执行任务的可持续性[6].因此,无人机集群的动态任务分配是集群智能决策与自主控制中的一项关键性技术.

无人机集群执行任务的过程是一个连续的动态过程,前期的任务执行结果会影响到后期任务的分配与执行情况,以前期任务执行后的状态作为后期任务开始的初始状态更符合整体任务执行过程中的实际需求.在无人机集群动态任务规划研究中,既要求计划的最优性,同时又要保障反映的快速性,二者相互制约[7].随着无人机集群执行任务的复杂度增高,单纯依靠提高算法速度很难满足需求,研究在线控制机制,优化求解时间与计划最优性之间的关系十分重要.

在无人机集群任务规划研究方面,佐治亚理工大学采用可扩展的商业开源平台完成了实时路径规划与目标分配,可通过地面站将指令发送到每架无人机[8].中国电子科技集团电子科学研究院等单位也实现了119架无人机集群的多任务目标分组、集群行动等任务[9].沙特哈立德国王大学的Ghamry等人将20个智能体的目标搜索规划问题建模为约束时间窗口下的多维度启发式组合优化问题并采用离散空间粒子群算法(discrete particle swarm optimization,DPSO)对其进行快速精确求解[10].

灰狼作为自然界中自组织行为显著的生物集群,其社会组织结构与层次十分明确,在捕食狩猎中采用机会主义策略,通过猎物选择提高整体捕食成功率以维持整个灰狼的生存与繁衍.灰狼在复杂、严峻的野外环境中进化出自发的集群捕食策略[11-12].

伦敦大学的Hubel将土狼、野狗等犬科动物的捕食过程与猎豹进行了1119次对比,虽然犬科动物的运动能力较猎豹较弱,但善于通过集体狩猎和食物分享来维持群体中每个个体的能量收支平衡[13-14].灰狼通过采用这种多次追逐的机会主义捕食策略来弥补个体捕食效率不足,平衡灰狼中的个体差异、猎物类型、环境等影响因素.灰狼捕食过程这一多因素交互迭代过程中演化出的行为机制符合无人机集群在执行任务过程中的动态任务规划所需的性质.佐治亚理工学院的Madden将灰狼捕食麋鹿的过程分解为搜索、逼近、群组攻击、个体攻击和捕食5个阶段,通过对场景与对象的模拟,较好的还原了真实的交互过程[15].

本文借鉴灰狼合作捕食行为,根据灰狼在捕食过程中表现的合作狩猎行为,建立交互行为动力学模型与合作捕食行为模型,设计无人机集群的动态任务分配方法,具有一定的技术优势.

2 灰狼合作捕食行为模型

2.1 灰狼交互行为动力学模型

灰狼群体中的因个体间的性别、年龄、体型等差异,在种群竞争关系中逐步形成社会地位差异,组成一定的社会层级结构.灰狼的社会层级结构是一种类似分叉属性的领导层级结构,头狼作为顶层节点,后代形成子树,并按照性别分开,生存能力最弱的个体作为最底层[16].

狼群中一般由年龄最长的个体作为头狼,从头狼到幼崽,按照指挥关系,存在一条信息流,为整个狼群提供交互行为的信息交流途径.为了方便通过数学表达式表征灰狼内部的交互关系,将每只灰狼当做一个节点,该节点具有的所有属性由下列数据结构体表示:

其中:R(i)表示当前第i个个体的领导者个体;Z(i)表示当前个体的性别属性;C(i)与Q(i)分别为当前个体支配的左子个体和右子个体;N(i)表示当前个体是否为幼崽.由此数据结构体表示形式可以得到第i只灰狼个体的邻居集合,可由式(2)表示:

2.2 灰狼合作捕食行为模型

其中:COT为捕食阶段个体在单位路径上的能量损耗(cost of transportation),D为捕食阶段个体的移动路径长度,COTlow与Dlow对应低速捕食阶段,COThigh与Dhigh对应高速捕食阶段;ξthreaten为猎物的威胁度,其取值范围为0～1;E为捕食成功后猎物提供的总能量;Cost为捕食猎物中灰狼的能量支出百分比;N为狼群中个体数量;Krate为灰狼个体杀伤率;Ecost为灰狼捕食过程中的能量支出.由上述灰狼合作捕食过程分析可知,灰狼个体杀伤率与猎物的威胁度负相关,灰狼捕食过程中的能量支出与猎物的威胁度正相关.设Krate,Ecost与ξthreaten的关系满足式(4):

其中:α为相应猎物威胁度下的个体最高杀伤率;β为猎物威胁度对个体杀伤率的影响系数,β≤0;θ为相应猎物威胁度下最低能量支出;γ为猎物威胁度对灰狼捕食能量支出的影响系数,γ≤0.

3 无人机集群动态任务分配

3.1 无人机模型

假定无人机配置有速度、航迹角与航向角3个回路的自驾仪,则无人机模型[17]可简化为

其中:Vc,γc与χc分别为速度、航迹角与航向角控制输入量;(x,y,z,V,γ,χ)为无人机的6个状态量,分别为无人机x,y与z轴坐标、飞行速度、航迹角与航向角;τV,τγ与τχ分别为速度、航迹角与航向角自动驾驶仪控制参数.

考虑到无人机自身的飞行条件限制

其中:Vmin,Vmax,γmin与γmax为无人机航速与航迹角限制;ωmax为无人机最大航向角速度的绝对值.

3.2 基于灰狼合作捕食行为模型的无人机集群动态任务分配

根据第2.1节中灰狼社会层级结构与表示个体属性的数据结构体构建无人机集群交互通讯结构,类似于狼群个体属性数据结构体,定义无人机属性结构体:

其中:R(i)表示当前第i架无人机的领导者编号;Z(i)表示当前无人机的状态,可参与任务为1,无法参与任务为−1;C(i)与Q(i)分别为当前无人机支配的左子个体与右子个体;N(i)表示当前无人机是否为信息传递路径的末端个体.

灰狼捕食过程中,发现猎物的个体会通过嚎叫的方式召唤周围愿意参与捕猎的同伴共同展开猎杀,参与捕食的个体合作攻击并在成功抓住猎物后平均分配.借鉴灰狼的群体合作捕食行为策略,设计了无人机集群动态任务分配策略,算法流程图如图1所示.

图1 基于灰狼捕食行为机制的无人机集群任务分配算法流程图Fig.1 Algorithm flowchart of UAV swarm dynamic mission planning inspired by cooperative predation of wolf-pack

借鉴灰狼捕食过程召唤周围同伴共同行动的行为,当指挥权限高的无人机接收到任务指令后,将任务信息发送给周围存在交互关系的无人机.当第i架无人机接受到指挥者传递的任务指令后,判断其资源量是否足够完成该任务,即Ri≥Rmin.若第i架无人机资源量足够完成该任务,则按照一定的激励概率选择是否参与执行任务,其激励概率函数为

若第i架无人机依据激励概率函数Pik(t)判断为执行任务,则向其指挥者无人机反馈当前资源量Qi.由上式可知,合作机制可以提高集群的任务完成率.

对于ℜk中的第n个子集˜ℜnk按式(17)计算其完成目标任务k的总体能量收益.

4 仿真结果

为验证该仿灰狼合作捕食行为的无人机集群动态任务规划方法的可行性和有效性,设计仿真实验为无人机集群在规定的任务区域内,对若干个运动的任务目标点进行追击.选取任务区域为20 km×20 km×20 km的矩形空间,无人机性能配置参数如下:

无人机和任务目标的初始位置均随机分布于任务区域内,且均满足式(5)的运动约束条件.无人机的初始空速为80 km/h,初始航迹角为0,初始航向角在[0,2π]范围内随机分布,任务目标的速度、任务方向与俯仰角都是随机调节的.每个任务目标的初始收益均为100,衰减因子φ=0.01.仿灰狼合作捕食行为动态任务分配方法的参数设置如下:a=0.01,b1=b2=333,Pmin=0.7.

文献[18]介绍了一种基于拍卖机制的分布式任务分配方法,该方法以个体打击概率、资源量、航程和目标威胁度作为任务分配的指标,且逻辑结构与本文所提仿灰狼算法类似.选取该拍卖算法作为本方法的对比算法.选取3个算例进行对比验证,分别为10架、15架、20架无人机对15个任务目标进行合作打击动态任务分配.得到仿真结果如图2-3所示.

图2 仿灰狼合作捕食行为任务分配三维仿真结果Fig.2 Simulation result of UAV swarm dynamic mission planning inspired by cooperative predation of wolf-pack in three dimensions

图2与图3分别给出了仿灰狼合作捕食行为的无人机集群动态任务分配算法与拍卖机制任务分配算法的三维仿真结果,图中标号代表无人机与目标编号.

图3 拍卖机制任务分配三维仿真结果Fig.3 Simulation result of UAV swarm dynamic mission planning inspired by auction mechanism in three dimensions

图4显示的分别是仿灰狼机制与拍卖机制在任务收益与资源分配平衡度方面的对比曲线,资源分配平衡度指标如式(22)所示:

图4 仿灰狼机制与拍卖机制任务收益与资源均衡度Fig.4 Task income and resource equilibrium of the wolfpack mechanism and auction mechanism

其中:Ji(t)为t时刻无人机的剩余资源量,Tmax为最大仿真时间, ¯Ji(t)为t时刻无人机集群的平均剩余资源量.

根据仿真结果可知,拍卖机制每次只分配一架打击概率最高的无人机对相应目标执行打击任务,不存在编队协同打击行为.这种机制的问题在于没有考虑打击编队与资源均衡两个因素,致使打击资源在任务执行前期消耗极不均匀.有的无人机因频繁遇到目标而提前消耗完携带的资源,导致任务执行后期会出现找不到合适打击者的问题.与之相反,仿灰狼合作捕食行为任务分配算法通过资源的均分机制,保留了大量持有有效打击资源的无人机个体.通过编队打击,不仅均衡了整个集群的打击资源,同时也为多机协同执行打击任务提供了更多的可选方案,提高了打击成功概率,体现了仿灰狼合作捕食机制的时效性与持久性等特点.

表1给出了两种算法任务分配主要指标的对比结果,表中数据为每种算例分别独立运行15次后取得的平均值.统计结果同样反映了两种任务分配算法的差异性,在击毁目标数量相近的情况下,仿灰狼合作捕食机制的累计收益明显高于拍卖机制,且在资源均衡度方面明显优于拍卖机制.资源的均衡在任务执行后期尤为重要,拍卖机制在后期出现了较为明显的资源分化,个别无人机出现资源匮乏的情况,导致可用无人机数量减少.通过表1也可以看出,无人机集群规模的增加并不一定能够提升拍卖算法的分配效果,而仿灰狼合作捕食机制的执行效能则大致与无人机集群规模成正比.

表1 仿灰狼机制与拍卖机制的任务分配指标统计结果Table 1 Task planning metric statistics of wolfpack mechanism and auction mechanism

5 结论

针对无人机集群任务分配问题中,优化计划最优性与响应快速性二者之间的关系,借鉴灰狼合作捕食行为,提出了一种无人机集群动态任务分配策略.首先,通过分析灰狼狩猎过程中表现出的社会层级结构与合作捕食行为,建立了一种灰狼交互行为模型与合作捕食行为模型.其次,建立了仿灰狼合作捕食行为机制与无人机集群动态任务分配之间的映射关系,建立了无人机集群动态任务分配流程框架.仿真结果表明,在有限时间内,本文所提方法在资源分配平衡度与任务收益度方面有具有较好优势,验证了该方法的有效性.