基于改进K-means算法和总时最短机制的无人机群多目标分配围猎策略

胡滨,朱亚辉,杜致泽,赵子昕,周延年

(1.西北工业大学 自动化学院,陕西 西安,710072;2.陕西学前师范学院 数学与统计学院,陕西 西安 710061；3.西北工业大学 机电学院,陕西 西安,710072;4.交通运输通信信息集团有限公司 卫星通信事业部,北京 100011;5.空军工程大学 防空反导学院,陕西 西安 710043)

通过无人机之间的配合协作，无人机群能够完成单体无人机难以应付的复杂问题[1]。空中目标围猎是多无人机群的典型应用场景，它源于自然界中普遍存在的捕食狩猎行为，在多年的研究发展中对围猎形式，围猎目的进行了丰富的扩展[2-3]。其中多目标围猎作为重要的战术环节是目标围猎的一个热点问题，可以作为抓捕敌方重要人员或在对抗中压制敌方重要目标的有力手段[4]。然而多目标围猎任务涉及智能体较多，因此也更具有挑战性。

多目标围猎策略影响了任务整体实现的复杂度，合理的策略是实现成功围猎的必要条件，因此对于无人机群多目标围猎任务需要制定高效围猎多个目标的策略。围捕策略是一种特殊的编队控制策略，根据不同目标数目，分为单目标围猎和多目标围猎。目前，协调多架无人机执行目标围猎任务的研究方法主要有基于虚拟结构法、基于行为法、人工势场法和图论法。常见的单目标围猎策略有受自然现象启发的狼群捕猎模式。Muro等[5]参考狼群的狩猎过程，提出了一种多智能体协同围猎模型。该模型对追捕者的沟通要求较低，同时不需要构建狼群中的等级制度来维持系统内秩序。Atamurat等[6]研究了在欧氏空间中所有个体速度相同情况下的单目标围猎问题，对围捕模型进行分析得出了围猎成功的条件。Chen等[7]研究了高速逃逸目标的围猎问题，给出了能够成功围猎的条件，包括所需执行者的最小数量、初始分布状态以及围捕策略。在多目标围猎方面，Lopez等[8]对多智能体和多个动态目标的围猎博弈进行研究，对所有博弈方设定最优策略，采用图论方法为智能体分配控制策略，最后对有限时间内的围猎效果做出分析。Amini等[9]提出了一种基于动态事件触发机制的围猎控制方法，利用分布式动态事件触发结构，在降低通信量的同时实现非完整智能体系统的多目标围猎任务。可以看出目前对于多目标围猎的研究还不成熟，往往需要依赖复杂的计算和控制策略，而且许多研究是将多个目标考虑为一个整体进行分析，针对多个目标分别围猎的研究较少。

处理复杂问题时，在全局中采用分布式、在局部采用集中式的方式在规模中等的任务分配中有较好的性能[10]。现阶段对于单目标围猎问题的研究比较成熟，且相对于多目标，单目标围猎更容易实现。因此在无人机群围猎多个独立目标时，考虑将复杂的多目标围猎问题通过聚类划分转换为多个简单的单目标围猎问题从而降低问题难度。常见的聚类算法有基于划分的K-means[11]及Voronoi算法[12]、基于密度的DBSCAN[13]算法以及基于图论的谱聚类算法[14]等。Elango等[15]利用K-means算法进行多机器人的任务分群从而最小化任务之间的距离。Bai等[16]分析了多种聚类算法，并提出将聚类策略与目标插入度量相结合的形式，保证了访问所有目标位置的总旅行时间在一个合理的可计算上界内。选择合适的算法有利于对多个目标进行快速划分，K-means聚类算法应用广泛，计算复杂度低，具有较好的收敛速度。因此本文使用K-means算法对多目标围猎问题进行初步划分。

围猎的实现需要每个无人机个体执行明确的任务指令，即到达确定的位置。通过任务分配可以确定每个UAV需要执行的子任务。Wang等[17]研究了多智能体系统中协同控制的任务分配机制，指出通过协同分配协议可以在间歇通讯情况下得到较好的分配结果。Lee等[18]提出了一种面向资源的分散拍卖算法，该算法考虑了智能体的资源消耗问题以及有限通讯范围问题。在分配任务时会出现冲突现象即同一个任务的最佳执行个体不唯一，此时就需要设计分配机制。设计准则可以是系统的资源消耗最少，任务完成的时间最短等。在实际情况中，防止目标在围捕之前逃逸，将目标快速围捕是最重要的。上述研究虽然可以实现最优解，但任务完成的总时间不一定最短。Bai等[19]研究了多个分散车辆访问一组目标的动态任务分配问题，提出了基于事件触发和时间触发的2种动态任务分配算法。但该算法较为复杂。因此本文考虑无人机群中的个体在速度相同的情况下，以完成围猎任务总时间最短为目标，设计任务分配算法并使该算法的计算量尽可能小。

本文主要研究适用于空中无人机群多目标围猎任务分配策略的整体解决方案。为了得到更好的围猎性能，采用混合式方法的思想，先利用分布式方法对系统进行分层处理，之后针对每个独立的子系统利用局部的集中式方法完成围捕任务的分配。通过对任务不断细分，实现复杂任务的简单化。

本文的创新点如下：

1) 改进了K-means法，通过该分布式算法可以将多目标围猎问题分解为多个相互独立的、能够满足围猎条件的单目标围猎系统。该算法计算量小、操作简单，能够处理大规模无人机群的任务分层。

2) 针对一个单目标围猎子系统，通过任务分解使单体无人机只需完成简单明确的子任务即可完成单目标的围猎。考虑到实际围猎情况，以完成围猎任务的总耗时最少为决策条件，设计了一种任务分配策略，能够以较少的计算量得到使任务完成时间最短的分配方案。

1 围猎问题描述

首先给出单目标被成功围猎的定义。当发现待围猎目标时，目标周围的n个UAV逐渐靠近,将目标限制在半径为r的范围内。根据围猎的临界条件[20],完成围猎需要3个智能体分布在目标同一平面内,即为了确保目标被成功围猎,须满足n≥3。此时以待围猎目标的位置pt为中心,在半径r的圆上作内接n多边形,当控制UAV占据多边形的n个顶点形成围猎阵型时可以认为围猎成功。

考虑到实际情况,允许UAV的位置pu与多边形顶点之间存在Δr的偏差。即

r-Δr≤‖pu-pt‖≤r+Δr

(1)

式中：pu为UAV的位置;pt为待围猎目标位置。围猎效果如图1所示。

图1 围猎成功示意图

2 任务分层与任务分配问题描述

通过任务分层可以将无人机群多目标围猎问题分解成与待围猎目标一一对应的多个单目标围猎子系统。子系统结构更简单且相互独立,从而可以降低无人机群多目标围猎系统的耦合性。子系统内部继续对围猎任务进行分解,将单目标围猎任务分解成多个简单的子任务并分配给具体的UAV个体。任务分层与任务分配问题如图2所示。

图2 任务分层与任务分配示意图

考虑在无人机群多目标围猎系统中有M个待围猎目标,定义待围猎目标个体的集合T为

T={ti|1≤i≤M}

(2)

同时空间中存在N个UAV,定义UAV个体的集合U为

U={uj|1≤j≤N}

(3)

为了保证所有的目标都能被成功围猎,需要满足N≥3M。

任务分层目标:分层结果需要保证每个待围猎目标ti对应一个子系统Si,并且每个子系统中包含的UAV数量q需要满足q≥3。子系统Si表示为

Si={uij|1≤i≤M,1≤j≤q}

(4)

子任务的集合表示为

S={Si|1≤i≤M}

(5)

任务分配是指:在围猎子系统Si中,若存在q个UAV,则会对应q个子任务。子系统i中待分配的子任务tik的集合表示为

Ti={tik|1≤i≤M,1≤k≤q}

(6)

子系统i中的UAV个体uij可以对tik做出评价,评价的效用值用bijk表示。对于可以执行的任务bijk≥0,若不能执行tik,则bijk=0。把完成任务所需的时间作为评价指标时,uij完成tik的时间越短,则bijk的值越大。

任务分配问题可以描述为

(7)

且需满足

(8)

通过(8)式可以保证子系统中的每个UAV都有需要待执行的子任务,同时每个待执行的子任务都必须由一个UAV去完成。

3 改进K-means算法的任务分层方法

传统的K-means算法能够对大量数据进行划分,从而形成所需数目的数据簇,同一个簇中数据元素之间的相近度较高,经过该算法的划分,每个数据只能隶属于一个数据簇。该算法的划分依据是最小误差函数,该误差函数可以描述各个数据与聚类中心的偏差情况。一般选用数据和中心的欧式距离作为误差函数。

根据任务分层的要求,将K-means算进行改进。改进后的算法主要有以下特点:

1) 将N个待围猎目标的坐标设置为聚类中心,并且该聚类中心不随着算法的迭代而发生变化。

2) 划分完成后分别判断每个子系统内的UAV个数是否满足要求,如果存在数量不满足的子系统,则重新划分。

改进的K-means算法步骤如下:

步骤1 设在空间R内存在由n个UAV组成的无人机群,以UAV位置坐标为元素的数据集记为p={p1,…,pn},同时存在m个待围捕目标,将目标的位置坐标设置为初始的m个聚类中心,表示为pti,i∈{1,…,m}。用(9)式计算pj相对于pti的距离dij。

(9)

根据计算结果,pj会被规划到距离最近的数据中心i所代表的数据簇Ci内。

Ci={pj|‖pj-pti‖≤‖pj-ptq‖,1≤q≤m}

(10)

步骤2 通过步骤1，初步形成m个子系统。之后判断每个子系统内的UAV数量是否满足要求。

步骤3 对于数量不满足的子系统Se,计算不包含在子系统Se内的元素与属于Se的聚类中心pte的距离,将距离该中心最近的元素划分至Se。在调整子系统内元素数量时,可能出现子系统内的元素被抽离后,该子系统元素个数不满足要求的情况,需要重新补充。为了防止同个元素被来回调动所造成的算法循环，需要限制被调动的元素不再考虑补充到原来的子系统中。

（19）分期出杳入宴，恍惚經緯萬方。（《太上說玄天大聖真武本傳神呪妙經註》卷二，《中华道藏》30/549）

步骤4 重复步骤2～3直至所有子系统内的元素满足要求。

改进K-means算法的流程图如图3所示。

图3 改进K-means算法流程图

4 基于总时最短机制的任务分配策略

系统分层后,每个子系统需要根据UAV的数量规划子任务并给出子任务的分配结果。通过设计任务分配机制,可以使整个系统得到能够实现需要的较为优化的解。

本文的任务分配机制是优先考虑任务完成的总时间最短。子系统内UAV完成围猎任务的总时间取决于完成子任务时间最长的UAV。假设同一子系统内的UAV同时执行任务且速度相同。这意味着UAV完成子任务需移动的距离d越短则完成子任务的用时t越少,即t∝d。基于上述设定,总时最短的分配机制可转化为分配结果使UAV完成子任务移动的距离最大值是众多分配方案中最小的。

对于一个包含q个UAV的子系统Si,任务分配算法步骤如下:

步骤1 选取距离待围猎目标最近的UAV作为任务分配中心记为ui1,计算该UAV到半径为r的围猎圆上的最近点,并将该点设为围猎圆的内接正q边形的一个顶点z1。同时将该顶点位置作为子任务分配给ui1。

(11)

步骤2 任务分配中心计算得出其余q-1个顶点的位置。将q-1个顶点位置作为子任务集向其他UAV发布。UAV个体uij,j∈{2,…,q}到顶点zk,k∈{2,…,q}的距离记为dijk。每个UAV分别计算与q-1个顶点的距离,得到该UAV的距离数据集dij,任务分配中心对每个数据集进行汇总得到矩阵Ai,此时Ai∈R(q-1)×(q-1)。

(12)

步骤3 若uij执行子任务tik,则从矩阵Ai中删除uij对应的列向量dij和子任务tik对应的行向量,此时Ai的阶数减1。

步骤4 任务分配中心找到矩阵Ai中的最大值,该值对应的UAV完成子任务的时间最长。若最大值不唯一,则找出所有最大值对应的列向量中的最小值,最小值表示该值对应的UAV完成子任务用时最短。最小值对应的UAV和子任务相互匹配,同时进行一次步骤3。若最大值唯一,则找出最大值所在列向量中的最小值。若最小值不唯一,则先将该列向量排除,并重复步骤4,直到该列向量中的最小值唯一,最小值对应的UAV和子任务相匹配。

步骤5 循环步骤3～4,直到所有子任务分配完成。

任务分配的流程图如图4所示。

图4 任务分配流程图

5 实验仿真

为了验证本文提出的多目标围猎策略的有效性,设计了一个仿真实验，指派9个UAV分别围猎3个目标。该系统的初始状态如图5所示。

图5 多无人机围猎系统初始状态

UAV的位置是随机确定的,表1～2给出了仿真中各UAV和待围猎目标位置。

表1 仿真中各UAV位置

表2 仿真中待围猎目标位置

根据第2节所述任务分层与任务分配策略,首先使用改进的K-means算法对系统进行分层,分层效果如图6所示。可以看出,分层算法能够生成与待围猎目标数量相同的子系统,并且能够对数目不满足的子系统进行补全。由图6b)～6c)可以看出,被调动过的UAV不会被重复调动,最终使得每个子系统都满足成功围猎的要求。

系统分层后每个子系统进行子任务的生成与分配,为了比较本文提出总时分配机制的性能,同时使用匈牙利算法对子任务进行分配。基于总时最短机制的分配结果如图7所示。基于匈牙利算法的分配结果如图8所示。

图6 任务分层效果

图7 各子系统基于总时最短机制的任务分解结果

图8 各子系统基于匈牙利算法的任务分解结果

各子系统内子任务对应的坐标如表3所示,任务分配中心对应子任务为1号子任务,其他子任务按照顺时针进行编号。

表3 各子系统中各子任务位置及对应关系

为了分析2种算法的效果,比较了2种分配结果对应的完成围猎任务的总时间,为了方便计算,设智能体的速度都为1,结果保留2位小数,如表4所示。结果表明本文提出的分配算法能够满足总时最短的要求。

表4 2种算法的完成任务用时对比

根据仿真结果可以看出本文提出的任务分配策略会选择总时最短的分配方案,例如图7b)所示子系统2的分配情况,子任务2.2对于5号UAV和6号UAV都是距离最近的子任务。因此会出现分配冲突,此时通过计算,6号UAV完成子任务2.3的时间比5号UAV完成子任务2.3的时间更长,因此为了使完成任务的时间最短,将子任务2.2分配给6号UAV。

6 结 论

本文提出的多目标任务分配策略将复杂的系统逐步分解为多个简单子任务,将计算任务分散在单体UAV上,提高了系统的灵活性。该策略首先通过改进K-means算法使系统分层形成多个子系统,实现系统的解耦。之后每个子系统作为单独的任务单元将任务细分并以完成任务的总时间为主要考虑因素对子任务进行分配,使UAV在最短时间内完成目标的围猎任务。通过仿真实验可以证明该策略易行且有效。